maps

Documentation

Index

• type Color
  • func (c Color) String() string
• type MapInterface
• type RWMutexMap
  • func (m *RWMutexMap[K, V]) CompareAndDelete(key K, old V) (deleted bool)
  • func (m *RWMutexMap[K, V]) CompareAndSwap(key K, old, new V) (swapped bool)
  • func (m *RWMutexMap[K, V]) Delete(key K)
  • func (m *RWMutexMap[K, V]) Load(key K) (value V, ok bool)
  • func (m *RWMutexMap[K, V]) LoadAndDelete(key K) (value V, loaded bool)
  • func (m *RWMutexMap[K, V]) LoadOrStore(key K, value V) (actual V, loaded bool)
  • func (m *RWMutexMap[K, V]) Range(f func(key K, value V) (shouldContinue bool))
  • func (m *RWMutexMap[K, V]) Store(key K, value V)
  • func (m *RWMutexMap[K, V]) Swap(key K, value V) (previous V, loaded bool)
• type SyncMap
  • func (m *SyncMap[K, V]) CompareAndDelete(key K, old V) (deleted bool)
  • func (m *SyncMap[K, V]) CompareAndSwap(key K, old, new V) bool
  • func (m *SyncMap[K, V]) Delete(key K)
  • func (m *SyncMap[K, V]) Load(key K) (value V, ok bool)
  • func (m *SyncMap[K, V]) LoadAndDelete(key K) (value V, loaded bool)
  • func (m *SyncMap[K, V]) LoadOrStore(key K, value V) (actual V, loaded bool)
  • func (m *SyncMap[K, V]) Range(f func(key K, value V) bool)
  • func (m *SyncMap[K, V]) Store(key K, value V)
  • func (m *SyncMap[K, V]) Swap(key K, value V) (previous V, loaded bool)
• type TreeEntry
  • func NewTreeEntry[K, V comparable](key K, val V, parent *TreeEntry[K, V]) *TreeEntry[K, V]
  • func (e *TreeEntry[K, V]) GetKey() K
  • func (e *TreeEntry[K, V]) GetValue() V
  • func (e *TreeEntry[K, V]) Height() int
  • func (e *TreeEntry[K, V]) SetValue(val V) V
• type TreeMap
  • func NewOrderedTreeMap[K cmp.Ordered, V comparable]() *TreeMap[K, V]
  • func NewTreeMap[K, V comparable](comparator algext.Comparator[K]) *TreeMap[K, V]
  • func NewTreeMapOf[M ~map[K]V, K cmp.Ordered, V comparable](unordered M) *TreeMap[K, V]
  • func (m *TreeMap[K, V]) CeilingEntry(key K) *TreeEntry[K, V]
  • func (m *TreeMap[K, V]) CeilingKey(key K) (K, bool)
  • func (m *TreeMap[K, V]) Clear()
  • func (m *TreeMap[K, V]) CompareAndDelete(key K, old V) (deleted bool)
  • func (m *TreeMap[K, V]) CompareAndSwap(key K, old, new V) (swapped bool)
  • func (m *TreeMap[K, V]) ContainsKey(key K) bool
  • func (m *TreeMap[K, V]) Delete(key K)
  • func (m *TreeMap[K, V]) FirstEntry() *TreeEntry[K, V]
  • func (m *TreeMap[K, V]) FirstKey() (K, bool)
  • func (m *TreeMap[K, V]) FloorEntry(key K) *TreeEntry[K, V]
  • func (m *TreeMap[K, V]) FloorKey(key K) (K, bool)
  • func (m *TreeMap[K, V]) Foreach(visit algext.KeyValVisitor[K, V])
  • func (m *TreeMap[K, V]) Get(key K) (V, bool)
  • func (m *TreeMap[K, V]) GetOrDefault(key K, defVal V) V
  • func (m *TreeMap[K, V]) HigherEntry(key K) *TreeEntry[K, V]
  • func (m *TreeMap[K, V]) HigherKey(key K) (K, bool)
  • func (m *TreeMap[K, V]) IsEmpty() bool
  • func (m *TreeMap[K, V]) Keys() []K
  • func (m *TreeMap[K, V]) LastEntry() *TreeEntry[K, V]
  • func (m *TreeMap[K, V]) LastKey() (K, bool)
  • func (m *TreeMap[K, V]) Load(key K) (V, bool)
  • func (m *TreeMap[K, V]) LoadAndDelete(key K) (value V, loaded bool)
  • func (m *TreeMap[K, V]) LoadOrStore(key K, value V) (actual V, loaded bool)
  • func (m *TreeMap[K, V]) Put(key K, value V) V
  • func (m *TreeMap[K, V]) PutIfAbsent(key K, value V) V
  • func (m *TreeMap[K, V]) Range(visit func(key K, value V) (shouldContinue bool))
  • func (m *TreeMap[K, V]) Remove(key K) bool
  • func (m *TreeMap[K, V]) RootEntry() *TreeEntry[K, V]
  • func (m *TreeMap[K, V]) Size() int
  • func (m *TreeMap[K, V]) Store(key K, value V)
  • func (m *TreeMap[K, V]) Swap(key K, value V) (previous V, loaded bool)
  • func (m *TreeMap[K, V]) ToHashMap() map[K]V
  • func (m *TreeMap[K, V]) Values() []V

