Lines Matching full:bucket
10 // into an array of buckets. Each bucket contains up to
12 // used to select a bucket. Each bucket contains a few
14 // within a single bucket.
16 // If more than 8 keys hash to a bucket, we chain on
21 // copied from the old bucket array to the new bucket array.
24 // return the keys in walk order (bucket #, then overflow
25 // chain order, then bucket index). To maintain iteration
26 // semantics, we never move keys within their bucket (if
29 // old table and must check the new table if the bucket
48 // %overflow = percentage of buckets which have an overflow bucket
63 // Maximum number of key/value pairs a bucket can hold.
67 // Maximum average load of a bucket that triggers growth.
86 // Each bucket (including its overflow buckets, if any) will have either all or none of its
90 evacuatedEmpty = 1 // cell is empty, bucket is evacuated.
101 // sentinel bucket ID for iterator checks
116 oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing
119 // If both key and value do not contain pointers and are inline, then we mark bucket
131 // A bucket for a Go map.
134 // for each key in this bucket. If tophash[0] < minTopHash,
135 // tophash[0] is a bucket evacuation state instead.
152 buckets unsafe.Pointer // bucket ptr at hash_iter initialization time
153 bptr *bmap // current bucket
155 startBucket uintptr // bucket iteration started at
156 offset uint8 // intra-bucket offset to start from during iteration (should be big enough to hold bucketCnt-1)
157 wrapped bool // already wrapped around from end of bucket array to beginning
160 bucket uintptr
201 if t.bucket.kind&kindNoPointers != 0 {
218 // If the compiler has determined that the map or the first bucket
219 // can be created on the stack, h and/or bucket may be non-nil.
221 // If bucket != nil, bucket can be used as the first bucket.
222 func makemap(t *maptype, hint int64, h *hmap, bucket unsafe.Pointer) *hmap {
265 throw("need padding in bucket (key)")
268 throw("need padding in bucket (value)")
279 buckets := bucket
281 buckets = newarray(t.bucket, 1<<B)
507 h.buckets = newarray(t.bucket, 1)
511 bucket := hash & (uintptr(1)<<h.B - 1)
513 growWork(t, h, bucket)
515 b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize)))
566 newb := (*bmap)(newobject(t.bucket))
618 bucket := hash & (uintptr(1)<<h.B - 1)
620 growWork(t, h, bucket)
622 b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize)))
696 // grab snapshot of bucket state
699 if t.bucket.kind&kindNoPointers != 0 {
717 it.bucket = it.startBucket
740 bucket := it.bucket
748 if bucket == it.startBucket && it.wrapped {
756 // If the bucket we're looking at hasn't been filled in yet (i.e. the old
757 // bucket hasn't been evacuated) then we need to iterate through the old
758 // bucket and only return the ones that will be migrated to this bucket.
759 oldbucket := bucket & it.h.oldbucketmask()
762 checkBucket = bucket
764 b = (*bmap)(add(it.buckets, bucket*uintptr(t.bucketsize)))
768 b = (*bmap)(add(it.buckets, bucket*uintptr(t.bucketsize)))
771 bucket++
772 if bucket == uintptr(1)<<it.B {
773 bucket = 0
785 // and the grow is not done yet. We're working on a bucket whose
787 // evacuated when we started the bucket. So we're iterating
789 // to the other new bucket (each oldbucket expands to two
797 // the current new bucket in the iteration, skip it.
856 it.bucket = bucket
880 newbuckets := newarray(t.bucket, 1<<(h.B+bigger))
950 func growWork(t *maptype, h *hmap, bucket uintptr) {
952 // to the bucket we're about to use
953 evacuate(t, h, bucket&h.oldbucketmask())
1006 // to send this key/value to bucket x or bucket y).
1037 newx := (*bmap)(newobject(t.bucket))
1061 newy := (*bmap)(newobject(t.bucket))
1090 if t.bucket.kind&kindNoPointers == 0 {
1102 // Growing is all done. Free old main bucket array.
