summaryrefslogtreecommitdiff
path: root/src/runtime/hashmap.go
diff options
context:
space:
mode:
Diffstat (limited to 'src/runtime/hashmap.go')
-rw-r--r--src/runtime/hashmap.go953
1 files changed, 953 insertions, 0 deletions
diff --git a/src/runtime/hashmap.go b/src/runtime/hashmap.go
new file mode 100644
index 000000000..b4e624423
--- /dev/null
+++ b/src/runtime/hashmap.go
@@ -0,0 +1,953 @@
+// Copyright 2014 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package runtime
+
+// This file contains the implementation of Go's map type.
+//
+// A map is just a hash table. The data is arranged
+// into an array of buckets. Each bucket contains up to
+// 8 key/value pairs. The low-order bits of the hash are
+// used to select a bucket. Each bucket contains a few
+// high-order bits of each hash to distinguish the entries
+// within a single bucket.
+//
+// If more than 8 keys hash to a bucket, we chain on
+// extra buckets.
+//
+// When the hashtable grows, we allocate a new array
+// of buckets twice as big. Buckets are incrementally
+// copied from the old bucket array to the new bucket array.
+//
+// Map iterators walk through the array of buckets and
+// return the keys in walk order (bucket #, then overflow
+// chain order, then bucket index). To maintain iteration
+// semantics, we never move keys within their bucket (if
+// we did, keys might be returned 0 or 2 times). When
+// growing the table, iterators remain iterating through the
+// old table and must check the new table if the bucket
+// they are iterating through has been moved ("evacuated")
+// to the new table.
+
+// Picking loadFactor: too large and we have lots of overflow
+// buckets, too small and we waste a lot of space. I wrote
+// a simple program to check some stats for different loads:
+// (64-bit, 8 byte keys and values)
+// loadFactor %overflow bytes/entry hitprobe missprobe
+// 4.00 2.13 20.77 3.00 4.00
+// 4.50 4.05 17.30 3.25 4.50
+// 5.00 6.85 14.77 3.50 5.00
+// 5.50 10.55 12.94 3.75 5.50
+// 6.00 15.27 11.67 4.00 6.00
+// 6.50 20.90 10.79 4.25 6.50
+// 7.00 27.14 10.15 4.50 7.00
+// 7.50 34.03 9.73 4.75 7.50
+// 8.00 41.10 9.40 5.00 8.00
+//
+// %overflow = percentage of buckets which have an overflow bucket
+// bytes/entry = overhead bytes used per key/value pair
+// hitprobe = # of entries to check when looking up a present key
+// missprobe = # of entries to check when looking up an absent key
+//
+// Keep in mind this data is for maximally loaded tables, i.e. just
+// before the table grows. Typical tables will be somewhat less loaded.
+
+import (
+ "unsafe"
+)
+
+const (
+ // Maximum number of key/value pairs a bucket can hold.
+ bucketCntBits = 3
+ bucketCnt = 1 << bucketCntBits
+
+ // Maximum average load of a bucket that triggers growth.
+ loadFactor = 6.5
+
+ // Maximum key or value size to keep inline (instead of mallocing per element).
+ // Must fit in a uint8.
+ // Fast versions cannot handle big values - the cutoff size for
+ // fast versions in ../../cmd/gc/walk.c must be at most this value.
+ maxKeySize = 128
+ maxValueSize = 128
+
+ // data offset should be the size of the bmap struct, but needs to be
+ // aligned correctly. For amd64p32 this means 64-bit alignment
+ // even though pointers are 32 bit.
+ dataOffset = unsafe.Offsetof(struct {
+ b bmap
+ v int64
+ }{}.v)
+
+ // Possible tophash values. We reserve a few possibilities for special marks.
+ // Each bucket (including its overflow buckets, if any) will have either all or none of its
+ // entries in the evacuated* states (except during the evacuate() method, which only happens
+ // during map writes and thus no one else can observe the map during that time).
+ empty = 0 // cell is empty
+ evacuatedEmpty = 1 // cell is empty, bucket is evacuated.
+ evacuatedX = 2 // key/value is valid. Entry has been evacuated to first half of larger table.
+ evacuatedY = 3 // same as above, but evacuated to second half of larger table.
+ minTopHash = 4 // minimum tophash for a normal filled cell.
+
+ // flags
+ iterator = 1 // there may be an iterator using buckets
+ oldIterator = 2 // there may be an iterator using oldbuckets
+
+ // sentinel bucket ID for iterator checks
+ noCheck = 1<<(8*ptrSize) - 1
+
+ // trigger a garbage collection at every alloc called from this code
+ checkgc = false
+)
+
+// A header for a Go map.
+type hmap struct {
+ // Note: the format of the Hmap is encoded in ../../cmd/gc/reflect.c and
+ // ../reflect/type.go. Don't change this structure without also changing that code!
+ count int // # live cells == size of map. Must be first (used by len() builtin)
+ flags uint32
+ hash0 uint32 // hash seed
+ B uint8 // log_2 of # of buckets (can hold up to loadFactor * 2^B items)
+
+ buckets unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.
+ oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing
+ nevacuate uintptr // progress counter for evacuation (buckets less than this have been evacuated)
+}
+
+// A bucket for a Go map.
+type bmap struct {
+ tophash [bucketCnt]uint8
+ overflow *bmap
+ // Followed by bucketCnt keys and then bucketCnt values.
+ // NOTE: packing all the keys together and then all the values together makes the
+ // code a bit more complicated than alternating key/value/key/value/... but it allows
+ // us to eliminate padding which would be needed for, e.g., map[int64]int8.
+}
+
+// A hash iteration structure.
+// If you modify hiter, also change cmd/gc/reflect.c to indicate
+// the layout of this structure.
+type hiter struct {
+ key unsafe.Pointer // Must be in first position. Write nil to indicate iteration end (see cmd/gc/range.c).
+ value unsafe.Pointer // Must be in second position (see cmd/gc/range.c).
+ t *maptype
+ h *hmap
+ buckets unsafe.Pointer // bucket ptr at hash_iter initialization time
+ bptr *bmap // current bucket
+ startBucket uintptr // bucket iteration started at
+ offset uint8 // intra-bucket offset to start from during iteration (should be big enough to hold bucketCnt-1)
+ wrapped bool // already wrapped around from end of bucket array to beginning
+ B uint8
+ i uint8
+ bucket uintptr
+ checkBucket uintptr
+}
+
+func evacuated(b *bmap) bool {
+ h := b.tophash[0]
+ return h > empty && h < minTopHash
+}
+
+func makemap(t *maptype, hint int64) *hmap {
+ if sz := unsafe.Sizeof(hmap{}); sz > 48 || sz != uintptr(t.hmap.size) {
+ gothrow("bad hmap size")
+ }
+
+ if hint < 0 || int64(int32(hint)) != hint {
+ panic("makemap: size out of range")
+ // TODO: make hint an int, then none of this nonsense
+ }
+
+ if !ismapkey(t.key) {
+ gothrow("runtime.makemap: unsupported map key type")
+ }
+
+ // check compiler's and reflect's math
+ if t.key.size > maxKeySize && (!t.indirectkey || t.keysize != uint8(ptrSize)) ||
+ t.key.size <= maxKeySize && (t.indirectkey || t.keysize != uint8(t.key.size)) {
+ gothrow("key size wrong")
+ }
+ if t.elem.size > maxValueSize && (!t.indirectvalue || t.valuesize != uint8(ptrSize)) ||
+ t.elem.size <= maxValueSize && (t.indirectvalue || t.valuesize != uint8(t.elem.size)) {
+ gothrow("value size wrong")
+ }
+
+ // invariants we depend on. We should probably check these at compile time
+ // somewhere, but for now we'll do it here.
+ if t.key.align > bucketCnt {
+ gothrow("key align too big")
+ }
+ if t.elem.align > bucketCnt {
+ gothrow("value align too big")
+ }
+ if uintptr(t.key.size)%uintptr(t.key.align) != 0 {
+ gothrow("key size not a multiple of key align")
+ }
+ if uintptr(t.elem.size)%uintptr(t.elem.align) != 0 {
+ gothrow("value size not a multiple of value align")
+ }
+ if bucketCnt < 8 {
+ gothrow("bucketsize too small for proper alignment")
+ }
+ if dataOffset%uintptr(t.key.align) != 0 {
+ gothrow("need padding in bucket (key)")
+ }
+ if dataOffset%uintptr(t.elem.align) != 0 {
+ gothrow("need padding in bucket (value)")
+ }
+
+ // find size parameter which will hold the requested # of elements
+ B := uint8(0)
+ for ; hint > bucketCnt && float32(hint) > loadFactor*float32(uintptr(1)<<B); B++ {
+ }
+
+ // allocate initial hash table
+ // if B == 0, the buckets field is allocated lazily later (in mapassign)
+ // If hint is large zeroing this memory could take a while.
+ var buckets unsafe.Pointer
+ if B != 0 {
+ if checkgc {
+ memstats.next_gc = memstats.heap_alloc
+ }
+ buckets = newarray(t.bucket, uintptr(1)<<B)
+ }
+
+ // initialize Hmap
+ if checkgc {
+ memstats.next_gc = memstats.heap_alloc
+ }
+ h := (*hmap)(newobject(t.hmap))
+ h.count = 0
+ h.B = B
+ h.flags = 0
+ h.hash0 = fastrand1()
+ h.buckets = buckets
+ h.oldbuckets = nil
+ h.nevacuate = 0
+
+ return h
+}
+
+// mapaccess1 returns a pointer to h[key]. Never returns nil, instead
+// it will return a reference to the zero object for the value type if
+// the key is not in the map.
+// NOTE: The returned pointer may keep the whole map live, so don't
+// hold onto it for very long.
+func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
+ if raceenabled && h != nil {
+ callerpc := getcallerpc(unsafe.Pointer(&t))
+ pc := funcPC(mapaccess1)
+ racereadpc(unsafe.Pointer(h), callerpc, pc)
+ raceReadObjectPC(t.key, key, callerpc, pc)
+ }
+ if h == nil || h.count == 0 {
+ return unsafe.Pointer(t.elem.zero)
+ }
+ alg := goalg(t.key.alg)
+ hash := alg.hash(key, uintptr(t.key.size), uintptr(h.hash0))
+ m := uintptr(1)<<h.B - 1
+ b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
+ if c := h.oldbuckets; c != nil {
+ oldb := (*bmap)(add(c, (hash&(m>>1))*uintptr(t.bucketsize)))
+ if !evacuated(oldb) {
+ b = oldb
+ }
+ }
+ top := uint8(hash >> (ptrSize*8 - 8))
+ if top < minTopHash {
+ top += minTopHash
+ }
+ for {
+ for i := uintptr(0); i < bucketCnt; i++ {
+ if b.tophash[i] != top {
+ continue
+ }
+ k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
+ if t.indirectkey {
+ k = *((*unsafe.Pointer)(k))
+ }
+ if alg.equal(key, k, uintptr(t.key.size)) {
+ v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
+ if t.indirectvalue {
+ v = *((*unsafe.Pointer)(v))
+ }
+ return v
+ }
+ }
+ b = b.overflow
+ if b == nil {
+ return unsafe.Pointer(t.elem.zero)
+ }
+ }
+}
+
+func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool) {
+ if raceenabled && h != nil {
+ callerpc := getcallerpc(unsafe.Pointer(&t))
+ pc := funcPC(mapaccess2)
+ racereadpc(unsafe.Pointer(h), callerpc, pc)
+ raceReadObjectPC(t.key, key, callerpc, pc)
+ }
+ if h == nil || h.count == 0 {
+ return unsafe.Pointer(t.elem.zero), false
+ }
+ alg := goalg(t.key.alg)
+ hash := alg.hash(key, uintptr(t.key.size), uintptr(h.hash0))
+ m := uintptr(1)<<h.B - 1
+ b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + (hash&m)*uintptr(t.bucketsize)))
+ if c := h.oldbuckets; c != nil {
+ oldb := (*bmap)(unsafe.Pointer(uintptr(c) + (hash&(m>>1))*uintptr(t.bucketsize)))
+ if !evacuated(oldb) {
+ b = oldb
+ }
+ }
+ top := uint8(hash >> (ptrSize*8 - 8))
+ if top < minTopHash {
+ top += minTopHash
+ }
+ for {
+ for i := uintptr(0); i < bucketCnt; i++ {
+ if b.tophash[i] != top {
+ continue
+ }
+ k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
+ if t.indirectkey {
+ k = *((*unsafe.Pointer)(k))
+ }
+ if alg.equal(key, k, uintptr(t.key.size)) {
+ v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
+ if t.indirectvalue {
+ v = *((*unsafe.Pointer)(v))
+ }
+ return v, true
+ }
+ }
+ b = b.overflow
+ if b == nil {
+ return unsafe.Pointer(t.elem.zero), false
+ }
+ }
+}
+
+// returns both key and value. Used by map iterator
+func mapaccessK(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, unsafe.Pointer) {
+ if h == nil || h.count == 0 {
+ return nil, nil
+ }
+ alg := goalg(t.key.alg)
+ hash := alg.hash(key, uintptr(t.key.size), uintptr(h.hash0))
+ m := uintptr(1)<<h.B - 1
+ b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + (hash&m)*uintptr(t.bucketsize)))
+ if c := h.oldbuckets; c != nil {
+ oldb := (*bmap)(unsafe.Pointer(uintptr(c) + (hash&(m>>1))*uintptr(t.bucketsize)))
+ if !evacuated(oldb) {
+ b = oldb
+ }
+ }
+ top := uint8(hash >> (ptrSize*8 - 8))
+ if top < minTopHash {
+ top += minTopHash
+ }
+ for {
+ for i := uintptr(0); i < bucketCnt; i++ {
+ if b.tophash[i] != top {
+ continue
+ }
+ k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
+ if t.indirectkey {
+ k = *((*unsafe.Pointer)(k))
+ }
+ if alg.equal(key, k, uintptr(t.key.size)) {
+ v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
+ if t.indirectvalue {
+ v = *((*unsafe.Pointer)(v))
+ }
+ return k, v
+ }
+ }
+ b = b.overflow
+ if b == nil {
+ return nil, nil
+ }
+ }
+}
+
+func mapassign1(t *maptype, h *hmap, key unsafe.Pointer, val unsafe.Pointer) {
+ if h == nil {
+ panic("assignment to entry in nil map")
+ }
+ if raceenabled {
+ callerpc := getcallerpc(unsafe.Pointer(&t))
+ pc := funcPC(mapassign1)
+ racewritepc(unsafe.Pointer(h), callerpc, pc)
+ raceReadObjectPC(t.key, key, callerpc, pc)
+ raceReadObjectPC(t.elem, val, callerpc, pc)
+ }
+
+ alg := goalg(t.key.alg)
+ hash := alg.hash(key, uintptr(t.key.size), uintptr(h.hash0))
+
+ if h.buckets == nil {
+ if checkgc {
+ memstats.next_gc = memstats.heap_alloc
+ }
+ h.buckets = newarray(t.bucket, 1)
+ }
+
+again:
+ bucket := hash & (uintptr(1)<<h.B - 1)
+ if h.oldbuckets != nil {
+ growWork(t, h, bucket)
+ }
+ b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize)))
+ top := uint8(hash >> (ptrSize*8 - 8))
+ if top < minTopHash {
+ top += minTopHash
+ }
+
+ var inserti *uint8
+ var insertk unsafe.Pointer
+ var insertv unsafe.Pointer
+ for {
+ for i := uintptr(0); i < bucketCnt; i++ {
+ if b.tophash[i] != top {
+ if b.tophash[i] == empty && inserti == nil {
+ inserti = &b.tophash[i]
+ insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
+ insertv = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
+ }
+ continue
+ }
+ k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
+ k2 := k
+ if t.indirectkey {
+ k2 = *((*unsafe.Pointer)(k2))
+ }
+ if !alg.equal(key, k2, uintptr(t.key.size)) {
+ continue
+ }
+ // already have a mapping for key. Update it.
+ memmove(k2, key, uintptr(t.key.size))
+ v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
+ v2 := v
+ if t.indirectvalue {
+ v2 = *((*unsafe.Pointer)(v2))
+ }
+ memmove(v2, val, uintptr(t.elem.size))
+ return
+ }
+ if b.overflow == nil {
+ break
+ }
+ b = b.overflow
+ }
+
+ // did not find mapping for key. Allocate new cell & add entry.
+ if float32(h.count) >= loadFactor*float32((uintptr(1)<<h.B)) && h.count >= bucketCnt {
+ hashGrow(t, h)
+ goto again // Growing the table invalidates everything, so try again
+ }
+
+ if inserti == nil {
+ // all current buckets are full, allocate a new one.
+ if checkgc {
+ memstats.next_gc = memstats.heap_alloc
+ }
+ newb := (*bmap)(newobject(t.bucket))
+ b.overflow = newb
+ inserti = &newb.tophash[0]
+ insertk = add(unsafe.Pointer(newb), dataOffset)
+ insertv = add(insertk, bucketCnt*uintptr(t.keysize))
+ }
+
+ // store new key/value at insert position
+ if t.indirectkey {
+ if checkgc {
+ memstats.next_gc = memstats.heap_alloc
+ }
+ kmem := newobject(t.key)
+ *(*unsafe.Pointer)(insertk) = kmem
+ insertk = kmem
+ }
+ if t.indirectvalue {
+ if checkgc {
+ memstats.next_gc = memstats.heap_alloc
+ }
+ vmem := newobject(t.elem)
+ *(*unsafe.Pointer)(insertv) = vmem
+ insertv = vmem
+ }
+ memmove(insertk, key, uintptr(t.key.size))
+ memmove(insertv, val, uintptr(t.elem.size))
+ *inserti = top
+ h.count++
+}
+
+func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {
+ if raceenabled && h != nil {
+ callerpc := getcallerpc(unsafe.Pointer(&t))
+ pc := funcPC(mapdelete)
+ racewritepc(unsafe.Pointer(h), callerpc, pc)
+ raceReadObjectPC(t.key, key, callerpc, pc)
+ }
+ if h == nil || h.count == 0 {
+ return
+ }
+ alg := goalg(t.key.alg)
+ hash := alg.hash(key, uintptr(t.key.size), uintptr(h.hash0))
+ bucket := hash & (uintptr(1)<<h.B - 1)
+ if h.oldbuckets != nil {
+ growWork(t, h, bucket)
+ }
+ b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize)))
+ top := uint8(hash >> (ptrSize*8 - 8))
+ if top < minTopHash {
+ top += minTopHash
+ }
+ for {
+ for i := uintptr(0); i < bucketCnt; i++ {
+ if b.tophash[i] != top {
+ continue
+ }
+ k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
+ k2 := k
+ if t.indirectkey {
+ k2 = *((*unsafe.Pointer)(k2))
+ }
+ if !alg.equal(key, k2, uintptr(t.key.size)) {
+ continue
+ }
+ memclr(k, uintptr(t.keysize))
+ v := unsafe.Pointer(uintptr(unsafe.Pointer(b)) + dataOffset + bucketCnt*uintptr(t.keysize) + i*uintptr(t.valuesize))
+ memclr(v, uintptr(t.valuesize))
+ b.tophash[i] = empty
+ h.count--
+ return
+ }
+ b = b.overflow
+ if b == nil {
+ return
+ }
+ }
+}
+
+func mapiterinit(t *maptype, h *hmap, it *hiter) {
+ // Clear pointer fields so garbage collector does not complain.
+ it.key = nil
+ it.value = nil
+ it.t = nil
+ it.h = nil
+ it.buckets = nil
+ it.bptr = nil
+
+ if raceenabled && h != nil {
+ callerpc := getcallerpc(unsafe.Pointer(&t))
+ racereadpc(unsafe.Pointer(h), callerpc, funcPC(mapiterinit))
+ }
+
+ if h == nil || h.count == 0 {
+ it.key = nil
+ it.value = nil
+ return
+ }
+
+ if unsafe.Sizeof(hiter{})/ptrSize != 10 {
+ gothrow("hash_iter size incorrect") // see ../../cmd/gc/reflect.c
+ }
+ it.t = t
+ it.h = h
+
+ // grab snapshot of bucket state
+ it.B = h.B
+ it.buckets = h.buckets
+
+ // decide where to start
+ r := uintptr(fastrand1())
+ if h.B > 31-bucketCntBits {
+ r += uintptr(fastrand1()) << 31
+ }
+ it.startBucket = r & (uintptr(1)<<h.B - 1)
+ it.offset = uint8(r >> h.B & (bucketCnt - 1))
+
+ // iterator state
+ it.bucket = it.startBucket
+ it.wrapped = false
+ it.bptr = nil
+
+ // Remember we have an iterator.
+ // Can run concurrently with another hash_iter_init().
+ for {
+ old := h.flags
+ if old == old|iterator|oldIterator {
+ break
+ }
+ if cas(&h.flags, old, old|iterator|oldIterator) {
+ break
+ }
+ }
+
+ mapiternext(it)
+}
+
+func mapiternext(it *hiter) {
+ h := it.h
+ if raceenabled {
+ callerpc := getcallerpc(unsafe.Pointer(&it))
+ racereadpc(unsafe.Pointer(h), callerpc, funcPC(mapiternext))
+ }
+ t := it.t
+ bucket := it.bucket
+ b := it.bptr
+ i := it.i
+ checkBucket := it.checkBucket
+ alg := goalg(t.key.alg)
+
+next:
+ if b == nil {
+ if bucket == it.startBucket && it.wrapped {
+ // end of iteration
+ it.key = nil
+ it.value = nil
+ return
+ }
+ if h.oldbuckets != nil && it.B == h.B {
+ // Iterator was started in the middle of a grow, and the grow isn't done yet.
+ // If the bucket we're looking at hasn't been filled in yet (i.e. the old
+ // bucket hasn't been evacuated) then we need to iterate through the old
+ // bucket and only return the ones that will be migrated to this bucket.
+ oldbucket := bucket & (uintptr(1)<<(it.B-1) - 1)
+ b = (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
+ if !evacuated(b) {
+ checkBucket = bucket
+ } else {
+ b = (*bmap)(add(it.buckets, bucket*uintptr(t.bucketsize)))
+ checkBucket = noCheck
+ }
+ } else {
+ b = (*bmap)(add(it.buckets, bucket*uintptr(t.bucketsize)))
+ checkBucket = noCheck
+ }
+ bucket++
+ if bucket == uintptr(1)<<it.B {
+ bucket = 0
+ it.wrapped = true
+ }
+ i = 0
+ }
+ for ; i < bucketCnt; i++ {
+ offi := (i + it.offset) & (bucketCnt - 1)
+ k := add(unsafe.Pointer(b), dataOffset+uintptr(offi)*uintptr(t.keysize))
+ v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+uintptr(offi)*uintptr(t.valuesize))
+ if b.tophash[offi] != empty && b.tophash[offi] != evacuatedEmpty {
+ if checkBucket != noCheck {
+ // Special case: iterator was started during a grow and the
+ // grow is not done yet. We're working on a bucket whose
+ // oldbucket has not been evacuated yet. Or at least, it wasn't
+ // evacuated when we started the bucket. So we're iterating
+ // through the oldbucket, skipping any keys that will go
+ // to the other new bucket (each oldbucket expands to two
+ // buckets during a grow).
+ k2 := k
+ if t.indirectkey {
+ k2 = *((*unsafe.Pointer)(k2))
+ }
+ if alg.equal(k2, k2, uintptr(t.key.size)) {
+ // If the item in the oldbucket is not destined for
+ // the current new bucket in the iteration, skip it.
+ hash := alg.hash(k2, uintptr(t.key.size), uintptr(h.hash0))
+ if hash&(uintptr(1)<<it.B-1) != checkBucket {
+ continue
+ }
+ } else {
+ // Hash isn't repeatable if k != k (NaNs). We need a
+ // repeatable and randomish choice of which direction
+ // to send NaNs during evacuation. We'll use the low
+ // bit of tophash to decide which way NaNs go.
+ // NOTE: this case is why we need two evacuate tophash
+ // values, evacuatedX and evacuatedY, that differ in
+ // their low bit.
+ if checkBucket>>(it.B-1) != uintptr(b.tophash[offi]&1) {
+ continue
+ }
+ }
+ }
+ if b.tophash[offi] != evacuatedX && b.tophash[offi] != evacuatedY {
+ // this is the golden data, we can return it.
+ if t.indirectkey {
+ k = *((*unsafe.Pointer)(k))
+ }
+ it.key = k
+ if t.indirectvalue {
+ v = *((*unsafe.Pointer)(v))
+ }
+ it.value = v
+ } else {
+ // The hash table has grown since the iterator was started.
+ // The golden data for this key is now somewhere else.
+ k2 := k
+ if t.indirectkey {
+ k2 = *((*unsafe.Pointer)(k2))
+ }
+ if alg.equal(k2, k2, uintptr(t.key.size)) {
+ // Check the current hash table for the data.
+ // This code handles the case where the key
+ // has been deleted, updated, or deleted and reinserted.
+ // NOTE: we need to regrab the key as it has potentially been
+ // updated to an equal() but not identical key (e.g. +0.0 vs -0.0).
+ rk, rv := mapaccessK(t, h, k2)
+ if rk == nil {
+ continue // key has been deleted
+ }
+ it.key = rk
+ it.value = rv
+ } else {
+ // if key!=key then the entry can't be deleted or
+ // updated, so we can just return it. That's lucky for
+ // us because when key!=key we can't look it up
+ // successfully in the current table.
+ it.key = k2
+ if t.indirectvalue {
+ v = *((*unsafe.Pointer)(v))
+ }
+ it.value = v
+ }
+ }
+ it.bucket = bucket
+ it.bptr = b
+ it.i = i + 1
+ it.checkBucket = checkBucket
+ return
+ }
+ }
+ b = b.overflow
+ i = 0
+ goto next
+}
+
+func hashGrow(t *maptype, h *hmap) {
+ if h.oldbuckets != nil {
+ gothrow("evacuation not done in time")
+ }
+ oldbuckets := h.buckets
+ if checkgc {
+ memstats.next_gc = memstats.heap_alloc
+ }
+ newbuckets := newarray(t.bucket, uintptr(1)<<(h.B+1))
+ flags := h.flags &^ (iterator | oldIterator)
+ if h.flags&iterator != 0 {
+ flags |= oldIterator
+ }
+ // commit the grow (atomic wrt gc)
+ h.B++
+ h.flags = flags
+ h.oldbuckets = oldbuckets
+ h.buckets = newbuckets
+ h.nevacuate = 0
+
+ // the actual copying of the hash table data is done incrementally
+ // by growWork() and evacuate().
+}
+
+func growWork(t *maptype, h *hmap, bucket uintptr) {
+ noldbuckets := uintptr(1) << (h.B - 1)
+
+ // make sure we evacuate the oldbucket corresponding
+ // to the bucket we're about to use
+ evacuate(t, h, bucket&(noldbuckets-1))
+
+ // evacuate one more oldbucket to make progress on growing
+ if h.oldbuckets != nil {
+ evacuate(t, h, h.nevacuate)
+ }
+}
+
+func evacuate(t *maptype, h *hmap, oldbucket uintptr) {
+ b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
+ newbit := uintptr(1) << (h.B - 1)
+ alg := goalg(t.key.alg)
+ if !evacuated(b) {
+ // TODO: reuse overflow buckets instead of using new ones, if there
+ // is no iterator using the old buckets. (If !oldIterator.)
+
+ x := (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize)))
+ y := (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize)))
+ xi := 0
+ yi := 0
+ xk := add(unsafe.Pointer(x), dataOffset)
+ yk := add(unsafe.Pointer(y), dataOffset)
+ xv := add(xk, bucketCnt*uintptr(t.keysize))
+ yv := add(yk, bucketCnt*uintptr(t.keysize))
+ for ; b != nil; b = b.overflow {
+ k := add(unsafe.Pointer(b), dataOffset)
+ v := add(k, bucketCnt*uintptr(t.keysize))
+ for i := 0; i < bucketCnt; i, k, v = i+1, add(k, uintptr(t.keysize)), add(v, uintptr(t.valuesize)) {
+ top := b.tophash[i]
+ if top == empty {
+ b.tophash[i] = evacuatedEmpty
+ continue
+ }
+ if top < minTopHash {
+ gothrow("bad map state")
+ }
+ k2 := k
+ if t.indirectkey {
+ k2 = *((*unsafe.Pointer)(k2))
+ }
+ // Compute hash to make our evacuation decision (whether we need
+ // to send this key/value to bucket x or bucket y).
+ hash := alg.hash(k2, uintptr(t.key.size), uintptr(h.hash0))
+ if h.flags&iterator != 0 {
+ if !alg.equal(k2, k2, uintptr(t.key.size)) {
+ // If key != key (NaNs), then the hash could be (and probably
+ // will be) entirely different from the old hash. Moreover,
+ // it isn't reproducible. Reproducibility is required in the
+ // presence of iterators, as our evacuation decision must
+ // match whatever decision the iterator made.
+ // Fortunately, we have the freedom to send these keys either
+ // way. Also, tophash is meaningless for these kinds of keys.
+ // We let the low bit of tophash drive the evacuation decision.
+ // We recompute a new random tophash for the next level so
+ // these keys will get evenly distributed across all buckets
+ // after multiple grows.
+ if (top & 1) != 0 {
+ hash |= newbit
+ } else {
+ hash &^= newbit
+ }
+ top = uint8(hash >> (ptrSize*8 - 8))
+ if top < minTopHash {
+ top += minTopHash
+ }
+ }
+ }
+ if (hash & newbit) == 0 {
+ b.tophash[i] = evacuatedX
+ if xi == bucketCnt {
+ if checkgc {
+ memstats.next_gc = memstats.heap_alloc
+ }
+ newx := (*bmap)(newobject(t.bucket))
+ x.overflow = newx
+ x = newx
+ xi = 0
+ xk = add(unsafe.Pointer(x), dataOffset)
+ xv = add(xk, bucketCnt*uintptr(t.keysize))
+ }
+ x.tophash[xi] = top
+ if t.indirectkey {
+ *(*unsafe.Pointer)(xk) = k2 // copy pointer
+ } else {
+ memmove(xk, k, uintptr(t.key.size)) // copy value
+ }
+ if t.indirectvalue {
+ *(*unsafe.Pointer)(xv) = *(*unsafe.Pointer)(v)
+ } else {
+ memmove(xv, v, uintptr(t.elem.size))
+ }
+ xi++
+ xk = add(xk, uintptr(t.keysize))
+ xv = add(xv, uintptr(t.valuesize))
+ } else {
+ b.tophash[i] = evacuatedY
+ if yi == bucketCnt {
+ if checkgc {
+ memstats.next_gc = memstats.heap_alloc
+ }
+ newy := (*bmap)(newobject(t.bucket))
+ y.overflow = newy
+ y = newy
+ yi = 0
+ yk = add(unsafe.Pointer(y), dataOffset)
+ yv = add(yk, bucketCnt*uintptr(t.keysize))
+ }
+ y.tophash[yi] = top
+ if t.indirectkey {
+ *(*unsafe.Pointer)(yk) = k2
+ } else {
+ memmove(yk, k, uintptr(t.key.size))
+ }
+ if t.indirectvalue {
+ *(*unsafe.Pointer)(yv) = *(*unsafe.Pointer)(v)
+ } else {
+ memmove(yv, v, uintptr(t.elem.size))
+ }
+ yi++
+ yk = add(yk, uintptr(t.keysize))
+ yv = add(yv, uintptr(t.valuesize))
+ }
+ }
+ }
+ // Unlink the overflow buckets & clear key/value to help GC.
+ if h.flags&oldIterator == 0 {
+ b = (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
+ b.overflow = nil
+ memclr(add(unsafe.Pointer(b), dataOffset), uintptr(t.bucketsize)-dataOffset)
+ }
+ }
+
+ // Advance evacuation mark
+ if oldbucket == h.nevacuate {
+ h.nevacuate = oldbucket + 1
+ if oldbucket+1 == newbit { // newbit == # of oldbuckets
+ // Growing is all done. Free old main bucket array.
+ h.oldbuckets = nil
+ }
+ }
+}
+
+func ismapkey(t *_type) bool {
+ return goalg(t.alg).hash != nil
+}
+
+// Reflect stubs. Called from ../reflect/asm_*.s
+
+func reflect_makemap(t *maptype) *hmap {
+ return makemap(t, 0)
+}
+
+func reflect_mapaccess(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
+ val, ok := mapaccess2(t, h, key)
+ if !ok {
+ // reflect wants nil for a missing element
+ val = nil
+ }
+ return val
+}
+
+func reflect_mapassign(t *maptype, h *hmap, key unsafe.Pointer, val unsafe.Pointer) {
+ mapassign1(t, h, key, val)
+}
+
+func reflect_mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {
+ mapdelete(t, h, key)
+}
+
+func reflect_mapiterinit(t *maptype, h *hmap) *hiter {
+ it := new(hiter)
+ mapiterinit(t, h, it)
+ return it
+}
+
+func reflect_mapiternext(it *hiter) {
+ mapiternext(it)
+}
+
+func reflect_mapiterkey(it *hiter) unsafe.Pointer {
+ return it.key
+}
+
+func reflect_maplen(h *hmap) int {
+ if h == nil {
+ return 0
+ }
+ if raceenabled {
+ callerpc := getcallerpc(unsafe.Pointer(&h))
+ racereadpc(unsafe.Pointer(h), callerpc, funcPC(reflect_maplen))
+ }
+ return h.count
+}
+
+func reflect_ismapkey(t *_type) bool {
+ return ismapkey(t)
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-05-21 00:33:56 +0000