go-datastructures: github.com/Workiva/go-datastructures/trie/ctrie Index | Files

package ctrie

import "github.com/Workiva/go-datastructures/trie/ctrie"

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

Package Files

ctrie.go

type Ctrie Uses

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 Uses

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 Uses

func (c *Ctrie) Clear()

Clear removes all keys from the Ctrie.

func (*Ctrie) Insert Uses

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 Uses

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 Uses

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 Uses

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 Uses

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 Uses

func (c *Ctrie) Size() uint

Size returns the number of keys in the Ctrie.

func (*Ctrie) Snapshot Uses

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 Uses

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

Entry contains a Ctrie key-value pair.

type HashFactory Uses

type HashFactory func() hash.Hash32

HashFactory returns a new Hash32 used to hash keys.

Package ctrie imports 7 packages (graph) and is imported by 2 packages. Updated 2018-08-30. Refresh now. Tools for package owners.