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