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 Edge
- type Edges
- func (z *Edges) DecodeMsg(dc *msgp.Reader) (err error)
- func (z Edges) EncodeMsg(en *msgp.Writer) (err error)
- func (e Edges) Len() int
- func (e Edges) Less(i, j int) bool
- func (z Edges) MarshalMsg(b []byte) (o []byte, err error)
- func (z Edges) Msgsize() (s int)
- func (e Edges) Sort()
- func (e Edges) Swap(i, j int)
- func (z *Edges) UnmarshalMsg(bts []byte) (o []byte, err error)
- type LeafNode
- type Node
- type Tree
- func (z *Tree) DecodeMsg(dc *msgp.Reader) (err error)
- func (t *Tree) Delete(s string) (interface{}, bool)
- func (t *Tree) DeletePrefix(s string) int
- func (z *Tree) EncodeMsg(en *msgp.Writer) (err error)
- 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 (z *Tree) MarshalMsg(b []byte) (o []byte, err error)
- func (t *Tree) Maximum() (string, interface{}, bool)
- func (t *Tree) Minimum() (string, interface{}, bool)
- func (z *Tree) Msgsize() (s int)
- func (t *Tree) ToMap() map[string]interface{}
- func (z *Tree) UnmarshalMsg(bts []byte) (o []byte, err error)
- func (t *Tree) Walk(fn WalkFn)
- func (t *Tree) WalkPath(path string, fn WalkFn)
- func (t *Tree) WalkPrefix(prefix string, fn WalkFn)
- type WalkFn
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Edge ¶
Edge is used to represent an Edge Node
func (*Edge) MarshalMsg ¶
MarshalMsg implements msgp.Marshaler
type Edges ¶
type Edges []Edge
func (Edges) MarshalMsg ¶
MarshalMsg implements msgp.Marshaler
type LeafNode ¶
type LeafNode struct {
Key string `msgp:"k"`
Val interface{} `msgp:"v"`
}
LeafNode is used to represent a value
func (LeafNode) MarshalMsg ¶
MarshalMsg implements msgp.Marshaler
type Node ¶
type Node struct {
// Leaf is used to store possible Leaf
Leaf *LeafNode `msgp:"l"`
// Prefix is the common Prefix we ignore
Prefix string `msgp:"p"`
// Edges should be stored in-order for iteration.
// We avoid a fully materialized slice to save memory,
// since in most cases we expect to be sparse
Edges Edges `msgp:"e"`
}
func (*Node) MarshalMsg ¶
MarshalMsg implements msgp.Marshaler
type Tree ¶
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 NewFromMap ¶
NewFromMap returns a new tree containing the keys from an existing map
func (*Tree) Delete ¶
Delete is used to delete a Key, returning the previous value and if it was deleted
func (*Tree) DeletePrefix ¶
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) Insert ¶
Insert is used to add a newentry or update an existing entry. Returns if updated.
func (*Tree) LongestPrefix ¶
LongestPrefix is like Get, but instead of an exact match, it will return the longest Prefix match.
func (*Tree) MarshalMsg ¶
MarshalMsg implements msgp.Marshaler
func (*Tree) Msgsize ¶
Msgsize returns an upper bound estimate of the number of bytes occupied by the serialized message
func (*Tree) UnmarshalMsg ¶
UnmarshalMsg implements msgp.Unmarshaler
func (*Tree) 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 (*Tree) WalkPrefix ¶
WalkPrefix is used to walk the tree under a Prefix
Source Files