1 // Copyright 2024 The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
4 5 package maps
6 7 import (
8 "internal/abi"
9 "internal/goarch"
10 "internal/runtime/sys"
11 "unsafe"
12 )
13 14 const (
15 // Maximum load factor prior to growing.
16 //
17 // 7/8 is the same load factor used by Abseil, but Abseil defaults to
18 // 16 slots per group, so they get two empty slots vs our one empty
19 // slot. We may want to reevaluate if this is best for us.
20 maxAvgGroupLoad = 7
21 22 ctrlEmpty ctrl = 0b10000000
23 ctrlDeleted ctrl = 0b11111110
24 25 bitsetLSB = 0x0101010101010101
26 bitsetMSB = 0x8080808080808080
27 bitsetEmpty = bitsetLSB * uint64(ctrlEmpty)
28 bitsetDeleted = bitsetLSB * uint64(ctrlDeleted)
29 )
30 31 // bitset represents a set of slots within a group.
32 //
33 // The underlying representation depends on GOARCH.
34 //
35 // On AMD64, bitset uses one bit per slot, where the bit is set if the slot is
36 // part of the set. All of the ctrlGroup.match* methods are replaced with
37 // intrinsics that return this packed representation.
38 //
39 // On other architectures, bitset uses one byte per slot, where each byte is
40 // either 0x80 if the slot is part of the set or 0x00 otherwise. This makes it
41 // convenient to calculate for an entire group at once using standard
42 // arithemetic instructions.
43 type bitset uint64
44 45 // first returns the relative index of the first control byte in the group that
46 // is in the set.
47 //
48 // Preconditions: b is not 0 (empty).
49 func (b bitset) first() uintptr {
50 return bitsetFirst(b)
51 }
52 53 // Portable implementation of first.
54 //
55 // On AMD64, this is replaced with an intrisic that simply does
56 // TrailingZeros64. There is no need to shift as the bitset is packed.
57 func bitsetFirst(b bitset) uintptr {
58 return uintptr(sys.TrailingZeros64(uint64(b))) >> 3
59 }
60 61 // removeFirst clears the first set bit (that is, resets the least significant
62 // set bit to 0).
63 func (b bitset) removeFirst() bitset {
64 return b & (b - 1)
65 }
66 67 // removeBelow clears all set bits below slot i (non-inclusive).
68 func (b bitset) removeBelow(i uintptr) bitset {
69 return bitsetRemoveBelow(b, i)
70 }
71 72 // Portable implementation of removeBelow.
73 //
74 // On AMD64, this is replaced with an intrisic that clears the lower i bits.
75 func bitsetRemoveBelow(b bitset, i uintptr) bitset {
76 // Clear all bits below slot i's byte.
77 mask := (uint64(1) << (8 * uint64(i))) - 1
78 return b &^ bitset(mask)
79 }
80 81 // lowestSet returns true if the bit is set for the lowest index in the bitset.
82 //
83 // This is intended for use with shiftOutLowest to loop over all entries in the
84 // bitset regardless of whether they are set.
85 func (b bitset) lowestSet() bool {
86 return bitsetLowestSet(b)
87 }
88 89 // Portable implementation of lowestSet.
90 //
91 // On AMD64, this is replaced with an intrisic that checks the lowest bit.
92 func bitsetLowestSet(b bitset) bool {
93 return b&(1<<7) != 0
94 }
95 96 // shiftOutLowest shifts the lowest entry out of the bitset. Afterwards, the
97 // lowest entry in the bitset corresponds to the next slot.
98 func (b bitset) shiftOutLowest() bitset {
99 return bitsetShiftOutLowest(b)
100 }
101 102 // Portable implementation of shiftOutLowest.
103 //
104 // On AMD64, this is replaced with an intrisic that shifts a single bit.
105 func bitsetShiftOutLowest(b bitset) bitset {
106 return b >> 8
107 }
108 109 // count returns the number of bits set in b.
110 func (b bitset) count() int {
111 // Note: works for both bitset representations (AMD64 and generic)
112 return sys.OnesCount64(uint64(b))
113 }
114 115 // Each slot in the hash table has a control byte which can have one of three
116 // states: empty, deleted, and full. They have the following bit patterns:
117 //
118 // empty: 1 0 0 0 0 0 0 0
119 // deleted: 1 1 1 1 1 1 1 0
120 // full: 0 h h h h h h h // h represents the H2 hash bits
121 //
122 // TODO(prattmic): Consider inverting the top bit so that the zero value is empty.
123 type ctrl uint8
124 125 // ctrlGroup is a fixed size array of abi.SwissMapGroupSlots control bytes
126 // stored in a uint64.
127 type ctrlGroup uint64
128 129 // get returns the i-th control byte.
130 func (g *ctrlGroup) get(i uintptr) ctrl {
131 if goarch.BigEndian {
132 return *(*ctrl)(unsafe.Add(unsafe.Pointer(g), 7-i))
133 }
134 return *(*ctrl)(unsafe.Add(unsafe.Pointer(g), i))
135 }
136 137 // set sets the i-th control byte.
138 func (g *ctrlGroup) set(i uintptr, c ctrl) {
139 if goarch.BigEndian {
140 *(*ctrl)(unsafe.Add(unsafe.Pointer(g), 7-i)) = c
141 return
142 }
143 *(*ctrl)(unsafe.Add(unsafe.Pointer(g), i)) = c
144 }
145 146 // setEmpty sets all the control bytes to empty.
147 func (g *ctrlGroup) setEmpty() {
148 *g = ctrlGroup(bitsetEmpty)
149 }
150 151 // matchH2 returns the set of slots which are full and for which the 7-bit hash
152 // matches the given value. May return false positives.
153 func (g ctrlGroup) matchH2(h uintptr) bitset {
154 return ctrlGroupMatchH2(g, h)
155 }
156 157 // Portable implementation of matchH2.
158 //
159 // Note: On AMD64, this is an intrinsic implemented with SIMD instructions. See
160 // note on bitset about the packed intrinsified return value.
161 func ctrlGroupMatchH2(g ctrlGroup, h uintptr) bitset {
162 // NB: This generic matching routine produces false positive matches when
163 // h is 2^N and the control bytes have a seq of 2^N followed by 2^N+1. For
164 // example: if ctrls==0x0302 and h=02, we'll compute v as 0x0100. When we
165 // subtract off 0x0101 the first 2 bytes we'll become 0xffff and both be
166 // considered matches of h. The false positive matches are not a problem,
167 // just a rare inefficiency. Note that they only occur if there is a real
168 // match and never occur on ctrlEmpty, or ctrlDeleted. The subsequent key
169 // comparisons ensure that there is no correctness issue.
170 v := uint64(g) ^ (bitsetLSB * uint64(h))
171 return bitset(((v - bitsetLSB) &^ v) & bitsetMSB)
172 }
173 174 // matchEmpty returns the set of slots in the group that are empty.
175 func (g ctrlGroup) matchEmpty() bitset {
176 return ctrlGroupMatchEmpty(g)
177 }
178 179 // Portable implementation of matchEmpty.
180 //
181 // Note: On AMD64, this is an intrinsic implemented with SIMD instructions. See
182 // note on bitset about the packed intrinsified return value.
183 func ctrlGroupMatchEmpty(g ctrlGroup) bitset {
184 // An empty slot is 1000 0000
185 // A deleted slot is 1111 1110
186 // A full slot is 0??? ????
187 //
188 // A slot is empty iff bit 7 is set and bit 1 is not. We could select any
189 // of the other bits here (e.g. v << 1 would also work).
190 v := uint64(g)
191 return bitset((v &^ (v << 6)) & bitsetMSB)
192 }
193 194 // matchEmptyOrDeleted returns the set of slots in the group that are empty or
195 // deleted.
196 func (g ctrlGroup) matchEmptyOrDeleted() bitset {
197 return ctrlGroupMatchEmptyOrDeleted(g)
198 }
199 200 // Portable implementation of matchEmptyOrDeleted.
201 //
202 // Note: On AMD64, this is an intrinsic implemented with SIMD instructions. See
203 // note on bitset about the packed intrinsified return value.
204 func ctrlGroupMatchEmptyOrDeleted(g ctrlGroup) bitset {
205 // An empty slot is 1000 0000
206 // A deleted slot is 1111 1110
207 // A full slot is 0??? ????
208 //
209 // A slot is empty or deleted iff bit 7 is set.
210 v := uint64(g)
211 return bitset(v & bitsetMSB)
212 }
213 214 // matchFull returns the set of slots in the group that are full.
215 func (g ctrlGroup) matchFull() bitset {
216 return ctrlGroupMatchFull(g)
217 }
218 219 // Portable implementation of matchFull.
220 //
221 // Note: On AMD64, this is an intrinsic implemented with SIMD instructions. See
222 // note on bitset about the packed intrinsified return value.
223 func ctrlGroupMatchFull(g ctrlGroup) bitset {
224 // An empty slot is 1000 0000
225 // A deleted slot is 1111 1110
226 // A full slot is 0??? ????
227 //
228 // A slot is full iff bit 7 is unset.
229 v := uint64(g)
230 return bitset(^v & bitsetMSB)
231 }
232 233 // groupReference is a wrapper type representing a single slot group stored at
234 // data.
235 //
236 // A group holds abi.SwissMapGroupSlots slots (key/elem pairs) plus their
237 // control word.
238 type groupReference struct {
239 // data points to the group, which is described by typ.Group and has
240 // layout:
241 //
242 // type group struct {
243 // ctrls ctrlGroup
244 // slots [abi.SwissMapGroupSlots]slot
245 // }
246 //
247 // type slot struct {
248 // key typ.Key
249 // elem typ.Elem
250 // }
251 data unsafe.Pointer // data *typ.Group
252 }
253 254 const (
255 ctrlGroupsSize = unsafe.Sizeof(ctrlGroup(0))
256 groupSlotsOffset = ctrlGroupsSize
257 )
258 259 // alignUp rounds n up to a multiple of a. a must be a power of 2.
260 func alignUp(n, a uintptr) uintptr {
261 return (n + a - 1) &^ (a - 1)
262 }
263 264 // alignUpPow2 rounds n up to the next power of 2.
265 //
266 // Returns true if round up causes overflow.
267 func alignUpPow2(n uint64) (uint64, bool) {
268 if n == 0 {
269 return 0, false
270 }
271 v := (uint64(1) << sys.Len64(n-1))
272 if v == 0 {
273 return 0, true
274 }
275 return v, false
276 }
277 278 // ctrls returns the group control word.
279 func (g *groupReference) ctrls() *ctrlGroup {
280 return (*ctrlGroup)(g.data)
281 }
282 283 // key returns a pointer to the key at index i.
284 func (g *groupReference) key(typ *abi.SwissMapType, i uintptr) unsafe.Pointer {
285 offset := groupSlotsOffset + i*typ.SlotSize
286 287 return unsafe.Pointer(uintptr(g.data) + offset)
288 }
289 290 // elem returns a pointer to the element at index i.
291 func (g *groupReference) elem(typ *abi.SwissMapType, i uintptr) unsafe.Pointer {
292 offset := groupSlotsOffset + i*typ.SlotSize + typ.ElemOff
293 294 return unsafe.Pointer(uintptr(g.data) + offset)
295 }
296 297 // groupsReference is a wrapper type describing an array of groups stored at
298 // data.
299 type groupsReference struct {
300 // data points to an array of groups. See groupReference above for the
301 // definition of group.
302 data unsafe.Pointer // data *[length]typ.Group
303 304 // lengthMask is the number of groups in data minus one (note that
305 // length must be a power of two). This allows computing i%length
306 // quickly using bitwise AND.
307 lengthMask uint64
308 }
309 310 // newGroups allocates a new array of length groups.
311 //
312 // Length must be a power of two.
313 func newGroups(typ *abi.SwissMapType, length uint64) groupsReference {
314 return groupsReference{
315 // TODO: make the length type the same throughout.
316 data: newarray(typ.Group, int(length)),
317 lengthMask: length - 1,
318 }
319 }
320 321 // group returns the group at index i.
322 func (g *groupsReference) group(typ *abi.SwissMapType, i uint64) groupReference {
323 // TODO(prattmic): Do something here about truncation on cast to
324 // uintptr on 32-bit systems?
325 offset := uintptr(i) * typ.GroupSize
326 327 return groupReference{
328 data: unsafe.Pointer(uintptr(g.data) + offset),
329 }
330 }
331 332 func cloneGroup(typ *abi.SwissMapType, newGroup, oldGroup groupReference) {
333 typedmemmove(typ.Group, newGroup.data, oldGroup.data)
334 if typ.IndirectKey() {
335 // Deep copy keys if indirect.
336 for i := uintptr(0); i < abi.SwissMapGroupSlots; i++ {
337 oldKey := *(*unsafe.Pointer)(oldGroup.key(typ, i))
338 if oldKey == nil {
339 continue
340 }
341 newKey := newobject(typ.Key)
342 typedmemmove(typ.Key, newKey, oldKey)
343 *(*unsafe.Pointer)(newGroup.key(typ, i)) = newKey
344 }
345 }
346 if typ.IndirectElem() {
347 // Deep copy elems if indirect.
348 for i := uintptr(0); i < abi.SwissMapGroupSlots; i++ {
349 oldElem := *(*unsafe.Pointer)(oldGroup.elem(typ, i))
350 if oldElem == nil {
351 continue
352 }
353 newElem := newobject(typ.Elem)
354 typedmemmove(typ.Elem, newElem, oldElem)
355 *(*unsafe.Pointer)(newGroup.elem(typ, i)) = newElem
356 }
357 }
358 359 }
360