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

    Constants

    This section is empty.

    Variables

    This section is empty.

    Functions

    This section is empty.

    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.

                            Source Files