1 package xsync
2 3 import (
4 "fmt"
5 "math"
6 "sync"
7 "sync/atomic"
8 "unsafe"
9 )
10 11 const (
12 // number of MapOf entries per bucket; 5 entries lead to size of 64B
13 // (one cache line) on 64-bit machines
14 entriesPerMapOfBucket = 5
15 defaultMeta uint64 = 0x8080808080808080
16 metaMask uint64 = 0xffffffffff
17 defaultMetaMasked uint64 = defaultMeta & metaMask
18 emptyMetaSlot uint8 = 0x80
19 )
20 21 // MapOf is like a Go map[K]V but is safe for concurrent
22 // use by multiple goroutines without additional locking or
23 // coordination. It follows the interface of sync.Map with
24 // a number of valuable extensions like Compute or Size.
25 //
26 // A MapOf must not be copied after first use.
27 //
28 // MapOf uses a modified version of Cache-Line Hash Table (CLHT)
29 // data structure: https://github.com/LPD-EPFL/CLHT
30 //
31 // CLHT is built around idea to organize the hash table in
32 // cache-line-sized buckets, so that on all modern CPUs update
33 // operations complete with at most one cache-line transfer.
34 // Also, Get operations involve no write to memory, as well as no
35 // mutexes or any other sort of locks. Due to this design, in all
36 // considered scenarios MapOf outperforms sync.Map.
37 //
38 // MapOf also borrows ideas from Java's j.u.c.ConcurrentHashMap
39 // (immutable K/V pair structs instead of atomic snapshots)
40 // and C++'s absl::flat_hash_map (meta memory and SWAR-based
41 // lookups).
42 type MapOf[K comparable, V any] struct {
43 totalGrowths int64
44 totalShrinks int64
45 resizing int64 // resize in progress flag; updated atomically
46 resizeMu sync.Mutex // only used along with resizeCond
47 resizeCond sync.Cond // used to wake up resize waiters (concurrent modifications)
48 table unsafe.Pointer // *mapOfTable
49 hasher func(K, uint64) uint64
50 minTableLen int
51 growOnly bool
52 }
53 54 type mapOfTable[K comparable, V any] struct {
55 buckets []bucketOfPadded
56 // striped counter for number of table entries;
57 // used to determine if a table shrinking is needed
58 // occupies min(buckets_memory/1024, 64KB) of memory
59 size []counterStripe
60 seed uint64
61 }
62 63 // bucketOfPadded is a CL-sized map bucket holding up to
64 // entriesPerMapOfBucket entries.
65 type bucketOfPadded struct {
66 //lint:ignore U1000 ensure each bucket takes two cache lines on both 32 and 64-bit archs
67 pad [cacheLineSize - unsafe.Sizeof(bucketOf{})]byte
68 bucketOf
69 }
70 71 type bucketOf struct {
72 meta uint64
73 entries [entriesPerMapOfBucket]unsafe.Pointer // *entryOf
74 next unsafe.Pointer // *bucketOfPadded
75 mu sync.Mutex
76 }
77 78 // entryOf is an immutable map entry.
79 type entryOf[K comparable, V any] struct {
80 key K
81 value V
82 }
83 84 // NewMapOf creates a new MapOf instance configured with the given
85 // options.
86 func NewMapOf[K comparable, V any](options ...func(*MapConfig)) *MapOf[K, V] {
87 return NewMapOfWithHasher[K, V](defaultHasher[K](), options...)
88 }
89 90 // NewMapOfWithHasher creates a new MapOf instance configured with
91 // the given hasher and options. The hash function is used instead
92 // of the built-in hash function configured when a map is created
93 // with the NewMapOf function.
94 func NewMapOfWithHasher[K comparable, V any](
95 hasher func(K, uint64) uint64,
96 options ...func(*MapConfig),
97 ) *MapOf[K, V] {
98 c := &MapConfig{
99 sizeHint: defaultMinMapTableLen * entriesPerMapOfBucket,
100 }
101 for _, o := range options {
102 o(c)
103 }
104 105 m := &MapOf[K, V]{}
106 m.resizeCond = *sync.NewCond(&m.resizeMu)
107 m.hasher = hasher
108 var table *mapOfTable[K, V]
109 if c.sizeHint <= defaultMinMapTableLen*entriesPerMapOfBucket {
110 table = newMapOfTable[K, V](defaultMinMapTableLen)
111 } else {
112 tableLen := nextPowOf2(uint32((float64(c.sizeHint) / entriesPerMapOfBucket) / mapLoadFactor))
113 table = newMapOfTable[K, V](int(tableLen))
114 }
115 m.minTableLen = len(table.buckets)
116 m.growOnly = c.growOnly
117 atomic.StorePointer(&m.table, unsafe.Pointer(table))
118 return m
119 }
120 121 // NewMapOfPresized creates a new MapOf instance with capacity enough
122 // to hold sizeHint entries. The capacity is treated as the minimal capacity
123 // meaning that the underlying hash table will never shrink to
124 // a smaller capacity. If sizeHint is zero or negative, the value
125 // is ignored.
126 //
127 // Deprecated: use NewMapOf in combination with WithPresize.
128 func NewMapOfPresized[K comparable, V any](sizeHint int) *MapOf[K, V] {
129 return NewMapOf[K, V](WithPresize(sizeHint))
130 }
131 132 func newMapOfTable[K comparable, V any](minTableLen int) *mapOfTable[K, V] {
133 buckets := make([]bucketOfPadded, minTableLen)
134 for i := range buckets {
135 buckets[i].meta = defaultMeta
136 }
137 counterLen := minTableLen >> 10
138 if counterLen < minMapCounterLen {
139 counterLen = minMapCounterLen
140 } else if counterLen > maxMapCounterLen {
141 counterLen = maxMapCounterLen
142 }
143 counter := make([]counterStripe, counterLen)
144 t := &mapOfTable[K, V]{
145 buckets: buckets,
146 size: counter,
147 seed: makeSeed(),
148 }
149 return t
150 }
151 152 // ToPlainMapOf returns a native map with a copy of xsync Map's
153 // contents. The copied xsync Map should not be modified while
154 // this call is made. If the copied Map is modified, the copying
155 // behavior is the same as in the Range method.
156 func ToPlainMapOf[K comparable, V any](m *MapOf[K, V]) map[K]V {
157 pm := make(map[K]V)
158 if m != nil {
159 m.Range(func(key K, value V) bool {
160 pm[key] = value
161 return true
162 })
163 }
164 return pm
165 }
166 167 // Load returns the value stored in the map for a key, or zero value
168 // of type V if no value is present.
169 // The ok result indicates whether value was found in the map.
170 func (m *MapOf[K, V]) Load(key K) (value V, ok bool) {
171 table := (*mapOfTable[K, V])(atomic.LoadPointer(&m.table))
172 hash := m.hasher(key, table.seed)
173 h1 := h1(hash)
174 h2w := broadcast(h2(hash))
175 bidx := uint64(len(table.buckets)-1) & h1
176 b := &table.buckets[bidx]
177 for {
178 metaw := atomic.LoadUint64(&b.meta)
179 markedw := markZeroBytes(metaw^h2w) & metaMask
180 for markedw != 0 {
181 idx := firstMarkedByteIndex(markedw)
182 eptr := atomic.LoadPointer(&b.entries[idx])
183 if eptr != nil {
184 e := (*entryOf[K, V])(eptr)
185 if e.key == key {
186 return e.value, true
187 }
188 }
189 markedw &= markedw - 1
190 }
191 bptr := atomic.LoadPointer(&b.next)
192 if bptr == nil {
193 return
194 }
195 b = (*bucketOfPadded)(bptr)
196 }
197 }
198 199 // Store sets the value for a key.
200 func (m *MapOf[K, V]) Store(key K, value V) {
201 m.doCompute(
202 key,
203 func(V, bool) (V, bool) {
204 return value, false
205 },
206 false,
207 false,
208 )
209 }
210 211 // LoadOrStore returns the existing value for the key if present.
212 // Otherwise, it stores and returns the given value.
213 // The loaded result is true if the value was loaded, false if stored.
214 func (m *MapOf[K, V]) LoadOrStore(key K, value V) (actual V, loaded bool) {
215 return m.doCompute(
216 key,
217 func(V, bool) (V, bool) {
218 return value, false
219 },
220 true,
221 false,
222 )
223 }
224 225 // LoadAndStore returns the existing value for the key if present,
226 // while setting the new value for the key.
227 // It stores the new value and returns the existing one, if present.
228 // The loaded result is true if the existing value was loaded,
229 // false otherwise.
230 func (m *MapOf[K, V]) LoadAndStore(key K, value V) (actual V, loaded bool) {
231 return m.doCompute(
232 key,
233 func(V, bool) (V, bool) {
234 return value, false
235 },
236 false,
237 false,
238 )
239 }
240 241 // LoadOrCompute returns the existing value for the key if present.
242 // Otherwise, it computes the value using the provided function, and
243 // then stores and returns the computed value. The loaded result is
244 // true if the value was loaded, false if computed.
245 //
246 // This call locks a hash table bucket while the compute function
247 // is executed. It means that modifications on other entries in
248 // the bucket will be blocked until the valueFn executes. Consider
249 // this when the function includes long-running operations.
250 func (m *MapOf[K, V]) LoadOrCompute(key K, valueFn func() V) (actual V, loaded bool) {
251 return m.doCompute(
252 key,
253 func(V, bool) (V, bool) {
254 return valueFn(), false
255 },
256 true,
257 false,
258 )
259 }
260 261 // LoadOrTryCompute returns the existing value for the key if present.
262 // Otherwise, it tries to compute the value using the provided function
263 // and, if successful, stores and returns the computed value. The loaded
264 // result is true if the value was loaded, or false if computed (whether
265 // successfully or not). If the compute attempt was cancelled (due to an
266 // error, for example), a zero value of type V will be returned.
267 //
268 // This call locks a hash table bucket while the compute function
269 // is executed. It means that modifications on other entries in
270 // the bucket will be blocked until the valueFn executes. Consider
271 // this when the function includes long-running operations.
272 func (m *MapOf[K, V]) LoadOrTryCompute(
273 key K,
274 valueFn func() (newValue V, cancel bool),
275 ) (value V, loaded bool) {
276 return m.doCompute(
277 key,
278 func(V, bool) (V, bool) {
279 nv, c := valueFn()
280 if !c {
281 return nv, false
282 }
283 return nv, true // nv is ignored
284 },
285 true,
286 false,
287 )
288 }
289 290 // Compute either sets the computed new value for the key or deletes
291 // the value for the key. When the delete result of the valueFn function
292 // is set to true, the value will be deleted, if it exists. When delete
293 // is set to false, the value is updated to the newValue.
294 // The ok result indicates whether value was computed and stored, thus, is
295 // present in the map. The actual result contains the new value in cases where
296 // the value was computed and stored. See the example for a few use cases.
297 //
298 // This call locks a hash table bucket while the compute function
299 // is executed. It means that modifications on other entries in
300 // the bucket will be blocked until the valueFn executes. Consider
301 // this when the function includes long-running operations.
302 func (m *MapOf[K, V]) Compute(
303 key K,
304 valueFn func(oldValue V, loaded bool) (newValue V, delete bool),
305 ) (actual V, ok bool) {
306 return m.doCompute(key, valueFn, false, true)
307 }
308 309 // LoadAndDelete deletes the value for a key, returning the previous
310 // value if any. The loaded result reports whether the key was
311 // present.
312 func (m *MapOf[K, V]) LoadAndDelete(key K) (value V, loaded bool) {
313 return m.doCompute(
314 key,
315 func(value V, loaded bool) (V, bool) {
316 return value, true
317 },
318 false,
319 false,
320 )
321 }
322 323 // Delete deletes the value for a key.
324 func (m *MapOf[K, V]) Delete(key K) {
325 m.doCompute(
326 key,
327 func(value V, loaded bool) (V, bool) {
328 return value, true
329 },
330 false,
331 false,
332 )
333 }
334 335 func (m *MapOf[K, V]) doCompute(
336 key K,
337 valueFn func(oldValue V, loaded bool) (V, bool),
338 loadIfExists, computeOnly bool,
339 ) (V, bool) {
340 // Read-only path.
341 if loadIfExists {
342 if v, ok := m.Load(key); ok {
343 return v, !computeOnly
344 }
345 }
346 // Write path.
347 for {
348 compute_attempt:
349 var (
350 emptyb *bucketOfPadded
351 emptyidx int
352 )
353 table := (*mapOfTable[K, V])(atomic.LoadPointer(&m.table))
354 tableLen := len(table.buckets)
355 hash := m.hasher(key, table.seed)
356 h1 := h1(hash)
357 h2 := h2(hash)
358 h2w := broadcast(h2)
359 bidx := uint64(len(table.buckets)-1) & h1
360 rootb := &table.buckets[bidx]
361 rootb.mu.Lock()
362 // The following two checks must go in reverse to what's
363 // in the resize method.
364 if m.resizeInProgress() {
365 // Resize is in progress. Wait, then go for another attempt.
366 rootb.mu.Unlock()
367 m.waitForResize()
368 goto compute_attempt
369 }
370 if m.newerTableExists(table) {
371 // Someone resized the table. Go for another attempt.
372 rootb.mu.Unlock()
373 goto compute_attempt
374 }
375 b := rootb
376 for {
377 metaw := b.meta
378 markedw := markZeroBytes(metaw^h2w) & metaMask
379 for markedw != 0 {
380 idx := firstMarkedByteIndex(markedw)
381 eptr := b.entries[idx]
382 if eptr != nil {
383 e := (*entryOf[K, V])(eptr)
384 if e.key == key {
385 if loadIfExists {
386 rootb.mu.Unlock()
387 return e.value, !computeOnly
388 }
389 // In-place update/delete.
390 // We get a copy of the value via an interface{} on each call,
391 // thus the live value pointers are unique. Otherwise atomic
392 // snapshot won't be correct in case of multiple Store calls
393 // using the same value.
394 oldv := e.value
395 newv, del := valueFn(oldv, true)
396 if del {
397 // Deletion.
398 // First we update the hash, then the entry.
399 newmetaw := setByte(metaw, emptyMetaSlot, idx)
400 atomic.StoreUint64(&b.meta, newmetaw)
401 atomic.StorePointer(&b.entries[idx], nil)
402 rootb.mu.Unlock()
403 table.addSize(bidx, -1)
404 // Might need to shrink the table if we left bucket empty.
405 if newmetaw == defaultMeta {
406 m.resize(table, mapShrinkHint)
407 }
408 return oldv, !computeOnly
409 }
410 newe := new(entryOf[K, V])
411 newe.key = key
412 newe.value = newv
413 atomic.StorePointer(&b.entries[idx], unsafe.Pointer(newe))
414 rootb.mu.Unlock()
415 if computeOnly {
416 // Compute expects the new value to be returned.
417 return newv, true
418 }
419 // LoadAndStore expects the old value to be returned.
420 return oldv, true
421 }
422 }
423 markedw &= markedw - 1
424 }
425 if emptyb == nil {
426 // Search for empty entries (up to 5 per bucket).
427 emptyw := metaw & defaultMetaMasked
428 if emptyw != 0 {
429 idx := firstMarkedByteIndex(emptyw)
430 emptyb = b
431 emptyidx = idx
432 }
433 }
434 if b.next == nil {
435 if emptyb != nil {
436 // Insertion into an existing bucket.
437 var zeroV V
438 newValue, del := valueFn(zeroV, false)
439 if del {
440 rootb.mu.Unlock()
441 return zeroV, false
442 }
443 newe := new(entryOf[K, V])
444 newe.key = key
445 newe.value = newValue
446 // First we update meta, then the entry.
447 atomic.StoreUint64(&emptyb.meta, setByte(emptyb.meta, h2, emptyidx))
448 atomic.StorePointer(&emptyb.entries[emptyidx], unsafe.Pointer(newe))
449 rootb.mu.Unlock()
450 table.addSize(bidx, 1)
451 return newValue, computeOnly
452 }
453 growThreshold := float64(tableLen) * entriesPerMapOfBucket * mapLoadFactor
454 if table.sumSize() > int64(growThreshold) {
455 // Need to grow the table. Then go for another attempt.
456 rootb.mu.Unlock()
457 m.resize(table, mapGrowHint)
458 goto compute_attempt
459 }
460 // Insertion into a new bucket.
461 var zeroV V
462 newValue, del := valueFn(zeroV, false)
463 if del {
464 rootb.mu.Unlock()
465 return newValue, false
466 }
467 // Create and append a bucket.
468 newb := new(bucketOfPadded)
469 newb.meta = setByte(defaultMeta, h2, 0)
470 newe := new(entryOf[K, V])
471 newe.key = key
472 newe.value = newValue
473 newb.entries[0] = unsafe.Pointer(newe)
474 atomic.StorePointer(&b.next, unsafe.Pointer(newb))
475 rootb.mu.Unlock()
476 table.addSize(bidx, 1)
477 return newValue, computeOnly
478 }
479 b = (*bucketOfPadded)(b.next)
480 }
481 }
482 }
483 484 func (m *MapOf[K, V]) newerTableExists(table *mapOfTable[K, V]) bool {
485 curTablePtr := atomic.LoadPointer(&m.table)
486 return uintptr(curTablePtr) != uintptr(unsafe.Pointer(table))
487 }
488 489 func (m *MapOf[K, V]) resizeInProgress() bool {
490 return atomic.LoadInt64(&m.resizing) == 1
491 }
492 493 func (m *MapOf[K, V]) waitForResize() {
494 m.resizeMu.Lock()
495 for m.resizeInProgress() {
496 m.resizeCond.Wait()
497 }
498 m.resizeMu.Unlock()
499 }
500 501 func (m *MapOf[K, V]) resize(knownTable *mapOfTable[K, V], hint mapResizeHint) {
502 knownTableLen := len(knownTable.buckets)
503 // Fast path for shrink attempts.
504 if hint == mapShrinkHint {
505 if m.growOnly ||
506 m.minTableLen == knownTableLen ||
507 knownTable.sumSize() > int64((knownTableLen*entriesPerMapOfBucket)/mapShrinkFraction) {
508 return
509 }
510 }
511 // Slow path.
512 if !atomic.CompareAndSwapInt64(&m.resizing, 0, 1) {
513 // Someone else started resize. Wait for it to finish.
514 m.waitForResize()
515 return
516 }
517 var newTable *mapOfTable[K, V]
518 table := (*mapOfTable[K, V])(atomic.LoadPointer(&m.table))
519 tableLen := len(table.buckets)
520 switch hint {
521 case mapGrowHint:
522 // Grow the table with factor of 2.
523 atomic.AddInt64(&m.totalGrowths, 1)
524 newTable = newMapOfTable[K, V](tableLen << 1)
525 case mapShrinkHint:
526 shrinkThreshold := int64((tableLen * entriesPerMapOfBucket) / mapShrinkFraction)
527 if tableLen > m.minTableLen && table.sumSize() <= shrinkThreshold {
528 // Shrink the table with factor of 2.
529 atomic.AddInt64(&m.totalShrinks, 1)
530 newTable = newMapOfTable[K, V](tableLen >> 1)
531 } else {
532 // No need to shrink. Wake up all waiters and give up.
533 m.resizeMu.Lock()
534 atomic.StoreInt64(&m.resizing, 0)
535 m.resizeCond.Broadcast()
536 m.resizeMu.Unlock()
537 return
538 }
539 case mapClearHint:
540 newTable = newMapOfTable[K, V](m.minTableLen)
541 default:
542 panic(fmt.Sprintf("unexpected resize hint: %d", hint))
543 }
544 // Copy the data only if we're not clearing the map.
545 if hint != mapClearHint {
546 for i := 0; i < tableLen; i++ {
547 copied := copyBucketOf(&table.buckets[i], newTable, m.hasher)
548 newTable.addSizePlain(uint64(i), copied)
549 }
550 }
551 // Publish the new table and wake up all waiters.
552 atomic.StorePointer(&m.table, unsafe.Pointer(newTable))
553 m.resizeMu.Lock()
554 atomic.StoreInt64(&m.resizing, 0)
555 m.resizeCond.Broadcast()
556 m.resizeMu.Unlock()
557 }
558 559 func copyBucketOf[K comparable, V any](
560 b *bucketOfPadded,
561 destTable *mapOfTable[K, V],
562 hasher func(K, uint64) uint64,
563 ) (copied int) {
564 rootb := b
565 rootb.mu.Lock()
566 for {
567 for i := 0; i < entriesPerMapOfBucket; i++ {
568 if b.entries[i] != nil {
569 e := (*entryOf[K, V])(b.entries[i])
570 hash := hasher(e.key, destTable.seed)
571 bidx := uint64(len(destTable.buckets)-1) & h1(hash)
572 destb := &destTable.buckets[bidx]
573 appendToBucketOf(h2(hash), b.entries[i], destb)
574 copied++
575 }
576 }
577 if b.next == nil {
578 rootb.mu.Unlock()
579 return
580 }
581 b = (*bucketOfPadded)(b.next)
582 }
583 }
584 585 // Range calls f sequentially for each key and value present in the
586 // map. If f returns false, range stops the iteration.
587 //
588 // Range does not necessarily correspond to any consistent snapshot
589 // of the Map's contents: no key will be visited more than once, but
590 // if the value for any key is stored or deleted concurrently, Range
591 // may reflect any mapping for that key from any point during the
592 // Range call.
593 //
594 // It is safe to modify the map while iterating it, including entry
595 // creation, modification and deletion. However, the concurrent
596 // modification rule apply, i.e. the changes may be not reflected
597 // in the subsequently iterated entries.
598 func (m *MapOf[K, V]) Range(f func(key K, value V) bool) {
599 var zeroPtr unsafe.Pointer
600 // Pre-allocate array big enough to fit entries for most hash tables.
601 bentries := make([]unsafe.Pointer, 0, 16*entriesPerMapOfBucket)
602 tablep := atomic.LoadPointer(&m.table)
603 table := *(*mapOfTable[K, V])(tablep)
604 for i := range table.buckets {
605 rootb := &table.buckets[i]
606 b := rootb
607 // Prevent concurrent modifications and copy all entries into
608 // the intermediate slice.
609 rootb.mu.Lock()
610 for {
611 for i := 0; i < entriesPerMapOfBucket; i++ {
612 if b.entries[i] != nil {
613 bentries = append(bentries, b.entries[i])
614 }
615 }
616 if b.next == nil {
617 rootb.mu.Unlock()
618 break
619 }
620 b = (*bucketOfPadded)(b.next)
621 }
622 // Call the function for all copied entries.
623 for j := range bentries {
624 entry := (*entryOf[K, V])(bentries[j])
625 if !f(entry.key, entry.value) {
626 return
627 }
628 // Remove the reference to avoid preventing the copied
629 // entries from being GCed until this method finishes.
630 bentries[j] = zeroPtr
631 }
632 bentries = bentries[:0]
633 }
634 }
635 636 // Clear deletes all keys and values currently stored in the map.
637 func (m *MapOf[K, V]) Clear() {
638 table := (*mapOfTable[K, V])(atomic.LoadPointer(&m.table))
639 m.resize(table, mapClearHint)
640 }
641 642 // Size returns current size of the map.
643 func (m *MapOf[K, V]) Size() int {
644 table := (*mapOfTable[K, V])(atomic.LoadPointer(&m.table))
645 return int(table.sumSize())
646 }
647 648 func appendToBucketOf(h2 uint8, entryPtr unsafe.Pointer, b *bucketOfPadded) {
649 for {
650 for i := 0; i < entriesPerMapOfBucket; i++ {
651 if b.entries[i] == nil {
652 b.meta = setByte(b.meta, h2, i)
653 b.entries[i] = entryPtr
654 return
655 }
656 }
657 if b.next == nil {
658 newb := new(bucketOfPadded)
659 newb.meta = setByte(defaultMeta, h2, 0)
660 newb.entries[0] = entryPtr
661 b.next = unsafe.Pointer(newb)
662 return
663 }
664 b = (*bucketOfPadded)(b.next)
665 }
666 }
667 668 func (table *mapOfTable[K, V]) addSize(bucketIdx uint64, delta int) {
669 cidx := uint64(len(table.size)-1) & bucketIdx
670 atomic.AddInt64(&table.size[cidx].c, int64(delta))
671 }
672 673 func (table *mapOfTable[K, V]) addSizePlain(bucketIdx uint64, delta int) {
674 cidx := uint64(len(table.size)-1) & bucketIdx
675 table.size[cidx].c += int64(delta)
676 }
677 678 func (table *mapOfTable[K, V]) sumSize() int64 {
679 sum := int64(0)
680 for i := range table.size {
681 sum += atomic.LoadInt64(&table.size[i].c)
682 }
683 return sum
684 }
685 686 func h1(h uint64) uint64 {
687 return h >> 7
688 }
689 690 func h2(h uint64) uint8 {
691 return uint8(h & 0x7f)
692 }
693 694 // Stats returns statistics for the MapOf. Just like other map
695 // methods, this one is thread-safe. Yet it's an O(N) operation,
696 // so it should be used only for diagnostics or debugging purposes.
697 func (m *MapOf[K, V]) Stats() MapStats {
698 stats := MapStats{
699 TotalGrowths: atomic.LoadInt64(&m.totalGrowths),
700 TotalShrinks: atomic.LoadInt64(&m.totalShrinks),
701 MinEntries: math.MaxInt32,
702 }
703 table := (*mapOfTable[K, V])(atomic.LoadPointer(&m.table))
704 stats.RootBuckets = len(table.buckets)
705 stats.Counter = int(table.sumSize())
706 stats.CounterLen = len(table.size)
707 for i := range table.buckets {
708 nentries := 0
709 b := &table.buckets[i]
710 stats.TotalBuckets++
711 for {
712 nentriesLocal := 0
713 stats.Capacity += entriesPerMapOfBucket
714 for i := 0; i < entriesPerMapOfBucket; i++ {
715 if atomic.LoadPointer(&b.entries[i]) != nil {
716 stats.Size++
717 nentriesLocal++
718 }
719 }
720 nentries += nentriesLocal
721 if nentriesLocal == 0 {
722 stats.EmptyBuckets++
723 }
724 if b.next == nil {
725 break
726 }
727 b = (*bucketOfPadded)(atomic.LoadPointer(&b.next))
728 stats.TotalBuckets++
729 }
730 if nentries < stats.MinEntries {
731 stats.MinEntries = nentries
732 }
733 if nentries > stats.MaxEntries {
734 stats.MaxEntries = nentries
735 }
736 }
737 return stats
738 }
739