iradix

README

go-immutable-radix

Based on hashicorp/go-immutable-radix, but very much stripped down to the bare essentials in order to satisfy the needs of Caravan DB.

Documentation

Index

• type Iterator
  • func (i *Iterator) Next() ([]byte, interface{}, bool)
  • func (i *Iterator) SeekLowerBound(key []byte)
  • func (i *Iterator) SeekPrefix(prefix []byte)
• type Node
  • func (n *Node) Get(k []byte) (interface{}, bool)
  • func (n *Node) Iterator() *Iterator
  • func (n *Node) Maximum() ([]byte, interface{}, bool)
  • func (n *Node) Minimum() ([]byte, interface{}, bool)
  • func (n *Node) ReverseIterator() *ReverseIterator
  • func (n *Node) Walk(fn WalkFn)
  • func (n *Node) WalkBackwards(fn WalkFn)
  • func (n *Node) WalkPath(path []byte, fn WalkFn)
  • func (n *Node) WalkPrefix(prefix []byte, fn WalkFn)
• type ReverseIterator
  • func NewReverseIterator(n *Node) *ReverseIterator
  • func (ri *ReverseIterator) Previous() ([]byte, interface{}, bool)
  • func (ri *ReverseIterator) SeekPrefix(prefix []byte)
  • func (ri *ReverseIterator) SeekReverseLowerBound(key []byte)
• type Tree
  • func New() *Tree
  • func (t *Tree) Delete(k []byte) (*Tree, interface{}, bool)
  • func (t *Tree) DeletePrefix(k []byte) (*Tree, bool)
  • func (t *Tree) Get(k []byte) (interface{}, bool)
  • func (t *Tree) Insert(k []byte, v interface{}) (*Tree, interface{}, bool)
  • func (t *Tree) Root() *Node
  • func (t *Tree) Txn() *Txn
• type Txn
  • func (t *Txn) Commit() (*Tree, bool)
  • func (t *Txn) Delete(k []byte) (interface{}, bool)
  • func (t *Txn) DeletePrefix(prefix []byte) bool
  • func (t *Txn) Get(k []byte) (interface{}, bool)
  • func (t *Txn) Insert(k []byte, v interface{}) (interface{}, bool)
  • func (t *Txn) Root() *Node
• type WalkFn

Types

type Iterator

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

Iterator is used to iterate over a set of nodes in pre-order

func (*Iterator) Next

func (i *Iterator) Next() ([]byte, interface{}, bool)

Next returns the next node in order

func (*Iterator) SeekLowerBound

func (i *Iterator) SeekLowerBound(key []byte)

SeekLowerBound is used to seek the iterator to the smallest key that is greater or equal to the given key. There is no watch variant as it's hard to predict based on the radix structure which node(s) changes might affect the result.

func (*Iterator) SeekPrefix

func (i *Iterator) SeekPrefix(prefix []byte)

SeekPrefix is used to seek the iterator to a given prefix

type Node

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

Node is an immutable node in the radix tree

func (*Node) Get

func (n *Node) Get(k []byte) (interface{}, bool)

func (*Node) Iterator

func (n *Node) Iterator() *Iterator

Iterator is used to return an iterator at the given node to walk the tree

func (*Node) Maximum

func (n *Node) Maximum() ([]byte, interface{}, bool)

Maximum is used to return the maximum value in the tree

func (*Node) Minimum

func (n *Node) Minimum() ([]byte, interface{}, bool)

Minimum is used to return the minimum value in the tree

func (*Node) ReverseIterator

func (n *Node) ReverseIterator() *ReverseIterator

ReverseIterator is used to return an iterator at the given node to walk the tree backwards

func (*Node) Walk

func (n *Node) Walk(fn WalkFn)

Walk is used to walk the tree

func (*Node) WalkBackwards

func (n *Node) WalkBackwards(fn WalkFn)

WalkBackwards is used to walk the tree in reverse order

func (*Node) WalkPath

func (n *Node) WalkPath(path []byte, fn WalkFn)

