1 // Copyright 2014 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 func mapaccess1_fast32(t
*maptype
, h
*hmap
, key
uint32) unsafe
.Pointer
{
13 if raceenabled
&& h
!= nil {
14 callerpc
:= getcallerpc(unsafe
.Pointer( /* &t */ nil))
15 racereadpc(unsafe
.Pointer(h
), callerpc
, funcPC(mapaccess1_fast32
))
17 if h
== nil || h
.count
== 0 {
18 return unsafe
.Pointer(&zeroVal
[0])
20 if h
.flags
&hashWriting
!= 0 {
21 throw("concurrent map read and map write")
25 // One-bucket table. No need to hash.
26 b
= (*bmap
)(h
.buckets
)
28 hash
:= t
.key
.hashfn(noescape(unsafe
.Pointer(&key
)), uintptr(h
.hash0
))
29 m
:= uintptr(1)<<h
.B
- 1
30 b
= (*bmap
)(add(h
.buckets
, (hash
&m
)*uintptr(t
.bucketsize
)))
31 if c
:= h
.oldbuckets
; c
!= nil {
32 if !h
.sameSizeGrow() {
33 // There used to be half as many buckets; mask down one more power of two.
36 oldb
:= (*bmap
)(add(c
, (hash
&m
)*uintptr(t
.bucketsize
)))
43 for i
:= uintptr(0); i
< bucketCnt
; i
++ {
44 k
:= *((*uint32)(add(unsafe
.Pointer(b
), dataOffset
+i
*4)))
48 x
:= *((*uint8)(add(unsafe
.Pointer(b
), i
))) // b.topbits[i] without the bounds check
52 return add(unsafe
.Pointer(b
), dataOffset
+bucketCnt
*4+i
*uintptr(t
.valuesize
))
56 return unsafe
.Pointer(&zeroVal
[0])
61 func mapaccess2_fast32(t
*maptype
, h
*hmap
, key
uint32) (unsafe
.Pointer
, bool) {
62 if raceenabled
&& h
!= nil {
63 callerpc
:= getcallerpc(unsafe
.Pointer( /* &t */ nil))
64 racereadpc(unsafe
.Pointer(h
), callerpc
, funcPC(mapaccess2_fast32
))
66 if h
== nil || h
.count
== 0 {
67 return unsafe
.Pointer(&zeroVal
[0]), false
69 if h
.flags
&hashWriting
!= 0 {
70 throw("concurrent map read and map write")
74 // One-bucket table. No need to hash.
75 b
= (*bmap
)(h
.buckets
)
77 hash
:= t
.key
.hashfn(noescape(unsafe
.Pointer(&key
)), uintptr(h
.hash0
))
78 m
:= uintptr(1)<<h
.B
- 1
79 b
= (*bmap
)(add(h
.buckets
, (hash
&m
)*uintptr(t
.bucketsize
)))
80 if c
:= h
.oldbuckets
; c
!= nil {
81 if !h
.sameSizeGrow() {
82 // There used to be half as many buckets; mask down one more power of two.
85 oldb
:= (*bmap
)(add(c
, (hash
&m
)*uintptr(t
.bucketsize
)))
92 for i
:= uintptr(0); i
< bucketCnt
; i
++ {
93 k
:= *((*uint32)(add(unsafe
.Pointer(b
), dataOffset
+i
*4)))
97 x
:= *((*uint8)(add(unsafe
.Pointer(b
), i
))) // b.topbits[i] without the bounds check
101 return add(unsafe
.Pointer(b
), dataOffset
+bucketCnt
*4+i
*uintptr(t
.valuesize
)), true
105 return unsafe
.Pointer(&zeroVal
[0]), false
110 func mapaccess1_fast64(t
*maptype
, h
*hmap
, key
uint64) unsafe
.Pointer
{
111 if raceenabled
&& h
!= nil {
112 callerpc
:= getcallerpc(unsafe
.Pointer( /* &t */ nil))
113 racereadpc(unsafe
.Pointer(h
), callerpc
, funcPC(mapaccess1_fast64
))
115 if h
== nil || h
.count
== 0 {
116 return unsafe
.Pointer(&zeroVal
[0])
118 if h
.flags
&hashWriting
!= 0 {
119 throw("concurrent map read and map write")
123 // One-bucket table. No need to hash.
124 b
= (*bmap
)(h
.buckets
)
126 hash
:= t
.key
.hashfn(noescape(unsafe
.Pointer(&key
)), uintptr(h
.hash0
))
127 m
:= uintptr(1)<<h
.B
- 1
128 b
= (*bmap
)(add(h
.buckets
, (hash
&m
)*uintptr(t
.bucketsize
)))
129 if c
:= h
.oldbuckets
; c
!= nil {
130 if !h
.sameSizeGrow() {
131 // There used to be half as many buckets; mask down one more power of two.
134 oldb
:= (*bmap
)(add(c
, (hash
&m
)*uintptr(t
.bucketsize
)))
135 if !evacuated(oldb
) {
141 for i
:= uintptr(0); i
< bucketCnt
; i
++ {
142 k
:= *((*uint64)(add(unsafe
.Pointer(b
), dataOffset
+i
*8)))
146 x
:= *((*uint8)(add(unsafe
.Pointer(b
), i
))) // b.topbits[i] without the bounds check
150 return add(unsafe
.Pointer(b
), dataOffset
+bucketCnt
*8+i
*uintptr(t
.valuesize
))
154 return unsafe
.Pointer(&zeroVal
[0])
159 func mapaccess2_fast64(t
*maptype
, h
*hmap
, key
uint64) (unsafe
.Pointer
, bool) {
160 if raceenabled
&& h
!= nil {
161 callerpc
:= getcallerpc(unsafe
.Pointer( /* &t */ nil))
162 racereadpc(unsafe
.Pointer(h
), callerpc
, funcPC(mapaccess2_fast64
))
164 if h
== nil || h
.count
== 0 {
165 return unsafe
.Pointer(&zeroVal
[0]), false
167 if h
.flags
&hashWriting
!= 0 {
168 throw("concurrent map read and map write")
172 // One-bucket table. No need to hash.
173 b
= (*bmap
)(h
.buckets
)
175 hash
:= t
.key
.hashfn(noescape(unsafe
.Pointer(&key
)), uintptr(h
.hash0
))
176 m
:= uintptr(1)<<h
.B
- 1
177 b
= (*bmap
)(add(h
.buckets
, (hash
&m
)*uintptr(t
.bucketsize
)))
178 if c
:= h
.oldbuckets
; c
!= nil {
179 if !h
.sameSizeGrow() {
180 // There used to be half as many buckets; mask down one more power of two.
183 oldb
:= (*bmap
)(add(c
, (hash
&m
)*uintptr(t
.bucketsize
)))
184 if !evacuated(oldb
) {
190 for i
:= uintptr(0); i
< bucketCnt
; i
++ {
191 k
:= *((*uint64)(add(unsafe
.Pointer(b
), dataOffset
+i
*8)))
195 x
:= *((*uint8)(add(unsafe
.Pointer(b
), i
))) // b.topbits[i] without the bounds check
199 return add(unsafe
.Pointer(b
), dataOffset
+bucketCnt
*8+i
*uintptr(t
.valuesize
)), true
203 return unsafe
.Pointer(&zeroVal
[0]), false
208 func mapaccess1_faststr(t
*maptype
, h
*hmap
, ky
string) unsafe
.Pointer
{
209 if raceenabled
&& h
!= nil {
210 callerpc
:= getcallerpc(unsafe
.Pointer( /* &t */ nil))
211 racereadpc(unsafe
.Pointer(h
), callerpc
, funcPC(mapaccess1_faststr
))
213 if h
== nil || h
.count
== 0 {
214 return unsafe
.Pointer(&zeroVal
[0])
216 if h
.flags
&hashWriting
!= 0 {
217 throw("concurrent map read and map write")
219 key
:= stringStructOf(&ky
)
222 b
:= (*bmap
)(h
.buckets
)
224 // short key, doing lots of comparisons is ok
225 for i
:= uintptr(0); i
< bucketCnt
; i
++ {
226 x
:= *((*uint8)(add(unsafe
.Pointer(b
), i
))) // b.topbits[i] without the bounds check
230 k
:= (*stringStruct
)(add(unsafe
.Pointer(b
), dataOffset
+i
*2*sys
.PtrSize
))
231 if k
.len != key
.len {
234 if k
.str
== key
.str ||
memequal(k
.str
, key
.str
, uintptr(key
.len)) {
235 return add(unsafe
.Pointer(b
), dataOffset
+bucketCnt
*2*sys
.PtrSize
+i
*uintptr(t
.valuesize
))
238 return unsafe
.Pointer(&zeroVal
[0])
240 // long key, try not to do more comparisons than necessary
241 keymaybe
:= uintptr(bucketCnt
)
242 for i
:= uintptr(0); i
< bucketCnt
; i
++ {
243 x
:= *((*uint8)(add(unsafe
.Pointer(b
), i
))) // b.topbits[i] without the bounds check
247 k
:= (*stringStruct
)(add(unsafe
.Pointer(b
), dataOffset
+i
*2*sys
.PtrSize
))
248 if k
.len != key
.len {
251 if k
.str
== key
.str
{
252 return add(unsafe
.Pointer(b
), dataOffset
+bucketCnt
*2*sys
.PtrSize
+i
*uintptr(t
.valuesize
))
254 // check first 4 bytes
255 // TODO: on amd64/386 at least, make this compile to one 4-byte comparison instead of
256 // four 1-byte comparisons.
257 if *((*[4]byte)(key
.str
)) != *((*[4]byte)(k
.str
)) {
260 // check last 4 bytes
261 if *((*[4]byte)(add(key
.str
, uintptr(key
.len)-4))) != *((*[4]byte)(add(k
.str
, uintptr(key
.len)-4))) {
264 if keymaybe
!= bucketCnt
{
265 // Two keys are potential matches. Use hash to distinguish them.
270 if keymaybe
!= bucketCnt
{
271 k
:= (*stringStruct
)(add(unsafe
.Pointer(b
), dataOffset
+keymaybe
*2*sys
.PtrSize
))
272 if memequal(k
.str
, key
.str
, uintptr(key
.len)) {
273 return add(unsafe
.Pointer(b
), dataOffset
+bucketCnt
*2*sys
.PtrSize
+keymaybe
*uintptr(t
.valuesize
))
276 return unsafe
.Pointer(&zeroVal
[0])
279 hash
:= t
.key
.hashfn(noescape(unsafe
.Pointer(&ky
)), uintptr(h
.hash0
))
280 m
:= uintptr(1)<<h
.B
- 1
281 b
:= (*bmap
)(add(h
.buckets
, (hash
&m
)*uintptr(t
.bucketsize
)))
282 if c
:= h
.oldbuckets
; c
!= nil {
283 if !h
.sameSizeGrow() {
284 // There used to be half as many buckets; mask down one more power of two.
287 oldb
:= (*bmap
)(add(c
, (hash
&m
)*uintptr(t
.bucketsize
)))
288 if !evacuated(oldb
) {
292 top
:= uint8(hash
>> (sys
.PtrSize
*8 - 8))
293 if top
< minTopHash
{
297 for i
:= uintptr(0); i
< bucketCnt
; i
++ {
298 x
:= *((*uint8)(add(unsafe
.Pointer(b
), i
))) // b.topbits[i] without the bounds check
302 k
:= (*stringStruct
)(add(unsafe
.Pointer(b
), dataOffset
+i
*2*sys
.PtrSize
))
303 if k
.len != key
.len {
306 if k
.str
== key
.str ||
memequal(k
.str
, key
.str
, uintptr(key
.len)) {
307 return add(unsafe
.Pointer(b
), dataOffset
+bucketCnt
*2*sys
.PtrSize
+i
*uintptr(t
.valuesize
))
312 return unsafe
.Pointer(&zeroVal
[0])
317 func mapaccess2_faststr(t
*maptype
, h
*hmap
, ky
string) (unsafe
.Pointer
, bool) {
318 if raceenabled
&& h
!= nil {
319 callerpc
:= getcallerpc(unsafe
.Pointer( /* &t */ nil))
320 racereadpc(unsafe
.Pointer(h
), callerpc
, funcPC(mapaccess2_faststr
))
322 if h
== nil || h
.count
== 0 {
323 return unsafe
.Pointer(&zeroVal
[0]), false
325 if h
.flags
&hashWriting
!= 0 {
326 throw("concurrent map read and map write")
328 key
:= stringStructOf(&ky
)
331 b
:= (*bmap
)(h
.buckets
)
333 // short key, doing lots of comparisons is ok
334 for i
:= uintptr(0); i
< bucketCnt
; i
++ {
335 x
:= *((*uint8)(add(unsafe
.Pointer(b
), i
))) // b.topbits[i] without the bounds check
339 k
:= (*stringStruct
)(add(unsafe
.Pointer(b
), dataOffset
+i
*2*sys
.PtrSize
))
340 if k
.len != key
.len {
343 if k
.str
== key
.str ||
memequal(k
.str
, key
.str
, uintptr(key
.len)) {
344 return add(unsafe
.Pointer(b
), dataOffset
+bucketCnt
*2*sys
.PtrSize
+i
*uintptr(t
.valuesize
)), true
347 return unsafe
.Pointer(&zeroVal
[0]), false
349 // long key, try not to do more comparisons than necessary
350 keymaybe
:= uintptr(bucketCnt
)
351 for i
:= uintptr(0); i
< bucketCnt
; i
++ {
352 x
:= *((*uint8)(add(unsafe
.Pointer(b
), i
))) // b.topbits[i] without the bounds check
356 k
:= (*stringStruct
)(add(unsafe
.Pointer(b
), dataOffset
+i
*2*sys
.PtrSize
))
357 if k
.len != key
.len {
360 if k
.str
== key
.str
{
361 return add(unsafe
.Pointer(b
), dataOffset
+bucketCnt
*2*sys
.PtrSize
+i
*uintptr(t
.valuesize
)), true
363 // check first 4 bytes
364 if *((*[4]byte)(key
.str
)) != *((*[4]byte)(k
.str
)) {
367 // check last 4 bytes
368 if *((*[4]byte)(add(key
.str
, uintptr(key
.len)-4))) != *((*[4]byte)(add(k
.str
, uintptr(key
.len)-4))) {
371 if keymaybe
!= bucketCnt
{
372 // Two keys are potential matches. Use hash to distinguish them.
377 if keymaybe
!= bucketCnt
{
378 k
:= (*stringStruct
)(add(unsafe
.Pointer(b
), dataOffset
+keymaybe
*2*sys
.PtrSize
))
379 if memequal(k
.str
, key
.str
, uintptr(key
.len)) {
380 return add(unsafe
.Pointer(b
), dataOffset
+bucketCnt
*2*sys
.PtrSize
+keymaybe
*uintptr(t
.valuesize
)), true
383 return unsafe
.Pointer(&zeroVal
[0]), false
386 hash
:= t
.key
.hashfn(noescape(unsafe
.Pointer(&ky
)), uintptr(h
.hash0
))
387 m
:= uintptr(1)<<h
.B
- 1
388 b
:= (*bmap
)(add(h
.buckets
, (hash
&m
)*uintptr(t
.bucketsize
)))
389 if c
:= h
.oldbuckets
; c
!= nil {
390 if !h
.sameSizeGrow() {
391 // There used to be half as many buckets; mask down one more power of two.
394 oldb
:= (*bmap
)(add(c
, (hash
&m
)*uintptr(t
.bucketsize
)))
395 if !evacuated(oldb
) {
399 top
:= uint8(hash
>> (sys
.PtrSize
*8 - 8))
400 if top
< minTopHash
{
404 for i
:= uintptr(0); i
< bucketCnt
; i
++ {
405 x
:= *((*uint8)(add(unsafe
.Pointer(b
), i
))) // b.topbits[i] without the bounds check
409 k
:= (*stringStruct
)(add(unsafe
.Pointer(b
), dataOffset
+i
*2*sys
.PtrSize
))
410 if k
.len != key
.len {
413 if k
.str
== key
.str ||
memequal(k
.str
, key
.str
, uintptr(key
.len)) {
414 return add(unsafe
.Pointer(b
), dataOffset
+bucketCnt
*2*sys
.PtrSize
+i
*uintptr(t
.valuesize
)), true
419 return unsafe
.Pointer(&zeroVal
[0]), false