2015-05-29 François Dumont fdumont@gcc.gnu.org>

[official-gcc.git] / libgo / go / runtime / hashmap.go

// 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
        // 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.
        // Followed by an overflow pointer.
}

// 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 (b *bmap) overflow(t *maptype) *bmap {
        return *(**bmap)(add(unsafe.Pointer(b), uintptr(t.bucketsize)-regSize))
}
func (b *bmap) setoverflow(t *maptype, ovf *bmap) {
        *(**bmap)(add(unsafe.Pointer(b), uintptr(t.bucketsize)-regSize)) = ovf
}

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(t)
                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(t)
                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(t)
                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
                }
                ovf := b.overflow(t)
                if ovf == nil {
                        break
                }
                b = ovf
        }

        // 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.setoverflow(t, 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(t)
                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(t)
        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(t) {
                        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.setoverflow(t, 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.setoverflow(t, 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)))
                        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)
}