WalkPath is used to walk the tree, but only visiting nodes from the root down to a given leaf. Where WalkPrefix walks all the entries *under* the given prefix, this walks the entries *above* the given prefix.

func (*Node) WalkPrefix

func (n *Node) WalkPrefix(prefix []byte, fn WalkFn)

WalkPrefix is used to walk the tree under a prefix

type ReverseIterator

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

ReverseIterator is used to iterate over a set of nodes in reverse in-order

func NewReverseIterator

func NewReverseIterator(n *Node) *ReverseIterator

NewReverseIterator returns a new ReverseIterator at a node

func (*ReverseIterator) Previous

func (ri *ReverseIterator) Previous() ([]byte, interface{}, bool)

Previous returns the previous node in reverse order

func (*ReverseIterator) SeekPrefix

func (ri *ReverseIterator) SeekPrefix(prefix []byte)

SeekPrefix is used to seek the iterator to a given prefix

func (*ReverseIterator) SeekReverseLowerBound

func (ri *ReverseIterator) SeekReverseLowerBound(key []byte)

SeekReverseLowerBound is used to seek the iterator to the largest key that is lower or equal to the given key. There is no watch variant as it's hard to predict based on the radix structure which node(s) changes might affect the result.

type Tree

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

Tree implements an immutable radix tree. This can be treated as a Dictionary abstract data type. The main advantage over a standard hash map is prefix-based lookups and ordered iteration. The immutability means that it is safe to concurrently read from a Tree without any coordination.

func New

func New() *Tree

New returns an empty Tree

func (*Tree) Delete

func (t *Tree) Delete(k []byte) (*Tree, interface{}, bool)

Delete is used to delete a given key. Returns the new tree, old value if any, and a bool indicating if the key was set.

func (*Tree) DeletePrefix

func (t *Tree) DeletePrefix(k []byte) (*Tree, bool)

DeletePrefix is used to delete all nodes starting with a given prefix. Returns the new tree, and a bool indicating if the prefix matched any nodes

func (*Tree) Get

func (t *Tree) Get(k []byte) (interface{}, bool)

Get is used to lookup a specific key, returning the value and if it was found

func (*Tree) Insert

func (t *Tree) Insert(k []byte, v interface{}) (*Tree, interface{}, bool)

Insert is used to add or update a given key. The return provides the new tree, previous value and a bool indicating if any was set.

func (*Tree) Root

func (t *Tree) Root() *Node

Root returns the root node of the tree which can be used for richer query operations.

func (*Tree) Txn

func (t *Tree) Txn() *Txn

Txn starts a new transaction that can be used to mutate the tree

type Txn

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

Txn is a transaction on the tree. This transaction is applied atomically and returns a new tree when committed. A transaction is not thread safe, and should only be used by a single goroutine.

func (*Txn) Commit

func (t *Txn) Commit() (*Tree, bool)

Commit is used to finalize the transaction and return a new tree. Indicates if the Tree has been mutated

func (*Txn) Delete

func (t *Txn) Delete(k []byte) (interface{}, bool)

Delete is used to delete a given key. Returns the old value if any, and a bool indicating if the key was set.

func (*Txn) DeletePrefix

func (t *Txn) DeletePrefix(prefix []byte) bool

DeletePrefix is used to delete an entire subtree that matches the prefix This will delete all nodes under that prefix

func (*Txn) Get

func (t *Txn) Get(k []byte) (interface{}, bool)

Get is used to lookup a specific key, returning the value and if it was found

func (*Txn) Insert

func (t *Txn) Insert(k []byte, v interface{}) (interface{}, bool)

Insert is used to add or update a given key. The return provides the previous value and a bool indicating if any was set.

func (*Txn) Root

func (t *Txn) Root() *Node

Root returns the current root of the radix tree within this transaction. The root is not safe across insert and delete operations, but can be used to read the current state during a transaction.

type WalkFn

type WalkFn func(k []byte, v interface{}) bool

WalkFn is used when walking the tree. Takes a key and value, returning if iteration should be terminated.