1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
|
package maps
import (
"fmt"
"reflect"
)
// OrderedMap provides a hashmap implementation that tracks the order in which keys are added.
type OrderedMap[K comparable, V any] struct {
ordered[K, V]
}
// NewOrdered returns a new instance of LRUMap with given initializing length and maximum capacity.
func NewOrdered[K comparable, V any](len int) *OrderedMap[K, V] {
m := new(OrderedMap[K, V])
m.Init(len)
return m
}
// Init will initialize this map with initial length.
func (m *OrderedMap[K, V]) Init(len int) {
if m.pool != nil {
panic("ordered map already initialized")
}
m.ordered.hmap = make(map[K]*elem[K, V], len)
m.ordered.pool = allocElems[K, V](len)
}
// Get will fetch value for given key from map. Returns false if not found.
func (m *OrderedMap[K, V]) Get(key K) (V, bool) {
if elem, ok := m.hmap[key]; ok {
return elem.V, true
}
var z V // zero value
return z, false
}
// Add will add the given key-value pair to the map, returns false if already exists.
func (m *OrderedMap[K, V]) Add(key K, value V) bool {
// Ensure safe
m.write_check()
// Look for existing elem
elem, ok := m.hmap[key]
if ok {
return false
}
// Allocate elem
elem = m.alloc()
elem.K = key
elem.V = value
// Add element map entry
m.hmap[key] = elem
// Push to back of list
m.list.PushBack(elem)
return true
}
// Set will ensure that given key-value pair exists in the map, by either adding new or updating existing.
func (m *OrderedMap[K, V]) Set(key K, value V) {
// Ensure safe
m.write_check()
// Look for existing elem
elem, ok := m.hmap[key]
if ok {
// Update existing
elem.V = value
} else {
// Allocate elem
elem = m.alloc()
elem.K = key
elem.V = value
// Add element map entry
m.hmap[key] = elem
// Push to back of list
m.list.PushBack(elem)
}
}
// Index returns the key-value pair at index from map. Returns false if index out of range.
func (m *OrderedMap[K, V]) Index(idx int) (K, V, bool) {
if idx < 0 || idx >= m.list.len {
var (
zk K
zv V
) // zero values
return zk, zv, false
}
elem := m.list.Index(idx)
return elem.K, elem.V, true
}
// Push will insert the given key-value pair at index in the map. Panics if index out of range.
func (m *OrderedMap[K, V]) Push(idx int, key K, value V) {
// Check index within bounds of map
if idx < 0 || idx >= m.list.len {
panic("index out of bounds")
}
// Ensure safe
m.write_check()
// Get element at index
next := m.list.Index(idx)
// Allocate new elem
elem := m.alloc()
elem.K = key
elem.V = value
// Add element map entry
m.hmap[key] = elem
// Move next forward
elem.next = next
elem.prev = next.prev
// Link up elem in chain
next.prev.next = elem
next.prev = elem
}
// Pop will remove and return the key-value pair at index in the map. Panics if index out of range.
func (m *OrderedMap[K, V]) Pop(idx int) (K, V) {
// Check index within bounds of map
if idx < 0 || idx >= m.list.len {
panic("index out of bounds")
}
// Ensure safe
m.write_check()
// Get element at index
elem := m.list.Index(idx)
// Unlink elem from list
m.list.Unlink(elem)
// Get elem values
k := elem.K
v := elem.V
// Release to pool
m.free(elem)
return k, v
}
// Format implements fmt.Formatter, allowing performant string formatting of map.
func (m *OrderedMap[K, V]) Format(state fmt.State, verb rune) {
m.format(reflect.TypeOf(m), state, verb)
}
|
