Version: v1.0.52 Latest Latest

This package is not in the latest version of its module.

Go to latest
Published: Mar 9, 2020 License: Apache-2.0 Imports: 7 Imported by: 0



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:




This section is empty.


This section is empty.


This section is empty.


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.

Source Files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
t or T : Toggle theme light dark auto
y or Y : Canonical URL