hashtriemap.go

     1  // Copyright 2024 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  //go:build goexperiment.synchashtriemap
     6  
     7  package sync
     8  
     9  import (
    10  	isync "internal/sync"
    11  )
    12  
    13  // Map is like a Go map[any]any but is safe for concurrent use
    14  // by multiple goroutines without additional locking or coordination.
    15  // Loads, stores, and deletes run in amortized constant time.
    16  //
    17  // The Map type is specialized. Most code should use a plain Go map instead,
    18  // with separate locking or coordination, for better type safety and to make it
    19  // easier to maintain other invariants along with the map content.
    20  //
    21  // The Map type is optimized for two common use cases: (1) when the entry for a given
    22  // key is only ever written once but read many times, as in caches that only grow,
    23  // or (2) when multiple goroutines read, write, and overwrite entries for disjoint
    24  // sets of keys. In these two cases, use of a Map may significantly reduce lock
    25  // contention compared to a Go map paired with a separate [Mutex] or [RWMutex].
    26  //
    27  // The zero Map is empty and ready for use. A Map must not be copied after first use.
    28  //
    29  // In the terminology of [the Go memory model], Map arranges that a write operation
    30  // “synchronizes before” any read operation that observes the effect of the write, where
    31  // read and write operations are defined as follows.
    32  // [Map.Load], [Map.LoadAndDelete], [Map.LoadOrStore], [Map.Swap], [Map.CompareAndSwap],
    33  // and [Map.CompareAndDelete] are read operations;
    34  // [Map.Delete], [Map.LoadAndDelete], [Map.Store], and [Map.Swap] are write operations;
    35  // [Map.LoadOrStore] is a write operation when it returns loaded set to false;
    36  // [Map.CompareAndSwap] is a write operation when it returns swapped set to true;
    37  // and [Map.CompareAndDelete] is a write operation when it returns deleted set to true.
    38  //
    39  // [the Go memory model]: https://go.dev/ref/mem
    40  type Map struct {
    41  	_ noCopy
    42  
    43  	m isync.HashTrieMap[any, any]
    44  }
    45  
    46  // Load returns the value stored in the map for a key, or nil if no
    47  // value is present.
    48  // The ok result indicates whether value was found in the map.
    49  func (m *Map) Load(key any) (value any, ok bool) {
    50  	return m.m.Load(key)
    51  }
    52  
    53  // Store sets the value for a key.
    54  func (m *Map) Store(key, value any) {
    55  	m.m.Store(key, value)
    56  }
    57  
    58  // Clear deletes all the entries, resulting in an empty Map.
    59  func (m *Map) Clear() {
    60  	m.m.Clear()
    61  }
    62  
    63  // LoadOrStore returns the existing value for the key if present.
    64  // Otherwise, it stores and returns the given value.
    65  // The loaded result is true if the value was loaded, false if stored.
    66  func (m *Map) LoadOrStore(key, value any) (actual any, loaded bool) {
    67  	return m.m.LoadOrStore(key, value)
    68  }
    69  
    70  // LoadAndDelete deletes the value for a key, returning the previous value if any.
    71  // The loaded result reports whether the key was present.
    72  func (m *Map) LoadAndDelete(key any) (value any, loaded bool) {
    73  	return m.m.LoadAndDelete(key)
    74  }
    75  
    76  // Delete deletes the value for a key.
    77  func (m *Map) Delete(key any) {
    78  	m.m.Delete(key)
    79  }
    80  
    81  // Swap swaps the value for a key and returns the previous value if any.
    82  // The loaded result reports whether the key was present.
    83  func (m *Map) Swap(key, value any) (previous any, loaded bool) {
    84  	return m.m.Swap(key, value)
    85  }
    86  
    87  // CompareAndSwap swaps the old and new values for key
    88  // if the value stored in the map is equal to old.
    89  // The old value must be of a comparable type.
    90  func (m *Map) CompareAndSwap(key, old, new any) (swapped bool) {
    91  	return m.m.CompareAndSwap(key, old, new)
    92  }
    93  
    94  // CompareAndDelete deletes the entry for key if its value is equal to old.
    95  // The old value must be of a comparable type.
    96  //
    97  // If there is no current value for key in the map, CompareAndDelete
    98  // returns false (even if the old value is the nil interface value).
    99  func (m *Map) CompareAndDelete(key, old any) (deleted bool) {
   100  	return m.m.CompareAndDelete(key, old)
   101  }
   102  
   103  // Range calls f sequentially for each key and value present in the map.
   104  // If f returns false, range stops the iteration.
   105  //
   106  // Range does not necessarily correspond to any consistent snapshot of the Map's
   107  // contents: no key will be visited more than once, but if the value for any key
   108  // is stored or deleted concurrently (including by f), Range may reflect any
   109  // mapping for that key from any point during the Range call. Range does not
   110  // block other methods on the receiver; even f itself may call any method on m.
   111  //
   112  // Range may be O(N) with the number of elements in the map even if f returns
   113  // false after a constant number of calls.
   114  func (m *Map) Range(f func(key, value any) bool) {
   115  	m.m.Range(f)
   116  }
   117
View as plain text