Documentation: runtime
1
2
3
4
5 package runtime
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 import (
57 "runtime/internal/atomic"
58 "runtime/internal/math"
59 "runtime/internal/sys"
60 "unsafe"
61 )
62
63 const (
64
65 bucketCntBits = 3
66 bucketCnt = 1 << bucketCntBits
67
68
69
70 loadFactorNum = 13
71 loadFactorDen = 2
72
73
74
75
76
77 maxKeySize = 128
78 maxElemSize = 128
79
80
81
82
83 dataOffset = unsafe.Offsetof(struct {
84 b bmap
85 v int64
86 }{}.v)
87
88
89
90
91
92 emptyRest = 0
93 emptyOne = 1
94 evacuatedX = 2
95 evacuatedY = 3
96 evacuatedEmpty = 4
97 minTopHash = 5
98
99
100 iterator = 1
101 oldIterator = 2
102 hashWriting = 4
103 sameSizeGrow = 8
104
105
106 noCheck = 1<<(8*sys.PtrSize) - 1
107 )
108
109
110 func isEmpty(x uint8) bool {
111 return x <= emptyOne
112 }
113
114
115 type hmap struct {
116
117
118 count int
119 flags uint8
120 B uint8
121 noverflow uint16
122 hash0 uint32
123
124 buckets unsafe.Pointer
125 oldbuckets unsafe.Pointer
126 nevacuate uintptr
127
128 extra *mapextra
129 }
130
131
132 type mapextra struct {
133
134
135
136
137
138
139
140
141 overflow *[]*bmap
142 oldoverflow *[]*bmap
143
144
145 nextOverflow *bmap
146 }
147
148
149 type bmap struct {
150
151
152
153 tophash [bucketCnt]uint8
154
155
156
157
158
159 }
160
161
162
163
164 type hiter struct {
165 key unsafe.Pointer
166 elem unsafe.Pointer
167 t *maptype
168 h *hmap
169 buckets unsafe.Pointer
170 bptr *bmap
171 overflow *[]*bmap
172 oldoverflow *[]*bmap
173 startBucket uintptr
174 offset uint8
175 wrapped bool
176 B uint8
177 i uint8
178 bucket uintptr
179 checkBucket uintptr
180 }
181
182
183 func bucketShift(b uint8) uintptr {
184
185 return uintptr(1) << (b & (sys.PtrSize*8 - 1))
186 }
187
188
189 func bucketMask(b uint8) uintptr {
190 return bucketShift(b) - 1
191 }
192
193
194 func tophash(hash uintptr) uint8 {
195 top := uint8(hash >> (sys.PtrSize*8 - 8))
196 if top < minTopHash {
197 top += minTopHash
198 }
199 return top
200 }
201
202 func evacuated(b *bmap) bool {
203 h := b.tophash[0]
204 return h > emptyOne && h < minTopHash
205 }
206
207 func (b *bmap) overflow(t *maptype) *bmap {
208 return *(**bmap)(add(unsafe.Pointer(b), uintptr(t.bucketsize)-sys.PtrSize))
209 }
210
211 func (b *bmap) setoverflow(t *maptype, ovf *bmap) {
212 *(**bmap)(add(unsafe.Pointer(b), uintptr(t.bucketsize)-sys.PtrSize)) = ovf
213 }
214
215 func (b *bmap) keys() unsafe.Pointer {
216 return add(unsafe.Pointer(b), dataOffset)
217 }
218
219
220
221
222
223
224
225
226 func (h *hmap) incrnoverflow() {
227
228
229
230 if h.B < 16 {
231 h.noverflow++
232 return
233 }
234
235
236
237 mask := uint32(1)<<(h.B-15) - 1
238
239
240 if fastrand()&mask == 0 {
241 h.noverflow++
242 }
243 }
244
245 func (h *hmap) newoverflow(t *maptype, b *bmap) *bmap {
246 var ovf *bmap
247 if h.extra != nil && h.extra.nextOverflow != nil {
248
249
250 ovf = h.extra.nextOverflow
251 if ovf.overflow(t) == nil {
252
253 h.extra.nextOverflow = (*bmap)(add(unsafe.Pointer(ovf), uintptr(t.bucketsize)))
254 } else {
255
256
257
258 ovf.setoverflow(t, nil)
259 h.extra.nextOverflow = nil
260 }
261 } else {
262 ovf = (*bmap)(newobject(t.bucket))
263 }
264 h.incrnoverflow()
265 if t.bucket.ptrdata == 0 {
266 h.createOverflow()
267 *h.extra.overflow = append(*h.extra.overflow, ovf)
268 }
269 b.setoverflow(t, ovf)
270 return ovf
271 }
272
273 func (h *hmap) createOverflow() {
274 if h.extra == nil {
275 h.extra = new(mapextra)
276 }
277 if h.extra.overflow == nil {
278 h.extra.overflow = new([]*bmap)
279 }
280 }
281
282 func makemap64(t *maptype, hint int64, h *hmap) *hmap {
283 if int64(int(hint)) != hint {
284 hint = 0
285 }
286 return makemap(t, int(hint), h)
287 }
288
289
290
291
292 func makemap_small() *hmap {
293 h := new(hmap)
294 h.hash0 = fastrand()
295 return h
296 }
297
298
299
300
301
302
303 func makemap(t *maptype, hint int, h *hmap) *hmap {
304 mem, overflow := math.MulUintptr(uintptr(hint), t.bucket.size)
305 if overflow || mem > maxAlloc {
306 hint = 0
307 }
308
309
310 if h == nil {
311 h = new(hmap)
312 }
313 h.hash0 = fastrand()
314
315
316
317 B := uint8(0)
318 for overLoadFactor(hint, B) {
319 B++
320 }
321 h.B = B
322
323
324
325
326 if h.B != 0 {
327 var nextOverflow *bmap
328 h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
329 if nextOverflow != nil {
330 h.extra = new(mapextra)
331 h.extra.nextOverflow = nextOverflow
332 }
333 }
334
335 return h
336 }
337
338
339
340
341
342
343
344 func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) {
345 base := bucketShift(b)
346 nbuckets := base
347
348
349 if b >= 4 {
350
351
352
353 nbuckets += bucketShift(b - 4)
354 sz := t.bucket.size * nbuckets
355 up := roundupsize(sz)
356 if up != sz {
357 nbuckets = up / t.bucket.size
358 }
359 }
360
361 if dirtyalloc == nil {
362 buckets = newarray(t.bucket, int(nbuckets))
363 } else {
364
365
366
367 buckets = dirtyalloc
368 size := t.bucket.size * nbuckets
369 if t.bucket.ptrdata != 0 {
370 memclrHasPointers(buckets, size)
371 } else {
372 memclrNoHeapPointers(buckets, size)
373 }
374 }
375
376 if base != nbuckets {
377
378
379
380
381
382 nextOverflow = (*bmap)(add(buckets, base*uintptr(t.bucketsize)))
383 last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.bucketsize)))
384 last.setoverflow(t, (*bmap)(buckets))
385 }
386 return buckets, nextOverflow
387 }
388
389
390
391
392
393
394 func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
395 if raceenabled && h != nil {
396 callerpc := getcallerpc()
397 pc := funcPC(mapaccess1)
398 racereadpc(unsafe.Pointer(h), callerpc, pc)
399 raceReadObjectPC(t.key, key, callerpc, pc)
400 }
401 if msanenabled && h != nil {
402 msanread(key, t.key.size)
403 }
404 if h == nil || h.count == 0 {
405 if t.hashMightPanic() {
406 t.hasher(key, 0)
407 }
408 return unsafe.Pointer(&zeroVal[0])
409 }
410 if h.flags&hashWriting != 0 {
411 throw("concurrent map read and map write")
412 }
413 hash := t.hasher(key, uintptr(h.hash0))
414 m := bucketMask(h.B)
415 b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
416 if c := h.oldbuckets; c != nil {
417 if !h.sameSizeGrow() {
418
419 m >>= 1
420 }
421 oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
422 if !evacuated(oldb) {
423 b = oldb
424 }
425 }
426 top := tophash(hash)
427 bucketloop:
428 for ; b != nil; b = b.overflow(t) {
429 for i := uintptr(0); i < bucketCnt; i++ {
430 if b.tophash[i] != top {
431 if b.tophash[i] == emptyRest {
432 break bucketloop
433 }
434 continue
435 }
436 k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
437 if t.indirectkey() {
438 k = *((*unsafe.Pointer)(k))
439 }
440 if t.key.equal(key, k) {
441 e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
442 if t.indirectelem() {
443 e = *((*unsafe.Pointer)(e))
444 }
445 return e
446 }
447 }
448 }
449 return unsafe.Pointer(&zeroVal[0])
450 }
451
452 func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool) {
453 if raceenabled && h != nil {
454 callerpc := getcallerpc()
455 pc := funcPC(mapaccess2)
456 racereadpc(unsafe.Pointer(h), callerpc, pc)
457 raceReadObjectPC(t.key, key, callerpc, pc)
458 }
459 if msanenabled && h != nil {
460 msanread(key, t.key.size)
461 }
462 if h == nil || h.count == 0 {
463 if t.hashMightPanic() {
464 t.hasher(key, 0)
465 }
466 return unsafe.Pointer(&zeroVal[0]), false
467 }
468 if h.flags&hashWriting != 0 {
469 throw("concurrent map read and map write")
470 }
471 hash := t.hasher(key, uintptr(h.hash0))
472 m := bucketMask(h.B)
473 b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + (hash&m)*uintptr(t.bucketsize)))
474 if c := h.oldbuckets; c != nil {
475 if !h.sameSizeGrow() {
476
477 m >>= 1
478 }
479 oldb := (*bmap)(unsafe.Pointer(uintptr(c) + (hash&m)*uintptr(t.bucketsize)))
480 if !evacuated(oldb) {
481 b = oldb
482 }
483 }
484 top := tophash(hash)
485 bucketloop:
486 for ; b != nil; b = b.overflow(t) {
487 for i := uintptr(0); i < bucketCnt; i++ {
488 if b.tophash[i] != top {
489 if b.tophash[i] == emptyRest {
490 break bucketloop
491 }
492 continue
493 }
494 k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
495 if t.indirectkey() {
496 k = *((*unsafe.Pointer)(k))
497 }
498 if t.key.equal(key, k) {
499 e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
500 if t.indirectelem() {
501 e = *((*unsafe.Pointer)(e))
502 }
503 return e, true
504 }
505 }
506 }
507 return unsafe.Pointer(&zeroVal[0]), false
508 }
509
510
511 func mapaccessK(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, unsafe.Pointer) {
512 if h == nil || h.count == 0 {
513 return nil, nil
514 }
515 hash := t.hasher(key, uintptr(h.hash0))
516 m := bucketMask(h.B)
517 b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + (hash&m)*uintptr(t.bucketsize)))
518 if c := h.oldbuckets; c != nil {
519 if !h.sameSizeGrow() {
520
521 m >>= 1
522 }
523 oldb := (*bmap)(unsafe.Pointer(uintptr(c) + (hash&m)*uintptr(t.bucketsize)))
524 if !evacuated(oldb) {
525 b = oldb
526 }
527 }
528 top := tophash(hash)
529 bucketloop:
530 for ; b != nil; b = b.overflow(t) {
531 for i := uintptr(0); i < bucketCnt; i++ {
532 if b.tophash[i] != top {
533 if b.tophash[i] == emptyRest {
534 break bucketloop
535 }
536 continue
537 }
538 k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
539 if t.indirectkey() {
540 k = *((*unsafe.Pointer)(k))
541 }
542 if t.key.equal(key, k) {
543 e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
544 if t.indirectelem() {
545 e = *((*unsafe.Pointer)(e))
546 }
547 return k, e
548 }
549 }
550 }
551 return nil, nil
552 }
553
554 func mapaccess1_fat(t *maptype, h *hmap, key, zero unsafe.Pointer) unsafe.Pointer {
555 e := mapaccess1(t, h, key)
556 if e == unsafe.Pointer(&zeroVal[0]) {
557 return zero
558 }
559 return e
560 }
561
562 func mapaccess2_fat(t *maptype, h *hmap, key, zero unsafe.Pointer) (unsafe.Pointer, bool) {
563 e := mapaccess1(t, h, key)
564 if e == unsafe.Pointer(&zeroVal[0]) {
565 return zero, false
566 }
567 return e, true
568 }
569
570
571 func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
572 if h == nil {
573 panic(plainError("assignment to entry in nil map"))
574 }
575 if raceenabled {
576 callerpc := getcallerpc()
577 pc := funcPC(mapassign)
578 racewritepc(unsafe.Pointer(h), callerpc, pc)
579 raceReadObjectPC(t.key, key, callerpc, pc)
580 }
581 if msanenabled {
582 msanread(key, t.key.size)
583 }
584 if h.flags&hashWriting != 0 {
585 throw("concurrent map writes")
586 }
587 hash := t.hasher(key, uintptr(h.hash0))
588
589
590
591 h.flags ^= hashWriting
592
593 if h.buckets == nil {
594 h.buckets = newobject(t.bucket)
595 }
596
597 again:
598 bucket := hash & bucketMask(h.B)
599 if h.growing() {
600 growWork(t, h, bucket)
601 }
602 b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize)))
603 top := tophash(hash)
604
605 var inserti *uint8
606 var insertk unsafe.Pointer
607 var elem unsafe.Pointer
608 bucketloop:
609 for {
610 for i := uintptr(0); i < bucketCnt; i++ {
611 if b.tophash[i] != top {
612 if isEmpty(b.tophash[i]) && inserti == nil {
613 inserti = &b.tophash[i]
614 insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
615 elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
616 }
617 if b.tophash[i] == emptyRest {
618 break bucketloop
619 }
620 continue
621 }
622 k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
623 if t.indirectkey() {
624 k = *((*unsafe.Pointer)(k))
625 }
626 if !t.key.equal(key, k) {
627 continue
628 }
629
630 if t.needkeyupdate() {
631 typedmemmove(t.key, k, key)
632 }
633 elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
634 goto done
635 }
636 ovf := b.overflow(t)
637 if ovf == nil {
638 break
639 }
640 b = ovf
641 }
642
643
644
645
646
647 if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
648 hashGrow(t, h)
649 goto again
650 }
651
652 if inserti == nil {
653
654 newb := h.newoverflow(t, b)
655 inserti = &newb.tophash[0]
656 insertk = add(unsafe.Pointer(newb), dataOffset)
657 elem = add(insertk, bucketCnt*uintptr(t.keysize))
658 }
659
660
661 if t.indirectkey() {
662 kmem := newobject(t.key)
663 *(*unsafe.Pointer)(insertk) = kmem
664 insertk = kmem
665 }
666 if t.indirectelem() {
667 vmem := newobject(t.elem)
668 *(*unsafe.Pointer)(elem) = vmem
669 }
670 typedmemmove(t.key, insertk, key)
671 *inserti = top
672 h.count++
673
674 done:
675 if h.flags&hashWriting == 0 {
676 throw("concurrent map writes")
677 }
678 h.flags &^= hashWriting
679 if t.indirectelem() {
680 elem = *((*unsafe.Pointer)(elem))
681 }
682 return elem
683 }
684
685 func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {
686 if raceenabled && h != nil {
687 callerpc := getcallerpc()
688 pc := funcPC(mapdelete)
689 racewritepc(unsafe.Pointer(h), callerpc, pc)
690 raceReadObjectPC(t.key, key, callerpc, pc)
691 }
692 if msanenabled && h != nil {
693 msanread(key, t.key.size)
694 }
695 if h == nil || h.count == 0 {
696 if t.hashMightPanic() {
697 t.hasher(key, 0)
698 }
699 return
700 }
701 if h.flags&hashWriting != 0 {
702 throw("concurrent map writes")
703 }
704
705 hash := t.hasher(key, uintptr(h.hash0))
706
707
708
709 h.flags ^= hashWriting
710
711 bucket := hash & bucketMask(h.B)
712 if h.growing() {
713 growWork(t, h, bucket)
714 }
715 b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))
716 bOrig := b
717 top := tophash(hash)
718 search:
719 for ; b != nil; b = b.overflow(t) {
720 for i := uintptr(0); i < bucketCnt; i++ {
721 if b.tophash[i] != top {
722 if b.tophash[i] == emptyRest {
723 break search
724 }
725 continue
726 }
727 k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
728 k2 := k
729 if t.indirectkey() {
730 k2 = *((*unsafe.Pointer)(k2))
731 }
732 if !t.key.equal(key, k2) {
733 continue
734 }
735
736 if t.indirectkey() {
737 *(*unsafe.Pointer)(k) = nil
738 } else if t.key.ptrdata != 0 {
739 memclrHasPointers(k, t.key.size)
740 }
741 e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
742 if t.indirectelem() {
743 *(*unsafe.Pointer)(e) = nil
744 } else if t.elem.ptrdata != 0 {
745 memclrHasPointers(e, t.elem.size)
746 } else {
747 memclrNoHeapPointers(e, t.elem.size)
748 }
749 b.tophash[i] = emptyOne
750
751
752
753
754 if i == bucketCnt-1 {
755 if b.overflow(t) != nil && b.overflow(t).tophash[0] != emptyRest {
756 goto notLast
757 }
758 } else {
759 if b.tophash[i+1] != emptyRest {
760 goto notLast
761 }
762 }
763 for {
764 b.tophash[i] = emptyRest
765 if i == 0 {
766 if b == bOrig {
767 break
768 }
769
770 c := b
771 for b = bOrig; b.overflow(t) != c; b = b.overflow(t) {
772 }
773 i = bucketCnt - 1
774 } else {
775 i--
776 }
777 if b.tophash[i] != emptyOne {
778 break
779 }
780 }
781 notLast:
782 h.count--
783 break search
784 }
785 }
786
787 if h.flags&hashWriting == 0 {
788 throw("concurrent map writes")
789 }
790 h.flags &^= hashWriting
791 }
792
793
794
795
796
797 func mapiterinit(t *maptype, h *hmap, it *hiter) {
798 if raceenabled && h != nil {
799 callerpc := getcallerpc()
800 racereadpc(unsafe.Pointer(h), callerpc, funcPC(mapiterinit))
801 }
802
803 if h == nil || h.count == 0 {
804 return
805 }
806
807 if unsafe.Sizeof(hiter{})/sys.PtrSize != 12 {
808 throw("hash_iter size incorrect")
809 }
810 it.t = t
811 it.h = h
812
813
814 it.B = h.B
815 it.buckets = h.buckets
816 if t.bucket.ptrdata == 0 {
817
818
819
820
821 h.createOverflow()
822 it.overflow = h.extra.overflow
823 it.oldoverflow = h.extra.oldoverflow
824 }
825
826
827 r := uintptr(fastrand())
828 if h.B > 31-bucketCntBits {
829 r += uintptr(fastrand()) << 31
830 }
831 it.startBucket = r & bucketMask(h.B)
832 it.offset = uint8(r >> h.B & (bucketCnt - 1))
833
834
835 it.bucket = it.startBucket
836
837
838
839 if old := h.flags; old&(iterator|oldIterator) != iterator|oldIterator {
840 atomic.Or8(&h.flags, iterator|oldIterator)
841 }
842
843 mapiternext(it)
844 }
845
846 func mapiternext(it *hiter) {
847 h := it.h
848 if raceenabled {
849 callerpc := getcallerpc()
850 racereadpc(unsafe.Pointer(h), callerpc, funcPC(mapiternext))
851 }
852 if h.flags&hashWriting != 0 {
853 throw("concurrent map iteration and map write")
854 }
855 t := it.t
856 bucket := it.bucket
857 b := it.bptr
858 i := it.i
859 checkBucket := it.checkBucket
860
861 next:
862 if b == nil {
863 if bucket == it.startBucket && it.wrapped {
864
865 it.key = nil
866 it.elem = nil
867 return
868 }
869 if h.growing() && it.B == h.B {
870
871
872
873
874 oldbucket := bucket & it.h.oldbucketmask()
875 b = (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
876 if !evacuated(b) {
877 checkBucket = bucket
878 } else {
879 b = (*bmap)(add(it.buckets, bucket*uintptr(t.bucketsize)))
880 checkBucket = noCheck
881 }
882 } else {
883 b = (*bmap)(add(it.buckets, bucket*uintptr(t.bucketsize)))
884 checkBucket = noCheck
885 }
886 bucket++
887 if bucket == bucketShift(it.B) {
888 bucket = 0
889 it.wrapped = true
890 }
891 i = 0
892 }
893 for ; i < bucketCnt; i++ {
894 offi := (i + it.offset) & (bucketCnt - 1)
895 if isEmpty(b.tophash[offi]) || b.tophash[offi] == evacuatedEmpty {
896
897
898 continue
899 }
900 k := add(unsafe.Pointer(b), dataOffset+uintptr(offi)*uintptr(t.keysize))
901 if t.indirectkey() {
902 k = *((*unsafe.Pointer)(k))
903 }
904 e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+uintptr(offi)*uintptr(t.elemsize))
905 if checkBucket != noCheck && !h.sameSizeGrow() {
906
907
908
909
910
911
912
913 if t.reflexivekey() || t.key.equal(k, k) {
914
915
916 hash := t.hasher(k, uintptr(h.hash0))
917 if hash&bucketMask(it.B) != checkBucket {
918 continue
919 }
920 } else {
921
922
923
924
925
926
927
928 if checkBucket>>(it.B-1) != uintptr(b.tophash[offi]&1) {
929 continue
930 }
931 }
932 }
933 if (b.tophash[offi] != evacuatedX && b.tophash[offi] != evacuatedY) ||
934 !(t.reflexivekey() || t.key.equal(k, k)) {
935
936
937
938
939 it.key = k
940 if t.indirectelem() {
941 e = *((*unsafe.Pointer)(e))
942 }
943 it.elem = e
944 } else {
945
946
947
948
949
950
951
952 rk, re := mapaccessK(t, h, k)
953 if rk == nil {
954 continue
955 }
956 it.key = rk
957 it.elem = re
958 }
959 it.bucket = bucket
960 if it.bptr != b {
961 it.bptr = b
962 }
963 it.i = i + 1
964 it.checkBucket = checkBucket
965 return
966 }
967 b = b.overflow(t)
968 i = 0
969 goto next
970 }
971
972
973 func mapclear(t *maptype, h *hmap) {
974 if raceenabled && h != nil {
975 callerpc := getcallerpc()
976 pc := funcPC(mapclear)
977 racewritepc(unsafe.Pointer(h), callerpc, pc)
978 }
979
980 if h == nil || h.count == 0 {
981 return
982 }
983
984 if h.flags&hashWriting != 0 {
985 throw("concurrent map writes")
986 }
987
988 h.flags ^= hashWriting
989
990 h.flags &^= sameSizeGrow
991 h.oldbuckets = nil
992 h.nevacuate = 0
993 h.noverflow = 0
994 h.count = 0
995
996
997 if h.extra != nil {
998 *h.extra = mapextra{}
999 }
1000
1001
1002
1003
1004 _, nextOverflow := makeBucketArray(t, h.B, h.buckets)
1005 if nextOverflow != nil {
1006
1007
1008 h.extra.nextOverflow = nextOverflow
1009 }
1010
1011 if h.flags&hashWriting == 0 {
1012 throw("concurrent map writes")
1013 }
1014 h.flags &^= hashWriting
1015 }
1016
1017 func hashGrow(t *maptype, h *hmap) {
1018
1019
1020
1021 bigger := uint8(1)
1022 if !overLoadFactor(h.count+1, h.B) {
1023 bigger = 0
1024 h.flags |= sameSizeGrow
1025 }
1026 oldbuckets := h.buckets
1027 newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)
1028
1029 flags := h.flags &^ (iterator | oldIterator)
1030 if h.flags&iterator != 0 {
1031 flags |= oldIterator
1032 }
1033
1034 h.B += bigger
1035 h.flags = flags
1036 h.oldbuckets = oldbuckets
1037 h.buckets = newbuckets
1038 h.nevacuate = 0
1039 h.noverflow = 0
1040
1041 if h.extra != nil && h.extra.overflow != nil {
1042
1043 if h.extra.oldoverflow != nil {
1044 throw("oldoverflow is not nil")
1045 }
1046 h.extra.oldoverflow = h.extra.overflow
1047 h.extra.overflow = nil
1048 }
1049 if nextOverflow != nil {
1050 if h.extra == nil {
1051 h.extra = new(mapextra)
1052 }
1053 h.extra.nextOverflow = nextOverflow
1054 }
1055
1056
1057
1058 }
1059
1060
1061 func overLoadFactor(count int, B uint8) bool {
1062 return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
1063 }
1064
1065
1066
1067
1068 func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {
1069
1070
1071
1072
1073 if B > 15 {
1074 B = 15
1075 }
1076
1077 return noverflow >= uint16(1)<<(B&15)
1078 }
1079
1080
1081 func (h *hmap) growing() bool {
1082 return h.oldbuckets != nil
1083 }
1084
1085
1086 func (h *hmap) sameSizeGrow() bool {
1087 return h.flags&sameSizeGrow != 0
1088 }
1089
1090
1091 func (h *hmap) noldbuckets() uintptr {
1092 oldB := h.B
1093 if !h.sameSizeGrow() {
1094 oldB--
1095 }
1096 return bucketShift(oldB)
1097 }
1098
1099
1100 func (h *hmap) oldbucketmask() uintptr {
1101 return h.noldbuckets() - 1
1102 }
1103
1104 func growWork(t *maptype, h *hmap, bucket uintptr) {
1105
1106
1107 evacuate(t, h, bucket&h.oldbucketmask())
1108
1109
1110 if h.growing() {
1111 evacuate(t, h, h.nevacuate)
1112 }
1113 }
1114
1115 func bucketEvacuated(t *maptype, h *hmap, bucket uintptr) bool {
1116 b := (*bmap)(add(h.oldbuckets, bucket*uintptr(t.bucketsize)))
1117 return evacuated(b)
1118 }
1119
1120
1121 type evacDst struct {
1122 b *bmap
1123 i int
1124 k unsafe.Pointer
1125 e unsafe.Pointer
1126 }
1127
1128 func evacuate(t *maptype, h *hmap, oldbucket uintptr) {
1129 b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
1130 newbit := h.noldbuckets()
1131 if !evacuated(b) {
1132
1133
1134
1135
1136 var xy [2]evacDst
1137 x := &xy[0]
1138 x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize)))
1139 x.k = add(unsafe.Pointer(x.b), dataOffset)
1140 x.e = add(x.k, bucketCnt*uintptr(t.keysize))
1141
1142 if !h.sameSizeGrow() {
1143
1144
1145 y := &xy[1]
1146 y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize)))
1147 y.k = add(unsafe.Pointer(y.b), dataOffset)
1148 y.e = add(y.k, bucketCnt*uintptr(t.keysize))
1149 }
1150
1151 for ; b != nil; b = b.overflow(t) {
1152 k := add(unsafe.Pointer(b), dataOffset)
1153 e := add(k, bucketCnt*uintptr(t.keysize))
1154 for i := 0; i < bucketCnt; i, k, e = i+1, add(k, uintptr(t.keysize)), add(e, uintptr(t.elemsize)) {
1155 top := b.tophash[i]
1156 if isEmpty(top) {
1157 b.tophash[i] = evacuatedEmpty
1158 continue
1159 }
1160 if top < minTopHash {
1161 throw("bad map state")
1162 }
1163 k2 := k
1164 if t.indirectkey() {
1165 k2 = *((*unsafe.Pointer)(k2))
1166 }
1167 var useY uint8
1168 if !h.sameSizeGrow() {
1169
1170
1171 hash := t.hasher(k2, uintptr(h.hash0))
1172 if h.flags&iterator != 0 && !t.reflexivekey() && !t.key.equal(k2, k2) {
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184 useY = top & 1
1185 top = tophash(hash)
1186 } else {
1187 if hash&newbit != 0 {
1188 useY = 1
1189 }
1190 }
1191 }
1192
1193 if evacuatedX+1 != evacuatedY || evacuatedX^1 != evacuatedY {
1194 throw("bad evacuatedN")
1195 }
1196
1197 b.tophash[i] = evacuatedX + useY
1198 dst := &xy[useY]
1199
1200 if dst.i == bucketCnt {
1201 dst.b = h.newoverflow(t, dst.b)
1202 dst.i = 0
1203 dst.k = add(unsafe.Pointer(dst.b), dataOffset)
1204 dst.e = add(dst.k, bucketCnt*uintptr(t.keysize))
1205 }
1206 dst.b.tophash[dst.i&(bucketCnt-1)] = top
1207 if t.indirectkey() {
1208 *(*unsafe.Pointer)(dst.k) = k2
1209 } else {
1210 typedmemmove(t.key, dst.k, k)
1211 }
1212 if t.indirectelem() {
1213 *(*unsafe.Pointer)(dst.e) = *(*unsafe.Pointer)(e)
1214 } else {
1215 typedmemmove(t.elem, dst.e, e)
1216 }
1217 dst.i++
1218
1219
1220
1221
1222 dst.k = add(dst.k, uintptr(t.keysize))
1223 dst.e = add(dst.e, uintptr(t.elemsize))
1224 }
1225 }
1226
1227 if h.flags&oldIterator == 0 && t.bucket.ptrdata != 0 {
1228 b := add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))
1229
1230
1231 ptr := add(b, dataOffset)
1232 n := uintptr(t.bucketsize) - dataOffset
1233 memclrHasPointers(ptr, n)
1234 }
1235 }
1236
1237 if oldbucket == h.nevacuate {
1238 advanceEvacuationMark(h, t, newbit)
1239 }
1240 }
1241
1242 func advanceEvacuationMark(h *hmap, t *maptype, newbit uintptr) {
1243 h.nevacuate++
1244
1245
1246 stop := h.nevacuate + 1024
1247 if stop > newbit {
1248 stop = newbit
1249 }
1250 for h.nevacuate != stop && bucketEvacuated(t, h, h.nevacuate) {
1251 h.nevacuate++
1252 }
1253 if h.nevacuate == newbit {
1254
1255 h.oldbuckets = nil
1256
1257
1258
1259 if h.extra != nil {
1260 h.extra.oldoverflow = nil
1261 }
1262 h.flags &^= sameSizeGrow
1263 }
1264 }
1265
1266
1267
1268
1269 func reflect_makemap(t *maptype, cap int) *hmap {
1270
1271 if t.key.equal == nil {
1272 throw("runtime.reflect_makemap: unsupported map key type")
1273 }
1274 if t.key.size > maxKeySize && (!t.indirectkey() || t.keysize != uint8(sys.PtrSize)) ||
1275 t.key.size <= maxKeySize && (t.indirectkey() || t.keysize != uint8(t.key.size)) {
1276 throw("key size wrong")
1277 }
1278 if t.elem.size > maxElemSize && (!t.indirectelem() || t.elemsize != uint8(sys.PtrSize)) ||
1279 t.elem.size <= maxElemSize && (t.indirectelem() || t.elemsize != uint8(t.elem.size)) {
1280 throw("elem size wrong")
1281 }
1282 if t.key.align > bucketCnt {
1283 throw("key align too big")
1284 }
1285 if t.elem.align > bucketCnt {
1286 throw("elem align too big")
1287 }
1288 if t.key.size%uintptr(t.key.align) != 0 {
1289 throw("key size not a multiple of key align")
1290 }
1291 if t.elem.size%uintptr(t.elem.align) != 0 {
1292 throw("elem size not a multiple of elem align")
1293 }
1294 if bucketCnt < 8 {
1295 throw("bucketsize too small for proper alignment")
1296 }
1297 if dataOffset%uintptr(t.key.align) != 0 {
1298 throw("need padding in bucket (key)")
1299 }
1300 if dataOffset%uintptr(t.elem.align) != 0 {
1301 throw("need padding in bucket (elem)")
1302 }
1303
1304 return makemap(t, cap, nil)
1305 }
1306
1307
1308 func reflect_mapaccess(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
1309 elem, ok := mapaccess2(t, h, key)
1310 if !ok {
1311
1312 elem = nil
1313 }
1314 return elem
1315 }
1316
1317
1318 func reflect_mapassign(t *maptype, h *hmap, key unsafe.Pointer, elem unsafe.Pointer) {
1319 p := mapassign(t, h, key)
1320 typedmemmove(t.elem, p, elem)
1321 }
1322
1323
1324 func reflect_mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {
1325 mapdelete(t, h, key)
1326 }
1327
1328
1329 func reflect_mapiterinit(t *maptype, h *hmap) *hiter {
1330 it := new(hiter)
1331 mapiterinit(t, h, it)
1332 return it
1333 }
1334
1335
1336 func reflect_mapiternext(it *hiter) {
1337 mapiternext(it)
1338 }
1339
1340
1341 func reflect_mapiterkey(it *hiter) unsafe.Pointer {
1342 return it.key
1343 }
1344
1345
1346 func reflect_mapiterelem(it *hiter) unsafe.Pointer {
1347 return it.elem
1348 }
1349
1350
1351 func reflect_maplen(h *hmap) int {
1352 if h == nil {
1353 return 0
1354 }
1355 if raceenabled {
1356 callerpc := getcallerpc()
1357 racereadpc(unsafe.Pointer(h), callerpc, funcPC(reflect_maplen))
1358 }
1359 return h.count
1360 }
1361
1362
1363 func reflectlite_maplen(h *hmap) int {
1364 if h == nil {
1365 return 0
1366 }
1367 if raceenabled {
1368 callerpc := getcallerpc()
1369 racereadpc(unsafe.Pointer(h), callerpc, funcPC(reflect_maplen))
1370 }
1371 return h.count
1372 }
1373
1374 const maxZero = 1024
1375 var zeroVal [maxZero]byte
1376
View as plain text