radix

README

go-radix

Provides the radix package that implements a 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

For an immutable variant, see go-immutable-radix.

Documentation

The full documentation is available on Godoc.

Example

Below is a simple example of usage

// Create a tree
r := radix.New()
r.Insert("foo", 1)
r.Insert("bar", 2)
r.Insert("foobar", 2)

// Find the longest prefix match
m, _, _ := r.LongestPrefix("foozip")
if m != "foo" {
    panic("should be foo")
}

Documentation

Index

• type Exportable
• type Tree
  • func Load(r io.Reader, factory ValueFactory) (*Tree, error)
  • func New() *Tree
  • func NewFromMap(m map[string]interface{}) *Tree
  • func (t *Tree) Delete(s string) (interface{}, bool)
  • func (t *Tree) DeletePrefix(s string) int
  • func (t *Tree) Get(s string) (interface{}, bool)
  • func (t *Tree) Insert(s string, v interface{}) (interface{}, bool)
  • func (t *Tree) Len() int
  • func (t *Tree) LongestPrefix(s string) (string, interface{}, bool)
  • func (t *Tree) Maximum() (string, interface{}, bool)
  • func (t *Tree) Minimum() (string, interface{}, bool)
  • func (t *Tree) Save(w io.Writer) (retErr error)
  • func (t *Tree) ToMap() map[string]interface{}
  • func (t *Tree) Walk(fn WalkFn)
  • func (t *Tree) WalkPath(path string, fn WalkFn)
  • func (t *Tree) WalkPrefix(prefix string, fn WalkFn)
• type ValueFactory
• type WalkFn

Types

type Exportable

type Exportable interface {
	Marshal() ([]byte, error)
	Unmarshal([]byte) error
}

Exportable interface can be implemented on the client side to use preferred encoding

type Tree

type Tree struct {
	// contains filtered or unexported fields
}

Tree implements a 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,

func Load

func Load(r io.Reader, factory ValueFactory) (*Tree, error)

Load reads the tree bytes from the reader and uses the ValueFactory to reconstruct the tree

func New

func New() *Tree

New returns an empty Tree

func NewFromMap

func NewFromMap(m map[string]interface{}) *Tree

NewFromMap returns a new tree containing the keys from an existing map

func (*Tree) Delete

func (t *Tree) Delete(s string) (interface{}, bool)

Delete is used to delete a key, returning the previous value and if it was deleted

func (*Tree) DeletePrefix

func (t *Tree) DeletePrefix(s string) int

DeletePrefix is used to delete the subtree under a prefix Returns how many nodes were deleted Use this to delete large subtrees efficiently

func (*Tree) Get

func (t *Tree) Get(s string) (interface{}, bool)

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

func (*Tree) Insert

func (t *Tree) Insert(s string, v interface{}) (interface{}, bool)

Insert is used to add a newentry or update an existing entry. Returns if updated.

func (*Tree) Len

func (t *Tree) Len() int

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

func (*Tree) LongestPrefix

func (t *Tree) LongestPrefix(s string) (string, interface{}, bool)

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

func (*Tree) Maximum

func (t *Tree) Maximum() (string, interface{}, bool)

Maximum is used to return the maximum value in the tree

func (*Tree) Minimum

func (t *Tree) Minimum() (string, interface{}, bool)

Minimum is used to return the minimum value in the tree

func (*Tree) Save

func (t *Tree) Save(w io.Writer) (retErr error)

Save writes the tree to w

func (*Tree) ToMap

func (t *Tree) ToMap() map[string]interface{}

ToMap is used to walk the tree and convert it into a map

func (*Tree) Walk

func (t *Tree) Walk(fn WalkFn)

Walk is used to walk the tree

func (*Tree) WalkPath

func (t *Tree) WalkPath(path string, fn WalkFn)

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 (*Tree) WalkPrefix

func (t *Tree) WalkPrefix(prefix string, fn WalkFn)

WalkPrefix is used to walk the tree under a prefix

type ValueFactory

type ValueFactory func(key string) Exportable

ValueFactory is a factory function which constructs the object which is to be used to understand the value stored. The key will be passed to this routine, so we should be able to construct different objects based on different keys

type WalkFn

type WalkFn func(s string, v interface{}) bool

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