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.
Documentation
The full documentation is available on Godoc.
Example
Below is a simple example of usage
// Create a tree
r := iradix.New()
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")
}
Documentation
¶
Index ¶
- type Iterator
- type Node
- func (n *Node) Get(k []byte) (interface{}, bool)
- func (n *Node) Iterator() *Iterator
- func (n *Node) LongestPrefix(k []byte) ([]byte, interface{}, bool)
- func (n *Node) Maximum() ([]byte, interface{}, bool)
- func (n *Node) Minimum() ([]byte, interface{}, bool)
- func (n *Node) Walk(fn WalkFn)
- func (n *Node) WalkPath(path []byte, fn WalkFn)
- func (n *Node) WalkPrefix(prefix []byte, fn WalkFn)
- type Tree
- type Txn
- type WalkFn
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
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) SeekPrefix ¶
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) LongestPrefix ¶
LongestPrefix is like Get, but instead of an exact match, it will return the longest prefix match.
func (*Node) 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) WalkPrefix ¶
WalkPrefix is used to walk the tree under a prefix
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 (*Tree) 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) 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 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) Delete ¶
Delete is used to delete a given key. Returns the old value if any, and a bool indicating if the key was set.
Source Files