Documentation
¶
Overview ¶
Package skipmap is a high-performance, scalable, concurrent-safe map based on skip-list. In the typical pattern(100000 operations, 90%LOAD 9%STORE 1%DELETE, 8C16T), the skipmap up to 10x faster than the built-in sync.Map.
Example ¶
s := New[string, int]()
s.Store("a", 0)
s.Store("a", 1)
s.Store("b", 2)
s.Store("c", 3)
fmt.Println(s.Len()) // 3
fmt.Println(s.Load("a")) // 1 true
fmt.Println(s.LoadAndDelete("a")) // 1 true
fmt.Println(s.LoadOrStore("a", 11)) // 11 false
fmt.Println(gson.ToString(s.ToMap())) // {"a":11, "b":2, "c": 3}
s.Delete("a")
s.Delete("b")
s.Delete("c")
var wg sync.WaitGroup
wg.Add(1000)
for i := 0; i < 1000; i++ {
i := i
go func() {
defer wg.Done()
s.Store(strconv.Itoa(i), i)
}()
}
wg.Wait()
fmt.Println(s.Len()) // 1000
Output: 3 1 true 1 true 11 false {"a":11,"b":2,"c":3} 1000
Index ¶
- type FuncMap
- func (s *FuncMap[keyT, valueT]) Delete(key keyT) bool
- func (s *FuncMap[keyT, valueT]) Len() int
- func (s *FuncMap[keyT, valueT]) Load(key keyT) (value valueT, ok bool)
- func (s *FuncMap[keyT, valueT]) LoadAndDelete(key keyT) (value valueT, loaded bool)
- func (s *FuncMap[keyT, valueT]) LoadOrStore(key keyT, value valueT) (actual valueT, loaded bool)
- func (s *FuncMap[keyT, valueT]) LoadOrStoreLazy(key keyT, f func() valueT) (actual valueT, loaded bool)
- func (s *FuncMap[keyT, valueT]) MarshalJSON() ([]byte, error)
- func (s *FuncMap[keyT, valueT]) Range(f func(key keyT, value valueT) bool)
- func (s *FuncMap[keyT, valueT]) Store(key keyT, value valueT)
- func (s *FuncMap[keyT, valueT]) UnmarshalJSON(data []byte) error
- type OrderedMap
- func (s *OrderedMap[keyT, valueT]) Delete(key keyT) bool
- func (s *OrderedMap[keyT, valueT]) Len() int
- func (s *OrderedMap[keyT, valueT]) Load(key keyT) (value valueT, ok bool)
- func (s *OrderedMap[keyT, valueT]) LoadAndDelete(key keyT) (value valueT, loaded bool)
- func (s *OrderedMap[keyT, valueT]) LoadOrStore(key keyT, value valueT) (actual valueT, loaded bool)
- func (s *OrderedMap[keyT, valueT]) LoadOrStoreLazy(key keyT, f func() valueT) (actual valueT, loaded bool)
- func (s *OrderedMap[keyT, valueT]) MarshalJSON() ([]byte, error)
- func (s *OrderedMap[keyT, valueT]) Range(f func(key keyT, value valueT) bool)
- func (s *OrderedMap[keyT, valueT]) Store(key keyT, value valueT)
- func (s *OrderedMap[keyT, valueT]) ToMap() map[keyT]valueT
- func (s *OrderedMap[keyT, valueT]) UnmarshalJSON(data []byte) error
- type OrderedMapDesc
- func (s *OrderedMapDesc[keyT, valueT]) Delete(key keyT) bool
- func (s *OrderedMapDesc[keyT, valueT]) Len() int
- func (s *OrderedMapDesc[keyT, valueT]) Load(key keyT) (value valueT, ok bool)
- func (s *OrderedMapDesc[keyT, valueT]) LoadAndDelete(key keyT) (value valueT, loaded bool)
- func (s *OrderedMapDesc[keyT, valueT]) LoadOrStore(key keyT, value valueT) (actual valueT, loaded bool)
- func (s *OrderedMapDesc[keyT, valueT]) LoadOrStoreLazy(key keyT, f func() valueT) (actual valueT, loaded bool)
- func (s *OrderedMapDesc[keyT, valueT]) MarshalJSON() ([]byte, error)
- func (s *OrderedMapDesc[keyT, valueT]) Range(f func(key keyT, value valueT) bool)
- func (s *OrderedMapDesc[keyT, valueT]) Store(key keyT, value valueT)
- func (s *OrderedMapDesc[keyT, valueT]) ToMap() map[keyT]valueT
- func (s *OrderedMapDesc[keyT, valueT]) UnmarshalJSON(data []byte) error
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type FuncMap ¶
FuncMap represents a map based on skip list.
func NewFunc ¶
NewFunc returns an empty skipmap in ascending order.
Note that the less function requires a strict weak ordering, see https://en.wikipedia.org/wiki/Weak_ordering#Strict_weak_orderings, or undefined behavior will happen.
func (*FuncMap[keyT, valueT]) Load ¶
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 (*FuncMap[keyT, valueT]) LoadAndDelete ¶
LoadAndDelete deletes the value for a key, returning the previous value if any. The loaded result reports whether the key was present. (Modified from Delete)
func (*FuncMap[keyT, valueT]) LoadOrStore ¶
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. (Modified from Store)
func (*FuncMap[keyT, valueT]) LoadOrStoreLazy ¶
func (s *FuncMap[keyT, valueT]) LoadOrStoreLazy(key keyT, f func() valueT) (actual valueT, loaded bool)
LoadOrStoreLazy returns the existing value for the key if present. Otherwise, it stores and returns the given value from f, f will only be called once. The loaded result is true if the value was loaded, false if stored. (Modified from LoadOrStore)
func (*FuncMap[keyT, valueT]) MarshalJSON ¶
MarshalJSON returns s as the JSON encoding of s.
func (*FuncMap[keyT, valueT]) Range ¶
Range calls f sequentially for each key and value present in the skipmap. If f returns false, range stops the iteration.
Range does not necessarily correspond to any consistent snapshot of the Map's contents: no key will be visited more than once, but if the value for any key is stored or deleted concurrently, Range may reflect any mapping for that key from any point during the Range call.
func (*FuncMap[keyT, valueT]) Store ¶
func (s *FuncMap[keyT, valueT]) Store(key keyT, value valueT)
Store sets the value for a key.
func (*FuncMap[keyT, valueT]) UnmarshalJSON ¶
UnmarshalJSON sets *s to a copy of data.
type OrderedMap ¶
type OrderedMap[keyT constraints.Ordered, valueT any] struct { // contains filtered or unexported fields }
OrderedMap represents a map based on skip list.
func New ¶
func New[keyT constraints.Ordered, valueT any]() *OrderedMap[keyT, valueT]
New returns an empty skipmap in ascending order.
func (*OrderedMap[keyT, valueT]) Delete ¶
func (s *OrderedMap[keyT, valueT]) Delete(key keyT) bool
Delete deletes the value for a key.
func (*OrderedMap[keyT, valueT]) Len ¶
func (s *OrderedMap[keyT, valueT]) Len() int
Len returns the length of this skipmap.
func (*OrderedMap[keyT, valueT]) Load ¶
func (s *OrderedMap[keyT, valueT]) Load(key keyT) (value valueT, 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 (*OrderedMap[keyT, valueT]) LoadAndDelete ¶
func (s *OrderedMap[keyT, valueT]) LoadAndDelete(key keyT) (value valueT, loaded bool)
LoadAndDelete deletes the value for a key, returning the previous value if any. The loaded result reports whether the key was present. (Modified from Delete)
func (*OrderedMap[keyT, valueT]) LoadOrStore ¶
func (s *OrderedMap[keyT, valueT]) LoadOrStore(key keyT, value valueT) (actual valueT, 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. (Modified from Store)
func (*OrderedMap[keyT, valueT]) LoadOrStoreLazy ¶
func (s *OrderedMap[keyT, valueT]) LoadOrStoreLazy(key keyT, f func() valueT) (actual valueT, loaded bool)
LoadOrStoreLazy returns the existing value for the key if present. Otherwise, it stores and returns the given value from f, f will only be called once. The loaded result is true if the value was loaded, false if stored. (Modified from LoadOrStore)
func (*OrderedMap[keyT, valueT]) MarshalJSON ¶
func (s *OrderedMap[keyT, valueT]) MarshalJSON() ([]byte, error)
MarshalJSON returns s as the JSON encoding of s.
func (*OrderedMap[keyT, valueT]) Range ¶
func (s *OrderedMap[keyT, valueT]) Range(f func(key keyT, value valueT) bool)
Range calls f sequentially for each key and value present in the skipmap. If f returns false, range stops the iteration.
Range does not necessarily correspond to any consistent snapshot of the Map's contents: no key will be visited more than once, but if the value for any key is stored or deleted concurrently, Range may reflect any mapping for that key from any point during the Range call.
func (*OrderedMap[keyT, valueT]) Store ¶
func (s *OrderedMap[keyT, valueT]) Store(key keyT, value valueT)
Store sets the value for a key.
func (*OrderedMap[keyT, valueT]) ToMap ¶
func (s *OrderedMap[keyT, valueT]) ToMap() map[keyT]valueT
ToMap converts this skipmap into a map.
func (*OrderedMap[keyT, valueT]) UnmarshalJSON ¶
func (s *OrderedMap[keyT, valueT]) UnmarshalJSON(data []byte) error
UnmarshalJSON sets *s to a copy of data.
type OrderedMapDesc ¶
type OrderedMapDesc[keyT constraints.Ordered, valueT any] struct { // contains filtered or unexported fields }
OrderedMapDesc represents a map based on skip list.
func NewDesc ¶
func NewDesc[keyT constraints.Ordered, valueT any]() *OrderedMapDesc[keyT, valueT]
NewDesc returns an empty skipmap in descending order.
func (*OrderedMapDesc[keyT, valueT]) Delete ¶
func (s *OrderedMapDesc[keyT, valueT]) Delete(key keyT) bool
Delete deletes the value for a key.
func (*OrderedMapDesc[keyT, valueT]) Len ¶
func (s *OrderedMapDesc[keyT, valueT]) Len() int
Len returns the length of this skipmap.
func (*OrderedMapDesc[keyT, valueT]) Load ¶
func (s *OrderedMapDesc[keyT, valueT]) Load(key keyT) (value valueT, 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 (*OrderedMapDesc[keyT, valueT]) LoadAndDelete ¶
func (s *OrderedMapDesc[keyT, valueT]) LoadAndDelete(key keyT) (value valueT, loaded bool)
LoadAndDelete deletes the value for a key, returning the previous value if any. The loaded result reports whether the key was present. (Modified from Delete)
func (*OrderedMapDesc[keyT, valueT]) LoadOrStore ¶
func (s *OrderedMapDesc[keyT, valueT]) LoadOrStore(key keyT, value valueT) (actual valueT, 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. (Modified from Store)
func (*OrderedMapDesc[keyT, valueT]) LoadOrStoreLazy ¶
func (s *OrderedMapDesc[keyT, valueT]) LoadOrStoreLazy(key keyT, f func() valueT) (actual valueT, loaded bool)
LoadOrStoreLazy returns the existing value for the key if present. Otherwise, it stores and returns the given value from f, f will only be called once. The loaded result is true if the value was loaded, false if stored. (Modified from LoadOrStore)
func (*OrderedMapDesc[keyT, valueT]) MarshalJSON ¶
func (s *OrderedMapDesc[keyT, valueT]) MarshalJSON() ([]byte, error)
MarshalJSON returns s as the JSON encoding of s.
func (*OrderedMapDesc[keyT, valueT]) Range ¶
func (s *OrderedMapDesc[keyT, valueT]) Range(f func(key keyT, value valueT) bool)
Range calls f sequentially for each key and value present in the skipmap. If f returns false, range stops the iteration.
Range does not necessarily correspond to any consistent snapshot of the Map's contents: no key will be visited more than once, but if the value for any key is stored or deleted concurrently, Range may reflect any mapping for that key from any point during the Range call.
func (*OrderedMapDesc[keyT, valueT]) Store ¶
func (s *OrderedMapDesc[keyT, valueT]) Store(key keyT, value valueT)
Store sets the value for a key.
func (*OrderedMapDesc[keyT, valueT]) ToMap ¶
func (s *OrderedMapDesc[keyT, valueT]) ToMap() map[keyT]valueT
ToMap converts this skipmap into a map.
func (*OrderedMapDesc[keyT, valueT]) UnmarshalJSON ¶
func (s *OrderedMapDesc[keyT, valueT]) UnmarshalJSON(data []byte) error
UnmarshalJSON sets *s to a copy of data.
Source Files