Types

type Color

type Color uint8

Color Red-black mechanics

const (
	RED   Color = 0
	BLACK Color = 1
)

func (Color) String

func (c Color) String() string

type MapInterface

type MapInterface[K, V comparable] interface {
	Load(K) (V, bool)
	Store(key K, value V)
	LoadOrStore(key K, value V) (actual V, loaded bool)
	LoadAndDelete(key K) (value V, loaded bool)
	Delete(K)
	Swap(key K, value V) (previous V, loaded bool)
	CompareAndSwap(key K, old, new V) (swapped bool)
	CompareAndDelete(key K, old V) (deleted bool)
	Range(func(key K, value V) (shouldContinue bool))
}

MapInterface is the interface SyncMap implements.

type RWMutexMap

type RWMutexMap[K, V comparable] struct {
	// contains filtered or unexported fields
}

RWMutexMap is an implementation of mapInterface using a sync.RWMutex.

func (*RWMutexMap[K, V]) CompareAndDelete

func (m *RWMutexMap[K, V]) CompareAndDelete(key K, old V) (deleted bool)

func (*RWMutexMap[K, V]) CompareAndSwap

func (m *RWMutexMap[K, V]) CompareAndSwap(key K, old, new V) (swapped bool)

func (*RWMutexMap[K, V]) Delete

func (m *RWMutexMap[K, V]) Delete(key K)

func (*RWMutexMap[K, V]) Load

func (m *RWMutexMap[K, V]) Load(key K) (value V, ok bool)

func (*RWMutexMap[K, V]) LoadAndDelete

func (m *RWMutexMap[K, V]) LoadAndDelete(key K) (value V, loaded bool)

func (*RWMutexMap[K, V]) LoadOrStore

func (m *RWMutexMap[K, V]) LoadOrStore(key K, value V) (actual V, loaded bool)

func (*RWMutexMap[K, V]) Range

func (m *RWMutexMap[K, V]) Range(f func(key K, value V) (shouldContinue bool))

func (*RWMutexMap[K, V]) Store

func (m *RWMutexMap[K, V]) Store(key K, value V)

func (*RWMutexMap[K, V]) Swap

func (m *RWMutexMap[K, V]) Swap(key K, value V) (previous V, loaded bool)

type SyncMap

type SyncMap[K, V comparable] struct {
	// contains filtered or unexported fields
}

SyncMap is like a Go map[interface{}]interface{} but is safe for concurrent use by multiple goroutines without additional locking or coordination. Loads, stores, and deletes run in amortized constant time.

The SyncMap type is specialized. Most code should use a plain Go map instead, with separate locking or coordination, for better type safety and to make it easier to maintain other invariants along with the map content.

The SyncMap type is optimized for two 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 two cases, use of a SyncMap may significantly reduce lock contention compared to a Go map paired with a separate Mutex or RWMutex.

The zero SyncMap is empty and ready for use. A SyncMap must not be copied after first use.

In the terminology of the Go memory model, SyncMap arranges that a write operation “synchronizes before” any read operation that observes the effect of the write, where read and write operations are defined as follows. Load, LoadAndDelete, LoadOrStore, Swap, CompareAndSwap, and CompareAndDelete are read operations; Delete, LoadAndDelete, Store, and Swap are write operations; LoadOrStore is a write operation when it returns loaded set to false; CompareAndSwap is a write operation when it returns swapped set to true; and CompareAndDelete is a write operation when it returns deleted set to true.

func (*SyncMap[K, V]) CompareAndDelete

func (m *SyncMap[K, V]) CompareAndDelete(key K, old V) (deleted bool)

CompareAndDelete deletes the entry for key if its value is equal to old. The old value must be of a comparable type.

If there is no current value for key in the map, CompareAndDelete returns false (even if the old value is the nil interface value).

func (*SyncMap[K, V]) CompareAndSwap

func (m *SyncMap[K, V]) CompareAndSwap(key K, old, new V) bool

