iradix

package module
v1.2.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: May 29, 2025 License: MPL-2.0 Imports: 2 Imported by: 0

README

go-iradix-generic

tests

This is a hard fork of Hashicorp's go-immutable-radix package.

The main difference from the original is the support for non-byte keys using Go generics.

State of the Fork

This project is provided AS IS, keeping the original Hashicorp's license. I will probably abandon it soon, so don't keep your hopes high. I will accept PRs, especially the ones that keep this fork in sync with the original.

Performance Impact

Practically, there's zero performance impact. Hashicorp's implementation uses LRU cache to keep write cache, however, according to unsophisticated benchmarks, LRU caching allocates more than a simple hashmap. For this reason, LRU is not a part of this package, however you can still plug it in. See benchmark/benchmark_test.go for an example.

Benchmark Results

The Generic implementation demonstrates improved performance and efficiency over Hashicorp's original version in most use cases. By removing LRU caching, which added overhead, it achieves faster execution and fewer allocations, particularly in Update, Insert, and Delete operations. Overall, it's a lightweight and effective alternative for scenarios where []byte keys are unnecessary.

☝ AI slop

ns/op
Benchmark Generic (ns/op) Generic-LRU (ns/op) Hashicorp (ns/op)
Get 508.6 528.9 544.1
Insert (Random) 1026 1848 1729
Insert (Sequential) 670.3 689.2 653.6
Insert (Reverse) 716.8 754.4 665.1
Update (First) 1623 2378 2578
Update (Second) 947.9 2583 2325
Delete (Random) 1228 1956 1768
Delete (Sequential) 857.6 832.6 733.9
Delete (Reverse) 74.54 73.96 76.03
allocs/op
Benchmark Generic (allocs/op) Generic-LRU (allocs/op) Hashicorp (allocs/op)
Get 0 0 0
Insert (Random) 5 9 9
Insert (Sequential) 5 5 5
Insert (Reverse) 5 5 5
Update (First) 5 11 11
Update (Second) 2 11 11
Delete (Random) 3 8 8
Delete (Sequential) 3 4 4
Delete (Reverse) 0 0 0

How to Use

This is a drop-in replacement. The only thing you'll need to change is how you create a new tree:

tree := iradix.New[byte, int]() // equivalent to `iradix.New[int]()` when using hashicorp's package

The full documentation is available on Godoc.

Examples

Below is a simple example of usage

// Create a tree
r := iradix.New[byte, 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[byte, 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

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type Cache added in v1.1.0 

type Cache interface {
	Set(ptr CacheableNode)
	Has(ptr CacheableNode) bool
	Clear()
}

func NoCache added in v1.1.0 

func NoCache() Cache

NoCache disables node caching.

type CacheProvider added in v1.1.0 

type CacheProvider func() Cache

CacheProvider can be used as an option to cache nodes during transaction execution.

func MapCache added in v1.1.0 

func MapCache(initCapacity int) CacheProvider

type CacheableNode added in v1.1.0 

type CacheableNode interface {
	// contains filtered or unexported methods
}

type Iterator 

type Iterator[K keyT, T any] struct {
	// contains filtered or unexported fields
}

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

func (*Iterator[K, T]) Next 

func (i *Iterator[K, T]) Next() ([]K, T, bool)

Next returns the next node in order

func (*Iterator[K, T]) SeekLowerBound 

func (i *Iterator[K, T]) SeekLowerBound(key []K)

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[K, T]) SeekPrefix 

func (i *Iterator[K, T]) SeekPrefix(prefix []K)

SeekPrefix is used to seek the iterator to a given prefix

func (*Iterator[K, T]) SeekPrefixWatch 

func (i *Iterator[K, T]) SeekPrefixWatch(prefix []K) (watch <-chan struct{})

SeekPrefixWatch is used to seek the iterator to a given prefix and returns the watch channel of the finest granularity

type Node 

type Node[K keyT, T any] struct {
	// contains filtered or unexported fields
}

Node is an immutable node in the radix tree

func (*Node[K, T]) Get 

func (n *Node[K, T]) Get(k []K) (T, bool)

func (*Node[K, T]) GetWatch 

func (n *Node[K, T]) GetWatch(k []K) (<-chan struct{}, T, bool)

func (*Node[K, T]) Iterator 

func (n *Node[K, T]) Iterator() *Iterator[K, T]

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

func (*Node[K, T]) LongestPrefix 

func (n *Node[K, T]) LongestPrefix(k []K) ([]K, T, bool)

LongestPrefix is like Get, but instead of an exact match, it will return the longest prefix match.

func (*Node[K, T]) Maximum 

func (n *Node[K, T]) Maximum() ([]K, T, bool)

Maximum is used to return the maximum value in the tree

func (*Node[K, T]) Minimum 

func (n *Node[K, T]) Minimum() ([]K, T, bool)

Minimum is used to return the minimum value in the tree

func (*Node[K, T]) PathIterator 

func (n *Node[K, T]) PathIterator(path []K) *PathIterator[K, T]

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

func (*Node[K, T]) ReverseIterator 

func (n *Node[K, T]) ReverseIterator() *ReverseIterator[K, T]

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

func (*Node[K, T]) Walk 

func (n *Node[K, T]) Walk(fn WalkFn[K, T])

Walk is used to walk the tree

func (*Node[K, T]) WalkBackwards 

func (n *Node[K, T]) WalkBackwards(fn WalkFn[K, T])

WalkBackwards is used to walk the tree in reverse order

func (*Node[K, T]) WalkPath 

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

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[K, T]) WalkPrefix 

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

