ctrie

Documentation

Overview

Package ctrie provides an implementation of the Map data structure, which is a concurrent, lock-free hash trie. This data structure was originally presented in the paper Concurrent Tries with Efficient Non-Blocking Clones:

https://axel22.github.io/resources/docs/ctries-clone.pdf

Index

• func BytesHash(key []byte) uint64
• func StringHash(key string) uint64
• type Hasher
• type Iter
  • func (i *Iter[Key, Value]) Key() Key
  • func (i *Iter[Key, Value]) Next() bool
  • func (i *Iter[Key, Value]) Value() Value
• type Map
  • func New[Key Hasher, Value any]() *Map[Key, Value]
  • func NewWithFuncs[Key, Value any](eqFunc func(k1, k2 Key) bool, hashFunc func(Key) uint64) *Map[Key, Value]
  • func (c *Map[Key, Value]) Clear()
  • func (c *Map[Key, Value]) Clone() *Map[Key, Value]
  • func (c *Map[Key, Value]) Delete(key Key) (Value, bool)
  • func (c *Map[Key, Value]) Get(key Key) (Value, bool)
  • func (c *Map[Key, Value]) Iterator() *Iter[Key, Value]
  • func (c *Map[Key, Value]) Len() int
  • func (c *Map[Key, Value]) RClone() *Map[Key, Value]
  • func (c *Map[Key, Value]) Set(key Key, value Value)
• type String
  • func (s String) Hash() uint64

Functions

func BytesHash

func BytesHash(key []byte) uint64

func StringHash

func StringHash(key string) uint64

Types

type Hasher

type Hasher interface {
	comparable
	Hash() uint64
}

type Iter

type Iter[Key, Value any] struct {
	// contains filtered or unexported fields
}

Iter is an iterator that iterates through entries in the map.

func (*Iter[Key, Value]) Key

func (i *Iter[Key, Value]) Key() Key

func (*Iter[Key, Value]) Next

func (i *Iter[Key, Value]) Next() bool

func (*Iter[Key, Value]) Value

func (i *Iter[Key, Value]) Value() Value

type Map

type Map[Key, Value any] struct {
	// contains filtered or unexported fields
}

Map implements a map that can be updated concurrently and also has a low cost snapshot operation.

func New

func New[Key Hasher, Value any]() *Map[Key, Value]

New returns a new empty Map.

func NewWithFuncs

func NewWithFuncs[Key, Value any](
	eqFunc func(k1, k2 Key) bool,
	hashFunc func(Key) uint64,
) *Map[Key, Value]

NewWithFuncs is like New except that it uses explicit functions for comparison and hashing instead of relying on comparison and hashing on the value itself.

func (*Map[Key, Value]) Clear

func (c *Map[Key, Value]) Clear()

Clear removes all keys from the Map.

func (*Map[Key, Value]) Clone

func (c *Map[Key, Value]) Clone() *Map[Key, Value]

Clone returns a stable, point-in-time clone of the Map. If the Map is read-only, the returned Map will also be read-only.

func (*Map[Key, Value]) Delete

func (c *Map[Key, Value]) Delete(key Key) (Value, bool)

Delete deletes the value for the associated key, returning the deleted value and returning true if an entry was removed.

func (*Map[Key, Value]) Get

func (c *Map[Key, Value]) Get(key Key) (Value, bool)

Get returns the value for the associated key and reports whether the key exists in the trie.

func (*Map[Key, Value]) Iterator

func (c *Map[Key, Value]) Iterator() *Iter[Key, Value]

Iterator returns an iterator over the entries of the Map.

func (*Map[Key, Value]) Len

func (c *Map[Key, Value]) Len() int

Len returns the number of keys in the Map. This operation is O(n).

func (*Map[Key, Value]) RClone

func (c *Map[Key, Value]) RClone() *Map[Key, Value]

RClone returns a stable, point-in-time clone of the Map which is read-only. Write operations on a read-only clone will panic.

func (*Map[Key, Value]) Set

func (c *Map[Key, Value]) Set(key Key, value Value)

Set sets the value for the given key, replacing the existing value if the key already exists.

type String

type String string

func (String) Hash

func (s String) Hash() uint64