ctrie

Documentation

Overview

Package ctrie provides an implementation of the Ctrie 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 Snapshots:

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

Index

• type Ctrie
  • func New(hashFactory HashFactory) *Ctrie
  • func (c *Ctrie) Clear()
  • func (c *Ctrie) Insert(key []byte, value interface{})
  • func (c *Ctrie) Iterator(cancel <-chan struct{}) <-chan *Entry
  • func (c *Ctrie) Lookup(key []byte) (interface{}, bool)
  • func (c *Ctrie) ReadOnlySnapshot() *Ctrie
  • func (c *Ctrie) Remove(key []byte) (interface{}, bool)
  • func (c *Ctrie) Size() uint
  • func (c *Ctrie) Snapshot() *Ctrie
• type Entry
• type HashFactory

Types

type Ctrie

type Ctrie struct {
	// contains filtered or unexported fields
}

Ctrie is a concurrent, lock-free hash trie. By default, keys are hashed using FNV-1a unless a HashFactory is provided to New.

func New

func New(hashFactory HashFactory) *Ctrie

New creates an empty Ctrie which uses the provided HashFactory for key hashing. If nil is passed in, it will default to FNV-1a hashing.

func (*Ctrie) Clear

func (c *Ctrie) Clear()

Clear removes all keys from the Ctrie.

func (*Ctrie) Insert

func (c *Ctrie) Insert(key []byte, value interface{})

Insert adds the key-value pair to the Ctrie, replacing the existing value if the key already exists.

func (*Ctrie) Iterator

func (c *Ctrie) Iterator(cancel <-chan struct{}) <-chan *Entry

Iterator returns a channel which yields the Entries of the Ctrie. If a cancel channel is provided, closing it will terminate and close the iterator channel. Note that if a cancel channel is not used and not every entry is read from the iterator, a goroutine will leak.

func (*Ctrie) Lookup

func (c *Ctrie) Lookup(key []byte) (interface{}, bool)

Lookup returns the value for the associated key or returns false if the key doesn't exist.

func (*Ctrie) ReadOnlySnapshot

func (c *Ctrie) ReadOnlySnapshot() *Ctrie

ReadOnlySnapshot returns a stable, point-in-time snapshot of the Ctrie which is read-only. Write operations on a read-only snapshot will panic.

func (*Ctrie) Remove

func (c *Ctrie) Remove(key []byte) (interface{}, bool)

Remove deletes the value for the associated key, returning true if it was removed or false if the entry doesn't exist.

func (*Ctrie) Size

func (c *Ctrie) Size() uint

Size returns the number of keys in the Ctrie.

func (*Ctrie) Snapshot

func (c *Ctrie) Snapshot() *Ctrie

Snapshot returns a stable, point-in-time snapshot of the Ctrie. If the Ctrie is read-only, the returned Ctrie will also be read-only.

type Entry

type Entry struct {
	Key   []byte
	Value interface{}
	// contains filtered or unexported fields
}

Entry contains a Ctrie key-value pair.

type HashFactory

type HashFactory func() hash.Hash32

HashFactory returns a new Hash32 used to hash keys.