gorax

README

gorax

gorax is a Go radix tree implementation inspired by the ANSI C Rax radix tree.

Documentation

The full documentation is available on Godoc.

Performance

The gorax Insert, Delete and Get are O(k) operations. In many cases, this can be faster than a hash table because the hash function is an O(k) operation too and in the worst case depending on how collisions are handled it may take even longer. Furthermore, hash tables have very poor cache locality.

Benchmark

The benchmark demonstrates well that the insertion, deletion and get times are independent of the number of elements stored in the gorax radix tree. In average insert and operations are taking less than 500ns/op measured on an 8 Core (11th Gen i7) Intel CPU.

goos: linux
goarch: amd64
pkg: github.com/snorwin/gorax
cpu: 11th Gen Intel(R) Core(TM) i7-1160G7 @ 1.20GHz
BenchmarkInsert1-8       	 2935486	       437.9 ns/op
BenchmarkInsert10-8      	  284378	      4073 ns/op
BenchmarkInsert100-8     	   33601	     36614 ns/op
BenchmarkInsert1000-8    	    3181	    383915 ns/op
BenchmarkInsert10000-8   	     268	   4245608 ns/op
BenchmarkGet1-8          	10413225	       125.3 ns/op
BenchmarkGet10-8         	 2489961	       466.6 ns/op
BenchmarkGet100-8        	  306944	      3282 ns/op
BenchmarkGet1000-8       	   60535	     31144 ns/op
BenchmarkGet10000-8      	    5689	    358072 ns/op
BenchmarkDelete1-8       	 6051354	     267.8 ns/op
BenchmarkDelete10-8      	 2085792	       581.9 ns/op
BenchmarkDelete100-8     	  342584	      3543 ns/op
BenchmarkDelete1000-8    	   38193	     31167 ns/op
BenchmarkDelete10000-8   	    3726	    326149 ns/op

Examples

Find longest prefix

// Create a tree
t := gorax.New()
_ = t.Insert("foo", nil)
_ = t.Insert("bar", 1)
_ = t.Insert("foobar", 2)

// Find the longest prefix match
prefix, _, _ := t.LongestPrefix("foojin")
fmt.Println(prefix)

foo

Create a gorax Tree from map

// Create a tree
t := gorax.FromMap(map[string]interface{}{
    "alligator":     nil,
    "alien":         1,
    "baloon":        2,
    "chromodynamic": 3,
    "romane":        4,
    "romanus":       5,
    "romulus":       6,
    "rubens":        7,
    "ruber":         8,
    "rubicon":       9,
    "rubicundus":    "a",
    "all":           "b",
    "rub":           "c",
    "ba":            "d",
})

// Convert to DOT graph
fmt.Println(t.ToDOTGraph().String())

DOT Graph representation of the Tree

(leaf nodes: blue color, compressed nodes: green color, key nodes: rectangular shape)

Trivia

In Star Wars gorax are a seldom-seen species of humanoids of gigantic proportion that are native to the mountains of Endor.

Documentation

Index

• type Nil
• type Tree
  • func FromMap(values map[string]interface{}) *Tree
  • func New() *Tree
  • func (t *Tree) Delete(key string) (interface{}, bool)
  • func (t *Tree) DeletePrefix(prefix string) int
  • func (t *Tree) Get(key string) (interface{}, bool)
  • func (t *Tree) Insert(key string, value interface{}) bool
  • func (t *Tree) Len() int
  • func (t *Tree) LongestPrefix(prefix string) (string, interface{}, bool)
  • func (t *Tree) Maximum() (string, interface{}, bool)
  • func (t *Tree) Minimum() (string, interface{}, bool)
  • func (t *Tree) ToDOTGraph() *dot.Graph
  • 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 WalkFn

Types

type Nil

type Nil struct{}

Nil is used to represent nil values in the Tree

type Tree

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

Tree implements a radix tree.

func FromMap

func FromMap(values map[string]interface{}) *Tree

FromMap returns a new Tree containing the keys from an existing map.

func New

func New() *Tree

New returns an empty Tree.

func (*Tree) Delete

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

Delete deletes a key and returns the previous value and if it was deleted.

func (*Tree) DeletePrefix

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

DeletePrefix deletes 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(key string) (interface{}, bool)

Get is used to lookup a specific key and returns the value and if it was found.

func (*Tree) Insert

func (t *Tree) Insert(key string, value interface{}) bool

Insert adds a new entry or updates an existing entry. Returns 'true' if entry was added.

func (*Tree) Len

func (t *Tree) Len() int

Len returns the number of elements in the Tree.

func (*Tree) LongestPrefix

func (t *Tree) LongestPrefix(prefix 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 returns the maximum value in the Tree.

func (*Tree) Minimum

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

Minimum returns the minimum value in the Tree.

func (*Tree) ToDOTGraph

func (t *Tree) ToDOTGraph() *dot.Graph

ToDOTGraph walks the Tree and converts it into a dot.Graph

func (*Tree) ToMap

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

ToMap walks the Tree and converts it into a map.

func (*Tree) Walk

func (t *Tree) Walk(fn WalkFn)

Walk walks 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.

func (*Tree) WalkPrefix

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

WalkPrefix walks the Tree under a prefix.

type WalkFn

type WalkFn func(key string, value interface{}) bool

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