Source file src/runtime/map.go

Documentation: runtime

     1  // Copyright 2014 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package runtime
     6  
     7  // This file contains the implementation of Go's map type.
     8  //
     9  // A map is just a hash table. The data is arranged
    10  // into an array of buckets. Each bucket contains up to
    11  // 8 key/value pairs. The low-order bits of the hash are
    12  // used to select a bucket. Each bucket contains a few
    13  // high-order bits of each hash to distinguish the entries
    14  // within a single bucket.
    15  //
    16  // If more than 8 keys hash to a bucket, we chain on
    17  // extra buckets.
    18  //
    19  // When the hashtable grows, we allocate a new array
    20  // of buckets twice as big. Buckets are incrementally
    21  // copied from the old bucket array to the new bucket array.
    22  //
    23  // Map iterators walk through the array of buckets and
    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
    27  // we did, keys might be returned 0 or 2 times).  When
    28  // growing the table, iterators remain iterating through the
    29  // old table and must check the new table if the bucket
    30  // they are iterating through has been moved ("evacuated")
    31  // to the new table.
    32  
    33  // Picking loadFactor: too large and we have lots of overflow
    34  // buckets, too small and we waste a lot of space. I wrote
    35  // a simple program to check some stats for different loads:
    36  // (64-bit, 8 byte keys and values)
    37  //  loadFactor    %overflow  bytes/entry     hitprobe    missprobe
    38  //        4.00         2.13        20.77         3.00         4.00
    39  //        4.50         4.05        17.30         3.25         4.50
    40  //        5.00         6.85        14.77         3.50         5.00
    41  //        5.50        10.55        12.94         3.75         5.50
    42  //        6.00        15.27        11.67         4.00         6.00
    43  //        6.50        20.90        10.79         4.25         6.50
    44  //        7.00        27.14        10.15         4.50         7.00
    45  //        7.50        34.03         9.73         4.75         7.50
    46  //        8.00        41.10         9.40         5.00         8.00
    47  //
    48  // %overflow   = percentage of buckets which have an overflow bucket
    49  // bytes/entry = overhead bytes used per key/value pair
    50  // hitprobe    = # of entries to check when looking up a present key
    51  // missprobe   = # of entries to check when looking up an absent key
    52  //
    53  // Keep in mind this data is for maximally loaded tables, i.e. just
    54  // before the table grows. Typical tables will be somewhat less loaded.
    55  
    56  import (
    57  	"runtime/internal/atomic"
    58  	"runtime/internal/sys"
    59  	"unsafe"
    60  )
    61  
    62  const (
    63  	// Maximum number of key/value pairs a bucket can hold.
    64  	bucketCntBits = 3
    65  	bucketCnt     = 1 << bucketCntBits
    66  
    67  	// Maximum average load of a bucket that triggers growth is 6.5.
    68  	// Represent as loadFactorNum/loadFactDen, to allow integer math.
    69  	loadFactorNum = 13
    70  	loadFactorDen = 2
    71  
    72  	// Maximum key or value size to keep inline (instead of mallocing per element).
    73  	// Must fit in a uint8.
    74  	// Fast versions cannot handle big values - the cutoff size for
    75  	// fast versions in cmd/compile/internal/gc/walk.go must be at most this value.
    76  	maxKeySize   = 128
    77  	maxValueSize = 128
    78  
    79  	// data offset should be the size of the bmap struct, but needs to be
    80  	// aligned correctly. For amd64p32 this means 64-bit alignment
    81  	// even though pointers are 32 bit.
    82  	dataOffset = unsafe.Offsetof(struct {
    83  		b bmap
    84  		v int64
    85  	}{}.v)
    86  
    87  	// Possible tophash values. We reserve a few possibilities for special marks.
    88  	// Each bucket (including its overflow buckets, if any) will have either all or none of its
    89  	// entries in the evacuated* states (except during the evacuate() method, which only happens
    90  	// during map writes and thus no one else can observe the map during that time).
    91  	empty          = 0 // cell is empty
    92  	evacuatedEmpty = 1 // cell is empty, bucket is evacuated.
    93  	evacuatedX     = 2 // key/value is valid.  Entry has been evacuated to first half of larger table.
    94  	evacuatedY     = 3 // same as above, but evacuated to second half of larger table.
    95  	minTopHash     = 4 // minimum tophash for a normal filled cell.
    96  
    97  	// flags
    98  	iterator     = 1 // there may be an iterator using buckets
    99  	oldIterator  = 2 // there may be an iterator using oldbuckets
   100  	hashWriting  = 4 // a goroutine is writing to the map
   101  	sameSizeGrow = 8 // the current map growth is to a new map of the same size
   102  
   103  	// sentinel bucket ID for iterator checks
   104  	noCheck = 1<<(8*sys.PtrSize) - 1
   105  )
   106  
   107  // A header for a Go map.
   108  type hmap struct {
   109  	// Note: the format of the hmap is also encoded in cmd/compile/internal/gc/reflect.go.
   110  	// Make sure this stays in sync with the compiler's definition.
   111  	count     int // # live cells == size of map.  Must be first (used by len() builtin)
   112  	flags     uint8
   113  	B         uint8  // log_2 of # of buckets (can hold up to loadFactor * 2^B items)
   114  	noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details
   115  	hash0     uint32 // hash seed
   116  
   117  	buckets    unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.
   118  	oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing
   119  	nevacuate  uintptr        // progress counter for evacuation (buckets less than this have been evacuated)
   120  
   121  	extra *mapextra // optional fields
   122  }
   123  
   124  // mapextra holds fields that are not present on all maps.
   125  type mapextra struct {
   126  	// If both key and value do not contain pointers and are inline, then we mark bucket
   127  	// type as containing no pointers. This avoids scanning such maps.
   128  	// However, bmap.overflow is a pointer. In order to keep overflow buckets
   129  	// alive, we store pointers to all overflow buckets in hmap.extra.overflow and hmap.extra.oldoverflow.
   130  	// overflow and oldoverflow are only used if key and value do not contain pointers.
   131  	// overflow contains overflow buckets for hmap.buckets.
   132  	// oldoverflow contains overflow buckets for hmap.oldbuckets.
   133  	// The indirection allows to store a pointer to the slice in hiter.
   134  	overflow    *[]*bmap
   135  	oldoverflow *[]*bmap
   136  
   137  	// nextOverflow holds a pointer to a free overflow bucket.
   138  	nextOverflow *bmap
   139  }
   140  
   141  // A bucket for a Go map.
   142  type bmap struct {
   143  	// tophash generally contains the top byte of the hash value
   144  	// for each key in this bucket. If tophash[0] < minTopHash,
   145  	// tophash[0] is a bucket evacuation state instead.
   146  	tophash [bucketCnt]uint8
   147  	// Followed by bucketCnt keys and then bucketCnt values.
   148  	// NOTE: packing all the keys together and then all the values together makes the
   149  	// code a bit more complicated than alternating key/value/key/value/... but it allows
   150  	// us to eliminate padding which would be needed for, e.g., map[int64]int8.
   151  	// Followed by an overflow pointer.
   152  }
   153  
   154  // A hash iteration structure.
   155  // If you modify hiter, also change cmd/compile/internal/gc/reflect.go to indicate
   156  // the layout of this structure.
   157  type hiter struct {
   158  	key         unsafe.Pointer // Must be in first position.  Write nil to indicate iteration end (see cmd/internal/gc/range.go).
   159  	value       unsafe.Pointer // Must be in second position (see cmd/internal/gc/range.go).
   160  	t           *maptype
   161  	h           *hmap
   162  	buckets     unsafe.Pointer // bucket ptr at hash_iter initialization time
   163  	bptr        *bmap          // current bucket
   164  	overflow    *[]*bmap       // keeps overflow buckets of hmap.buckets alive
   165  	oldoverflow *[]*bmap       // keeps overflow buckets of hmap.oldbuckets alive
   166  	startBucket uintptr        // bucket iteration started at
   167  	offset      uint8          // intra-bucket offset to start from during iteration (should be big enough to hold bucketCnt-1)
   168  	wrapped     bool           // already wrapped around from end of bucket array to beginning
   169  	B           uint8
   170  	i           uint8
   171  	bucket      uintptr
   172  	checkBucket uintptr
   173  }
   174  
   175  // bucketShift returns 1<<b, optimized for code generation.
   176  func bucketShift(b uint8) uintptr {
   177  	if sys.GoarchAmd64|sys.GoarchAmd64p32|sys.Goarch386 != 0 {
   178  		b &= sys.PtrSize*8 - 1 // help x86 archs remove shift overflow checks
   179  	}
   180  	return uintptr(1) << b
   181  }
   182  
   183  // bucketMask returns 1<<b - 1, optimized for code generation.
   184  func bucketMask(b uint8) uintptr {
   185  	return bucketShift(b) - 1
   186  }
   187  
   188  // tophash calculates the tophash value for hash.
   189  func tophash(hash uintptr) uint8 {
   190  	top := uint8(hash >> (sys.PtrSize*8 - 8))
   191  	if top < minTopHash {
   192  		top += minTopHash
   193  	}
   194  	return top
   195  }
   196  
   197  func evacuated(b *bmap) bool {
   198  	h := b.tophash[0]
   199  	return h > empty && h < minTopHash
   200  }
   201  
   202  func (b *bmap) overflow(t *maptype) *bmap {
   203  	return *(**bmap)(add(unsafe.Pointer(b), uintptr(t.bucketsize)-sys.PtrSize))
   204  }
   205  
   206  func (b *bmap) setoverflow(t *maptype, ovf *bmap) {
   207  	*(**bmap)(add(unsafe.Pointer(b), uintptr(t.bucketsize)-sys.PtrSize)) = ovf
   208  }
   209  
   210  func (b *bmap) keys() unsafe.Pointer {
   211  	return add(unsafe.Pointer(b), dataOffset)
   212  }
   213  
   214  // incrnoverflow increments h.noverflow.
   215  // noverflow counts the number of overflow buckets.
   216  // This is used to trigger same-size map growth.
   217  // See also tooManyOverflowBuckets.
   218  // To keep hmap small, noverflow is a uint16.
   219  // When there are few buckets, noverflow is an exact count.
   220  // When there are many buckets, noverflow is an approximate count.
   221  func (h *hmap) incrnoverflow() {
   222  	// We trigger same-size map growth if there are
   223  	// as many overflow buckets as buckets.
   224  	// We need to be able to count to 1<<h.B.
   225  	if h.B < 16 {
   226  		h.noverflow++
   227  		return
   228  	}
   229  	// Increment with probability 1/(1<<(h.B-15)).
   230  	// When we reach 1<<15 - 1, we will have approximately
   231  	// as many overflow buckets as buckets.
   232  	mask := uint32(1)<<(h.B-15) - 1
   233  	// Example: if h.B == 18, then mask == 7,
   234  	// and fastrand & 7 == 0 with probability 1/8.
   235  	if fastrand()&mask == 0 {
   236  		h.noverflow++
   237  	}
   238  }
   239  
   240  func (h *hmap) newoverflow(t *maptype, b *bmap) *bmap {
   241  	var ovf *bmap
   242  	if h.extra != nil && h.extra.nextOverflow != nil {
   243  		// We have preallocated overflow buckets available.
   244  		// See makeBucketArray for more details.
   245  		ovf = h.extra.nextOverflow
   246  		if ovf.overflow(t) == nil {
   247  			// We're not at the end of the preallocated overflow buckets. Bump the pointer.
   248  			h.extra.nextOverflow = (*bmap)(add(unsafe.Pointer(ovf), uintptr(t.bucketsize)))
   249  		} else {
   250  			// This is the last preallocated overflow bucket.
   251  			// Reset the overflow pointer on this bucket,
   252  			// which was set to a non-nil sentinel value.
   253  			ovf.setoverflow(t, nil)
   254  			h.extra.nextOverflow = nil
   255  		}
   256  	} else {
   257  		ovf = (*bmap)(newobject(t.bucket))
   258  	}
   259  	h.incrnoverflow()
   260  	if t.bucket.kind&kindNoPointers != 0 {
   261  		h.createOverflow()
   262  		*h.extra.overflow = append(*h.extra.overflow, ovf)
   263  	}
   264  	b.setoverflow(t, ovf)
   265  	return ovf
   266  }
   267  
   268  func (h *hmap) createOverflow() {
   269  	if h.extra == nil {
   270  		h.extra = new(mapextra)
   271  	}
   272  	if h.extra.overflow == nil {
   273  		h.extra.overflow = new([]*bmap)
   274  	}
   275  }
   276  
   277  func makemap64(t *maptype, hint int64, h *hmap) *hmap {
   278  	if int64(int(hint)) != hint {
   279  		hint = 0
   280  	}
   281  	return makemap(t, int(hint), h)
   282  }
   283  
   284  // makehmap_small implements Go map creation for make(map[k]v) and
   285  // make(map[k]v, hint) when hint is known to be at most bucketCnt
   286  // at compile time and the map needs to be allocated on the heap.
   287  func makemap_small() *hmap {
   288  	h := new(hmap)
   289  	h.hash0 = fastrand()
   290  	return h
   291  }
   292  
   293  // makemap implements Go map creation for make(map[k]v, hint).
   294  // If the compiler has determined that the map or the first bucket
   295  // can be created on the stack, h and/or bucket may be non-nil.
   296  // If h != nil, the map can be created directly in h.
   297  // If h.buckets != nil, bucket pointed to can be used as the first bucket.
   298  func makemap(t *maptype, hint int, h *hmap) *hmap {
   299  	if hint < 0 || hint > int(maxSliceCap(t.bucket.size)) {
   300  		hint = 0
   301  	}
   302  
   303  	// initialize Hmap
   304  	if h == nil {
   305  		h = new(hmap)
   306  	}
   307  	h.hash0 = fastrand()
   308  
   309  	// find size parameter which will hold the requested # of elements
   310  	B := uint8(0)
   311  	for overLoadFactor(hint, B) {
   312  		B++
   313  	}
   314  	h.B = B
   315  
   316  	// allocate initial hash table
   317  	// if B == 0, the buckets field is allocated lazily later (in mapassign)
   318  	// If hint is large zeroing this memory could take a while.
   319  	if h.B != 0 {
   320  		var nextOverflow *bmap
   321  		h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
   322  		if nextOverflow != nil {
   323  			h.extra = new(mapextra)
   324  			h.extra.nextOverflow = nextOverflow
   325  		}
   326  	}
   327  
   328  	return h
   329  }
   330  
   331  // makeBucketArray initializes a backing array for map buckets.
   332  // 1<<b is the minimum number of buckets to allocate.
   333  // dirtyalloc should either be nil or a bucket array previously
   334  // allocated by makeBucketArray with the same t and b parameters.
   335  // If dirtyalloc is nil a new backing array will be alloced and
   336  // otherwise dirtyalloc will be cleared and reused as backing array.
   337  func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) {
   338  	base := bucketShift(b)
   339  	nbuckets := base
   340  	// For small b, overflow buckets are unlikely.
   341  	// Avoid the overhead of the calculation.
   342  	if b >= 4 {
   343  		// Add on the estimated number of overflow buckets
   344  		// required to insert the median number of elements
   345  		// used with this value of b.
   346  		nbuckets += bucketShift(b - 4)
   347  		sz := t.bucket.size * nbuckets
   348  		up := roundupsize(sz)
   349  		if up != sz {
   350  			nbuckets = up / t.bucket.size
   351  		}
   352  	}
   353  
   354  	if dirtyalloc == nil {
   355  		buckets = newarray(t.bucket, int(nbuckets))
   356  	} else {
   357  		// dirtyalloc was previously generated by
   358  		// the above newarray(t.bucket, int(nbuckets))
   359  		// but may not be empty.
   360  		buckets = dirtyalloc
   361  		size := t.bucket.size * nbuckets
   362  		if t.bucket.kind&kindNoPointers == 0 {
   363  			memclrHasPointers(buckets, size)
   364  		} else {
   365  			memclrNoHeapPointers(buckets, size)
   366  		}
   367  	}
   368  
   369  	if base != nbuckets {
   370  		// We preallocated some overflow buckets.
   371  		// To keep the overhead of tracking these overflow buckets to a minimum,
   372  		// we use the convention that if a preallocated overflow bucket's overflow
   373  		// pointer is nil, then there are more available by bumping the pointer.
   374  		// We need a safe non-nil pointer for the last overflow bucket; just use buckets.
   375  		nextOverflow = (*bmap)(add(buckets, base*uintptr(t.bucketsize)))
   376  		last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.bucketsize)))
   377  		last.setoverflow(t, (*bmap)(buckets))
   378  	}
   379  	return buckets, nextOverflow
   380  }
   381  
   382  // mapaccess1 returns a pointer to h[key].  Never returns nil, instead
   383  // it will return a reference to the zero object for the value type if
   384  // the key is not in the map.
   385  // NOTE: The returned pointer may keep the whole map live, so don't
   386  // hold onto it for very long.
   387  func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
   388  	if raceenabled && h != nil {
   389  		callerpc := getcallerpc()
   390  		pc := funcPC(mapaccess1)
   391  		racereadpc(unsafe.Pointer(h), callerpc, pc)
   392  		raceReadObjectPC(t.key, key, callerpc, pc)
   393  	}
   394  	if msanenabled && h != nil {
   395  		msanread(key, t.key.size)
   396  	}
   397  	if h == nil || h.count == 0 {
   398  		return unsafe.Pointer(&zeroVal[0])
   399  	}
   400  	if h.flags&hashWriting != 0 {
   401  		throw("concurrent map read and map write")
   402  	}
   403  	alg := t.key.alg
   404  	hash := alg.hash(key, uintptr(h.hash0))
   405  	m := bucketMask(h.B)
   406  	b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
   407  	if c := h.oldbuckets; c != nil {
   408  		if !h.sameSizeGrow() {
   409  			// There used to be half as many buckets; mask down one more power of two.
   410  			m >>= 1
   411  		}
   412  		oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
   413  		if !evacuated(oldb) {
   414  			b = oldb
   415  		}
   416  	}
   417  	top := tophash(hash)
   418  	for ; b != nil; b = b.overflow(t) {
   419  		for i := uintptr(0); i < bucketCnt; i++ {
   420  			if b.tophash[i] != top {
   421  				continue
   422  			}
   423  			k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
   424  			if t.indirectkey {
   425  				k = *((*unsafe.Pointer)(k))
   426  			}
   427  			if alg.equal(key, k) {
   428  				v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
   429  				if t.indirectvalue {
   430  					v = *((*unsafe.Pointer)(v))
   431  				}
   432  				return v
   433  			}
   434  		}
   435  	}
   436  	return unsafe.Pointer(&zeroVal[0])
   437  }
   438  
   439  func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool) {
   440  	if raceenabled && h != nil {
   441  		callerpc := getcallerpc()
   442  		pc := funcPC(mapaccess2)
   443  		racereadpc(unsafe.Pointer(h), callerpc, pc)
   444  		raceReadObjectPC(t.key, key, callerpc, pc)
   445  	}
   446  	if msanenabled && h != nil {
   447  		msanread(key, t.key.size)
   448  	}
   449  	if h == nil || h.count == 0 {
   450  		return unsafe.Pointer(&zeroVal[0]), false
   451  	}
   452  	if h.flags&hashWriting != 0 {
   453  		throw("concurrent map read and map write")
   454  	}
   455  	alg := t.key.alg
   456  	hash := alg.hash(key, uintptr(h.hash0))
   457  	m := bucketMask(h.B)
   458  	b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + (hash&m)*uintptr(t.bucketsize)))
   459  	if c := h.oldbuckets; c != nil {
   460  		if !h.sameSizeGrow() {
   461  			// There used to be half as many buckets; mask down one more power of two.
   462  			m >>= 1
   463  		}
   464  		oldb := (*bmap)(unsafe.Pointer(uintptr(c) + (hash&m)*uintptr(t.bucketsize)))
   465  		if !evacuated(oldb) {
   466  			b = oldb
   467  		}
   468  	}
   469  	top := tophash(hash)
   470  	for ; b != nil; b = b.overflow(t) {
   471  		for i := uintptr(0); i < bucketCnt; i++ {
   472  			if b.tophash[i] != top {
   473  				continue
   474  			}
   475  			k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
   476  			if t.indirectkey {
   477  				k = *((*unsafe.Pointer)(k))
   478  			}
   479  			if alg.equal(key, k) {
   480  				v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
   481  				if t.indirectvalue {
   482  					v = *((*unsafe.Pointer)(v))
   483  				}
   484  				return v, true
   485  			}
   486  		}
   487  	}
   488  	return unsafe.Pointer(&zeroVal[0]), false
   489  }
   490  
   491  // returns both key and value. Used by map iterator
   492  func mapaccessK(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, unsafe.Pointer) {
   493  	if h == nil || h.count == 0 {
   494  		return nil, nil
   495  	}
   496  	alg := t.key.alg
   497  	hash := alg.hash(key, uintptr(h.hash0))
   498  	m := bucketMask(h.B)
   499  	b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + (hash&m)*uintptr(t.bucketsize)))
   500  	if c := h.oldbuckets; c != nil {
   501  		if !h.sameSizeGrow() {
   502  			// There used to be half as many buckets; mask down one more power of two.
   503  			m >>= 1
   504  		}
   505  		oldb := (*bmap)(unsafe.Pointer(uintptr(c) + (hash&m)*uintptr(t.bucketsize)))
   506  		if !evacuated(oldb) {
   507  			b = oldb
   508  		}
   509  	}
   510  	top := tophash(hash)
   511  	for ; b != nil; b = b.overflow(t) {
   512  		for i := uintptr(0); i < bucketCnt; i++ {
   513  			if b.tophash[i] != top {
   514  				continue
   515  			}
   516  			k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
   517  			if t.indirectkey {
   518  				k = *((*unsafe.Pointer)(k))
   519  			}
   520  			if alg.equal(key, k) {
   521  				v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
   522  				if t.indirectvalue {
   523  					v = *((*unsafe.Pointer)(v))
   524  				}
   525  				return k, v
   526  			}
   527  		}
   528  	}
   529  	return nil, nil
   530  }
   531  
   532  func mapaccess1_fat(t *maptype, h *hmap, key, zero unsafe.Pointer) unsafe.Pointer {
   533  	v := mapaccess1(t, h, key)
   534  	if v == unsafe.Pointer(&zeroVal[0]) {
   535  		return zero
   536  	}
   537  	return v
   538  }
   539  
   540  func mapaccess2_fat(t *maptype, h *hmap, key, zero unsafe.Pointer) (unsafe.Pointer, bool) {
   541  	v := mapaccess1(t, h, key)
   542  	if v == unsafe.Pointer(&zeroVal[0]) {
   543  		return zero, false
   544  	}
   545  	return v, true
   546  }
   547  
   548  // Like mapaccess, but allocates a slot for the key if it is not present in the map.
   549  func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
   550  	if h == nil {
   551  		panic(plainError("assignment to entry in nil map"))
   552  	}
   553  	if raceenabled {
   554  		callerpc := getcallerpc()
   555  		pc := funcPC(mapassign)
   556  		racewritepc(unsafe.Pointer(h), callerpc, pc)
   557  		raceReadObjectPC(t.key, key, callerpc, pc)
   558  	}
   559  	if msanenabled {
   560  		msanread(key, t.key.size)
   561  	}
   562  	if h.flags&hashWriting != 0 {
   563  		throw("concurrent map writes")
   564  	}
   565  	alg := t.key.alg
   566  	hash := alg.hash(key, uintptr(h.hash0))
   567  
   568  	// Set hashWriting after calling alg.hash, since alg.hash may panic,
   569  	// in which case we have not actually done a write.
   570  	h.flags |= hashWriting
   571  
   572  	if h.buckets == nil {
   573  		h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
   574  	}
   575  
   576  again:
   577  	bucket := hash & bucketMask(h.B)
   578  	if h.growing() {
   579  		growWork(t, h, bucket)
   580  	}
   581  	b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize)))
   582  	top := tophash(hash)
   583  
   584  	var inserti *uint8
   585  	var insertk unsafe.Pointer
   586  	var val unsafe.Pointer
   587  	for {
   588  		for i := uintptr(0); i < bucketCnt; i++ {
   589  			if b.tophash[i] != top {
   590  				if b.tophash[i] == empty && inserti == nil {
   591  					inserti = &b.tophash[i]
   592  					insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
   593  					val = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
   594  				}
   595  				continue
   596  			}
   597  			k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
   598  			if t.indirectkey {
   599  				k = *((*unsafe.Pointer)(k))
   600  			}
   601  			if !alg.equal(key, k) {
   602  				continue
   603  			}
   604  			// already have a mapping for key. Update it.
   605  			if t.needkeyupdate {
   606  				typedmemmove(t.key, k, key)
   607  			}
   608  			val = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
   609  			goto done
   610  		}
   611  		ovf := b.overflow(t)
   612  		if ovf == nil {
   613  			break
   614  		}
   615  		b = ovf
   616  	}
   617  
   618  	// Did not find mapping for key. Allocate new cell & add entry.
   619  
   620  	// If we hit the max load factor or we have too many overflow buckets,
   621  	// and we're not already in the middle of growing, start growing.
   622  	if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
   623  		hashGrow(t, h)
   624  		goto again // Growing the table invalidates everything, so try again
   625  	}
   626  
   627  	if inserti == nil {
   628  		// all current buckets are full, allocate a new one.
   629  		newb := h.newoverflow(t, b)
   630  		inserti = &newb.tophash[0]
   631  		insertk = add(unsafe.Pointer(newb), dataOffset)
   632  		val = add(insertk, bucketCnt*uintptr(t.keysize))
   633  	}
   634  
   635  	// store new key/value at insert position
   636  	if t.indirectkey {
   637  		kmem := newobject(t.key)
   638  		*(*unsafe.Pointer)(insertk) = kmem
   639  		insertk = kmem
   640  	}
   641  	if t.indirectvalue {
   642  		vmem := newobject(t.elem)
   643  		*(*unsafe.Pointer)(val) = vmem
   644  	}
   645  	typedmemmove(t.key, insertk, key)
   646  	*inserti = top
   647  	h.count++
   648  
   649  done:
   650  	if h.flags&hashWriting == 0 {
   651  		throw("concurrent map writes")
   652  	}
   653  	h.flags &^= hashWriting
   654  	if t.indirectvalue {
   655  		val = *((*unsafe.Pointer)(val))
   656  	}
   657  	return val
   658  }
   659  
   660  func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {
   661  	if raceenabled && h != nil {
   662  		callerpc := getcallerpc()
   663  		pc := funcPC(mapdelete)
   664  		racewritepc(unsafe.Pointer(h), callerpc, pc)
   665  		raceReadObjectPC(t.key, key, callerpc, pc)
   666  	}
   667  	if msanenabled && h != nil {
   668  		msanread(key, t.key.size)
   669  	}
   670  	if h == nil || h.count == 0 {
   671  		return
   672  	}
   673  	if h.flags&hashWriting != 0 {
   674  		throw("concurrent map writes")
   675  	}
   676  
   677  	alg := t.key.alg
   678  	hash := alg.hash(key, uintptr(h.hash0))
   679  
   680  	// Set hashWriting after calling alg.hash, since alg.hash may panic,
   681  	// in which case we have not actually done a write (delete).
   682  	h.flags |= hashWriting
   683  
   684  	bucket := hash & bucketMask(h.B)
   685  	if h.growing() {
   686  		growWork(t, h, bucket)
   687  	}
   688  	b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))
   689  	top := tophash(hash)
   690  search:
   691  	for ; b != nil; b = b.overflow(t) {
   692  		for i := uintptr(0); i < bucketCnt; i++ {
   693  			if b.tophash[i] != top {
   694  				continue
   695  			}
   696  			k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
   697  			k2 := k
   698  			if t.indirectkey {
   699  				k2 = *((*unsafe.Pointer)(k2))
   700  			}
   701  			if !alg.equal(key, k2) {
   702  				continue
   703  			}
   704  			// Only clear key if there are pointers in it.
   705  			if t.indirectkey {
   706  				*(*unsafe.Pointer)(k) = nil
   707  			} else if t.key.kind&kindNoPointers == 0 {
   708  				memclrHasPointers(k, t.key.size)
   709  			}
   710  			v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
   711  			if t.indirectvalue {
   712  				*(*unsafe.Pointer)(v) = nil
   713  			} else if t.elem.kind&kindNoPointers == 0 {
   714  				memclrHasPointers(v, t.elem.size)
   715  			} else {
   716  				memclrNoHeapPointers(v, t.elem.size)
   717  			}
   718  			b.tophash[i] = empty
   719  			h.count--
   720  			break search
   721  		}
   722  	}
   723  
   724  	if h.flags&hashWriting == 0 {
   725  		throw("concurrent map writes")
   726  	}
   727  	h.flags &^= hashWriting
   728  }
   729  
   730  // mapiterinit initializes the hiter struct used for ranging over maps.
   731  // The hiter struct pointed to by 'it' is allocated on the stack
   732  // by the compilers order pass or on the heap by reflect_mapiterinit.
   733  // Both need to have zeroed hiter since the struct contains pointers.
   734  func mapiterinit(t *maptype, h *hmap, it *hiter) {
   735  	if raceenabled && h != nil {
   736  		callerpc := getcallerpc()
   737  		racereadpc(unsafe.Pointer(h), callerpc, funcPC(mapiterinit))
   738  	}
   739  
   740  	if h == nil || h.count == 0 {
   741  		return
   742  	}
   743  
   744  	if unsafe.Sizeof(hiter{})/sys.PtrSize != 12 {
   745  		throw("hash_iter size incorrect") // see cmd/compile/internal/gc/reflect.go
   746  	}
   747  	it.t = t
   748  	it.h = h
   749  
   750  	// grab snapshot of bucket state
   751  	it.B = h.B
   752  	it.buckets = h.buckets
   753  	if t.bucket.kind&kindNoPointers != 0 {
   754  		// Allocate the current slice and remember pointers to both current and old.
   755  		// This preserves all relevant overflow buckets alive even if
   756  		// the table grows and/or overflow buckets are added to the table
   757  		// while we are iterating.
   758  		h.createOverflow()
   759  		it.overflow = h.extra.overflow
   760  		it.oldoverflow = h.extra.oldoverflow
   761  	}
   762  
   763  	// decide where to start
   764  	r := uintptr(fastrand())
   765  	if h.B > 31-bucketCntBits {
   766  		r += uintptr(fastrand()) << 31
   767  	}
   768  	it.startBucket = r & bucketMask(h.B)
   769  	it.offset = uint8(r >> h.B & (bucketCnt - 1))
   770  
   771  	// iterator state
   772  	it.bucket = it.startBucket
   773  
   774  	// Remember we have an iterator.
   775  	// Can run concurrently with another mapiterinit().
   776  	if old := h.flags; old&(iterator|oldIterator) != iterator|oldIterator {
   777  		atomic.Or8(&h.flags, iterator|oldIterator)
   778  	}
   779  
   780  	mapiternext(it)
   781  }
   782  
   783  func mapiternext(it *hiter) {
   784  	h := it.h
   785  	if raceenabled {
   786  		callerpc := getcallerpc()
   787  		racereadpc(unsafe.Pointer(h), callerpc, funcPC(mapiternext))
   788  	}
   789  	if h.flags&hashWriting != 0 {
   790  		throw("concurrent map iteration and map write")
   791  	}
   792  	t := it.t
   793  	bucket := it.bucket
   794  	b := it.bptr
   795  	i := it.i
   796  	checkBucket := it.checkBucket
   797  	alg := t.key.alg
   798  
   799  next:
   800  	if b == nil {
   801  		if bucket == it.startBucket && it.wrapped {
   802  			// end of iteration
   803  			it.key = nil
   804  			it.value = nil
   805  			return
   806  		}
   807  		if h.growing() && it.B == h.B {
   808  			// Iterator was started in the middle of a grow, and the grow isn't done yet.
   809  			// If the bucket we're looking at hasn't been filled in yet (i.e. the old
   810  			// bucket hasn't been evacuated) then we need to iterate through the old
   811  			// bucket and only return the ones that will be migrated to this bucket.
   812  			oldbucket := bucket & it.h.oldbucketmask()
   813  			b = (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
   814  			if !evacuated(b) {
   815  				checkBucket = bucket
   816  			} else {
   817  				b = (*bmap)(add(it.buckets, bucket*uintptr(t.bucketsize)))
   818  				checkBucket = noCheck
   819  			}
   820  		} else {
   821  			b = (*bmap)(add(it.buckets, bucket*uintptr(t.bucketsize)))
   822  			checkBucket = noCheck
   823  		}
   824  		bucket++
   825  		if bucket == bucketShift(it.B) {
   826  			bucket = 0
   827  			it.wrapped = true
   828  		}
   829  		i = 0
   830  	}
   831  	for ; i < bucketCnt; i++ {
   832  		offi := (i + it.offset) & (bucketCnt - 1)
   833  		if b.tophash[offi] == empty || b.tophash[offi] == evacuatedEmpty {
   834  			continue
   835  		}
   836  		k := add(unsafe.Pointer(b), dataOffset+uintptr(offi)*uintptr(t.keysize))
   837  		if t.indirectkey {
   838  			k = *((*unsafe.Pointer)(k))
   839  		}
   840  		v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+uintptr(offi)*uintptr(t.valuesize))
   841  		if checkBucket != noCheck && !h.sameSizeGrow() {
   842  			// Special case: iterator was started during a grow to a larger size
   843  			// and the grow is not done yet. We're working on a bucket whose
   844  			// oldbucket has not been evacuated yet. Or at least, it wasn't
   845  			// evacuated when we started the bucket. So we're iterating
   846  			// through the oldbucket, skipping any keys that will go
   847  			// to the other new bucket (each oldbucket expands to two
   848  			// buckets during a grow).
   849  			if t.reflexivekey || alg.equal(k, k) {
   850  				// If the item in the oldbucket is not destined for
   851  				// the current new bucket in the iteration, skip it.
   852  				hash := alg.hash(k, uintptr(h.hash0))
   853  				if hash&bucketMask(it.B) != checkBucket {
   854  					continue
   855  				}
   856  			} else {
   857  				// Hash isn't repeatable if k != k (NaNs).  We need a
   858  				// repeatable and randomish choice of which direction
   859  				// to send NaNs during evacuation. We'll use the low
   860  				// bit of tophash to decide which way NaNs go.
   861  				// NOTE: this case is why we need two evacuate tophash
   862  				// values, evacuatedX and evacuatedY, that differ in
   863  				// their low bit.
   864  				if checkBucket>>(it.B-1) != uintptr(b.tophash[offi]&1) {
   865  					continue
   866  				}
   867  			}
   868  		}
   869  		if (b.tophash[offi] != evacuatedX && b.tophash[offi] != evacuatedY) ||
   870  			!(t.reflexivekey || alg.equal(k, k)) {
   871  			// This is the golden data, we can return it.
   872  			// OR
   873  			// key!=key, so the entry can't be deleted or updated, so we can just return it.
   874  			// That's lucky for us because when key!=key we can't look it up successfully.
   875  			it.key = k
   876  			if t.indirectvalue {
   877  				v = *((*unsafe.Pointer)(v))
   878  			}
   879  			it.value = v
   880  		} else {
   881  			// The hash table has grown since the iterator was started.
   882  			// The golden data for this key is now somewhere else.
   883  			// Check the current hash table for the data.
   884  			// This code handles the case where the key
   885  			// has been deleted, updated, or deleted and reinserted.
   886  			// NOTE: we need to regrab the key as it has potentially been
   887  			// updated to an equal() but not identical key (e.g. +0.0 vs -0.0).
   888  			rk, rv := mapaccessK(t, h, k)
   889  			if rk == nil {
   890  				continue // key has been deleted
   891  			}
   892  			it.key = rk
   893  			it.value = rv
   894  		}
   895  		it.bucket = bucket
   896  		if it.bptr != b { // avoid unnecessary write barrier; see issue 14921
   897  			it.bptr = b
   898  		}
   899  		it.i = i + 1
   900  		it.checkBucket = checkBucket
   901  		return
   902  	}
   903  	b = b.overflow(t)
   904  	i = 0
   905  	goto next
   906  }
   907  
   908  // mapclear deletes all keys from a map.
   909  func mapclear(t *maptype, h *hmap) {
   910  	if raceenabled && h != nil {
   911  		callerpc := getcallerpc()
   912  		pc := funcPC(mapclear)
   913  		racewritepc(unsafe.Pointer(h), callerpc, pc)
   914  	}
   915  
   916  	if h == nil || h.count == 0 {
   917  		return
   918  	}
   919  
   920  	if h.flags&hashWriting != 0 {
   921  		throw("concurrent map writes")
   922  	}
   923  
   924  	h.flags |= hashWriting
   925  
   926  	h.flags &^= sameSizeGrow
   927  	h.oldbuckets = nil
   928  	h.nevacuate = 0
   929  	h.noverflow = 0
   930  	h.count = 0
   931  
   932  	// Keep the mapextra allocation but clear any extra information.
   933  	if h.extra != nil {
   934  		*h.extra = mapextra{}
   935  	}
   936  
   937  	// makeBucketArray clears the memory pointed to by h.buckets
   938  	// and recovers any overflow buckets by generating them
   939  	// as if h.buckets was newly alloced.
   940  	_, nextOverflow := makeBucketArray(t, h.B, h.buckets)
   941  	if nextOverflow != nil {
   942  		// If overflow buckets are created then h.extra
   943  		// will have been allocated during initial bucket creation.
   944  		h.extra.nextOverflow = nextOverflow
   945  	}
   946  
   947  	if h.flags&hashWriting == 0 {
   948  		throw("concurrent map writes")
   949  	}
   950  	h.flags &^= hashWriting
   951  }
   952  
   953  func hashGrow(t *maptype, h *hmap) {
   954  	// If we've hit the load factor, get bigger.
   955  	// Otherwise, there are too many overflow buckets,
   956  	// so keep the same number of buckets and "grow" laterally.
   957  	bigger := uint8(1)
   958  	if !overLoadFactor(h.count+1, h.B) {
   959  		bigger = 0
   960  		h.flags |= sameSizeGrow
   961  	}
   962  	oldbuckets := h.buckets
   963  	newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)
   964  
   965  	flags := h.flags &^ (iterator | oldIterator)
   966  	if h.flags&iterator != 0 {
   967  		flags |= oldIterator
   968  	}
   969  	// commit the grow (atomic wrt gc)
   970  	h.B += bigger
   971  	h.flags = flags
   972  	h.oldbuckets = oldbuckets
   973  	h.buckets = newbuckets
   974  	h.nevacuate = 0
   975  	h.noverflow = 0
   976  
   977  	if h.extra != nil && h.extra.overflow != nil {
   978  		// Promote current overflow buckets to the old generation.
   979  		if h.extra.oldoverflow != nil {
   980  			throw("oldoverflow is not nil")
   981  		}
   982  		h.extra.oldoverflow = h.extra.overflow
   983  		h.extra.overflow = nil
   984  	}
   985  	if nextOverflow != nil {
   986  		if h.extra == nil {
   987  			h.extra = new(mapextra)
   988  		}
   989  		h.extra.nextOverflow = nextOverflow
   990  	}
   991  
   992  	// the actual copying of the hash table data is done incrementally
   993  	// by growWork() and evacuate().
   994  }
   995  
   996  // overLoadFactor reports whether count items placed in 1<<B buckets is over loadFactor.
   997  func overLoadFactor(count int, B uint8) bool {
   998  	return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
   999  }
  1000  
  1001  // tooManyOverflowBuckets reports whether noverflow buckets is too many for a map with 1<<B buckets.
  1002  // Note that most of these overflow buckets must be in sparse use;
  1003  // if use was dense, then we'd have already triggered regular map growth.
  1004  func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {
  1005  	// If the threshold is too low, we do extraneous work.
  1006  	// If the threshold is too high, maps that grow and shrink can hold on to lots of unused memory.
  1007  	// "too many" means (approximately) as many overflow buckets as regular buckets.
  1008  	// See incrnoverflow for more details.
  1009  	if B > 15 {
  1010  		B = 15
  1011  	}
  1012  	// The compiler doesn't see here that B < 16; mask B to generate shorter shift code.
  1013  	return noverflow >= uint16(1)<<(B&15)
  1014  }
  1015  
  1016  // growing reports whether h is growing. The growth may be to the same size or bigger.
  1017  func (h *hmap) growing() bool {
  1018  	return h.oldbuckets != nil
  1019  }
  1020  
  1021  // sameSizeGrow reports whether the current growth is to a map of the same size.
  1022  func (h *hmap) sameSizeGrow() bool {
  1023  	return h.flags&sameSizeGrow != 0
  1024  }
  1025  
  1026  // noldbuckets calculates the number of buckets prior to the current map growth.
  1027  func (h *hmap) noldbuckets() uintptr {
  1028  	oldB := h.B
  1029  	if !h.sameSizeGrow() {
  1030  		oldB--
  1031  	}
  1032  	return bucketShift(oldB)
  1033  }
  1034  
  1035  // oldbucketmask provides a mask that can be applied to calculate n % noldbuckets().
  1036  func (h *hmap) oldbucketmask() uintptr {
  1037  	return h.noldbuckets() - 1
  1038  }
  1039  
  1040  func growWork(t *maptype, h *hmap, bucket uintptr) {
  1041  	// make sure we evacuate the oldbucket corresponding
  1042  	// to the bucket we're about to use
  1043  	evacuate(t, h, bucket&h.oldbucketmask())
  1044  
  1045  	// evacuate one more oldbucket to make progress on growing
  1046  	if h.growing() {
  1047  		evacuate(t, h, h.nevacuate)
  1048  	}
  1049  }
  1050  
  1051  func bucketEvacuated(t *maptype, h *hmap, bucket uintptr) bool {
  1052  	b := (*bmap)(add(h.oldbuckets, bucket*uintptr(t.bucketsize)))
  1053  	return evacuated(b)
  1054  }
  1055  
  1056  // evacDst is an evacuation destination.
  1057  type evacDst struct {
  1058  	b *bmap          // current destination bucket
  1059  	i int            // key/val index into b
  1060  	k unsafe.Pointer // pointer to current key storage
  1061  	v unsafe.Pointer // pointer to current value storage
  1062  }
  1063  
  1064  func evacuate(t *maptype, h *hmap, oldbucket uintptr) {
  1065  	b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
  1066  	newbit := h.noldbuckets()
  1067  	if !evacuated(b) {
  1068  		// TODO: reuse overflow buckets instead of using new ones, if there
  1069  		// is no iterator using the old buckets.  (If !oldIterator.)
  1070  
  1071  		// xy contains the x and y (low and high) evacuation destinations.
  1072  		var xy [2]evacDst
  1073  		x := &xy[0]
  1074  		x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize)))
  1075  		x.k = add(unsafe.Pointer(x.b), dataOffset)
  1076  		x.v = add(x.k, bucketCnt*uintptr(t.keysize))
  1077  
  1078  		if !h.sameSizeGrow() {
  1079  			// Only calculate y pointers if we're growing bigger.
  1080  			// Otherwise GC can see bad pointers.
  1081  			y := &xy[1]
  1082  			y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize)))
  1083  			y.k = add(unsafe.Pointer(y.b), dataOffset)
  1084  			y.v = add(y.k, bucketCnt*uintptr(t.keysize))
  1085  		}
  1086  
  1087  		for ; b != nil; b = b.overflow(t) {
  1088  			k := add(unsafe.Pointer(b), dataOffset)
  1089  			v := add(k, bucketCnt*uintptr(t.keysize))
  1090  			for i := 0; i < bucketCnt; i, k, v = i+1, add(k, uintptr(t.keysize)), add(v, uintptr(t.valuesize)) {
  1091  				top := b.tophash[i]
  1092  				if top == empty {
  1093  					b.tophash[i] = evacuatedEmpty
  1094  					continue
  1095  				}
  1096  				if top < minTopHash {
  1097  					throw("bad map state")
  1098  				}
  1099  				k2 := k
  1100  				if t.indirectkey {
  1101  					k2 = *((*unsafe.Pointer)(k2))
  1102  				}
  1103  				var useY uint8
  1104  				if !h.sameSizeGrow() {
  1105  					// Compute hash to make our evacuation decision (whether we need
  1106  					// to send this key/value to bucket x or bucket y).
  1107  					hash := t.key.alg.hash(k2, uintptr(h.hash0))
  1108  					if h.flags&iterator != 0 && !t.reflexivekey && !t.key.alg.equal(k2, k2) {
  1109  						// If key != key (NaNs), then the hash could be (and probably
  1110  						// will be) entirely different from the old hash. Moreover,
  1111  						// it isn't reproducible. Reproducibility is required in the
  1112  						// presence of iterators, as our evacuation decision must
  1113  						// match whatever decision the iterator made.
  1114  						// Fortunately, we have the freedom to send these keys either
  1115  						// way. Also, tophash is meaningless for these kinds of keys.
  1116  						// We let the low bit of tophash drive the evacuation decision.
  1117  						// We recompute a new random tophash for the next level so
  1118  						// these keys will get evenly distributed across all buckets
  1119  						// after multiple grows.
  1120  						useY = top & 1
  1121  						top = tophash(hash)
  1122  					} else {
  1123  						if hash&newbit != 0 {
  1124  							useY = 1
  1125  						}
  1126  					}
  1127  				}
  1128  
  1129  				if evacuatedX+1 != evacuatedY {
  1130  					throw("bad evacuatedN")
  1131  				}
  1132  
  1133  				b.tophash[i] = evacuatedX + useY // evacuatedX + 1 == evacuatedY
  1134  				dst := &xy[useY]                 // evacuation destination
  1135  
  1136  				if dst.i == bucketCnt {
  1137  					dst.b = h.newoverflow(t, dst.b)
  1138  					dst.i = 0
  1139  					dst.k = add(unsafe.Pointer(dst.b), dataOffset)
  1140  					dst.v = add(dst.k, bucketCnt*uintptr(t.keysize))
  1141  				}
  1142  				dst.b.tophash[dst.i&(bucketCnt-1)] = top // mask dst.i as an optimization, to avoid a bounds check
  1143  				if t.indirectkey {
  1144  					*(*unsafe.Pointer)(dst.k) = k2 // copy pointer
  1145  				} else {
  1146  					typedmemmove(t.key, dst.k, k) // copy value
  1147  				}
  1148  				if t.indirectvalue {
  1149  					*(*unsafe.Pointer)(dst.v) = *(*unsafe.Pointer)(v)
  1150  				} else {
  1151  					typedmemmove(t.elem, dst.v, v)
  1152  				}
  1153  				dst.i++
  1154  				// These updates might push these pointers past the end of the
  1155  				// key or value arrays.  That's ok, as we have the overflow pointer
  1156  				// at the end of the bucket to protect against pointing past the
  1157  				// end of the bucket.
  1158  				dst.k = add(dst.k, uintptr(t.keysize))
  1159  				dst.v = add(dst.v, uintptr(t.valuesize))
  1160  			}
  1161  		}
  1162  		// Unlink the overflow buckets & clear key/value to help GC.
  1163  		if h.flags&oldIterator == 0 && t.bucket.kind&kindNoPointers == 0 {
  1164  			b := add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))
  1165  			// Preserve b.tophash because the evacuation
  1166  			// state is maintained there.
  1167  			ptr := add(b, dataOffset)
  1168  			n := uintptr(t.bucketsize) - dataOffset
  1169  			memclrHasPointers(ptr, n)
  1170  		}
  1171  	}
  1172  
  1173  	if oldbucket == h.nevacuate {
  1174  		advanceEvacuationMark(h, t, newbit)
  1175  	}
  1176  }
  1177  
  1178  func advanceEvacuationMark(h *hmap, t *maptype, newbit uintptr) {
  1179  	h.nevacuate++
  1180  	// Experiments suggest that 1024 is overkill by at least an order of magnitude.
  1181  	// Put it in there as a safeguard anyway, to ensure O(1) behavior.
  1182  	stop := h.nevacuate + 1024
  1183  	if stop > newbit {
  1184  		stop = newbit
  1185  	}
  1186  	for h.nevacuate != stop && bucketEvacuated(t, h, h.nevacuate) {
  1187  		h.nevacuate++
  1188  	}
  1189  	if h.nevacuate == newbit { // newbit == # of oldbuckets
  1190  		// Growing is all done. Free old main bucket array.
  1191  		h.oldbuckets = nil
  1192  		// Can discard old overflow buckets as well.
  1193  		// If they are still referenced by an iterator,
  1194  		// then the iterator holds a pointers to the slice.
  1195  		if h.extra != nil {
  1196  			h.extra.oldoverflow = nil
  1197  		}
  1198  		h.flags &^= sameSizeGrow
  1199  	}
  1200  }
  1201  
  1202  func ismapkey(t *_type) bool {
  1203  	return t.alg.hash != nil
  1204  }
  1205  
  1206  // Reflect stubs. Called from ../reflect/asm_*.s
  1207  
  1208  //go:linkname reflect_makemap reflect.makemap
  1209  func reflect_makemap(t *maptype, cap int) *hmap {
  1210  	// Check invariants and reflects math.
  1211  	if !ismapkey(t.key) {
  1212  		throw("runtime.reflect_makemap: unsupported map key type")
  1213  	}
  1214  	if t.key.size > maxKeySize && (!t.indirectkey || t.keysize != uint8(sys.PtrSize)) ||
  1215  		t.key.size <= maxKeySize && (t.indirectkey || t.keysize != uint8(t.key.size)) {
  1216  		throw("key size wrong")
  1217  	}
  1218  	if t.elem.size > maxValueSize && (!t.indirectvalue || t.valuesize != uint8(sys.PtrSize)) ||
  1219  		t.elem.size <= maxValueSize && (t.indirectvalue || t.valuesize != uint8(t.elem.size)) {
  1220  		throw("value size wrong")
  1221  	}
  1222  	if t.key.align > bucketCnt {
  1223  		throw("key align too big")
  1224  	}
  1225  	if t.elem.align > bucketCnt {
  1226  		throw("value align too big")
  1227  	}
  1228  	if t.key.size%uintptr(t.key.align) != 0 {
  1229  		throw("key size not a multiple of key align")
  1230  	}
  1231  	if t.elem.size%uintptr(t.elem.align) != 0 {
  1232  		throw("value size not a multiple of value align")
  1233  	}
  1234  	if bucketCnt < 8 {
  1235  		throw("bucketsize too small for proper alignment")
  1236  	}
  1237  	if dataOffset%uintptr(t.key.align) != 0 {
  1238  		throw("need padding in bucket (key)")
  1239  	}
  1240  	if dataOffset%uintptr(t.elem.align) != 0 {
  1241  		throw("need padding in bucket (value)")
  1242  	}
  1243  
  1244  	return makemap(t, cap, nil)
  1245  }
  1246  
  1247  //go:linkname reflect_mapaccess reflect.mapaccess
  1248  func reflect_mapaccess(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
  1249  	val, ok := mapaccess2(t, h, key)
  1250  	if !ok {
  1251  		// reflect wants nil for a missing element
  1252  		val = nil
  1253  	}
  1254  	return val
  1255  }
  1256  
  1257  //go:linkname reflect_mapassign reflect.mapassign
  1258  func reflect_mapassign(t *maptype, h *hmap, key unsafe.Pointer, val unsafe.Pointer) {
  1259  	p := mapassign(t, h, key)
  1260  	typedmemmove(t.elem, p, val)
  1261  }
  1262  
  1263  //go:linkname reflect_mapdelete reflect.mapdelete
  1264  func reflect_mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {
  1265  	mapdelete(t, h, key)
  1266  }
  1267  
  1268  //go:linkname reflect_mapiterinit reflect.mapiterinit
  1269  func reflect_mapiterinit(t *maptype, h *hmap) *hiter {
  1270  	it := new(hiter)
  1271  	mapiterinit(t, h, it)
  1272  	return it
  1273  }
  1274  
  1275  //go:linkname reflect_mapiternext reflect.mapiternext
  1276  func reflect_mapiternext(it *hiter) {
  1277  	mapiternext(it)
  1278  }
  1279  
  1280  //go:linkname reflect_mapiterkey reflect.mapiterkey
  1281  func reflect_mapiterkey(it *hiter) unsafe.Pointer {
  1282  	return it.key
  1283  }
  1284  
  1285  //go:linkname reflect_maplen reflect.maplen
  1286  func reflect_maplen(h *hmap) int {
  1287  	if h == nil {
  1288  		return 0
  1289  	}
  1290  	if raceenabled {
  1291  		callerpc := getcallerpc()
  1292  		racereadpc(unsafe.Pointer(h), callerpc, funcPC(reflect_maplen))
  1293  	}
  1294  	return h.count
  1295  }
  1296  
  1297  //go:linkname reflect_ismapkey reflect.ismapkey
  1298  func reflect_ismapkey(t *_type) bool {
  1299  	return ismapkey(t)
  1300  }
  1301  
  1302  const maxZero = 1024 // must match value in cmd/compile/internal/gc/walk.go
  1303  var zeroVal [maxZero]byte
  1304  

View as plain text