radixtree

Documentation

Index

• type InspectFunc
• type Tree
  • func New[T any]() *Tree[T]
  • func (t *Tree[T]) Delete(key []byte) bool
  • func (t *Tree[T]) DeletePrefix(prefix []byte) bool
  • func (t *Tree[T]) Get(key []byte) (value T, ok bool)
  • func (t *Tree[T]) Inspect(inspectFn InspectFunc[T])
  • func (t *Tree[T]) Len() int
  • func (t *Tree[T]) Put(key []byte, value T) bool
  • func (t *Tree[T]) Walk(key []byte, walkFn WalkFunc)
  • func (t *Tree[T]) WalkPath(key []byte, walkFn WalkFunc)
• type WalkFunc

Types

type InspectFunc

type InspectFunc[T any] func(link, prefix, key []byte, depth, children int, hasValue bool, value T) bool

InspectFunc is the type of the function called for each node visited by Inspect. The key argument contains the key at which the node is located, the depth is the distance from the root of the tree, and children is the number of children the node has.

If the function returns true Inspect stops immediately and returns.

type Tree

type Tree[T any] struct {
	// contains filtered or unexported fields
}

Tree is a radix tree of bytes keys and any values.

func New

func New[T any]() *Tree[T]

New creates a new bytes-based radix tree

func (*Tree[T]) Delete

func (t *Tree[T]) Delete(key []byte) bool

Delete removes the value associated with the given key. Returns true if there was a value stored for the key. If the node or any of its ancestors becomes childless as a result, they are removed from the tree.

func (*Tree[T]) DeletePrefix

func (t *Tree[T]) DeletePrefix(prefix []byte) bool

DeletePrefix removes all values whose key is prefixed by the given prefix. Returns true if any values were removed.

func (*Tree[T]) Get

func (t *Tree[T]) Get(key []byte) (value T, ok bool)

Get returns the value stored at the given key. Returns false if there is no value present for the key.

func (*Tree[T]) Inspect

func (t *Tree[T]) Inspect(inspectFn InspectFunc[T])

Inspect walks every node of the tree, whether or not it holds a value, calling inspectFn with information about each node. This allows the structure of the tree to be examined and detailed statistics to be collected.

If inspectFn returns false, the traversal is stopped and Inspect returns.

The tree is traversed in lexical order, making the output deterministic.

func (*Tree[T]) Len

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

Len returns the number of values stored in the tree.

func (*Tree[T]) Put

func (t *Tree[T]) Put(key []byte, value T) bool

Put inserts the value into the tree at the given key, replacing any existing items. It returns true if it adds a new value, false if it replaces an existing value.

func (*Tree[T]) Walk

func (t *Tree[T]) Walk(key []byte, walkFn WalkFunc)

Walk visits all nodes whose keys match or are prefixed by the specified key, calling walkFn for each value found. If walkFn returns true, Walk returns. Use empty key "" to visit all nodes starting from the root or the Tree.

The tree is traversed in lexical order, making the output deterministic.

func (*Tree[T]) WalkPath

func (t *Tree[T]) WalkPath(key []byte, walkFn WalkFunc)

WalkPath walks each node along the path from the root to the node at the given key, calling walkFn for each node that has a value. If walkFn returns true, WalkPath returns.

The tree is traversed in lexical order, making the output deterministic.

type WalkFunc

type WalkFunc func(key []byte, value any) bool

WalkFunc is the type of the function called for each value visited by Walk or WalkPath. The key argument contains the elements of the key at which the value is stored.

If the function returns true Walk stops immediately and returns. This applies to WalkPath as well.