1 package xsync
2 3 import (
4 "fmt"
5 "math"
6 "runtime"
7 "strings"
8 "sync"
9 "sync/atomic"
10 "unsafe"
11 )
12 13 type mapResizeHint int
14 15 const (
16 mapGrowHint mapResizeHint = 0
17 mapShrinkHint mapResizeHint = 1
18 mapClearHint mapResizeHint = 2
19 )
20 21 const (
22 // number of Map entries per bucket; 3 entries lead to size of 64B
23 // (one cache line) on 64-bit machines
24 entriesPerMapBucket = 3
25 // threshold fraction of table occupation to start a table shrinking
26 // when deleting the last entry in a bucket chain
27 mapShrinkFraction = 128
28 // map load factor to trigger a table resize during insertion;
29 // a map holds up to mapLoadFactor*entriesPerMapBucket*mapTableLen
30 // key-value pairs (this is a soft limit)
31 mapLoadFactor = 0.75
32 // minimal table size, i.e. number of buckets; thus, minimal map
33 // capacity can be calculated as entriesPerMapBucket*defaultMinMapTableLen
34 defaultMinMapTableLen = 32
35 // minimum counter stripes to use
36 minMapCounterLen = 8
37 // maximum counter stripes to use; stands for around 4KB of memory
38 maxMapCounterLen = 32
39 )
40 41 var (
42 topHashMask = uint64((1<<20)-1) << 44
43 topHashEntryMasks = [3]uint64{
44 topHashMask,
45 topHashMask >> 20,
46 topHashMask >> 40,
47 }
48 )
49 50 // Map is like a Go map[string]interface{} but is safe for concurrent
51 // use by multiple goroutines without additional locking or
52 // coordination. It follows the interface of sync.Map with
53 // a number of valuable extensions like Compute or Size.
54 //
55 // A Map must not be copied after first use.
56 //
57 // Map uses a modified version of Cache-Line Hash Table (CLHT)
58 // data structure: https://github.com/LPD-EPFL/CLHT
59 //
60 // CLHT is built around idea to organize the hash table in
61 // cache-line-sized buckets, so that on all modern CPUs update
62 // operations complete with at most one cache-line transfer.
63 // Also, Get operations involve no write to memory, as well as no
64 // mutexes or any other sort of locks. Due to this design, in all
65 // considered scenarios Map outperforms sync.Map.
66 //
67 // One important difference with sync.Map is that only string keys
68 // are supported. That's because Golang standard library does not
69 // expose the built-in hash functions for interface{} values.
70 type Map struct {
71 totalGrowths int64
72 totalShrinks int64
73 resizing int64 // resize in progress flag; updated atomically
74 resizeMu sync.Mutex // only used along with resizeCond
75 resizeCond sync.Cond // used to wake up resize waiters (concurrent modifications)
76 table unsafe.Pointer // *mapTable
77 minTableLen int
78 growOnly bool
79 }
80 81 type mapTable struct {
82 buckets []bucketPadded
83 // striped counter for number of table entries;
84 // used to determine if a table shrinking is needed
85 // occupies min(buckets_memory/1024, 64KB) of memory
86 size []counterStripe
87 seed uint64
88 }
89 90 type counterStripe struct {
91 c int64
92 //lint:ignore U1000 prevents false sharing
93 pad [cacheLineSize - 8]byte
94 }
95 96 type bucketPadded struct {
97 //lint:ignore U1000 ensure each bucket takes two cache lines on both 32 and 64-bit archs
98 pad [cacheLineSize - unsafe.Sizeof(bucket{})]byte
99 bucket
100 }
101 102 type bucket struct {
103 next unsafe.Pointer // *bucketPadded
104 keys [entriesPerMapBucket]unsafe.Pointer
105 values [entriesPerMapBucket]unsafe.Pointer
106 // topHashMutex is a 2-in-1 value.
107 //
108 // It contains packed top 20 bits (20 MSBs) of hash codes for keys
109 // stored in the bucket:
110 // | key 0's top hash | key 1's top hash | key 2's top hash | bitmap for keys | mutex |
111 // | 20 bits | 20 bits | 20 bits | 3 bits | 1 bit |
112 //
113 // The least significant bit is used for the mutex (TTAS spinlock).
114 topHashMutex uint64
115 }
116 117 type rangeEntry struct {
118 key unsafe.Pointer
119 value unsafe.Pointer
120 }
121 122 // MapConfig defines configurable Map/MapOf options.
123 type MapConfig struct {
124 sizeHint int
125 growOnly bool
126 }
127 128 // WithPresize configures new Map/MapOf instance with capacity enough
129 // to hold sizeHint entries. The capacity is treated as the minimal
130 // capacity meaning that the underlying hash table will never shrink
131 // to a smaller capacity. If sizeHint is zero or negative, the value
132 // is ignored.
133 func WithPresize(sizeHint int) func(*MapConfig) {
134 return func(c *MapConfig) {
135 c.sizeHint = sizeHint
136 }
137 }
138 139 // WithGrowOnly configures new Map/MapOf instance to be grow-only.
140 // This means that the underlying hash table grows in capacity when
141 // new keys are added, but does not shrink when keys are deleted.
142 // The only exception to this rule is the Clear method which
143 // shrinks the hash table back to the initial capacity.
144 func WithGrowOnly() func(*MapConfig) {
145 return func(c *MapConfig) {
146 c.growOnly = true
147 }
148 }
149 150 // NewMap creates a new Map instance configured with the given
151 // options.
152 func NewMap(options ...func(*MapConfig)) *Map {
153 c := &MapConfig{
154 sizeHint: defaultMinMapTableLen * entriesPerMapBucket,
155 }
156 for _, o := range options {
157 o(c)
158 }
159 160 m := &Map{}
161 m.resizeCond = *sync.NewCond(&m.resizeMu)
162 var table *mapTable
163 if c.sizeHint <= defaultMinMapTableLen*entriesPerMapBucket {
164 table = newMapTable(defaultMinMapTableLen)
165 } else {
166 tableLen := nextPowOf2(uint32((float64(c.sizeHint) / entriesPerMapBucket) / mapLoadFactor))
167 table = newMapTable(int(tableLen))
168 }
169 m.minTableLen = len(table.buckets)
170 m.growOnly = c.growOnly
171 atomic.StorePointer(&m.table, unsafe.Pointer(table))
172 return m
173 }
174 175 // NewMapPresized creates a new Map instance with capacity enough to hold
176 // sizeHint entries. The capacity is treated as the minimal capacity
177 // meaning that the underlying hash table will never shrink to
178 // a smaller capacity. If sizeHint is zero or negative, the value
179 // is ignored.
180 //
181 // Deprecated: use NewMap in combination with WithPresize.
182 func NewMapPresized(sizeHint int) *Map {
183 return NewMap(WithPresize(sizeHint))
184 }
185 186 func newMapTable(minTableLen int) *mapTable {
187 buckets := make([]bucketPadded, minTableLen)
188 counterLen := minTableLen >> 10
189 if counterLen < minMapCounterLen {
190 counterLen = minMapCounterLen
191 } else if counterLen > maxMapCounterLen {
192 counterLen = maxMapCounterLen
193 }
194 counter := make([]counterStripe, counterLen)
195 t := &mapTable{
196 buckets: buckets,
197 size: counter,
198 seed: makeSeed(),
199 }
200 return t
201 }
202 203 // ToPlainMap returns a native map with a copy of xsync Map's
204 // contents. The copied xsync Map should not be modified while
205 // this call is made. If the copied Map is modified, the copying
206 // behavior is the same as in the Range method.
207 func ToPlainMap(m *Map) map[string]interface{} {
208 pm := make(map[string]interface{})
209 if m != nil {
210 m.Range(func(key string, value interface{}) bool {
211 pm[key] = value
212 return true
213 })
214 }
215 return pm
216 }
217 218 // Load returns the value stored in the map for a key, or nil if no
219 // value is present.
220 // The ok result indicates whether value was found in the map.
221 func (m *Map) Load(key string) (value interface{}, ok bool) {
222 table := (*mapTable)(atomic.LoadPointer(&m.table))
223 hash := hashString(key, table.seed)
224 bidx := uint64(len(table.buckets)-1) & hash
225 b := &table.buckets[bidx]
226 for {
227 topHashes := atomic.LoadUint64(&b.topHashMutex)
228 for i := 0; i < entriesPerMapBucket; i++ {
229 if !topHashMatch(hash, topHashes, i) {
230 continue
231 }
232 atomic_snapshot:
233 // Start atomic snapshot.
234 vp := atomic.LoadPointer(&b.values[i])
235 kp := atomic.LoadPointer(&b.keys[i])
236 if kp != nil && vp != nil {
237 if key == derefKey(kp) {
238 if uintptr(vp) == uintptr(atomic.LoadPointer(&b.values[i])) {
239 // Atomic snapshot succeeded.
240 return derefValue(vp), true
241 }
242 // Concurrent update/remove. Go for another spin.
243 goto atomic_snapshot
244 }
245 }
246 }
247 bptr := atomic.LoadPointer(&b.next)
248 if bptr == nil {
249 return
250 }
251 b = (*bucketPadded)(bptr)
252 }
253 }
254 255 // Store sets the value for a key.
256 func (m *Map) Store(key string, value interface{}) {
257 m.doCompute(
258 key,
259 func(interface{}, bool) (interface{}, bool) {
260 return value, false
261 },
262 false,
263 false,
264 )
265 }
266 267 // LoadOrStore returns the existing value for the key if present.
268 // Otherwise, it stores and returns the given value.
269 // The loaded result is true if the value was loaded, false if stored.
270 func (m *Map) LoadOrStore(key string, value interface{}) (actual interface{}, loaded bool) {
271 return m.doCompute(
272 key,
273 func(interface{}, bool) (interface{}, bool) {
274 return value, false
275 },
276 true,
277 false,
278 )
279 }
280 281 // LoadAndStore returns the existing value for the key if present,
282 // while setting the new value for the key.
283 // It stores the new value and returns the existing one, if present.
284 // The loaded result is true if the existing value was loaded,
285 // false otherwise.
286 func (m *Map) LoadAndStore(key string, value interface{}) (actual interface{}, loaded bool) {
287 return m.doCompute(
288 key,
289 func(interface{}, bool) (interface{}, bool) {
290 return value, false
291 },
292 false,
293 false,
294 )
295 }
296 297 // LoadOrCompute returns the existing value for the key if present.
298 // Otherwise, it computes the value using the provided function, and
299 // then stores and returns the computed value. The loaded result is
300 // true if the value was loaded, false if computed.
301 //
302 // This call locks a hash table bucket while the compute function
303 // is executed. It means that modifications on other entries in
304 // the bucket will be blocked until the valueFn executes. Consider
305 // this when the function includes long-running operations.
306 func (m *Map) LoadOrCompute(key string, valueFn func() interface{}) (actual interface{}, loaded bool) {
307 return m.doCompute(
308 key,
309 func(interface{}, bool) (interface{}, bool) {
310 return valueFn(), false
311 },
312 true,
313 false,
314 )
315 }
316 317 // LoadOrTryCompute returns the existing value for the key if present.
318 // Otherwise, it tries to compute the value using the provided function
319 // and, if successful, stores and returns the computed value. The loaded
320 // result is true if the value was loaded, or false if computed (whether
321 // successfully or not). If the compute attempt was cancelled (due to an
322 // error, for example), a nil value will be returned.
323 //
324 // This call locks a hash table bucket while the compute function
325 // is executed. It means that modifications on other entries in
326 // the bucket will be blocked until the valueFn executes. Consider
327 // this when the function includes long-running operations.
328 func (m *Map) LoadOrTryCompute(
329 key string,
330 valueFn func() (newValue interface{}, cancel bool),
331 ) (value interface{}, loaded bool) {
332 return m.doCompute(
333 key,
334 func(interface{}, bool) (interface{}, bool) {
335 nv, c := valueFn()
336 if !c {
337 return nv, false
338 }
339 return nil, true
340 },
341 true,
342 false,
343 )
344 }
345 346 // Compute either sets the computed new value for the key or deletes
347 // the value for the key. When the delete result of the valueFn function
348 // is set to true, the value will be deleted, if it exists. When delete
349 // is set to false, the value is updated to the newValue.
350 // The ok result indicates whether value was computed and stored, thus, is
351 // present in the map. The actual result contains the new value in cases where
352 // the value was computed and stored. See the example for a few use cases.
353 //
354 // This call locks a hash table bucket while the compute function
355 // is executed. It means that modifications on other entries in
356 // the bucket will be blocked until the valueFn executes. Consider
357 // this when the function includes long-running operations.
358 func (m *Map) Compute(
359 key string,
360 valueFn func(oldValue interface{}, loaded bool) (newValue interface{}, delete bool),
361 ) (actual interface{}, ok bool) {
362 return m.doCompute(key, valueFn, false, true)
363 }
364 365 // LoadAndDelete deletes the value for a key, returning the previous
366 // value if any. The loaded result reports whether the key was
367 // present.
368 func (m *Map) LoadAndDelete(key string) (value interface{}, loaded bool) {
369 return m.doCompute(
370 key,
371 func(value interface{}, loaded bool) (interface{}, bool) {
372 return value, true
373 },
374 false,
375 false,
376 )
377 }
378 379 // Delete deletes the value for a key.
380 func (m *Map) Delete(key string) {
381 m.doCompute(
382 key,
383 func(value interface{}, loaded bool) (interface{}, bool) {
384 return value, true
385 },
386 false,
387 false,
388 )
389 }
390 391 func (m *Map) doCompute(
392 key string,
393 valueFn func(oldValue interface{}, loaded bool) (interface{}, bool),
394 loadIfExists, computeOnly bool,
395 ) (interface{}, bool) {
396 // Read-only path.
397 if loadIfExists {
398 if v, ok := m.Load(key); ok {
399 return v, !computeOnly
400 }
401 }
402 // Write path.
403 for {
404 compute_attempt:
405 var (
406 emptyb *bucketPadded
407 emptyidx int
408 hintNonEmpty int
409 )
410 table := (*mapTable)(atomic.LoadPointer(&m.table))
411 tableLen := len(table.buckets)
412 hash := hashString(key, table.seed)
413 bidx := uint64(len(table.buckets)-1) & hash
414 rootb := &table.buckets[bidx]
415 lockBucket(&rootb.topHashMutex)
416 // The following two checks must go in reverse to what's
417 // in the resize method.
418 if m.resizeInProgress() {
419 // Resize is in progress. Wait, then go for another attempt.
420 unlockBucket(&rootb.topHashMutex)
421 m.waitForResize()
422 goto compute_attempt
423 }
424 if m.newerTableExists(table) {
425 // Someone resized the table. Go for another attempt.
426 unlockBucket(&rootb.topHashMutex)
427 goto compute_attempt
428 }
429 b := rootb
430 for {
431 topHashes := atomic.LoadUint64(&b.topHashMutex)
432 for i := 0; i < entriesPerMapBucket; i++ {
433 if b.keys[i] == nil {
434 if emptyb == nil {
435 emptyb = b
436 emptyidx = i
437 }
438 continue
439 }
440 if !topHashMatch(hash, topHashes, i) {
441 hintNonEmpty++
442 continue
443 }
444 if key == derefKey(b.keys[i]) {
445 vp := b.values[i]
446 if loadIfExists {
447 unlockBucket(&rootb.topHashMutex)
448 return derefValue(vp), !computeOnly
449 }
450 // In-place update/delete.
451 // We get a copy of the value via an interface{} on each call,
452 // thus the live value pointers are unique. Otherwise atomic
453 // snapshot won't be correct in case of multiple Store calls
454 // using the same value.
455 oldValue := derefValue(vp)
456 newValue, del := valueFn(oldValue, true)
457 if del {
458 // Deletion.
459 // First we update the value, then the key.
460 // This is important for atomic snapshot states.
461 atomic.StoreUint64(&b.topHashMutex, eraseTopHash(topHashes, i))
462 atomic.StorePointer(&b.values[i], nil)
463 atomic.StorePointer(&b.keys[i], nil)
464 leftEmpty := false
465 if hintNonEmpty == 0 {
466 leftEmpty = isEmptyBucket(b)
467 }
468 unlockBucket(&rootb.topHashMutex)
469 table.addSize(bidx, -1)
470 // Might need to shrink the table.
471 if leftEmpty {
472 m.resize(table, mapShrinkHint)
473 }
474 return oldValue, !computeOnly
475 }
476 nvp := unsafe.Pointer(&newValue)
477 if assertionsEnabled && vp == nvp {
478 panic("non-unique value pointer")
479 }
480 atomic.StorePointer(&b.values[i], nvp)
481 unlockBucket(&rootb.topHashMutex)
482 if computeOnly {
483 // Compute expects the new value to be returned.
484 return newValue, true
485 }
486 // LoadAndStore expects the old value to be returned.
487 return oldValue, true
488 }
489 hintNonEmpty++
490 }
491 if b.next == nil {
492 if emptyb != nil {
493 // Insertion into an existing bucket.
494 var zeroV interface{}
495 newValue, del := valueFn(zeroV, false)
496 if del {
497 unlockBucket(&rootb.topHashMutex)
498 return zeroV, false
499 }
500 // First we update the value, then the key.
501 // This is important for atomic snapshot states.
502 topHashes = atomic.LoadUint64(&emptyb.topHashMutex)
503 atomic.StoreUint64(&emptyb.topHashMutex, storeTopHash(hash, topHashes, emptyidx))
504 atomic.StorePointer(&emptyb.values[emptyidx], unsafe.Pointer(&newValue))
505 atomic.StorePointer(&emptyb.keys[emptyidx], unsafe.Pointer(&key))
506 unlockBucket(&rootb.topHashMutex)
507 table.addSize(bidx, 1)
508 return newValue, computeOnly
509 }
510 growThreshold := float64(tableLen) * entriesPerMapBucket * mapLoadFactor
511 if table.sumSize() > int64(growThreshold) {
512 // Need to grow the table. Then go for another attempt.
513 unlockBucket(&rootb.topHashMutex)
514 m.resize(table, mapGrowHint)
515 goto compute_attempt
516 }
517 // Insertion into a new bucket.
518 var zeroV interface{}
519 newValue, del := valueFn(zeroV, false)
520 if del {
521 unlockBucket(&rootb.topHashMutex)
522 return newValue, false
523 }
524 // Create and append a bucket.
525 newb := new(bucketPadded)
526 newb.keys[0] = unsafe.Pointer(&key)
527 newb.values[0] = unsafe.Pointer(&newValue)
528 newb.topHashMutex = storeTopHash(hash, newb.topHashMutex, 0)
529 atomic.StorePointer(&b.next, unsafe.Pointer(newb))
530 unlockBucket(&rootb.topHashMutex)
531 table.addSize(bidx, 1)
532 return newValue, computeOnly
533 }
534 b = (*bucketPadded)(b.next)
535 }
536 }
537 }
538 539 func (m *Map) newerTableExists(table *mapTable) bool {
540 curTablePtr := atomic.LoadPointer(&m.table)
541 return uintptr(curTablePtr) != uintptr(unsafe.Pointer(table))
542 }
543 544 func (m *Map) resizeInProgress() bool {
545 return atomic.LoadInt64(&m.resizing) == 1
546 }
547 548 func (m *Map) waitForResize() {
549 m.resizeMu.Lock()
550 for m.resizeInProgress() {
551 m.resizeCond.Wait()
552 }
553 m.resizeMu.Unlock()
554 }
555 556 func (m *Map) resize(knownTable *mapTable, hint mapResizeHint) {
557 knownTableLen := len(knownTable.buckets)
558 // Fast path for shrink attempts.
559 if hint == mapShrinkHint {
560 if m.growOnly ||
561 m.minTableLen == knownTableLen ||
562 knownTable.sumSize() > int64((knownTableLen*entriesPerMapBucket)/mapShrinkFraction) {
563 return
564 }
565 }
566 // Slow path.
567 if !atomic.CompareAndSwapInt64(&m.resizing, 0, 1) {
568 // Someone else started resize. Wait for it to finish.
569 m.waitForResize()
570 return
571 }
572 var newTable *mapTable
573 table := (*mapTable)(atomic.LoadPointer(&m.table))
574 tableLen := len(table.buckets)
575 switch hint {
576 case mapGrowHint:
577 // Grow the table with factor of 2.
578 atomic.AddInt64(&m.totalGrowths, 1)
579 newTable = newMapTable(tableLen << 1)
580 case mapShrinkHint:
581 shrinkThreshold := int64((tableLen * entriesPerMapBucket) / mapShrinkFraction)
582 if tableLen > m.minTableLen && table.sumSize() <= shrinkThreshold {
583 // Shrink the table with factor of 2.
584 atomic.AddInt64(&m.totalShrinks, 1)
585 newTable = newMapTable(tableLen >> 1)
586 } else {
587 // No need to shrink. Wake up all waiters and give up.
588 m.resizeMu.Lock()
589 atomic.StoreInt64(&m.resizing, 0)
590 m.resizeCond.Broadcast()
591 m.resizeMu.Unlock()
592 return
593 }
594 case mapClearHint:
595 newTable = newMapTable(m.minTableLen)
596 default:
597 panic(fmt.Sprintf("unexpected resize hint: %d", hint))
598 }
599 // Copy the data only if we're not clearing the map.
600 if hint != mapClearHint {
601 for i := 0; i < tableLen; i++ {
602 copied := copyBucket(&table.buckets[i], newTable)
603 newTable.addSizePlain(uint64(i), copied)
604 }
605 }
606 // Publish the new table and wake up all waiters.
607 atomic.StorePointer(&m.table, unsafe.Pointer(newTable))
608 m.resizeMu.Lock()
609 atomic.StoreInt64(&m.resizing, 0)
610 m.resizeCond.Broadcast()
611 m.resizeMu.Unlock()
612 }
613 614 func copyBucket(b *bucketPadded, destTable *mapTable) (copied int) {
615 rootb := b
616 lockBucket(&rootb.topHashMutex)
617 for {
618 for i := 0; i < entriesPerMapBucket; i++ {
619 if b.keys[i] != nil {
620 k := derefKey(b.keys[i])
621 hash := hashString(k, destTable.seed)
622 bidx := uint64(len(destTable.buckets)-1) & hash
623 destb := &destTable.buckets[bidx]
624 appendToBucket(hash, b.keys[i], b.values[i], destb)
625 copied++
626 }
627 }
628 if b.next == nil {
629 unlockBucket(&rootb.topHashMutex)
630 return
631 }
632 b = (*bucketPadded)(b.next)
633 }
634 }
635 636 func appendToBucket(hash uint64, keyPtr, valPtr unsafe.Pointer, b *bucketPadded) {
637 for {
638 for i := 0; i < entriesPerMapBucket; i++ {
639 if b.keys[i] == nil {
640 b.keys[i] = keyPtr
641 b.values[i] = valPtr
642 b.topHashMutex = storeTopHash(hash, b.topHashMutex, i)
643 return
644 }
645 }
646 if b.next == nil {
647 newb := new(bucketPadded)
648 newb.keys[0] = keyPtr
649 newb.values[0] = valPtr
650 newb.topHashMutex = storeTopHash(hash, newb.topHashMutex, 0)
651 b.next = unsafe.Pointer(newb)
652 return
653 }
654 b = (*bucketPadded)(b.next)
655 }
656 }
657 658 func isEmptyBucket(rootb *bucketPadded) bool {
659 b := rootb
660 for {
661 for i := 0; i < entriesPerMapBucket; i++ {
662 if b.keys[i] != nil {
663 return false
664 }
665 }
666 if b.next == nil {
667 return true
668 }
669 b = (*bucketPadded)(b.next)
670 }
671 }
672 673 // Range calls f sequentially for each key and value present in the
674 // map. If f returns false, range stops the iteration.
675 //
676 // Range does not necessarily correspond to any consistent snapshot
677 // of the Map's contents: no key will be visited more than once, but
678 // if the value for any key is stored or deleted concurrently, Range
679 // may reflect any mapping for that key from any point during the
680 // Range call.
681 //
682 // It is safe to modify the map while iterating it, including entry
683 // creation, modification and deletion. However, the concurrent
684 // modification rule apply, i.e. the changes may be not reflected
685 // in the subsequently iterated entries.
686 func (m *Map) Range(f func(key string, value interface{}) bool) {
687 var zeroEntry rangeEntry
688 // Pre-allocate array big enough to fit entries for most hash tables.
689 bentries := make([]rangeEntry, 0, 16*entriesPerMapBucket)
690 tablep := atomic.LoadPointer(&m.table)
691 table := *(*mapTable)(tablep)
692 for i := range table.buckets {
693 rootb := &table.buckets[i]
694 b := rootb
695 // Prevent concurrent modifications and copy all entries into
696 // the intermediate slice.
697 lockBucket(&rootb.topHashMutex)
698 for {
699 for i := 0; i < entriesPerMapBucket; i++ {
700 if b.keys[i] != nil {
701 bentries = append(bentries, rangeEntry{
702 key: b.keys[i],
703 value: b.values[i],
704 })
705 }
706 }
707 if b.next == nil {
708 unlockBucket(&rootb.topHashMutex)
709 break
710 }
711 b = (*bucketPadded)(b.next)
712 }
713 // Call the function for all copied entries.
714 for j := range bentries {
715 k := derefKey(bentries[j].key)
716 v := derefValue(bentries[j].value)
717 if !f(k, v) {
718 return
719 }
720 // Remove the reference to avoid preventing the copied
721 // entries from being GCed until this method finishes.
722 bentries[j] = zeroEntry
723 }
724 bentries = bentries[:0]
725 }
726 }
727 728 // Clear deletes all keys and values currently stored in the map.
729 func (m *Map) Clear() {
730 table := (*mapTable)(atomic.LoadPointer(&m.table))
731 m.resize(table, mapClearHint)
732 }
733 734 // Size returns current size of the map.
735 func (m *Map) Size() int {
736 table := (*mapTable)(atomic.LoadPointer(&m.table))
737 return int(table.sumSize())
738 }
739 740 func derefKey(keyPtr unsafe.Pointer) string {
741 return *(*string)(keyPtr)
742 }
743 744 func derefValue(valuePtr unsafe.Pointer) interface{} {
745 return *(*interface{})(valuePtr)
746 }
747 748 func lockBucket(mu *uint64) {
749 for {
750 var v uint64
751 for {
752 v = atomic.LoadUint64(mu)
753 if v&1 != 1 {
754 break
755 }
756 runtime.Gosched()
757 }
758 if atomic.CompareAndSwapUint64(mu, v, v|1) {
759 return
760 }
761 runtime.Gosched()
762 }
763 }
764 765 func unlockBucket(mu *uint64) {
766 v := atomic.LoadUint64(mu)
767 atomic.StoreUint64(mu, v&^1)
768 }
769 770 func topHashMatch(hash, topHashes uint64, idx int) bool {
771 if topHashes&(1<<(idx+1)) == 0 {
772 // Entry is not present.
773 return false
774 }
775 hash = hash & topHashMask
776 topHashes = (topHashes & topHashEntryMasks[idx]) << (20 * idx)
777 return hash == topHashes
778 }
779 780 func storeTopHash(hash, topHashes uint64, idx int) uint64 {
781 // Zero out top hash at idx.
782 topHashes = topHashes &^ topHashEntryMasks[idx]
783 // Chop top 20 MSBs of the given hash and position them at idx.
784 hash = (hash & topHashMask) >> (20 * idx)
785 // Store the MSBs.
786 topHashes = topHashes | hash
787 // Mark the entry as present.
788 return topHashes | (1 << (idx + 1))
789 }
790 791 func eraseTopHash(topHashes uint64, idx int) uint64 {
792 return topHashes &^ (1 << (idx + 1))
793 }
794 795 func (table *mapTable) addSize(bucketIdx uint64, delta int) {
796 cidx := uint64(len(table.size)-1) & bucketIdx
797 atomic.AddInt64(&table.size[cidx].c, int64(delta))
798 }
799 800 func (table *mapTable) addSizePlain(bucketIdx uint64, delta int) {
801 cidx := uint64(len(table.size)-1) & bucketIdx
802 table.size[cidx].c += int64(delta)
803 }
804 805 func (table *mapTable) sumSize() int64 {
806 sum := int64(0)
807 for i := range table.size {
808 sum += atomic.LoadInt64(&table.size[i].c)
809 }
810 return sum
811 }
812 813 // MapStats is Map/MapOf statistics.
814 //
815 // Warning: map statistics are intented to be used for diagnostic
816 // purposes, not for production code. This means that breaking changes
817 // may be introduced into this struct even between minor releases.
818 type MapStats struct {
819 // RootBuckets is the number of root buckets in the hash table.
820 // Each bucket holds a few entries.
821 RootBuckets int
822 // TotalBuckets is the total number of buckets in the hash table,
823 // including root and their chained buckets. Each bucket holds
824 // a few entries.
825 TotalBuckets int
826 // EmptyBuckets is the number of buckets that hold no entries.
827 EmptyBuckets int
828 // Capacity is the Map/MapOf capacity, i.e. the total number of
829 // entries that all buckets can physically hold. This number
830 // does not consider the load factor.
831 Capacity int
832 // Size is the exact number of entries stored in the map.
833 Size int
834 // Counter is the number of entries stored in the map according
835 // to the internal atomic counter. In case of concurrent map
836 // modifications this number may be different from Size.
837 Counter int
838 // CounterLen is the number of internal atomic counter stripes.
839 // This number may grow with the map capacity to improve
840 // multithreaded scalability.
841 CounterLen int
842 // MinEntries is the minimum number of entries per a chain of
843 // buckets, i.e. a root bucket and its chained buckets.
844 MinEntries int
845 // MinEntries is the maximum number of entries per a chain of
846 // buckets, i.e. a root bucket and its chained buckets.
847 MaxEntries int
848 // TotalGrowths is the number of times the hash table grew.
849 TotalGrowths int64
850 // TotalGrowths is the number of times the hash table shrinked.
851 TotalShrinks int64
852 }
853 854 // ToString returns string representation of map stats.
855 func (s *MapStats) ToString() string {
856 var sb strings.Builder
857 sb.WriteString("MapStats{\n")
858 sb.WriteString(fmt.Sprintf("RootBuckets: %d\n", s.RootBuckets))
859 sb.WriteString(fmt.Sprintf("TotalBuckets: %d\n", s.TotalBuckets))
860 sb.WriteString(fmt.Sprintf("EmptyBuckets: %d\n", s.EmptyBuckets))
861 sb.WriteString(fmt.Sprintf("Capacity: %d\n", s.Capacity))
862 sb.WriteString(fmt.Sprintf("Size: %d\n", s.Size))
863 sb.WriteString(fmt.Sprintf("Counter: %d\n", s.Counter))
864 sb.WriteString(fmt.Sprintf("CounterLen: %d\n", s.CounterLen))
865 sb.WriteString(fmt.Sprintf("MinEntries: %d\n", s.MinEntries))
866 sb.WriteString(fmt.Sprintf("MaxEntries: %d\n", s.MaxEntries))
867 sb.WriteString(fmt.Sprintf("TotalGrowths: %d\n", s.TotalGrowths))
868 sb.WriteString(fmt.Sprintf("TotalShrinks: %d\n", s.TotalShrinks))
869 sb.WriteString("}\n")
870 return sb.String()
871 }
872 873 // Stats returns statistics for the Map. Just like other map
874 // methods, this one is thread-safe. Yet it's an O(N) operation,
875 // so it should be used only for diagnostics or debugging purposes.
876 func (m *Map) Stats() MapStats {
877 stats := MapStats{
878 TotalGrowths: atomic.LoadInt64(&m.totalGrowths),
879 TotalShrinks: atomic.LoadInt64(&m.totalShrinks),
880 MinEntries: math.MaxInt32,
881 }
882 table := (*mapTable)(atomic.LoadPointer(&m.table))
883 stats.RootBuckets = len(table.buckets)
884 stats.Counter = int(table.sumSize())
885 stats.CounterLen = len(table.size)
886 for i := range table.buckets {
887 nentries := 0
888 b := &table.buckets[i]
889 stats.TotalBuckets++
890 for {
891 nentriesLocal := 0
892 stats.Capacity += entriesPerMapBucket
893 for i := 0; i < entriesPerMapBucket; i++ {
894 if atomic.LoadPointer(&b.keys[i]) != nil {
895 stats.Size++
896 nentriesLocal++
897 }
898 }
899 nentries += nentriesLocal
900 if nentriesLocal == 0 {
901 stats.EmptyBuckets++
902 }
903 if b.next == nil {
904 break
905 }
906 b = (*bucketPadded)(atomic.LoadPointer(&b.next))
907 stats.TotalBuckets++
908 }
909 if nentries < stats.MinEntries {
910 stats.MinEntries = nentries
911 }
912 if nentries > stats.MaxEntries {
913 stats.MaxEntries = nentries
914 }
915 }
916 return stats
917 }
918