README
¶
go-immutable-radix 
Provides the iradix package that implements an immutable radix tree.
The package only provides a single Tree implementation, optimized for sparse nodes.
As a radix tree, it provides the following:
- O(k) operations. In many cases, this can be faster than a hash table since the hash function is an O(k) operation, and hash tables have very poor cache locality.
- Minimum / Maximum value lookups
- Ordered iteration
A tree supports using a transaction to batch multiple updates (insert, delete) in a more efficient manner than performing each operation one at a time.
For a mutable variant, see go-radix.
V2
The v2 of go-immutable-radix introduces generics to improve compile-time type
safety for users of the package. The module name for v2 is
github.com/hashicorp/go-immutable-radix/v2.
Documentation
The full documentation is available on Godoc.
Example
Below is a simple example of usage
// Create a tree
r := iradix.New[int]()
r, _, _ = r.Insert([]byte("foo"), 1)
r, _, _ = r.Insert([]byte("bar"), 2)
r, _, _ = r.Insert([]byte("foobar"), 2)
// Find the longest prefix match
m, _, _ := r.Root().LongestPrefix([]byte("foozip"))
if string(m) != "foo" {
panic("should be foo")
}
Here is an example of performing a range scan of the keys.
// Create a tree
r := iradix.New[int]()
r, _, _ = r.Insert([]byte("001"), 1)
r, _, _ = r.Insert([]byte("002"), 2)
r, _, _ = r.Insert([]byte("005"), 5)
r, _, _ = r.Insert([]byte("010"), 10)
r, _, _ = r.Insert([]byte("100"), 10)
// Range scan over the keys that sort lexicographically between [003, 050)
it := r.Root().Iterator()
it.SeekLowerBound([]byte("003"))
for key, _, ok := it.Next(); ok; key, _, ok = it.Next() {
if string(key) >= "050" {
break
}
fmt.Println(string(key))
}
// Output:
// 005
// 010
Documentation
¶
Index ¶
- type Iterator
- type Node
- func (n *Node[T]) Get(k []byte) (T, bool)
- func (n *Node[T]) GetWatch(k []byte) (<-chan struct{}, T, bool)
- func (n *Node[T]) Iterator() *Iterator[T]
- func (n *Node[T]) LongestPrefix(k []byte) ([]byte, T, bool)
- func (n *Node[T]) Maximum() ([]byte, T, bool)
- func (n *Node[T]) Minimum() ([]byte, T, bool)
- func (n *Node[T]) PathIterator(path []byte) *PathIterator[T]
- func (n *Node[T]) ReverseIterator() *ReverseIterator[T]
- func (n *Node[T]) Walk(fn WalkFn[T])
- func (n *Node[T]) WalkBackwards(fn WalkFn[T])
- func (n *Node[T]) WalkPath(path []byte, fn WalkFn[T])
- func (n *Node[T]) WalkPrefix(prefix []byte, fn WalkFn[T])
- type PathIterator
- type ReverseIterator
- type Tree
- func (t *Tree[T]) Delete(k []byte) (*Tree[T], T, bool)
- func (t *Tree[T]) DeletePrefix(k []byte) (*Tree[T], bool)
- func (t *Tree[T]) Get(k []byte) (T, bool)
- func (t *Tree[T]) Insert(k []byte, v T) (*Tree[T], T, bool)
- func (t *Tree[T]) Len() int
- func (t *Tree[T]) Root() *Node[T]
- func (t *Tree[T]) Txn() *Txn[T]
- type Txn
- func (t *Txn[T]) Clone() *Txn[T]
- func (t *Txn[T]) Commit() *Tree[T]
- func (t *Txn[T]) CommitOnly() *Tree[T]
- func (t *Txn[T]) Delete(k []byte) (T, bool)
- func (t *Txn[T]) DeletePrefix(prefix []byte) bool
- func (t *Txn[T]) Get(k []byte) (T, bool)
- func (t *Txn[T]) GetWatch(k []byte) (<-chan struct{}, T, bool)
- func (t *Txn[T]) Insert(k []byte, v T) (T, bool)
- func (t *Txn[T]) Notify()
- func (t *Txn[T]) Root() *Node[T]
- func (t *Txn[T]) TrackMutate(track bool)
- type WalkFn
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Iterator ¶
type Iterator[T any] struct { // contains filtered or unexported fields }
Iterator is used to iterate over a set of nodes in pre-order
func (*Iterator[T]) SeekLowerBound ¶
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[T]) SeekPrefix ¶
SeekPrefix is used to seek the iterator to a given prefix
func (*Iterator[T]) SeekPrefixWatch ¶
SeekPrefixWatch is used to seek the iterator to a given prefix and returns the watch channel of the finest granularity
type Node ¶
type Node[T any] struct { // contains filtered or unexported fields }
Node is an immutable node in the radix tree
func (*Node[T]) Iterator ¶
Iterator is used to return an iterator at the given node to walk the tree
func (*Node[T]) LongestPrefix ¶
LongestPrefix is like Get, but instead of an exact match, it will return the longest prefix match.
func (*Node[T]) PathIterator ¶ added in v2.1.0
func (n *Node[T]) PathIterator(path []byte) *PathIterator[T]
Iterator is used to return an iterator at the given node to walk the tree
func (*Node[T]) ReverseIterator ¶
func (n *Node[T]) ReverseIterator() *ReverseIterator[T]
ReverseIterator is used to return an iterator at the given node to walk the tree backwards
func (*Node[T]) WalkBackwards ¶
WalkBackwards is used to walk the tree in reverse order
func (*Node[T]) WalkPath ¶
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[T]) WalkPrefix ¶
WalkPrefix is used to walk the tree under a prefix
type PathIterator ¶ added in v2.1.0
type PathIterator[T any] struct { // contains filtered or unexported fields }
PathIterator is used to iterate over a set of nodes from the root down to a specified path. This will iterate over the same values that the Node.WalkPath method will.
func (*PathIterator[T]) Next ¶ added in v2.1.0
func (i *PathIterator[T]) Next() ([]byte, T, bool)
Next returns the next node in order
type ReverseIterator ¶
type ReverseIterator[T any] struct { // contains filtered or unexported fields }
ReverseIterator is used to iterate over a set of nodes in reverse in-order
func NewReverseIterator ¶
func NewReverseIterator[T any](n *Node[T]) *ReverseIterator[T]
NewReverseIterator returns a new ReverseIterator at a node
func (*ReverseIterator[T]) Previous ¶
func (ri *ReverseIterator[T]) Previous() ([]byte, T, bool)
Previous returns the previous node in reverse order
func (*ReverseIterator[T]) SeekPrefix ¶
func (ri *ReverseIterator[T]) SeekPrefix(prefix []byte)
SeekPrefix is used to seek the iterator to a given prefix
func (*ReverseIterator[T]) SeekPrefixWatch ¶
func (ri *ReverseIterator[T]) SeekPrefixWatch(prefix []byte) (watch <-chan struct{})
SeekPrefixWatch is used to seek the iterator to a given prefix and returns the watch channel of the finest granularity
func (*ReverseIterator[T]) SeekReverseLowerBound ¶
func (ri *ReverseIterator[T]) 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[T any] 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 (*Tree[T]) Delete ¶
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[T]) DeletePrefix ¶
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[T]) Insert ¶
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.
type Txn ¶
type Txn[T any] 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[T]) Clone ¶
Clone makes an independent copy of the transaction. The new transaction does not track any nodes and has TrackMutate turned off. The cloned transaction will contain any uncommitted writes in the original transaction but further mutations to either will be independent and result in different radix trees on Commit. A cloned transaction may be passed to another goroutine and mutated there independently however each transaction may only be mutated in a single thread.
func (*Txn[T]) Commit ¶
Commit is used to finalize the transaction and return a new tree. If mutation tracking is turned on then notifications will also be issued.
func (*Txn[T]) CommitOnly ¶
CommitOnly is used to finalize the transaction and return a new tree, but does not issue any notifications until Notify is called.
func (*Txn[T]) Delete ¶
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[T]) DeletePrefix ¶
DeletePrefix is used to delete an entire subtree that matches the prefix This will delete all nodes under that prefix
func (*Txn[T]) GetWatch ¶
GetWatch is used to lookup a specific key, returning the watch channel, value and if it was found
func (*Txn[T]) Insert ¶
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[T]) Notify ¶
func (t *Txn[T]) Notify()
Notify is used along with TrackMutate to trigger notifications. This must only be done once a transaction is committed via CommitOnly, and it is called automatically by Commit.
func (*Txn[T]) Root ¶
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.
func (*Txn[T]) TrackMutate ¶
TrackMutate can be used to toggle if mutations are tracked. If this is enabled then notifications will be issued for affected internal nodes and leaves when the transaction is committed.
Source Files