radixtree

README

radixtree

An adaptive radix tree for Go.

import "github.com/zmj/radixtree"

Usage

The zero value is ready to use:

var t radixtree.Tree[string, int]
t.Set("api/users", 1)
t.Set("api/users/list", 2)
t.Set("api/posts", 3)

val, ok := t.Get("api/users") // 1, true

Or use the constructor:

t := radixtree.New[int]()

Prefix scanning

Iterate keys sharing a common prefix, in lexicographic order:

for key, val := range t.Scan("api/users") {
    fmt.Println(key, val)
}
// api/users 1
// api/users/list 2

Pass an empty prefix to iterate the entire tree:

for key, val := range t.Scan("") {
    // all keys in sorted order
}

Longest prefix matching

Find the longest key that prefixes a lookup key:

t.Set("/", rootHandler)
t.Set("/api/", apiHandler)
t.Set("/api/users/", usersHandler)

key, handler, ok := t.LongestPrefix("/api/users/123")
// "/api/users/", usersHandler, true

key, handler, ok = t.LongestPrefix("/api/posts/456")
// "/api/", apiHandler, true

Other operations

t.Delete("api/users")  // returns true if key existed
t.Len()                // number of keys
t.Compact()            // reclaim memory after many deletes

Notes

• Not safe for concurrent use
• Keys can be any ~string type
• Set panics on a nil *Tree; other methods return zero values

Documentation

Overview

Package radixtree implements an adaptive radix tree.

Index

• type ScanOption
• type Tree
  • func New[V any]() *Tree[string, V]
  • func (t *Tree[K, V]) Compact()
  • func (t *Tree[K, V]) Delete(key K) bool
  • func (t *Tree[K, V]) Get(key K) (V, bool)
  • func (t *Tree[K, V]) Len() int
  • func (t *Tree[K, V]) LongestPrefix(key K) (K, V, bool)
  • func (t *Tree[K, V]) Scan(prefix K, opts ...ScanOption) iter.Seq2[K, V]
  • func (t *Tree[K, V]) Set(key K, val V)

Types

type ScanOption

type ScanOption func(*scanConfig)

ScanOption modifies the behavior of the iterator returned from Scan.

type Tree

type Tree[K ~string, V any] struct {
	// contains filtered or unexported fields
}

A Tree is a key-value store that also supports querying by key prefix. The zero value is an empty Tree ready to use. A Tree is not safe for concurrent use or copying.

func New

func New[V any]() *Tree[string, V]

New returns an empty Tree with string keys.

func (*Tree[K, V]) Compact

func (t *Tree[K, V]) Compact()

Compact frees memory associated with deleted keys. Compact is an expensive operation; call it after many Deletes, not after each Delete.

func (*Tree[K, V]) Delete

func (t *Tree[K, V]) Delete(key K) bool

Delete removes the value for a key, and reports whether the key existed. Delete does not free all memory associated with the key. Consider calling Compact after many Deletes.

func (*Tree[K, V]) Get

func (t *Tree[K, V]) Get(key K) (V, bool)

Get returns the value for a key, and reports whether the key exists.

func (*Tree[K, V]) Len

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

Len returns the number of keys in the Tree.

func (*Tree[K, V]) LongestPrefix

func (t *Tree[K, V]) LongestPrefix(key K) (K, V, bool)

LongestPrefix returns the longest key that prefixes the input key, the value for that key, and reports whether any such key exists.

func (*Tree[K, V]) Scan

func (t *Tree[K, V]) Scan(prefix K, opts ...ScanOption) iter.Seq2[K, V]

Scan returns an iterator over keys beginning with a prefix. An empty string prefix iterates the entire Tree.

func (*Tree[K, V]) Set

func (t *Tree[K, V]) Set(key K, val V)

Set adds a key and value, or updates an existing value for that key. Set panics if called on a nil Tree.