Source file src/runtime/hashmap_fast.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  import (
     8  	"runtime/internal/sys"
     9  	"unsafe"
    10  )
    11  
    12  func mapaccess1_fast32(t *maptype, h *hmap, key uint32) unsafe.Pointer {
    13  	if raceenabled && h != nil {
    14  		callerpc := getcallerpc()
    15  		racereadpc(unsafe.Pointer(h), callerpc, funcPC(mapaccess1_fast32))
    16  	}
    17  	if h == nil || h.count == 0 {
    18  		return unsafe.Pointer(&zeroVal[0])
    19  	}
    20  	if h.flags&hashWriting != 0 {
    21  		throw("concurrent map read and map write")
    22  	}
    23  	var b *bmap
    24  	if h.B == 0 {
    25  		// One-bucket table. No need to hash.
    26  		b = (*bmap)(h.buckets)
    27  	} else {
    28  		hash := t.key.alg.hash(noescape(unsafe.Pointer(&key)), uintptr(h.hash0))
    29  		m := bucketMask(h.B)
    30  		b = (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
    31  		if c := h.oldbuckets; c != nil {
    32  			if !h.sameSizeGrow() {
    33  				// There used to be half as many buckets; mask down one more power of two.
    34  				m >>= 1
    35  			}
    36  			oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
    37  			if !evacuated(oldb) {
    38  				b = oldb
    39  			}
    40  		}
    41  	}
    42  	for ; b != nil; b = b.overflow(t) {
    43  		for i, k := uintptr(0), b.keys(); i < bucketCnt; i, k = i+1, add(k, 4) {
    44  			if *(*uint32)(k) == key && b.tophash[i] != empty {
    45  				return add(unsafe.Pointer(b), dataOffset+bucketCnt*4+i*uintptr(t.valuesize))
    46  			}
    47  		}
    48  	}
    49  	return unsafe.Pointer(&zeroVal[0])
    50  }
    51  
    52  func mapaccess2_fast32(t *maptype, h *hmap, key uint32) (unsafe.Pointer, bool) {
    53  	if raceenabled && h != nil {
    54  		callerpc := getcallerpc()
    55  		racereadpc(unsafe.Pointer(h), callerpc, funcPC(mapaccess2_fast32))
    56  	}
    57  	if h == nil || h.count == 0 {
    58  		return unsafe.Pointer(&zeroVal[0]), false
    59  	}
    60  	if h.flags&hashWriting != 0 {
    61  		throw("concurrent map read and map write")
    62  	}
    63  	var b *bmap
    64  	if h.B == 0 {
    65  		// One-bucket table. No need to hash.
    66  		b = (*bmap)(h.buckets)
    67  	} else {
    68  		hash := t.key.alg.hash(noescape(unsafe.Pointer(&key)), uintptr(h.hash0))
    69  		m := bucketMask(h.B)
    70  		b = (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
    71  		if c := h.oldbuckets; c != nil {
    72  			if !h.sameSizeGrow() {
    73  				// There used to be half as many buckets; mask down one more power of two.
    74  				m >>= 1
    75  			}
    76  			oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
    77  			if !evacuated(oldb) {
    78  				b = oldb
    79  			}
    80  		}
    81  	}
    82  	for ; b != nil; b = b.overflow(t) {
    83  		for i, k := uintptr(0), b.keys(); i < bucketCnt; i, k = i+1, add(k, 4) {
    84  			if *(*uint32)(k) == key && b.tophash[i] != empty {
    85  				return add(unsafe.Pointer(b), dataOffset+bucketCnt*4+i*uintptr(t.valuesize)), true
    86  			}
    87  		}
    88  	}
    89  	return unsafe.Pointer(&zeroVal[0]), false
    90  }
    91  
    92  func mapaccess1_fast64(t *maptype, h *hmap, key uint64) unsafe.Pointer {
    93  	if raceenabled && h != nil {
    94  		callerpc := getcallerpc()
    95  		racereadpc(unsafe.Pointer(h), callerpc, funcPC(mapaccess1_fast64))
    96  	}
    97  	if h == nil || h.count == 0 {
    98  		return unsafe.Pointer(&zeroVal[0])
    99  	}
   100  	if h.flags&hashWriting != 0 {
   101  		throw("concurrent map read and map write")
   102  	}
   103  	var b *bmap
   104  	if h.B == 0 {
   105  		// One-bucket table. No need to hash.
   106  		b = (*bmap)(h.buckets)
   107  	} else {
   108  		hash := t.key.alg.hash(noescape(unsafe.Pointer(&key)), uintptr(h.hash0))
   109  		m := bucketMask(h.B)
   110  		b = (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
   111  		if c := h.oldbuckets; c != nil {
   112  			if !h.sameSizeGrow() {
   113  				// There used to be half as many buckets; mask down one more power of two.
   114  				m >>= 1
   115  			}
   116  			oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
   117  			if !evacuated(oldb) {
   118  				b = oldb
   119  			}
   120  		}
   121  	}
   122  	for ; b != nil; b = b.overflow(t) {
   123  		for i, k := uintptr(0), b.keys(); i < bucketCnt; i, k = i+1, add(k, 8) {
   124  			if *(*uint64)(k) == key && b.tophash[i] != empty {
   125  				return add(unsafe.Pointer(b), dataOffset+bucketCnt*8+i*uintptr(t.valuesize))
   126  			}
   127  		}
   128  	}
   129  	return unsafe.Pointer(&zeroVal[0])
   130  }
   131  
   132  func mapaccess2_fast64(t *maptype, h *hmap, key uint64) (unsafe.Pointer, bool) {
   133  	if raceenabled && h != nil {
   134  		callerpc := getcallerpc()
   135  		racereadpc(unsafe.Pointer(h), callerpc, funcPC(mapaccess2_fast64))
   136  	}
   137  	if h == nil || h.count == 0 {
   138  		return unsafe.Pointer(&zeroVal[0]), false
   139  	}
   140  	if h.flags&hashWriting != 0 {
   141  		throw("concurrent map read and map write")
   142  	}
   143  	var b *bmap
   144  	if h.B == 0 {
   145  		// One-bucket table. No need to hash.
   146  		b = (*bmap)(h.buckets)
   147  	} else {
   148  		hash := t.key.alg.hash(noescape(unsafe.Pointer(&key)), uintptr(h.hash0))
   149  		m := bucketMask(h.B)
   150  		b = (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
   151  		if c := h.oldbuckets; c != nil {
   152  			if !h.sameSizeGrow() {
   153  				// There used to be half as many buckets; mask down one more power of two.
   154  				m >>= 1
   155  			}
   156  			oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
   157  			if !evacuated(oldb) {
   158  				b = oldb
   159  			}
   160  		}
   161  	}
   162  	for ; b != nil; b = b.overflow(t) {
   163  		for i, k := uintptr(0), b.keys(); i < bucketCnt; i, k = i+1, add(k, 8) {
   164  			if *(*uint64)(k) == key && b.tophash[i] != empty {
   165  				return add(unsafe.Pointer(b), dataOffset+bucketCnt*8+i*uintptr(t.valuesize)), true
   166  			}
   167  		}
   168  	}
   169  	return unsafe.Pointer(&zeroVal[0]), false
   170  }
   171  
   172  func mapaccess1_faststr(t *maptype, h *hmap, ky string) unsafe.Pointer {
   173  	if raceenabled && h != nil {
   174  		callerpc := getcallerpc()
   175  		racereadpc(unsafe.Pointer(h), callerpc, funcPC(mapaccess1_faststr))
   176  	}
   177  	if h == nil || h.count == 0 {
   178  		return unsafe.Pointer(&zeroVal[0])
   179  	}
   180  	if h.flags&hashWriting != 0 {
   181  		throw("concurrent map read and map write")
   182  	}
   183  	key := stringStructOf(&ky)
   184  	if h.B == 0 {
   185  		// One-bucket table.
   186  		b := (*bmap)(h.buckets)
   187  		if key.len < 32 {
   188  			// short key, doing lots of comparisons is ok
   189  			for i, kptr := uintptr(0), b.keys(); i < bucketCnt; i, kptr = i+1, add(kptr, 2*sys.PtrSize) {
   190  				k := (*stringStruct)(kptr)
   191  				if k.len != key.len || b.tophash[i] == empty {
   192  					continue
   193  				}
   194  				if k.str == key.str || memequal(k.str, key.str, uintptr(key.len)) {
   195  					return add(unsafe.Pointer(b), dataOffset+bucketCnt*2*sys.PtrSize+i*uintptr(t.valuesize))
   196  				}
   197  			}
   198  			return unsafe.Pointer(&zeroVal[0])
   199  		}
   200  		// long key, try not to do more comparisons than necessary
   201  		keymaybe := uintptr(bucketCnt)
   202  		for i, kptr := uintptr(0), b.keys(); i < bucketCnt; i, kptr = i+1, add(kptr, 2*sys.PtrSize) {
   203  			k := (*stringStruct)(kptr)
   204  			if k.len != key.len || b.tophash[i] == empty {
   205  				continue
   206  			}
   207  			if k.str == key.str {
   208  				return add(unsafe.Pointer(b), dataOffset+bucketCnt*2*sys.PtrSize+i*uintptr(t.valuesize))
   209  			}
   210  			// check first 4 bytes
   211  			if *((*[4]byte)(key.str)) != *((*[4]byte)(k.str)) {
   212  				continue
   213  			}
   214  			// check last 4 bytes
   215  			if *((*[4]byte)(add(key.str, uintptr(key.len)-4))) != *((*[4]byte)(add(k.str, uintptr(key.len)-4))) {
   216  				continue
   217  			}
   218  			if keymaybe != bucketCnt {
   219  				// Two keys are potential matches. Use hash to distinguish them.
   220  				goto dohash
   221  			}
   222  			keymaybe = i
   223  		}
   224  		if keymaybe != bucketCnt {
   225  			k := (*stringStruct)(add(unsafe.Pointer(b), dataOffset+keymaybe*2*sys.PtrSize))
   226  			if memequal(k.str, key.str, uintptr(key.len)) {
   227  				return add(unsafe.Pointer(b), dataOffset+bucketCnt*2*sys.PtrSize+keymaybe*uintptr(t.valuesize))
   228  			}
   229  		}
   230  		return unsafe.Pointer(&zeroVal[0])
   231  	}
   232  dohash:
   233  	hash := t.key.alg.hash(noescape(unsafe.Pointer(&ky)), uintptr(h.hash0))
   234  	m := bucketMask(h.B)
   235  	b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
   236  	if c := h.oldbuckets; c != nil {
   237  		if !h.sameSizeGrow() {
   238  			// There used to be half as many buckets; mask down one more power of two.
   239  			m >>= 1
   240  		}
   241  		oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
   242  		if !evacuated(oldb) {
   243  			b = oldb
   244  		}
   245  	}
   246  	top := tophash(hash)
   247  	for ; b != nil; b = b.overflow(t) {
   248  		for i, kptr := uintptr(0), b.keys(); i < bucketCnt; i, kptr = i+1, add(kptr, 2*sys.PtrSize) {
   249  			k := (*stringStruct)(kptr)
   250  			if k.len != key.len || b.tophash[i] != top {
   251  				continue
   252  			}
   253  			if k.str == key.str || memequal(k.str, key.str, uintptr(key.len)) {
   254  				return add(unsafe.Pointer(b), dataOffset+bucketCnt*2*sys.PtrSize+i*uintptr(t.valuesize))
   255  			}
   256  		}
   257  	}
   258  	return unsafe.Pointer(&zeroVal[0])
   259  }
   260  
   261  func mapaccess2_faststr(t *maptype, h *hmap, ky string) (unsafe.Pointer, bool) {
   262  	if raceenabled && h != nil {
   263  		callerpc := getcallerpc()
   264  		racereadpc(unsafe.Pointer(h), callerpc, funcPC(mapaccess2_faststr))
   265  	}
   266  	if h == nil || h.count == 0 {
   267  		return unsafe.Pointer(&zeroVal[0]), false
   268  	}
   269  	if h.flags&hashWriting != 0 {
   270  		throw("concurrent map read and map write")
   271  	}
   272  	key := stringStructOf(&ky)
   273  	if h.B == 0 {
   274  		// One-bucket table.
   275  		b := (*bmap)(h.buckets)
   276  		if key.len < 32 {
   277  			// short key, doing lots of comparisons is ok
   278  			for i, kptr := uintptr(0), b.keys(); i < bucketCnt; i, kptr = i+1, add(kptr, 2*sys.PtrSize) {
   279  				k := (*stringStruct)(kptr)
   280  				if k.len != key.len || b.tophash[i] == empty {
   281  					continue
   282  				}
   283  				if k.str == key.str || memequal(k.str, key.str, uintptr(key.len)) {
   284  					return add(unsafe.Pointer(b), dataOffset+bucketCnt*2*sys.PtrSize+i*uintptr(t.valuesize)), true
   285  				}
   286  			}
   287  			return unsafe.Pointer(&zeroVal[0]), false
   288  		}
   289  		// long key, try not to do more comparisons than necessary
   290  		keymaybe := uintptr(bucketCnt)
   291  		for i, kptr := uintptr(0), b.keys(); i < bucketCnt; i, kptr = i+1, add(kptr, 2*sys.PtrSize) {
   292  			k := (*stringStruct)(kptr)
   293  			if k.len != key.len || b.tophash[i] == empty {
   294  				continue
   295  			}
   296  			if k.str == key.str {
   297  				return add(unsafe.Pointer(b), dataOffset+bucketCnt*2*sys.PtrSize+i*uintptr(t.valuesize)), true
   298  			}
   299  			// check first 4 bytes
   300  			if *((*[4]byte)(key.str)) != *((*[4]byte)(k.str)) {
   301  				continue
   302  			}
   303  			// check last 4 bytes
   304  			if *((*[4]byte)(add(key.str, uintptr(key.len)-4))) != *((*[4]byte)(add(k.str, uintptr(key.len)-4))) {
   305  				continue
   306  			}
   307  			if keymaybe != bucketCnt {
   308  				// Two keys are potential matches. Use hash to distinguish them.
   309  				goto dohash
   310  			}
   311  			keymaybe = i
   312  		}
   313  		if keymaybe != bucketCnt {
   314  			k := (*stringStruct)(add(unsafe.Pointer(b), dataOffset+keymaybe*2*sys.PtrSize))
   315  			if memequal(k.str, key.str, uintptr(key.len)) {
   316  				return add(unsafe.Pointer(b), dataOffset+bucketCnt*2*sys.PtrSize+keymaybe*uintptr(t.valuesize)), true
   317  			}
   318  		}
   319  		return unsafe.Pointer(&zeroVal[0]), false
   320  	}
   321  dohash:
   322  	hash := t.key.alg.hash(noescape(unsafe.Pointer(&ky)), uintptr(h.hash0))
   323  	m := bucketMask(h.B)
   324  	b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
   325  	if c := h.oldbuckets; c != nil {
   326  		if !h.sameSizeGrow() {
   327  			// There used to be half as many buckets; mask down one more power of two.
   328  			m >>= 1
   329  		}
   330  		oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
   331  		if !evacuated(oldb) {
   332  			b = oldb
   333  		}
   334  	}
   335  	top := tophash(hash)
   336  	for ; b != nil; b = b.overflow(t) {
   337  		for i, kptr := uintptr(0), b.keys(); i < bucketCnt; i, kptr = i+1, add(kptr, 2*sys.PtrSize) {
   338  			k := (*stringStruct)(kptr)
   339  			if k.len != key.len || b.tophash[i] != top {
   340  				continue
   341  			}
   342  			if k.str == key.str || memequal(k.str, key.str, uintptr(key.len)) {
   343  				return add(unsafe.Pointer(b), dataOffset+bucketCnt*2*sys.PtrSize+i*uintptr(t.valuesize)), true
   344  			}
   345  		}
   346  	}
   347  	return unsafe.Pointer(&zeroVal[0]), false
   348  }
   349  
   350  func mapassign_fast32(t *maptype, h *hmap, key uint32) unsafe.Pointer {
   351  	if h == nil {
   352  		panic(plainError("assignment to entry in nil map"))
   353  	}
   354  	if raceenabled {
   355  		callerpc := getcallerpc()
   356  		racewritepc(unsafe.Pointer(h), callerpc, funcPC(mapassign_fast32))
   357  	}
   358  	if h.flags&hashWriting != 0 {
   359  		throw("concurrent map writes")
   360  	}
   361  	hash := t.key.alg.hash(noescape(unsafe.Pointer(&key)), uintptr(h.hash0))
   362  
   363  	// Set hashWriting after calling alg.hash for consistency with mapassign.
   364  	h.flags |= hashWriting
   365  
   366  	if h.buckets == nil {
   367  		h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
   368  	}
   369  
   370  again:
   371  	bucket := hash & bucketMask(h.B)
   372  	if h.growing() {
   373  		growWork_fast32(t, h, bucket)
   374  	}
   375  	b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize)))
   376  
   377  	var insertb *bmap
   378  	var inserti uintptr
   379  	var insertk unsafe.Pointer
   380  
   381  	for {
   382  		for i := uintptr(0); i < bucketCnt; i++ {
   383  			if b.tophash[i] == empty {
   384  				if insertb == nil {
   385  					inserti = i
   386  					insertb = b
   387  				}
   388  				continue
   389  			}
   390  			k := *((*uint32)(add(unsafe.Pointer(b), dataOffset+i*4)))
   391  			if k != key {
   392  				continue
   393  			}
   394  			inserti = i
   395  			insertb = b
   396  			goto done
   397  		}
   398  		ovf := b.overflow(t)
   399  		if ovf == nil {
   400  			break
   401  		}
   402  		b = ovf
   403  	}
   404  
   405  	// Did not find mapping for key. Allocate new cell & add entry.
   406  
   407  	// If we hit the max load factor or we have too many overflow buckets,
   408  	// and we're not already in the middle of growing, start growing.
   409  	if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
   410  		hashGrow(t, h)
   411  		goto again // Growing the table invalidates everything, so try again
   412  	}
   413  
   414  	if insertb == nil {
   415  		// all current buckets are full, allocate a new one.
   416  		insertb = h.newoverflow(t, b)
   417  		inserti = 0 // not necessary, but avoids needlessly spilling inserti
   418  	}
   419  	insertb.tophash[inserti&(bucketCnt-1)] = tophash(hash) // mask inserti to avoid bounds checks
   420  
   421  	insertk = add(unsafe.Pointer(insertb), dataOffset+inserti*4)
   422  	// store new key at insert position
   423  	*(*uint32)(insertk) = key
   424  
   425  	h.count++
   426  
   427  done:
   428  	val := add(unsafe.Pointer(insertb), dataOffset+bucketCnt*4+inserti*uintptr(t.valuesize))
   429  	if h.flags&hashWriting == 0 {
   430  		throw("concurrent map writes")
   431  	}
   432  	h.flags &^= hashWriting
   433  	return val
   434  }
   435  
   436  func mapassign_fast32ptr(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
   437  	if h == nil {
   438  		panic(plainError("assignment to entry in nil map"))
   439  	}
   440  	if raceenabled {
   441  		callerpc := getcallerpc()
   442  		racewritepc(unsafe.Pointer(h), callerpc, funcPC(mapassign_fast32))
   443  	}
   444  	if h.flags&hashWriting != 0 {
   445  		throw("concurrent map writes")
   446  	}
   447  	hash := t.key.alg.hash(noescape(unsafe.Pointer(&key)), uintptr(h.hash0))
   448  
   449  	// Set hashWriting after calling alg.hash for consistency with mapassign.
   450  	h.flags |= hashWriting
   451  
   452  	if h.buckets == nil {
   453  		h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
   454  	}
   455  
   456  again:
   457  	bucket := hash & bucketMask(h.B)
   458  	if h.growing() {
   459  		growWork_fast32(t, h, bucket)
   460  	}
   461  	b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize)))
   462  
   463  	var insertb *bmap
   464  	var inserti uintptr
   465  	var insertk unsafe.Pointer
   466  
   467  	for {
   468  		for i := uintptr(0); i < bucketCnt; i++ {
   469  			if b.tophash[i] == empty {
   470  				if insertb == nil {
   471  					inserti = i
   472  					insertb = b
   473  				}
   474  				continue
   475  			}
   476  			k := *((*unsafe.Pointer)(add(unsafe.Pointer(b), dataOffset+i*4)))
   477  			if k != key {
   478  				continue
   479  			}
   480  			inserti = i
   481  			insertb = b
   482  			goto done
   483  		}
   484  		ovf := b.overflow(t)
   485  		if ovf == nil {
   486  			break
   487  		}
   488  		b = ovf
   489  	}
   490  
   491  	// Did not find mapping for key. Allocate new cell & add entry.
   492  
   493  	// If we hit the max load factor or we have too many overflow buckets,
   494  	// and we're not already in the middle of growing, start growing.
   495  	if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
   496  		hashGrow(t, h)
   497  		goto again // Growing the table invalidates everything, so try again
   498  	}
   499  
   500  	if insertb == nil {
   501  		// all current buckets are full, allocate a new one.
   502  		insertb = h.newoverflow(t, b)
   503  		inserti = 0 // not necessary, but avoids needlessly spilling inserti
   504  	}
   505  	insertb.tophash[inserti&(bucketCnt-1)] = tophash(hash) // mask inserti to avoid bounds checks
   506  
   507  	insertk = add(unsafe.Pointer(insertb), dataOffset+inserti*4)
   508  	// store new key at insert position
   509  	*(*unsafe.Pointer)(insertk) = key
   510  
   511  	h.count++
   512  
   513  done:
   514  	val := add(unsafe.Pointer(insertb), dataOffset+bucketCnt*4+inserti*uintptr(t.valuesize))
   515  	if h.flags&hashWriting == 0 {
   516  		throw("concurrent map writes")
   517  	}
   518  	h.flags &^= hashWriting
   519  	return val
   520  }
   521  
   522  func mapassign_fast64(t *maptype, h *hmap, key uint64) unsafe.Pointer {
   523  	if h == nil {
   524  		panic(plainError("assignment to entry in nil map"))
   525  	}
   526  	if raceenabled {
   527  		callerpc := getcallerpc()
   528  		racewritepc(unsafe.Pointer(h), callerpc, funcPC(mapassign_fast64))
   529  	}
   530  	if h.flags&hashWriting != 0 {
   531  		throw("concurrent map writes")
   532  	}
   533  	hash := t.key.alg.hash(noescape(unsafe.Pointer(&key)), uintptr(h.hash0))
   534  
   535  	// Set hashWriting after calling alg.hash for consistency with mapassign.
   536  	h.flags |= hashWriting
   537  
   538  	if h.buckets == nil {
   539  		h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
   540  	}
   541  
   542  again:
   543  	bucket := hash & bucketMask(h.B)
   544  	if h.growing() {
   545  		growWork_fast64(t, h, bucket)
   546  	}
   547  	b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize)))
   548  
   549  	var insertb *bmap
   550  	var inserti uintptr
   551  	var insertk unsafe.Pointer
   552  
   553  	for {
   554  		for i := uintptr(0); i < bucketCnt; i++ {
   555  			if b.tophash[i] == empty {
   556  				if insertb == nil {
   557  					insertb = b
   558  					inserti = i
   559  				}
   560  				continue
   561  			}
   562  			k := *((*uint64)(add(unsafe.Pointer(b), dataOffset+i*8)))
   563  			if k != key {
   564  				continue
   565  			}
   566  			insertb = b
   567  			inserti = i
   568  			goto done
   569  		}
   570  		ovf := b.overflow(t)
   571  		if ovf == nil {
   572  			break
   573  		}
   574  		b = ovf
   575  	}
   576  
   577  	// Did not find mapping for key. Allocate new cell & add entry.
   578  
   579  	// If we hit the max load factor or we have too many overflow buckets,
   580  	// and we're not already in the middle of growing, start growing.
   581  	if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
   582  		hashGrow(t, h)
   583  		goto again // Growing the table invalidates everything, so try again
   584  	}
   585  
   586  	if insertb == nil {
   587  		// all current buckets are full, allocate a new one.
   588  		insertb = h.newoverflow(t, b)
   589  		inserti = 0 // not necessary, but avoids needlessly spilling inserti
   590  	}
   591  	insertb.tophash[inserti&(bucketCnt-1)] = tophash(hash) // mask inserti to avoid bounds checks
   592  
   593  	insertk = add(unsafe.Pointer(insertb), dataOffset+inserti*8)
   594  	// store new key at insert position
   595  	*(*uint64)(insertk) = key
   596  
   597  	h.count++
   598  
   599  done:
   600  	val := add(unsafe.Pointer(insertb), dataOffset+bucketCnt*8+inserti*uintptr(t.valuesize))
   601  	if h.flags&hashWriting == 0 {
   602  		throw("concurrent map writes")
   603  	}
   604  	h.flags &^= hashWriting
   605  	return val
   606  }
   607  
   608  func mapassign_fast64ptr(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
   609  	if h == nil {
   610  		panic(plainError("assignment to entry in nil map"))
   611  	}
   612  	if raceenabled {
   613  		callerpc := getcallerpc()
   614  		racewritepc(unsafe.Pointer(h), callerpc, funcPC(mapassign_fast64))
   615  	}
   616  	if h.flags&hashWriting != 0 {
   617  		throw("concurrent map writes")
   618  	}
   619  	hash := t.key.alg.hash(noescape(unsafe.Pointer(&key)), uintptr(h.hash0))
   620  
   621  	// Set hashWriting after calling alg.hash for consistency with mapassign.
   622  	h.flags |= hashWriting
   623  
   624  	if h.buckets == nil {
   625  		h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
   626  	}
   627  
   628  again:
   629  	bucket := hash & bucketMask(h.B)
   630  	if h.growing() {
   631  		growWork_fast64(t, h, bucket)
   632  	}
   633  	b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize)))
   634  
   635  	var insertb *bmap
   636  	var inserti uintptr
   637  	var insertk unsafe.Pointer
   638  
   639  	for {
   640  		for i := uintptr(0); i < bucketCnt; i++ {
   641  			if b.tophash[i] == empty {
   642  				if insertb == nil {
   643  					insertb = b
   644  					inserti = i
   645  				}
   646  				continue
   647  			}
   648  			k := *((*unsafe.Pointer)(add(unsafe.Pointer(b), dataOffset+i*8)))
   649  			if k != key {
   650  				continue
   651  			}
   652  			insertb = b
   653  			inserti = i
   654  			goto done
   655  		}
   656  		ovf := b.overflow(t)
   657  		if ovf == nil {
   658  			break
   659  		}
   660  		b = ovf
   661  	}
   662  
   663  	// Did not find mapping for key. Allocate new cell & add entry.
   664  
   665  	// If we hit the max load factor or we have too many overflow buckets,
   666  	// and we're not already in the middle of growing, start growing.
   667  	if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
   668  		hashGrow(t, h)
   669  		goto again // Growing the table invalidates everything, so try again
   670  	}
   671  
   672  	if insertb == nil {
   673  		// all current buckets are full, allocate a new one.
   674  		insertb = h.newoverflow(t, b)
   675  		inserti = 0 // not necessary, but avoids needlessly spilling inserti
   676  	}
   677  	insertb.tophash[inserti&(bucketCnt-1)] = tophash(hash) // mask inserti to avoid bounds checks
   678  
   679  	insertk = add(unsafe.Pointer(insertb), dataOffset+inserti*8)
   680  	// store new key at insert position
   681  	*(*unsafe.Pointer)(insertk) = key
   682  
   683  	h.count++
   684  
   685  done:
   686  	val := add(unsafe.Pointer(insertb), dataOffset+bucketCnt*8+inserti*uintptr(t.valuesize))
   687  	if h.flags&hashWriting == 0 {
   688  		throw("concurrent map writes")
   689  	}
   690  	h.flags &^= hashWriting
   691  	return val
   692  }
   693  
   694  func mapassign_faststr(t *maptype, h *hmap, s string) unsafe.Pointer {
   695  	if h == nil {
   696  		panic(plainError("assignment to entry in nil map"))
   697  	}
   698  	if raceenabled {
   699  		callerpc := getcallerpc()
   700  		racewritepc(unsafe.Pointer(h), callerpc, funcPC(mapassign_faststr))
   701  	}
   702  	if h.flags&hashWriting != 0 {
   703  		throw("concurrent map writes")
   704  	}
   705  	key := stringStructOf(&s)
   706  	hash := t.key.alg.hash(noescape(unsafe.Pointer(&s)), uintptr(h.hash0))
   707  
   708  	// Set hashWriting after calling alg.hash for consistency with mapassign.
   709  	h.flags |= hashWriting
   710  
   711  	if h.buckets == nil {
   712  		h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
   713  	}
   714  
   715  again:
   716  	bucket := hash & bucketMask(h.B)
   717  	if h.growing() {
   718  		growWork_faststr(t, h, bucket)
   719  	}
   720  	b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize)))
   721  	top := tophash(hash)
   722  
   723  	var insertb *bmap
   724  	var inserti uintptr
   725  	var insertk unsafe.Pointer
   726  
   727  	for {
   728  		for i := uintptr(0); i < bucketCnt; i++ {
   729  			if b.tophash[i] != top {
   730  				if b.tophash[i] == empty && insertb == nil {
   731  					insertb = b
   732  					inserti = i
   733  				}
   734  				continue
   735  			}
   736  			k := (*stringStruct)(add(unsafe.Pointer(b), dataOffset+i*2*sys.PtrSize))
   737  			if k.len != key.len {
   738  				continue
   739  			}
   740  			if k.str != key.str && !memequal(k.str, key.str, uintptr(key.len)) {
   741  				continue
   742  			}
   743  			// already have a mapping for key. Update it.
   744  			inserti = i
   745  			insertb = b
   746  			goto done
   747  		}
   748  		ovf := b.overflow(t)
   749  		if ovf == nil {
   750  			break
   751  		}
   752  		b = ovf
   753  	}
   754  
   755  	// Did not find mapping for key. Allocate new cell & add entry.
   756  
   757  	// If we hit the max load factor or we have too many overflow buckets,
   758  	// and we're not already in the middle of growing, start growing.
   759  	if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
   760  		hashGrow(t, h)
   761  		goto again // Growing the table invalidates everything, so try again
   762  	}
   763  
   764  	if insertb == nil {
   765  		// all current buckets are full, allocate a new one.
   766  		insertb = h.newoverflow(t, b)
   767  		inserti = 0 // not necessary, but avoids needlessly spilling inserti
   768  	}
   769  	insertb.tophash[inserti&(bucketCnt-1)] = top // mask inserti to avoid bounds checks
   770  
   771  	insertk = add(unsafe.Pointer(insertb), dataOffset+inserti*2*sys.PtrSize)
   772  	// store new key at insert position
   773  	*((*stringStruct)(insertk)) = *key
   774  	h.count++
   775  
   776  done:
   777  	val := add(unsafe.Pointer(insertb), dataOffset+bucketCnt*2*sys.PtrSize+inserti*uintptr(t.valuesize))
   778  	if h.flags&hashWriting == 0 {
   779  		throw("concurrent map writes")
   780  	}
   781  	h.flags &^= hashWriting
   782  	return val
   783  }
   784  
   785  func mapdelete_fast32(t *maptype, h *hmap, key uint32) {
   786  	if raceenabled && h != nil {
   787  		callerpc := getcallerpc()
   788  		racewritepc(unsafe.Pointer(h), callerpc, funcPC(mapdelete_fast32))
   789  	}
   790  	if h == nil || h.count == 0 {
   791  		return
   792  	}
   793  	if h.flags&hashWriting != 0 {
   794  		throw("concurrent map writes")
   795  	}
   796  
   797  	hash := t.key.alg.hash(noescape(unsafe.Pointer(&key)), uintptr(h.hash0))
   798  
   799  	// Set hashWriting after calling alg.hash for consistency with mapdelete
   800  	h.flags |= hashWriting
   801  
   802  	bucket := hash & bucketMask(h.B)
   803  	if h.growing() {
   804  		growWork_fast32(t, h, bucket)
   805  	}
   806  	b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))
   807  search:
   808  	for ; b != nil; b = b.overflow(t) {
   809  		for i, k := uintptr(0), b.keys(); i < bucketCnt; i, k = i+1, add(k, 4) {
   810  			if key != *(*uint32)(k) || b.tophash[i] == empty {
   811  				continue
   812  			}
   813  			// Only clear key if there are pointers in it.
   814  			if t.key.kind&kindNoPointers == 0 {
   815  				memclrHasPointers(k, t.key.size)
   816  			}
   817  			// Only clear value if there are pointers in it.
   818  			if t.elem.kind&kindNoPointers == 0 {
   819  				v := add(unsafe.Pointer(b), dataOffset+bucketCnt*4+i*uintptr(t.valuesize))
   820  				memclrHasPointers(v, t.elem.size)
   821  			}
   822  			b.tophash[i] = empty
   823  			h.count--
   824  			break search
   825  		}
   826  	}
   827  
   828  	if h.flags&hashWriting == 0 {
   829  		throw("concurrent map writes")
   830  	}
   831  	h.flags &^= hashWriting
   832  }
   833  
   834  func mapdelete_fast64(t *maptype, h *hmap, key uint64) {
   835  	if raceenabled && h != nil {
   836  		callerpc := getcallerpc()
   837  		racewritepc(unsafe.Pointer(h), callerpc, funcPC(mapdelete_fast64))
   838  	}
   839  	if h == nil || h.count == 0 {
   840  		return
   841  	}
   842  	if h.flags&hashWriting != 0 {
   843  		throw("concurrent map writes")
   844  	}
   845  
   846  	hash := t.key.alg.hash(noescape(unsafe.Pointer(&key)), uintptr(h.hash0))
   847  
   848  	// Set hashWriting after calling alg.hash for consistency with mapdelete
   849  	h.flags |= hashWriting
   850  
   851  	bucket := hash & bucketMask(h.B)
   852  	if h.growing() {
   853  		growWork_fast64(t, h, bucket)
   854  	}
   855  	b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))
   856  search:
   857  	for ; b != nil; b = b.overflow(t) {
   858  		for i, k := uintptr(0), b.keys(); i < bucketCnt; i, k = i+1, add(k, 8) {
   859  			if key != *(*uint64)(k) || b.tophash[i] == empty {
   860  				continue
   861  			}
   862  			// Only clear key if there are pointers in it.
   863  			if t.key.kind&kindNoPointers == 0 {
   864  				memclrHasPointers(k, t.key.size)
   865  			}
   866  			// Only clear value if there are pointers in it.
   867  			if t.elem.kind&kindNoPointers == 0 {
   868  				v := add(unsafe.Pointer(b), dataOffset+bucketCnt*8+i*uintptr(t.valuesize))
   869  				memclrHasPointers(v, t.elem.size)
   870  			}
   871  			b.tophash[i] = empty
   872  			h.count--
   873  			break search
   874  		}
   875  	}
   876  
   877  	if h.flags&hashWriting == 0 {
   878  		throw("concurrent map writes")
   879  	}
   880  	h.flags &^= hashWriting
   881  }
   882  
   883  func mapdelete_faststr(t *maptype, h *hmap, ky string) {
   884  	if raceenabled && h != nil {
   885  		callerpc := getcallerpc()
   886  		racewritepc(unsafe.Pointer(h), callerpc, funcPC(mapdelete_faststr))
   887  	}
   888  	if h == nil || h.count == 0 {
   889  		return
   890  	}
   891  	if h.flags&hashWriting != 0 {
   892  		throw("concurrent map writes")
   893  	}
   894  
   895  	key := stringStructOf(&ky)
   896  	hash := t.key.alg.hash(noescape(unsafe.Pointer(&ky)), uintptr(h.hash0))
   897  
   898  	// Set hashWriting after calling alg.hash for consistency with mapdelete
   899  	h.flags |= hashWriting
   900  
   901  	bucket := hash & bucketMask(h.B)
   902  	if h.growing() {
   903  		growWork_faststr(t, h, bucket)
   904  	}
   905  	b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))
   906  	top := tophash(hash)
   907  search:
   908  	for ; b != nil; b = b.overflow(t) {
   909  		for i, kptr := uintptr(0), b.keys(); i < bucketCnt; i, kptr = i+1, add(kptr, 2*sys.PtrSize) {
   910  			k := (*stringStruct)(kptr)
   911  			if k.len != key.len || b.tophash[i] != top {
   912  				continue
   913  			}
   914  			if k.str != key.str && !memequal(k.str, key.str, uintptr(key.len)) {
   915  				continue
   916  			}
   917  			// Clear key's pointer.
   918  			k.str = nil
   919  			// Only clear value if there are pointers in it.
   920  			if t.elem.kind&kindNoPointers == 0 {
   921  				v := add(unsafe.Pointer(b), dataOffset+bucketCnt*2*sys.PtrSize+i*uintptr(t.valuesize))
   922  				memclrHasPointers(v, t.elem.size)
   923  			}
   924  			b.tophash[i] = empty
   925  			h.count--
   926  			break search
   927  		}
   928  	}
   929  
   930  	if h.flags&hashWriting == 0 {
   931  		throw("concurrent map writes")
   932  	}
   933  	h.flags &^= hashWriting
   934  }
   935  
   936  func growWork_fast32(t *maptype, h *hmap, bucket uintptr) {
   937  	// make sure we evacuate the oldbucket corresponding
   938  	// to the bucket we're about to use
   939  	evacuate_fast32(t, h, bucket&h.oldbucketmask())
   940  
   941  	// evacuate one more oldbucket to make progress on growing
   942  	if h.growing() {
   943  		evacuate_fast32(t, h, h.nevacuate)
   944  	}
   945  }
   946  
   947  func evacuate_fast32(t *maptype, h *hmap, oldbucket uintptr) {
   948  	b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
   949  	newbit := h.noldbuckets()
   950  	if !evacuated(b) {
   951  		// TODO: reuse overflow buckets instead of using new ones, if there
   952  		// is no iterator using the old buckets.  (If !oldIterator.)
   953  
   954  		// xy contains the x and y (low and high) evacuation destinations.
   955  		var xy [2]evacDst
   956  		x := &xy[0]
   957  		x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize)))
   958  		x.k = add(unsafe.Pointer(x.b), dataOffset)
   959  		x.v = add(x.k, bucketCnt*4)
   960  
   961  		if !h.sameSizeGrow() {
   962  			// Only calculate y pointers if we're growing bigger.
   963  			// Otherwise GC can see bad pointers.
   964  			y := &xy[1]
   965  			y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize)))
   966  			y.k = add(unsafe.Pointer(y.b), dataOffset)
   967  			y.v = add(y.k, bucketCnt*4)
   968  		}
   969  
   970  		for ; b != nil; b = b.overflow(t) {
   971  			k := add(unsafe.Pointer(b), dataOffset)
   972  			v := add(k, bucketCnt*4)
   973  			for i := 0; i < bucketCnt; i, k, v = i+1, add(k, 4), add(v, uintptr(t.valuesize)) {
   974  				top := b.tophash[i]
   975  				if top == empty {
   976  					b.tophash[i] = evacuatedEmpty
   977  					continue
   978  				}
   979  				if top < minTopHash {
   980  					throw("bad map state")
   981  				}
   982  				var useY uint8
   983  				if !h.sameSizeGrow() {
   984  					// Compute hash to make our evacuation decision (whether we need
   985  					// to send this key/value to bucket x or bucket y).
   986  					hash := t.key.alg.hash(k, uintptr(h.hash0))
   987  					if hash&newbit != 0 {
   988  						useY = 1
   989  					}
   990  				}
   991  
   992  				b.tophash[i] = evacuatedX + useY // evacuatedX + 1 == evacuatedY, enforced in makemap
   993  				dst := &xy[useY]                 // evacuation destination
   994  
   995  				if dst.i == bucketCnt {
   996  					dst.b = h.newoverflow(t, dst.b)
   997  					dst.i = 0
   998  					dst.k = add(unsafe.Pointer(dst.b), dataOffset)
   999  					dst.v = add(dst.k, bucketCnt*4)
  1000  				}
  1001  				dst.b.tophash[dst.i&(bucketCnt-1)] = top // mask dst.i as an optimization, to avoid a bounds check
  1002  
  1003  				// Copy key.
  1004  				if sys.PtrSize == 4 && t.key.kind&kindNoPointers == 0 && writeBarrier.enabled {
  1005  					writebarrierptr((*uintptr)(dst.k), *(*uintptr)(k))
  1006  				} else {
  1007  					*(*uint32)(dst.k) = *(*uint32)(k)
  1008  				}
  1009  
  1010  				typedmemmove(t.elem, dst.v, v)
  1011  				dst.i++
  1012  				// These updates might push these pointers past the end of the
  1013  				// key or value arrays.  That's ok, as we have the overflow pointer
  1014  				// at the end of the bucket to protect against pointing past the
  1015  				// end of the bucket.
  1016  				dst.k = add(dst.k, 4)
  1017  				dst.v = add(dst.v, uintptr(t.valuesize))
  1018  			}
  1019  		}
  1020  		// Unlink the overflow buckets & clear key/value to help GC.
  1021  		if h.flags&oldIterator == 0 && t.bucket.kind&kindNoPointers == 0 {
  1022  			b := add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))
  1023  			// Preserve b.tophash because the evacuation
  1024  			// state is maintained there.
  1025  			ptr := add(b, dataOffset)
  1026  			n := uintptr(t.bucketsize) - dataOffset
  1027  			memclrHasPointers(ptr, n)
  1028  		}
  1029  	}
  1030  
  1031  	if oldbucket == h.nevacuate {
  1032  		advanceEvacuationMark(h, t, newbit)
  1033  	}
  1034  }
  1035  
  1036  func growWork_fast64(t *maptype, h *hmap, bucket uintptr) {
  1037  	// make sure we evacuate the oldbucket corresponding
  1038  	// to the bucket we're about to use
  1039  	evacuate_fast64(t, h, bucket&h.oldbucketmask())
  1040  
  1041  	// evacuate one more oldbucket to make progress on growing
  1042  	if h.growing() {
  1043  		evacuate_fast64(t, h, h.nevacuate)
  1044  	}
  1045  }
  1046  
  1047  func evacuate_fast64(t *maptype, h *hmap, oldbucket uintptr) {
  1048  	b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
  1049  	newbit := h.noldbuckets()
  1050  	if !evacuated(b) {
  1051  		// TODO: reuse overflow buckets instead of using new ones, if there
  1052  		// is no iterator using the old buckets.  (If !oldIterator.)
  1053  
  1054  		// xy contains the x and y (low and high) evacuation destinations.
  1055  		var xy [2]evacDst
  1056  		x := &xy[0]
  1057  		x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize)))
  1058  		x.k = add(unsafe.Pointer(x.b), dataOffset)
  1059  		x.v = add(x.k, bucketCnt*8)
  1060  
  1061  		if !h.sameSizeGrow() {
  1062  			// Only calculate y pointers if we're growing bigger.
  1063  			// Otherwise GC can see bad pointers.
  1064  			y := &xy[1]
  1065  			y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize)))
  1066  			y.k = add(unsafe.Pointer(y.b), dataOffset)
  1067  			y.v = add(y.k, bucketCnt*8)
  1068  		}
  1069  
  1070  		for ; b != nil; b = b.overflow(t) {
  1071  			k := add(unsafe.Pointer(b), dataOffset)
  1072  			v := add(k, bucketCnt*8)
  1073  			for i := 0; i < bucketCnt; i, k, v = i+1, add(k, 8), add(v, uintptr(t.valuesize)) {
  1074  				top := b.tophash[i]
  1075  				if top == empty {
  1076  					b.tophash[i] = evacuatedEmpty
  1077  					continue
  1078  				}
  1079  				if top < minTopHash {
  1080  					throw("bad map state")
  1081  				}
  1082  				var useY uint8
  1083  				if !h.sameSizeGrow() {
  1084  					// Compute hash to make our evacuation decision (whether we need
  1085  					// to send this key/value to bucket x or bucket y).
  1086  					hash := t.key.alg.hash(k, uintptr(h.hash0))
  1087  					if hash&newbit != 0 {
  1088  						useY = 1
  1089  					}
  1090  				}
  1091  
  1092  				b.tophash[i] = evacuatedX + useY // evacuatedX + 1 == evacuatedY, enforced in makemap
  1093  				dst := &xy[useY]                 // evacuation destination
  1094  
  1095  				if dst.i == bucketCnt {
  1096  					dst.b = h.newoverflow(t, dst.b)
  1097  					dst.i = 0
  1098  					dst.k = add(unsafe.Pointer(dst.b), dataOffset)
  1099  					dst.v = add(dst.k, bucketCnt*8)
  1100  				}
  1101  				dst.b.tophash[dst.i&(bucketCnt-1)] = top // mask dst.i as an optimization, to avoid a bounds check
  1102  
  1103  				// Copy key.
  1104  				if t.key.kind&kindNoPointers == 0 && writeBarrier.enabled {
  1105  					if sys.PtrSize == 8 {
  1106  						writebarrierptr((*uintptr)(dst.k), *(*uintptr)(k))
  1107  					} else {
  1108  						// There are three ways to squeeze at least one 32 bit pointer into 64 bits.
  1109  						// Give up and call typedmemmove.
  1110  						typedmemmove(t.key, dst.k, k)
  1111  					}
  1112  				} else {
  1113  					*(*uint64)(dst.k) = *(*uint64)(k)
  1114  				}
  1115  
  1116  				typedmemmove(t.elem, dst.v, v)
  1117  				dst.i++
  1118  				// These updates might push these pointers past the end of the
  1119  				// key or value arrays.  That's ok, as we have the overflow pointer
  1120  				// at the end of the bucket to protect against pointing past the
  1121  				// end of the bucket.
  1122  				dst.k = add(dst.k, 8)
  1123  				dst.v = add(dst.v, uintptr(t.valuesize))
  1124  			}
  1125  		}
  1126  		// Unlink the overflow buckets & clear key/value to help GC.
  1127  		if h.flags&oldIterator == 0 && t.bucket.kind&kindNoPointers == 0 {
  1128  			b := add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))
  1129  			// Preserve b.tophash because the evacuation
  1130  			// state is maintained there.
  1131  			ptr := add(b, dataOffset)
  1132  			n := uintptr(t.bucketsize) - dataOffset
  1133  			memclrHasPointers(ptr, n)
  1134  		}
  1135  	}
  1136  
  1137  	if oldbucket == h.nevacuate {
  1138  		advanceEvacuationMark(h, t, newbit)
  1139  	}
  1140  }
  1141  
  1142  func growWork_faststr(t *maptype, h *hmap, bucket uintptr) {
  1143  	// make sure we evacuate the oldbucket corresponding
  1144  	// to the bucket we're about to use
  1145  	evacuate_faststr(t, h, bucket&h.oldbucketmask())
  1146  
  1147  	// evacuate one more oldbucket to make progress on growing
  1148  	if h.growing() {
  1149  		evacuate_faststr(t, h, h.nevacuate)
  1150  	}
  1151  }
  1152  
  1153  func evacuate_faststr(t *maptype, h *hmap, oldbucket uintptr) {
  1154  	b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
  1155  	newbit := h.noldbuckets()
  1156  	if !evacuated(b) {
  1157  		// TODO: reuse overflow buckets instead of using new ones, if there
  1158  		// is no iterator using the old buckets.  (If !oldIterator.)
  1159  
  1160  		// xy contains the x and y (low and high) evacuation destinations.
  1161  		var xy [2]evacDst
  1162  		x := &xy[0]
  1163  		x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize)))
  1164  		x.k = add(unsafe.Pointer(x.b), dataOffset)
  1165  		x.v = add(x.k, bucketCnt*2*sys.PtrSize)
  1166  
  1167  		if !h.sameSizeGrow() {
  1168  			// Only calculate y pointers if we're growing bigger.
  1169  			// Otherwise GC can see bad pointers.
  1170  			y := &xy[1]
  1171  			y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize)))
  1172  			y.k = add(unsafe.Pointer(y.b), dataOffset)
  1173  			y.v = add(y.k, bucketCnt*2*sys.PtrSize)
  1174  		}
  1175  
  1176  		for ; b != nil; b = b.overflow(t) {
  1177  			k := add(unsafe.Pointer(b), dataOffset)
  1178  			v := add(k, bucketCnt*2*sys.PtrSize)
  1179  			for i := 0; i < bucketCnt; i, k, v = i+1, add(k, 2*sys.PtrSize), add(v, uintptr(t.valuesize)) {
  1180  				top := b.tophash[i]
  1181  				if top == empty {
  1182  					b.tophash[i] = evacuatedEmpty
  1183  					continue
  1184  				}
  1185  				if top < minTopHash {
  1186  					throw("bad map state")
  1187  				}
  1188  				var useY uint8
  1189  				if !h.sameSizeGrow() {
  1190  					// Compute hash to make our evacuation decision (whether we need
  1191  					// to send this key/value to bucket x or bucket y).
  1192  					hash := t.key.alg.hash(k, uintptr(h.hash0))
  1193  					if hash&newbit != 0 {
  1194  						useY = 1
  1195  					}
  1196  				}
  1197  
  1198  				b.tophash[i] = evacuatedX + useY // evacuatedX + 1 == evacuatedY, enforced in makemap
  1199  				dst := &xy[useY]                 // evacuation destination
  1200  
  1201  				if dst.i == bucketCnt {
  1202  					dst.b = h.newoverflow(t, dst.b)
  1203  					dst.i = 0
  1204  					dst.k = add(unsafe.Pointer(dst.b), dataOffset)
  1205  					dst.v = add(dst.k, bucketCnt*2*sys.PtrSize)
  1206  				}
  1207  				dst.b.tophash[dst.i&(bucketCnt-1)] = top // mask dst.i as an optimization, to avoid a bounds check
  1208  
  1209  				// Copy key.
  1210  				*(*string)(dst.k) = *(*string)(k)
  1211  
  1212  				typedmemmove(t.elem, dst.v, v)
  1213  				dst.i++
  1214  				// These updates might push these pointers past the end of the
  1215  				// key or value arrays.  That's ok, as we have the overflow pointer
  1216  				// at the end of the bucket to protect against pointing past the
  1217  				// end of the bucket.
  1218  				dst.k = add(dst.k, 2*sys.PtrSize)
  1219  				dst.v = add(dst.v, uintptr(t.valuesize))
  1220  			}
  1221  		}
  1222  		// Unlink the overflow buckets & clear key/value to help GC.
  1223  		// Unlink the overflow buckets & clear key/value to help GC.
  1224  		if h.flags&oldIterator == 0 && t.bucket.kind&kindNoPointers == 0 {
  1225  			b := add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))
  1226  			// Preserve b.tophash because the evacuation
  1227  			// state is maintained there.
  1228  			ptr := add(b, dataOffset)
  1229  			n := uintptr(t.bucketsize) - dataOffset
  1230  			memclrHasPointers(ptr, n)
  1231  		}
  1232  	}
  1233  
  1234  	if oldbucket == h.nevacuate {
  1235  		advanceEvacuationMark(h, t, newbit)
  1236  	}
  1237  }
  1238  

View as plain text