1 // Copyright 2018 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.
12 // For gccgo, use go:linkname to export compiler-called functions.
14 //go:linkname mapaccess1_faststr
15 //go:linkname mapaccess2_faststr
16 //go:linkname mapassign_faststr
17 //go:linkname mapdelete_faststr
19 func mapaccess1_faststr(t
*maptype
, h
*hmap
, ky
string) unsafe
.Pointer
{
20 if raceenabled
&& h
!= nil {
21 callerpc
:= getcallerpc()
22 racereadpc(unsafe
.Pointer(h
), callerpc
, funcPC(mapaccess1_faststr
))
24 if h
== nil || h
.count
== 0 {
25 return unsafe
.Pointer(&zeroVal
[0])
27 if h
.flags
&hashWriting
!= 0 {
28 throw("concurrent map read and map write")
30 key
:= stringStructOf(&ky
)
33 b
:= (*bmap
)(h
.buckets
)
35 // short key, doing lots of comparisons is ok
36 for i
, kptr
:= uintptr(0), b
.keys(); i
< bucketCnt
; i
, kptr
= i
+1, add(kptr
, 2*sys
.PtrSize
) {
37 k
:= (*stringStruct
)(kptr
)
38 if k
.len != key
.len ||
isEmpty(b
.tophash
[i
]) {
39 if b
.tophash
[i
] == emptyRest
{
44 if k
.str
== key
.str ||
memequal(k
.str
, key
.str
, uintptr(key
.len)) {
45 return add(unsafe
.Pointer(b
), dataOffset
+bucketCnt
*2*sys
.PtrSize
+i
*uintptr(t
.elemsize
))
48 return unsafe
.Pointer(&zeroVal
[0])
50 // long key, try not to do more comparisons than necessary
51 keymaybe
:= uintptr(bucketCnt
)
52 for i
, kptr
:= uintptr(0), b
.keys(); i
< bucketCnt
; i
, kptr
= i
+1, add(kptr
, 2*sys
.PtrSize
) {
53 k
:= (*stringStruct
)(kptr
)
54 if k
.len != key
.len ||
isEmpty(b
.tophash
[i
]) {
55 if b
.tophash
[i
] == emptyRest
{
61 return add(unsafe
.Pointer(b
), dataOffset
+bucketCnt
*2*sys
.PtrSize
+i
*uintptr(t
.elemsize
))
63 // check first 4 bytes
64 if *((*[4]byte)(key
.str
)) != *((*[4]byte)(k
.str
)) {
68 if *((*[4]byte)(add(key
.str
, uintptr(key
.len)-4))) != *((*[4]byte)(add(k
.str
, uintptr(key
.len)-4))) {
71 if keymaybe
!= bucketCnt
{
72 // Two keys are potential matches. Use hash to distinguish them.
77 if keymaybe
!= bucketCnt
{
78 k
:= (*stringStruct
)(add(unsafe
.Pointer(b
), dataOffset
+keymaybe
*2*sys
.PtrSize
))
79 if memequal(k
.str
, key
.str
, uintptr(key
.len)) {
80 return add(unsafe
.Pointer(b
), dataOffset
+bucketCnt
*2*sys
.PtrSize
+keymaybe
*uintptr(t
.elemsize
))
83 return unsafe
.Pointer(&zeroVal
[0])
86 hash
:= t
.hasher(noescape(unsafe
.Pointer(&ky
)), uintptr(h
.hash0
))
88 b
:= (*bmap
)(add(h
.buckets
, (hash
&m
)*uintptr(t
.bucketsize
)))
89 if c
:= h
.oldbuckets
; c
!= nil {
90 if !h
.sameSizeGrow() {
91 // There used to be half as many buckets; mask down one more power of two.
94 oldb
:= (*bmap
)(add(c
, (hash
&m
)*uintptr(t
.bucketsize
)))
100 for ; b
!= nil; b
= b
.overflow(t
) {
101 for i
, kptr
:= uintptr(0), b
.keys(); i
< bucketCnt
; i
, kptr
= i
+1, add(kptr
, 2*sys
.PtrSize
) {
102 k
:= (*stringStruct
)(kptr
)
103 if k
.len != key
.len || b
.tophash
[i
] != top
{
106 if k
.str
== key
.str ||
memequal(k
.str
, key
.str
, uintptr(key
.len)) {
107 return add(unsafe
.Pointer(b
), dataOffset
+bucketCnt
*2*sys
.PtrSize
+i
*uintptr(t
.elemsize
))
111 return unsafe
.Pointer(&zeroVal
[0])
114 func mapaccess2_faststr(t
*maptype
, h
*hmap
, ky
string) (unsafe
.Pointer
, bool) {
115 if raceenabled
&& h
!= nil {
116 callerpc
:= getcallerpc()
117 racereadpc(unsafe
.Pointer(h
), callerpc
, funcPC(mapaccess2_faststr
))
119 if h
== nil || h
.count
== 0 {
120 return unsafe
.Pointer(&zeroVal
[0]), false
122 if h
.flags
&hashWriting
!= 0 {
123 throw("concurrent map read and map write")
125 key
:= stringStructOf(&ky
)
128 b
:= (*bmap
)(h
.buckets
)
130 // short key, doing lots of comparisons is ok
131 for i
, kptr
:= uintptr(0), b
.keys(); i
< bucketCnt
; i
, kptr
= i
+1, add(kptr
, 2*sys
.PtrSize
) {
132 k
:= (*stringStruct
)(kptr
)
133 if k
.len != key
.len ||
isEmpty(b
.tophash
[i
]) {
134 if b
.tophash
[i
] == emptyRest
{
139 if k
.str
== key
.str ||
memequal(k
.str
, key
.str
, uintptr(key
.len)) {
140 return add(unsafe
.Pointer(b
), dataOffset
+bucketCnt
*2*sys
.PtrSize
+i
*uintptr(t
.elemsize
)), true
143 return unsafe
.Pointer(&zeroVal
[0]), false
145 // long key, try not to do more comparisons than necessary
146 keymaybe
:= uintptr(bucketCnt
)
147 for i
, kptr
:= uintptr(0), b
.keys(); i
< bucketCnt
; i
, kptr
= i
+1, add(kptr
, 2*sys
.PtrSize
) {
148 k
:= (*stringStruct
)(kptr
)
149 if k
.len != key
.len ||
isEmpty(b
.tophash
[i
]) {
150 if b
.tophash
[i
] == emptyRest
{
155 if k
.str
== key
.str
{
156 return add(unsafe
.Pointer(b
), dataOffset
+bucketCnt
*2*sys
.PtrSize
+i
*uintptr(t
.elemsize
)), true
158 // check first 4 bytes
159 if *((*[4]byte)(key
.str
)) != *((*[4]byte)(k
.str
)) {
162 // check last 4 bytes
163 if *((*[4]byte)(add(key
.str
, uintptr(key
.len)-4))) != *((*[4]byte)(add(k
.str
, uintptr(key
.len)-4))) {
166 if keymaybe
!= bucketCnt
{
167 // Two keys are potential matches. Use hash to distinguish them.
172 if keymaybe
!= bucketCnt
{
173 k
:= (*stringStruct
)(add(unsafe
.Pointer(b
), dataOffset
+keymaybe
*2*sys
.PtrSize
))
174 if memequal(k
.str
, key
.str
, uintptr(key
.len)) {
175 return add(unsafe
.Pointer(b
), dataOffset
+bucketCnt
*2*sys
.PtrSize
+keymaybe
*uintptr(t
.elemsize
)), true
178 return unsafe
.Pointer(&zeroVal
[0]), false
181 hash
:= t
.hasher(noescape(unsafe
.Pointer(&ky
)), uintptr(h
.hash0
))
183 b
:= (*bmap
)(add(h
.buckets
, (hash
&m
)*uintptr(t
.bucketsize
)))
184 if c
:= h
.oldbuckets
; c
!= nil {
185 if !h
.sameSizeGrow() {
186 // There used to be half as many buckets; mask down one more power of two.
189 oldb
:= (*bmap
)(add(c
, (hash
&m
)*uintptr(t
.bucketsize
)))
190 if !evacuated(oldb
) {
195 for ; b
!= nil; b
= b
.overflow(t
) {
196 for i
, kptr
:= uintptr(0), b
.keys(); i
< bucketCnt
; i
, kptr
= i
+1, add(kptr
, 2*sys
.PtrSize
) {
197 k
:= (*stringStruct
)(kptr
)
198 if k
.len != key
.len || b
.tophash
[i
] != top
{
201 if k
.str
== key
.str ||
memequal(k
.str
, key
.str
, uintptr(key
.len)) {
202 return add(unsafe
.Pointer(b
), dataOffset
+bucketCnt
*2*sys
.PtrSize
+i
*uintptr(t
.elemsize
)), true
206 return unsafe
.Pointer(&zeroVal
[0]), false
209 func mapassign_faststr(t
*maptype
, h
*hmap
, s
string) unsafe
.Pointer
{
211 panic(plainError("assignment to entry in nil map"))
214 callerpc
:= getcallerpc()
215 racewritepc(unsafe
.Pointer(h
), callerpc
, funcPC(mapassign_faststr
))
217 if h
.flags
&hashWriting
!= 0 {
218 throw("concurrent map writes")
220 key
:= stringStructOf(&s
)
221 hash
:= t
.hasher(noescape(unsafe
.Pointer(&s
)), uintptr(h
.hash0
))
223 // Set hashWriting after calling t.hasher for consistency with mapassign.
224 h
.flags
^= hashWriting
226 if h
.buckets
== nil {
227 h
.buckets
= newobject(t
.bucket
) // newarray(t.bucket, 1)
231 bucket
:= hash
& bucketMask(h
.B
)
233 growWork_faststr(t
, h
, bucket
)
235 b
:= (*bmap
)(unsafe
.Pointer(uintptr(h
.buckets
) + bucket
*uintptr(t
.bucketsize
)))
240 var insertk unsafe
.Pointer
244 for i
:= uintptr(0); i
< bucketCnt
; i
++ {
245 if b
.tophash
[i
] != top
{
246 if isEmpty(b
.tophash
[i
]) && insertb
== nil {
250 if b
.tophash
[i
] == emptyRest
{
255 k
:= (*stringStruct
)(add(unsafe
.Pointer(b
), dataOffset
+i
*2*sys
.PtrSize
))
256 if k
.len != key
.len {
259 if k
.str
!= key
.str
&& !memequal(k
.str
, key
.str
, uintptr(key
.len)) {
262 // already have a mapping for key. Update it.
274 // Did not find mapping for key. Allocate new cell & add entry.
276 // If we hit the max load factor or we have too many overflow buckets,
277 // and we're not already in the middle of growing, start growing.
278 if !h
.growing() && (overLoadFactor(h
.count
+1, h
.B
) ||
tooManyOverflowBuckets(h
.noverflow
, h
.B
)) {
280 goto again
// Growing the table invalidates everything, so try again
284 // all current buckets are full, allocate a new one.
285 insertb
= h
.newoverflow(t
, b
)
286 inserti
= 0 // not necessary, but avoids needlessly spilling inserti
288 insertb
.tophash
[inserti
&(bucketCnt
-1)] = top
// mask inserti to avoid bounds checks
290 insertk
= add(unsafe
.Pointer(insertb
), dataOffset
+inserti
*2*sys
.PtrSize
)
291 // store new key at insert position
292 *((*stringStruct
)(insertk
)) = *key
296 elem
:= add(unsafe
.Pointer(insertb
), dataOffset
+bucketCnt
*2*sys
.PtrSize
+inserti
*uintptr(t
.elemsize
))
297 if h
.flags
&hashWriting
== 0 {
298 throw("concurrent map writes")
300 h
.flags
&^= hashWriting
304 func mapdelete_faststr(t
*maptype
, h
*hmap
, ky
string) {
305 if raceenabled
&& h
!= nil {
306 callerpc
:= getcallerpc()
307 racewritepc(unsafe
.Pointer(h
), callerpc
, funcPC(mapdelete_faststr
))
309 if h
== nil || h
.count
== 0 {
312 if h
.flags
&hashWriting
!= 0 {
313 throw("concurrent map writes")
316 key
:= stringStructOf(&ky
)
317 hash
:= t
.hasher(noescape(unsafe
.Pointer(&ky
)), uintptr(h
.hash0
))
319 // Set hashWriting after calling t.hasher for consistency with mapdelete
320 h
.flags
^= hashWriting
322 bucket
:= hash
& bucketMask(h
.B
)
324 growWork_faststr(t
, h
, bucket
)
326 b
:= (*bmap
)(add(h
.buckets
, bucket
*uintptr(t
.bucketsize
)))
330 for ; b
!= nil; b
= b
.overflow(t
) {
331 for i
, kptr
:= uintptr(0), b
.keys(); i
< bucketCnt
; i
, kptr
= i
+1, add(kptr
, 2*sys
.PtrSize
) {
332 k
:= (*stringStruct
)(kptr
)
333 if k
.len != key
.len || b
.tophash
[i
] != top
{
336 if k
.str
!= key
.str
&& !memequal(k
.str
, key
.str
, uintptr(key
.len)) {
339 // Clear key's pointer.
341 e
:= add(unsafe
.Pointer(b
), dataOffset
+bucketCnt
*2*sys
.PtrSize
+i
*uintptr(t
.elemsize
))
342 if t
.elem
.ptrdata
!= 0 {
343 memclrHasPointers(e
, t
.elem
.size
)
345 memclrNoHeapPointers(e
, t
.elem
.size
)
347 b
.tophash
[i
] = emptyOne
348 // If the bucket now ends in a bunch of emptyOne states,
349 // change those to emptyRest states.
350 if i
== bucketCnt
-1 {
351 if b
.overflow(t
) != nil && b
.overflow(t
).tophash
[0] != emptyRest
{
355 if b
.tophash
[i
+1] != emptyRest
{
360 b
.tophash
[i
] = emptyRest
363 break // beginning of initial bucket, we're done.
365 // Find previous bucket, continue at its last entry.
367 for b
= bOrig
; b
.overflow(t
) != c
; b
= b
.overflow(t
) {
373 if b
.tophash
[i
] != emptyOne
{
383 if h
.flags
&hashWriting
== 0 {
384 throw("concurrent map writes")
386 h
.flags
&^= hashWriting
389 func growWork_faststr(t
*maptype
, h
*hmap
, bucket
uintptr) {
390 // make sure we evacuate the oldbucket corresponding
391 // to the bucket we're about to use
392 evacuate_faststr(t
, h
, bucket
&h
.oldbucketmask())
394 // evacuate one more oldbucket to make progress on growing
396 evacuate_faststr(t
, h
, h
.nevacuate
)
400 func evacuate_faststr(t
*maptype
, h
*hmap
, oldbucket
uintptr) {
401 b
:= (*bmap
)(add(h
.oldbuckets
, oldbucket
*uintptr(t
.bucketsize
)))
402 newbit
:= h
.noldbuckets()
404 // TODO: reuse overflow buckets instead of using new ones, if there
405 // is no iterator using the old buckets. (If !oldIterator.)
407 // xy contains the x and y (low and high) evacuation destinations.
410 x
.b
= (*bmap
)(add(h
.buckets
, oldbucket
*uintptr(t
.bucketsize
)))
411 x
.k
= add(unsafe
.Pointer(x
.b
), dataOffset
)
412 x
.e
= add(x
.k
, bucketCnt
*2*sys
.PtrSize
)
414 if !h
.sameSizeGrow() {
415 // Only calculate y pointers if we're growing bigger.
416 // Otherwise GC can see bad pointers.
418 y
.b
= (*bmap
)(add(h
.buckets
, (oldbucket
+newbit
)*uintptr(t
.bucketsize
)))
419 y
.k
= add(unsafe
.Pointer(y
.b
), dataOffset
)
420 y
.e
= add(y
.k
, bucketCnt
*2*sys
.PtrSize
)
423 for ; b
!= nil; b
= b
.overflow(t
) {
424 k
:= add(unsafe
.Pointer(b
), dataOffset
)
425 e
:= add(k
, bucketCnt
*2*sys
.PtrSize
)
426 for i
:= 0; i
< bucketCnt
; i
, k
, e
= i
+1, add(k
, 2*sys
.PtrSize
), add(e
, uintptr(t
.elemsize
)) {
429 b
.tophash
[i
] = evacuatedEmpty
432 if top
< minTopHash
{
433 throw("bad map state")
436 if !h
.sameSizeGrow() {
437 // Compute hash to make our evacuation decision (whether we need
438 // to send this key/elem to bucket x or bucket y).
439 hash
:= t
.hasher(k
, uintptr(h
.hash0
))
440 if hash
&newbit
!= 0 {
445 b
.tophash
[i
] = evacuatedX
+ useY
// evacuatedX + 1 == evacuatedY, enforced in makemap
446 dst
:= &xy
[useY
] // evacuation destination
448 if dst
.i
== bucketCnt
{
449 dst
.b
= h
.newoverflow(t
, dst
.b
)
451 dst
.k
= add(unsafe
.Pointer(dst
.b
), dataOffset
)
452 dst
.e
= add(dst
.k
, bucketCnt
*2*sys
.PtrSize
)
454 dst
.b
.tophash
[dst
.i
&(bucketCnt
-1)] = top
// mask dst.i as an optimization, to avoid a bounds check
457 *(*string)(dst
.k
) = *(*string)(k
)
459 typedmemmove(t
.elem
, dst
.e
, e
)
461 // These updates might push these pointers past the end of the
462 // key or elem arrays. That's ok, as we have the overflow pointer
463 // at the end of the bucket to protect against pointing past the
464 // end of the bucket.
465 dst
.k
= add(dst
.k
, 2*sys
.PtrSize
)
466 dst
.e
= add(dst
.e
, uintptr(t
.elemsize
))
469 // Unlink the overflow buckets & clear key/elem to help GC.
470 if h
.flags
&oldIterator
== 0 && t
.bucket
.ptrdata
!= 0 {
471 b
:= add(h
.oldbuckets
, oldbucket
*uintptr(t
.bucketsize
))
472 // Preserve b.tophash because the evacuation
473 // state is maintained there.
474 ptr
:= add(b
, dataOffset
)
475 n
:= uintptr(t
.bucketsize
) - dataOffset
476 memclrHasPointers(ptr
, n
)
480 if oldbucket
== h
.nevacuate
{
481 advanceEvacuationMark(h
, t
, newbit
)