README
¶
Enhanced Map
Usage
import (
"github.com/jamestrandung/go-data-structure/emap"
)
go get "github.com/jamestrandung/go-data-structure/emap"
Implemented interface
// Map is a map for K -> V.
type Map[K comparable, V any] interface {
// SetAll sets all k-v pairs from the given map in this map.
SetAll(data map[K]V)
// Set sets a new k-v pair in this map, then returns the previous value associated with
// key, and whether such value exists.
Set(key K, value V) (V, bool)
// Get gets a value based on the given key.
Get(key K) (V, bool)
// GetAndSetIf gets a value based on the given key and sets a new value based on some condition,
// returning all inset and outset params in the condition func.
GetAndSetIf(key K, conditionFn func(currentVal V, found bool) (newVal V, shouldSet bool)) (currentVal V, found bool, newVal V, shouldSet bool)
// GetElseCreate return the value associated with the given key and true. If the key doesn't
// exist in this map, create a new value, set it in the map and then return the new value
// together with false instead.
GetElseCreate(key K, newValueFn func() V) (V, bool)
// Count returns size of this map.
Count() int
// IsEmpty returns whether this map is empty.
IsEmpty() bool
// Has returns whether given key is in this map.
Has(key K) bool
// Remove pops a K-V pair from this map, then returns it.
Remove(key K) (V, bool)
// RemoveIf removes the given key from this map based on some condition, then returns the value
// associated with the removed key and true. If the given key doesn't exist in this map or the
// key was not removed because of the condition func, a zero-value and false will be returned.
RemoveIf(key K, conditionFn func(currentVal V) bool) (V, bool)
// Clear removes all k-v pairs from this map.
Clear()
// Iter returns a channel which could be used in a for range loop. The capacity of the returned
// channel is the same as the size of the map at the time Iter() is called.
Iter() <-chan Tuple[K, V]
// Items returns all k-v pairs as a slice of core.Tuple.
Items() []Tuple[K, V]
// ForEach executes the given doEachFn on every element in this map. If `doEachFn` returns true,
// stop execution immediately.
ForEach(doEachFn func(key K, val V) bool)
// MarshalJSON returns the JSON bytes of this map.
MarshalJSON() ([]byte, error)
// UnmarshalJSON consumes a slice of JSON bytes to populate this map.
UnmarshalJSON(b []byte) error
// String returns a string representation of the current state of this map.
String() string
}
Concurrent Map
The basic map type in Go does not support concurrent reads and writes. emap provides a high
performance solution by utilizing shards to minimize the time required to acquire a lock to read
or write. It is suitable for cases where many goroutines read & write over the same set of keys.
Do note that since Go 1.9, there's a built-in sync.Map that is optimized for 2 common use cases:
(1) when the entry for a given key is only ever written once but read many times, as in caches that
only grow, or (2) when multiple goroutines read, write, and overwrite entries for disjoint sets of
keys. In these cases, using sync.Map may significantly reduce lock content compared to emap.
Read more: https://pkg.go.dev/sync#Map
Extra methods
// AsMap returns all k-v pairs as map[K]V.
AsMap() map[K]V
Example
// Create a new map
cm := emap.NewConcurrentMap[string, string]()
// Set item in map
cm.Set("foo", "bar")
// Get item from map without any casting required
if bar, ok := cm.Get("foo"); ok {
// Do something with "bar"
}
// Remove item under key "foo"
cm.Remove("foo")
For more examples, have a look at cmap_test.go.
Documentation
¶
Index ¶
- func HashString(s string) uint32
- type BasicKeyType
- type ConcurrentMap
- func (cm ConcurrentMap[K, V]) AsMap() map[K]V
- func (cm ConcurrentMap[K, V]) Clear()
- func (cm ConcurrentMap[K, V]) Count() int
- func (cm ConcurrentMap[K, V]) ForEach(doEachFn func(key K, val V) bool)
- func (cm ConcurrentMap[K, V]) Get(key K) (V, bool)
- func (cm ConcurrentMap[K, V]) GetAndSetIf(key K, conditionFn func(currentVal V, found bool) (newVal V, shouldSet bool)) (currentVal V, found bool, newVal V, shouldSet bool)
- func (cm ConcurrentMap[K, V]) GetElseCreate(key K, newValueFn func() V) (V, bool)
- func (cm ConcurrentMap[K, V]) Has(key K) bool
- func (cm ConcurrentMap[K, V]) IsEmpty() bool
- func (cm ConcurrentMap[K, V]) Items() []ds.Tuple[K, V]
- func (cm ConcurrentMap[K, V]) Iter() <-chan ds.Tuple[K, V]
- func (cm ConcurrentMap[K, V]) MarshalJSON() ([]byte, error)
- func (cm ConcurrentMap[K, V]) Remove(key K) (V, bool)
- func (cm ConcurrentMap[K, V]) RemoveAll(keys []K) bool
- func (cm ConcurrentMap[K, V]) RemoveIf(key K, conditionFn func(currentVal V) bool) (V, bool)
- func (cm ConcurrentMap[K, V]) Set(key K, value V) (V, bool)
- func (cm ConcurrentMap[K, V]) SetAll(data map[K]V)
- func (cm ConcurrentMap[K, V]) SetIfAbsent(key K, value V) bool
- func (cm ConcurrentMap[K, V]) String() string
- func (cm ConcurrentMap[K, V]) UnmarshalJSON(b []byte) error
- type ConcurrentMapShard
- type ConcurrentMapShardUnsafeKey
- type ConcurrentMapUnsafeKey
- func (cm ConcurrentMapUnsafeKey[V]) AsMap() map[interface{}]V
- func (cm ConcurrentMapUnsafeKey[V]) Clear()
- func (cm ConcurrentMapUnsafeKey[V]) Count() int
- func (cm ConcurrentMapUnsafeKey[V]) ForEach(doEachFn func(key interface{}, val V) bool)
- func (cm ConcurrentMapUnsafeKey[V]) Get(key interface{}) (V, bool)
- func (cm ConcurrentMapUnsafeKey[V]) GetAndSetIf(key interface{}, ...) (currentVal V, found bool, newVal V, shouldSet bool)
- func (cm ConcurrentMapUnsafeKey[V]) GetElseCreate(key interface{}, newValueFn func() V) (V, bool)
- func (cm ConcurrentMapUnsafeKey[V]) Has(key interface{}) bool
- func (cm ConcurrentMapUnsafeKey[V]) IsEmpty() bool
- func (cm ConcurrentMapUnsafeKey[V]) Items() []ds.Tuple[interface{}, V]
- func (cm ConcurrentMapUnsafeKey[V]) Iter() <-chan ds.Tuple[interface{}, V]
- func (cm ConcurrentMapUnsafeKey[V]) Remove(key interface{}) (V, bool)
- func (cm ConcurrentMapUnsafeKey[V]) RemoveAll(keys []interface{}) bool
- func (cm ConcurrentMapUnsafeKey[V]) RemoveIf(key interface{}, conditionFn func(currentVal V) bool) (V, bool)
- func (cm ConcurrentMapUnsafeKey[V]) Set(key interface{}, value V) (V, bool)
- func (cm ConcurrentMapUnsafeKey[V]) SetAll(data map[interface{}]V)
- func (cm ConcurrentMapUnsafeKey[V]) SetIfAbsent(key interface{}, value V) bool
- func (cm ConcurrentMapUnsafeKey[V]) String() string
- type Hasher
- type UnlockFn
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func HashString ¶
HashString converts the given string into a hash value.
Types ¶
type BasicKeyType ¶
type ConcurrentMap ¶
type ConcurrentMap[K comparable, V any] []*ConcurrentMapShard[K, V]
ConcurrentMap is a thread safe map for K -> V. To avoid lock bottlenecks this map is divided into to several ConcurrentMapShard.
To distribute keys into the underlying shards, when K is one of the BasicKeyType, the library will convert provided keys into string and then hash it using Go built-in fnv.New64(). On the other hand, if K is NOT one of the BasicKeyType, the library will use hashstructure.Hash with hashstructure.FormatV2 to hash provided keys. Clients should take a look at the documentation from hashstructure to understand how it works and how to customize its behaviors at runtime (e.g. ignore some struct fields).
Alternatively, clients can implement the Hasher core to provide their own hashing algo. This is preferred for optimizing performance since clients can choose fields to hash based on the actual type of keys without relying on heavy reflections inside hashstructure.Hash.
func NewConcurrentMap ¶
func NewConcurrentMap[K comparable, V any]() ConcurrentMap[K, V]
NewConcurrentMap returns a new instance of ConcurrentMap.
func NewConcurrentMapWithConcurrencyLevel ¶
func NewConcurrentMapWithConcurrencyLevel[K comparable, V any](concurrencyLevel int) ConcurrentMap[K, V]
NewConcurrentMapWithConcurrencyLevel returns a new instance of ConcurrentMap with the given amount of shards.
func (ConcurrentMap[K, V]) AsMap ¶
func (cm ConcurrentMap[K, V]) AsMap() map[K]V
AsMap returns all k-v pairs as map[K]V.
func (ConcurrentMap[K, V]) Clear ¶
func (cm ConcurrentMap[K, V]) Clear()
Clear removes all k-v pairs from this map.
func (ConcurrentMap[K, V]) Count ¶
func (cm ConcurrentMap[K, V]) Count() int
Count returns size of this map.
func (ConcurrentMap[K, V]) ForEach ¶
func (cm ConcurrentMap[K, V]) ForEach(doEachFn func(key K, val V) bool)
ForEach executes the given doEachFn on every element in this map. If `doEachFn` returns true, stop execution immediately.
Note: doEachFn is called while lock is held. Hence, it must NOT access this map as it may lead to deadlock since sync.RWLock is not reentrant.
func (ConcurrentMap[K, V]) Get ¶
func (cm ConcurrentMap[K, V]) Get(key K) (V, bool)
Get gets a value based on the given key.
func (ConcurrentMap[K, V]) GetAndSetIf ¶
func (cm ConcurrentMap[K, V]) GetAndSetIf( key K, conditionFn func(currentVal V, found bool) (newVal V, shouldSet bool), ) (currentVal V, found bool, newVal V, shouldSet bool)
GetAndSetIf gets a value based on the given key and sets a new value based on some condition, returning all inset and outset params in the condition func.
Note: Condition func is called while lock is held. Hence, it must NOT access this map as it may lead to deadlock since sync.RWLock is not reentrant.
func (ConcurrentMap[K, V]) GetElseCreate ¶
func (cm ConcurrentMap[K, V]) GetElseCreate(key K, newValueFn func() V) (V, bool)
GetElseCreate return the value associated with the given key and true. If the key doesn't exist in this map, create a new value, set it in the map and then return the new value together with false instead.
Note: newValueFn is called while lock is held. Hence, it must NOT access this map as it may lead to deadlock since sync.RWLock is not reentrant.
func (ConcurrentMap[K, V]) Has ¶
func (cm ConcurrentMap[K, V]) Has(key K) bool
Has returns whether given key is in this map.
func (ConcurrentMap[K, V]) IsEmpty ¶
func (cm ConcurrentMap[K, V]) IsEmpty() bool
IsEmpty returns whether this map is empty
func (ConcurrentMap[K, V]) Items ¶
func (cm ConcurrentMap[K, V]) Items() []ds.Tuple[K, V]
Items returns all k-v pairs as a slice of core.Tuple.
func (ConcurrentMap[K, V]) Iter ¶
func (cm ConcurrentMap[K, V]) Iter() <-chan ds.Tuple[K, V]
Iter returns a channel which could be used in a for range loop. The capacity of the returned channel is the same as the size of the map at the time Iter() is called.
func (ConcurrentMap[K, V]) MarshalJSON ¶
func (cm ConcurrentMap[K, V]) MarshalJSON() ([]byte, error)
MarshalJSON returns the JSON bytes of this map.
func (ConcurrentMap[K, V]) Remove ¶
func (cm ConcurrentMap[K, V]) Remove(key K) (V, bool)
Remove pops a K-V pair from this map, then returns it.
func (ConcurrentMap[K, V]) RemoveAll ¶
func (cm ConcurrentMap[K, V]) RemoveAll(keys []K) bool
RemoveAll removes all given keys from this map, then returns whether this map changed as a result of the call.
func (ConcurrentMap[K, V]) RemoveIf ¶
func (cm ConcurrentMap[K, V]) RemoveIf(key K, conditionFn func(currentVal V) bool) (V, bool)
RemoveIf removes the given key from this map based on some condition, then returns the value associated with the removed key and true. If the given key doesn't exist in this map or the key was not removed because of the condition func, a zero-value and false will be returned.
Note: Condition func is called while lock is held. Hence, it must NOT access this map as it may lead to deadlock since sync.RWLock is not reentrant.
func (ConcurrentMap[K, V]) Set ¶
func (cm ConcurrentMap[K, V]) Set(key K, value V) (V, bool)
Set sets a new k-v pair in this map, then returns the previous value associated with key, and whether such value exists.
func (ConcurrentMap[K, V]) SetAll ¶
func (cm ConcurrentMap[K, V]) SetAll(data map[K]V)
SetAll sets all k-v pairs from the given map in this map.
func (ConcurrentMap[K, V]) SetIfAbsent ¶
func (cm ConcurrentMap[K, V]) SetIfAbsent(key K, value V) bool
SetIfAbsent sets a new k-v pair in this map if it doesn't contain this key, then returns whether such k-v pair was absent.
func (ConcurrentMap[K, V]) String ¶
func (cm ConcurrentMap[K, V]) String() string
String returns a string representation of the current state of this map.
func (ConcurrentMap[K, V]) UnmarshalJSON ¶
func (cm ConcurrentMap[K, V]) UnmarshalJSON(b []byte) error
UnmarshalJSON consumes a slice of JSON bytes to populate this map.
type ConcurrentMapShard ¶
type ConcurrentMapShard[K comparable, V any] struct { sync.RWMutex // contains filtered or unexported fields }
ConcurrentMapShard is 1 shard in a ConcurrentMap
func (*ConcurrentMapShard[K, V]) GetItemsToRead ¶
func (s *ConcurrentMapShard[K, V]) GetItemsToRead() (map[K]V, UnlockFn)
GetItemsToRead returns the items in this shard and an UnlockFn after getting RLock
func (*ConcurrentMapShard[K, V]) GetItemsToWrite ¶
func (s *ConcurrentMapShard[K, V]) GetItemsToWrite() (map[K]V, UnlockFn)
GetItemsToWrite returns the items in this shard and an UnlockFn after getting Lock
type ConcurrentMapShardUnsafeKey ¶ added in v1.0.1
type ConcurrentMapShardUnsafeKey[V any] struct { sync.RWMutex // contains filtered or unexported fields }
ConcurrentMapShardUnsafeKey is 1 shard in a ConcurrentMapUnsafeKey
func (*ConcurrentMapShardUnsafeKey[V]) GetItemsToRead ¶ added in v1.0.1
func (s *ConcurrentMapShardUnsafeKey[V]) GetItemsToRead() (map[interface{}]V, UnlockFn)
GetItemsToRead returns the items in this shard and an UnlockFn after getting RLock
func (*ConcurrentMapShardUnsafeKey[V]) GetItemsToWrite ¶ added in v1.0.1
func (s *ConcurrentMapShardUnsafeKey[V]) GetItemsToWrite() (map[interface{}]V, UnlockFn)
GetItemsToWrite returns the items in this shard and an UnlockFn after getting Lock
type ConcurrentMapUnsafeKey ¶ added in v1.0.1
type ConcurrentMapUnsafeKey[V any] []*ConcurrentMapShardUnsafeKey[V]
ConcurrentMapUnsafeKey is almost the same as ConcurrentMap but different in that it can accept unsafe interface{} keys. Clients may run into panics if they write into this map using non-comparable keys.
func NewConcurrentMapUnsafeKey ¶ added in v1.0.1
func NewConcurrentMapUnsafeKey[V any]() ConcurrentMapUnsafeKey[V]
NewConcurrentMapUnsafeKey returns a new instance of ConcurrentMapUnsafeKey.
func NewConcurrentMapUnsafeKeyWithConcurrencyLevel ¶ added in v1.0.1
func NewConcurrentMapUnsafeKeyWithConcurrencyLevel[V any](concurrencyLevel int) ConcurrentMapUnsafeKey[V]
NewConcurrentMapUnsafeKeyWithConcurrencyLevel returns a new instance of ConcurrentMapUnsafeKey with the given amount of shards.
func (ConcurrentMapUnsafeKey[V]) AsMap ¶ added in v1.0.1
func (cm ConcurrentMapUnsafeKey[V]) AsMap() map[interface{}]V
AsMap returns all k-v pairs as map[K]V.
func (ConcurrentMapUnsafeKey[V]) Clear ¶ added in v1.0.1
func (cm ConcurrentMapUnsafeKey[V]) Clear()
Clear removes all k-v pairs from this map.
func (ConcurrentMapUnsafeKey[V]) Count ¶ added in v1.0.1
func (cm ConcurrentMapUnsafeKey[V]) Count() int
Count returns size of this map.
func (ConcurrentMapUnsafeKey[V]) ForEach ¶ added in v1.0.1
func (cm ConcurrentMapUnsafeKey[V]) ForEach(doEachFn func(key interface{}, val V) bool)
ForEach executes the given doEachFn on every element in this map. If `doEachFn` returns true, stop execution immediately.
Note: doEachFn is called while lock is held. Hence, it must NOT access this map as it may lead to deadlock since sync.RWLock is not reentrant.
func (ConcurrentMapUnsafeKey[V]) Get ¶ added in v1.0.1
func (cm ConcurrentMapUnsafeKey[V]) Get(key interface{}) (V, bool)
Get gets a value based on the given key.
func (ConcurrentMapUnsafeKey[V]) GetAndSetIf ¶ added in v1.0.1
func (cm ConcurrentMapUnsafeKey[V]) GetAndSetIf( key interface{}, conditionFn func(currentVal V, found bool) (newVal V, shouldSet bool), ) (currentVal V, found bool, newVal V, shouldSet bool)
GetAndSetIf gets a value based on the given key and sets a new value based on some condition, returning all inset and outset params in the condition func.
Note: Condition func is called while lock is held. Hence, it must NOT access this map as it may lead to deadlock since sync.RWLock is not reentrant.
func (ConcurrentMapUnsafeKey[V]) GetElseCreate ¶ added in v1.0.1
func (cm ConcurrentMapUnsafeKey[V]) GetElseCreate(key interface{}, newValueFn func() V) (V, bool)
GetElseCreate return the value associated with the given key and true. If the key doesn't exist in this map, create a new value, set it in the map and then return the new value together with false instead.
Note: newValueFn is called while lock is held. Hence, it must NOT access this map as it may lead to deadlock since sync.RWLock is not reentrant.
func (ConcurrentMapUnsafeKey[V]) Has ¶ added in v1.0.1
func (cm ConcurrentMapUnsafeKey[V]) Has(key interface{}) bool
Has returns whether given key is in this map.
func (ConcurrentMapUnsafeKey[V]) IsEmpty ¶ added in v1.0.1
func (cm ConcurrentMapUnsafeKey[V]) IsEmpty() bool
IsEmpty returns whether this map is empty
func (ConcurrentMapUnsafeKey[V]) Items ¶ added in v1.0.1
func (cm ConcurrentMapUnsafeKey[V]) Items() []ds.Tuple[interface{}, V]
Items returns all k-v pairs as a slice of core.Tuple.
func (ConcurrentMapUnsafeKey[V]) Iter ¶ added in v1.0.1
func (cm ConcurrentMapUnsafeKey[V]) Iter() <-chan ds.Tuple[interface{}, V]
Iter returns a channel which could be used in a for range loop. The capacity of the returned channel is the same as the size of the map at the time Iter() is called.
func (ConcurrentMapUnsafeKey[V]) Remove ¶ added in v1.0.1
func (cm ConcurrentMapUnsafeKey[V]) Remove(key interface{}) (V, bool)
Remove pops a K-V pair from this map, then returns it.
func (ConcurrentMapUnsafeKey[V]) RemoveAll ¶ added in v1.0.1
func (cm ConcurrentMapUnsafeKey[V]) RemoveAll(keys []interface{}) bool
RemoveAll removes all given keys from this map, then returns whether this map changed as a result of the call.
func (ConcurrentMapUnsafeKey[V]) RemoveIf ¶ added in v1.0.1
func (cm ConcurrentMapUnsafeKey[V]) RemoveIf(key interface{}, conditionFn func(currentVal V) bool) (V, bool)
RemoveIf removes the given key from this map based on some condition, then returns the value associated with the removed key and true. If the given key doesn't exist in this map or the key was not removed because of the condition func, a zero-value and false will be returned.
Note: Condition func is called while lock is held. Hence, it must NOT access this map as it may lead to deadlock since sync.RWLock is not reentrant.
func (ConcurrentMapUnsafeKey[V]) Set ¶ added in v1.0.1
func (cm ConcurrentMapUnsafeKey[V]) Set(key interface{}, value V) (V, bool)
Set sets a new k-v pair in this map, then returns the previous value associated with key, and whether such value exists.
func (ConcurrentMapUnsafeKey[V]) SetAll ¶ added in v1.0.1
func (cm ConcurrentMapUnsafeKey[V]) SetAll(data map[interface{}]V)
SetAll sets all k-v pairs from the given map in this map.
func (ConcurrentMapUnsafeKey[V]) SetIfAbsent ¶ added in v1.0.1
func (cm ConcurrentMapUnsafeKey[V]) SetIfAbsent(key interface{}, value V) bool
SetIfAbsent sets a new k-v pair in this map if it doesn't contain this key, then returns whether such k-v pair was absent.
func (ConcurrentMapUnsafeKey[V]) String ¶ added in v1.0.1
func (cm ConcurrentMapUnsafeKey[V]) String() string
String returns a string representation of the current state of this map.
type Hasher ¶
type Hasher interface {
Hash() uint64
}
Hasher can be implemented by the type to be used as keys in case clients want to provide their own hashing algo. Note that this hash does NOT control which bucket will hold a key in the actual map in each shard. Instead, it is used to distribute keys into the underlying shards which can be locked/unlocked independently by many goroutines.
To guarantee good performance for ConcurrentMap, clients must make sure their hashing algo can evenly distribute keys across shards. Otherwise, a hot shard may become a bottleneck when many goroutines try to lock it at the same time.
Note: we prioritize availability over correctness. If clients' hashing algo panics, the library will automatically recover and return 0, meaning all panicked keys will go into the 1st shard. As a consequence, subsequent concurrent accesses to these keys will happen on the same shard and performance may suffer. However, client applications will still work.
Source Files