CompareAndSwap swaps the old and new values for key if the value stored in the map is equal to old. The old value must be of a comparable type.

func (*SyncMap[K, V]) Delete

func (m *SyncMap[K, V]) Delete(key K)

Delete deletes the value for a key.

func (*SyncMap[K, V]) Load

func (m *SyncMap[K, V]) Load(key K) (value V, ok bool)

Load returns the value stored in the map for a key, or nil if no value is present. The ok result indicates whether value was found in the map.

func (*SyncMap[K, V]) LoadAndDelete

func (m *SyncMap[K, V]) LoadAndDelete(key K) (value V, loaded bool)

LoadAndDelete deletes the value for a key, returning the previous value if any. The loaded result reports whether the key was present.

func (*SyncMap[K, V]) LoadOrStore

func (m *SyncMap[K, V]) LoadOrStore(key K, value V) (actual V, loaded bool)

LoadOrStore returns the existing value for the key if present. Otherwise, it stores and returns the given value. The loaded result is true if the value was loaded, false if stored.

func (*SyncMap[K, V]) Range

func (m *SyncMap[K, V]) Range(f func(key K, value V) bool)

Range calls f sequentially for each key and value present in the map. If f returns false, range stops the iteration.

Range does not necessarily correspond to any consistent snapshot of the SyncMap's contents: no key will be visited more than once, but if the value for any key is stored or deleted concurrently (including by f), Range may reflect any mapping for that key from any point during the Range call. Range does not block other methods on the receiver; even f itself may call any method on m.

Range may be O(N) with the number of elements in the map even if f returns false after a constant number of calls.

func (*SyncMap[K, V]) Store

func (m *SyncMap[K, V]) Store(key K, value V)

Store sets the value for a key.

func (*SyncMap[K, V]) Swap

func (m *SyncMap[K, V]) Swap(key K, value V) (previous V, loaded bool)

Swap swaps the value for a key and returns the previous value if any. The loaded result reports whether the key was present.

type TreeEntry

type TreeEntry[K, V comparable] struct {
	// contains filtered or unexported fields
}

func NewTreeEntry

func NewTreeEntry[K, V comparable](key K, val V, parent *TreeEntry[K, V]) *TreeEntry[K, V]

func (*TreeEntry[K, V]) GetKey

func (e *TreeEntry[K, V]) GetKey() K

func (*TreeEntry[K, V]) GetValue

func (e *TreeEntry[K, V]) GetValue() V

func (*TreeEntry[K, V]) Height

func (e *TreeEntry[K, V]) Height() int

func (*TreeEntry[K, V]) SetValue

func (e *TreeEntry[K, V]) SetValue(val V) V

type TreeMap

type TreeMap[K, V comparable] struct {
	// contains filtered or unexported fields
}

func NewOrderedTreeMap

func NewOrderedTreeMap[K cmp.Ordered, V comparable]() *TreeMap[K, V]

func NewTreeMap

func NewTreeMap[K, V comparable](comparator algext.Comparator[K]) *TreeMap[K, V]

func NewTreeMapOf

func NewTreeMapOf[M ~map[K]V, K cmp.Ordered, V comparable](unordered M) *TreeMap[K, V]

func (*TreeMap[K, V]) CeilingEntry

func (m *TreeMap[K, V]) CeilingEntry(key K) *TreeEntry[K, V]

CeilingEntry gets the entry corresponding to the specified key; returns the entry for the least key greater than the specified key if not exist.

func (*TreeMap[K, V]) CeilingKey

func (m *TreeMap[K, V]) CeilingKey(key K) (K, bool)

CeilingKey gets the specified key, return the least key greater than the specified key if not exist.

func (*TreeMap[K, V]) Clear

func (m *TreeMap[K, V]) Clear()

Clear removes all the mappings from this map.

func (*TreeMap[K, V]) CompareAndDelete

func (m *TreeMap[K, V]) CompareAndDelete(key K, old V) (deleted bool)

func (*TreeMap[K, V]) CompareAndSwap

func (m *TreeMap[K, V]) CompareAndSwap(key K, old, new V) (swapped bool)

CompareAndSwap swaps the old and new values for key if the value stored in the map is equal to old. The old value must be of a comparable type.

func (*TreeMap[K, V]) ContainsKey

func (m *TreeMap[K, V]) ContainsKey(key K) bool

ContainsKey return true if this map contains a mapping for the specified key

func (*TreeMap[K, V]) Delete

func (m *TreeMap[K, V]) Delete(key K)

func (*TreeMap[K, V]) FirstEntry

func (m *TreeMap[K, V]) FirstEntry() *TreeEntry[K, V]

