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