WalkPrefix is used to walk the tree under a prefix

type Option added in v1.1.0 

type Option func(o *options)

func WithCacheProvider added in v1.1.0 

func WithCacheProvider(cache CacheProvider) Option

func WithChannelLimit added in v1.1.0 

func WithChannelLimit(limit int) Option

type PathIterator 

type PathIterator[K keyT, 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[K, T]) Next 

func (i *PathIterator[K, T]) Next() ([]K, T, bool)

Next returns the next node in order

type ReverseIterator 

type ReverseIterator[K keyT, 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[K keyT, T any](n *Node[K, T]) *ReverseIterator[K, T]

NewReverseIterator returns a new ReverseIterator at a node

func (*ReverseIterator[K, T]) Previous 

func (ri *ReverseIterator[K, T]) Previous() ([]K, T, bool)

Previous returns the previous node in reverse order

func (*ReverseIterator[K, T]) SeekPrefix 

func (ri *ReverseIterator[K, T]) SeekPrefix(prefix []K)

SeekPrefix is used to seek the iterator to a given prefix

func (*ReverseIterator[K, T]) SeekPrefixWatch 

func (ri *ReverseIterator[K, T]) SeekPrefixWatch(prefix []K) (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[K, T]) SeekReverseLowerBound 

func (ri *ReverseIterator[K, T]) SeekReverseLowerBound(key []K)

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[K keyT, 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 New 

func New[K keyT, T any](opts ...Option) *Tree[K, T]

New returns an empty Tree

func (*Tree[K, T]) Delete 

func (t *Tree[K, T]) Delete(k []K) (*Tree[K, T], T, 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[K, T]) DeletePrefix 

func (t *Tree[K, T]) DeletePrefix(k []K) (*Tree[K, T], 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[K, T]) Get 

func (t *Tree[K, T]) Get(k []K) (T, bool)

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

func (*Tree[K, T]) Insert 

func (t *Tree[K, T]) Insert(k []K, v T) (*Tree[K, T], T, 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[K, T]) Len 

func (t *Tree[K, T]) Len() int

Len is used to return the number of elements in the tree

func (*Tree[K, T]) Root 

func (t *Tree[K, T]) Root() *Node[K, T]

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

func (*Tree[K, T]) Txn 

func (t *Tree[K, T]) Txn() *Txn[K, T]

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

type Txn 

type Txn[K keyT, 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[K, T]) Clone 

func (t *Txn[K, T]) Clone() *Txn[K, T]

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[K, T]) Commit 

func (t *Txn[K, T]) Commit() *Tree[K, T]

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[K, T]) CommitOnly 

func (t *Txn[K, T]) CommitOnly() *Tree[K, T]

CommitOnly is used to finalize the transaction and return a new tree, but does not issue any notifications until Notify is called.

func (*Txn[K, T]) Delete 

func (t *Txn[K, T]) Delete(k []K) (T, 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[K, T]) DeletePrefix 

func (t *Txn[K, T]) DeletePrefix(prefix []K) bool

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

func (*Txn[K, T]) Get 

func (t *Txn[K, T]) Get(k []K) (T, bool)

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

func (*Txn[K, T]) GetWatch 

func (t *Txn[K, T]) GetWatch(k []K) (<-chan struct{}, T, bool)

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

func (*Txn[K, T]) Insert 

func (t *Txn[K, T]) Insert(k []K, v T) (T, 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[K, T]) Notify 

func (t *Txn[K, 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[K, T]) Root 

func (t *Txn[K, T]) Root() *Node[K, T]

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[K, T]) TrackMutate 

func (t *Txn[K, T]) TrackMutate(track bool)

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.

type WalkFn 

type WalkFn[K keyT, T any] func(k []K, v T) bool

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

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.