func (*TreeMap[K, V]) FirstKey

func (m *TreeMap[K, V]) FirstKey() (K, bool)

FirstKey returns the first key in the TreeMap (according to the key's order)

func (*TreeMap[K, V]) FloorEntry

func (m *TreeMap[K, V]) FloorEntry(key K) *TreeEntry[K, V]

FloorEntry gets the entry corresponding to the specified key; if no such entry exists, returns the entry for the greatest key less than the specified key;

func (*TreeMap[K, V]) FloorKey

func (m *TreeMap[K, V]) FloorKey(key K) (K, bool)

FloorKey gets the specified key, returns the greatest key less than the specified key if not exist.

func (*TreeMap[K, V]) Foreach

func (m *TreeMap[K, V]) Foreach(visit algext.KeyValVisitor[K, V])

Foreach performs the given action for each entry in this map until all entries have been processed or the action panic

func (*TreeMap[K, V]) Get

func (m *TreeMap[K, V]) Get(key K) (V, bool)

Get returns the value to which the specified key is mapped, or nil if this map contains no mapping for the key.

func (*TreeMap[K, V]) GetOrDefault

func (m *TreeMap[K, V]) GetOrDefault(key K, defVal V) V

GetOrDefault returns the value to which the specified key is mapped, or `defaultValue` if this map contains no mapping for the key.

func (*TreeMap[K, V]) HigherEntry

func (m *TreeMap[K, V]) HigherEntry(key K) *TreeEntry[K, V]

HigherEntry gets the entry for the least key greater than the specified key

func (*TreeMap[K, V]) HigherKey

func (m *TreeMap[K, V]) HigherKey(key K) (K, bool)

HigherKey returns the least key greater than the specified key

func (*TreeMap[K, V]) IsEmpty

func (m *TreeMap[K, V]) IsEmpty() bool

func (*TreeMap[K, V]) Keys

func (m *TreeMap[K, V]) Keys() []K

Keys return list of all keys

func (*TreeMap[K, V]) LastEntry

func (m *TreeMap[K, V]) LastEntry() *TreeEntry[K, V]

func (*TreeMap[K, V]) LastKey

func (m *TreeMap[K, V]) LastKey() (K, bool)

LastKey returns the last key in the TreeMap (according to the key's order)

func (*TreeMap[K, V]) Load

func (m *TreeMap[K, V]) Load(key K) (V, bool)

func (*TreeMap[K, V]) LoadAndDelete

func (m *TreeMap[K, V]) LoadAndDelete(key K) (value V, loaded bool)

LoadAndDelete deletes the value for a key, returning the previous value if any. The loaded result reports whether the key was present.

func (*TreeMap[K, V]) LoadOrStore

func (m *TreeMap[K, V]) LoadOrStore(key K, value V) (actual V, loaded bool)

LoadOrStore returns the existing value for the key if present. Otherwise, it stores and returns the given value. The loaded result is true if the value was loaded, false if stored.

func (*TreeMap[K, V]) Put

func (m *TreeMap[K, V]) Put(key K, value V) V

Put associates the specified value with the specified key in this map. If the map previously contained a mapping for the key, the old value is replaced.

func (*TreeMap[K, V]) PutIfAbsent

func (m *TreeMap[K, V]) PutIfAbsent(key K, value V) V

PutIfAbsent put a key-value pair if the key is not already associated with a value.

func (*TreeMap[K, V]) Range

func (m *TreeMap[K, V]) Range(visit func(key K, value V) (shouldContinue bool))

Range calls f sequentially for each key and value present in the map. If f returns false, range stops the iteration.

func (*TreeMap[K, V]) Remove

func (m *TreeMap[K, V]) Remove(key K) bool

Remove removes the mapping for this key from this TreeMap if present.

func (*TreeMap[K, V]) RootEntry

func (m *TreeMap[K, V]) RootEntry() *TreeEntry[K, V]

func (*TreeMap[K, V]) Size

func (m *TreeMap[K, V]) Size() int

Size returns the number of key-value mappings in this map.

func (*TreeMap[K, V]) Store

func (m *TreeMap[K, V]) Store(key K, value V)

Store sets the value for a key, equivalent to Put.

func (*TreeMap[K, V]) Swap

func (m *TreeMap[K, V]) Swap(key K, value V) (previous V, loaded bool)

Swap swaps the value for a key and returns the previous value if any. The loaded result reports whether the key was present.

func (*TreeMap[K, V]) ToHashMap

func (m *TreeMap[K, V]) ToHashMap() map[K]V

func (*TreeMap[K, V]) Values

func (m *TreeMap[K, V]) Values() []V

Values return list of all values