trie

README

Trie

Package trie implements rune-wise and path-wise Tries optimized for Get performance and to allocate 0 bytes of heap memory (i.e. garbage) per Get.

A typical use case is to perform any Put or Delete operations upfront to populate the trie, then perform Get operations very quickly. The Tries do not synchronize access (not thread-safe).

When Tries are chosen over maps, it is typically for their space efficiency. However, in situations where direct key lookup is not possible (e.g. routers), tries can provide faster lookups and avoid key iteration.

Install

$ go get github.com/dghubble/trie

Documentation

Read Godoc

Performance

RuneTrie is a typical Trie which segments strings rune-wise (i.e. by unicode code point). These benchmarks perform Puts and Gets of random string keys that are 30 bytes long and of random '/' separated paths that have 3 parts and are 30 bytes long (longer if you count the '/' seps).

BenchmarkRuneTriePutStringKey-8   3000000    437 ns/op     9 B/op     1 allocs/op
BenchmarkRuneTrieGetStringKey-8   3000000    411 ns/op     0 B/op     0 allocs/op
BenchmarkRuneTriePutPathKey-8     3000000    464 ns/op     9 B/op     1 allocs/op
BenchmarkRuneTrieGetPathKey-8     3000000    429 ns/op     0 B/op     0 allocs/op

PathTrie segments strings by forward slash separators which can boost performance for some use cases. These benchmarks perform Puts and Gets of random string keys that are 30 bytes long and of random '/' separated paths that have 3 parts and are 30 bytes long (longer if you count the '/' seps).

BenchmarkPathTriePutStringKey-8   30000000   55.5 ns/op    8 B/op     1 allocs/op
BenchmarkPathTrieGetStringKey-8   50000000   37.9 ns/op    0 B/op     0 allocs/op
BenchmarkPathTriePutPathKey-8     20000000   88.7 ns/op    8 B/op     1 allocs/op
BenchmarkPathTrieGetPathKey-8     20000000   68.6 ns/op    0 B/op     0 allocs/op

Note that for random string Puts and Gets, the PathTrie is effectively a map as every node is a direct child of the root (except for strings that happen to have a slash).

This benchmark measures the performance of the PathSegmenter alone. It is used to segment random paths that have 3 '/' separated parts and are 30 bytes long.

BenchmarkPathSegmenter-8          50000000   32.0 ns/op    0 B/op     0 allocs/op

License

MIT License

Documentation

Overview

Package trie implements several types of performant Tries (e.g. rune-wise, path-wise).

The implementations are optimized for Get performance and to allocate 0 bytes of heap memory (i.e. garbage) per Get.

The Tries do not synchronize access (not thread-safe). A typical use case is to perform Puts and Deletes upfront to populate the Trie, then perform Gets very quickly.

Index

• func PathSegmenter(path string, start int) (segment string, next int)
• type PathTrie
  • func LoadPathTrie(in io.Reader) (*PathTrie, error)
  • func NewPathTrie() *PathTrie
  • func (trie *PathTrie) Delete(key string) bool
  • func (trie *PathTrie) Get(key string) interface{}
  • func (trie *PathTrie) Put(key string, value interface{}) bool
  • func (trie *PathTrie) Save(out io.Writer) error
  • func (trie *PathTrie) Walk(walker WalkFunc) error
• type RuneTrie
  • func LoadRuneTrie(in io.Reader) (*RuneTrie, error)
  • func NewRuneTrie() *RuneTrie
  • func (trie *RuneTrie) Delete(key string) bool
  • func (trie *RuneTrie) Get(key string) interface{}
  • func (trie *RuneTrie) Put(key string, value interface{}) bool
  • func (trie *RuneTrie) Save(out io.Writer) error
  • func (trie *RuneTrie) Walk(walker WalkFunc) error
• type StringSegmenter
• type Trier
• type WalkFunc

Functions

func PathSegmenter

func PathSegmenter(path string, start int) (segment string, next int)

PathSegmenter segments string key paths by slash separators. For example, "/a/b/c" -> ("/a", 2), ("/b", 4), ("/c", -1) in successive calls. It does not allocate any heap memory.

Types

type PathTrie

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

PathTrie is a trie of string keys and interface{} values. Internal nodes have nil values so stored nil values cannot be distinguished and are excluded from walks. By default, PathTrie will segment keys by forward slashes with PathSegmenter (e.g. "/a/b/c" -> "/a", "/b", "/c"). A custom StringSegmenter may be used to customize how strings are segmented into nodes. A classic trie might segment keys by rune (i.e. unicode points).

func LoadPathTrie

func LoadPathTrie(in io.Reader) (*PathTrie, error)

LoadPathTrie reads a PathTrie from file (or io.Reader)

func NewPathTrie

func NewPathTrie() *PathTrie

NewPathTrie allocates and returns a new *PathTrie.

func (*PathTrie) Delete

func (trie *PathTrie) Delete(key string) bool

Delete removes the value associated with the given key. Returns true if a node was found for the given key. If the node or any of its ancestors becomes childless as a result, it is removed from the trie.

func (*PathTrie) Get

func (trie *PathTrie) Get(key string) interface{}

Get returns the value stored at the given key. Returns nil for internal nodes or for nodes with a value of nil.

func (*PathTrie) Put

func (trie *PathTrie) Put(key string, value interface{}) bool

Put inserts the value into the trie at the given key, replacing any existing items. It returns true if the put adds a new value, false if it replaces an existing value. Note that internal nodes have nil values so a stored nil value will not be distinguishable and will not be included in Walks.

func (*PathTrie) Save

func (trie *PathTrie) Save(out io.Writer) error

Save stores the trie to file in a gob format. does not store the Segmenter function

func (*PathTrie) Walk

func (trie *PathTrie) Walk(walker WalkFunc) error

Walk iterates over each key/value stored in the trie and calls the given walker function with the key and value. If the walker function returns an error, the walk is aborted. The traversal is depth first with no guaranteed order.

type RuneTrie

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

RuneTrie is a trie of runes with string keys and interface{} values. Note that internal nodes have nil values so a stored nil value will not be distinguishable and will not be included in Walks.

func LoadRuneTrie

func LoadRuneTrie(in io.Reader) (*RuneTrie, error)

LoadRuneTrie reads a RuneTrie from file (or any io.Reader)

func NewRuneTrie

func NewRuneTrie() *RuneTrie

NewRuneTrie allocates and returns a new *RuneTrie.

func (*RuneTrie) Delete

func (trie *RuneTrie) Delete(key string) bool

Delete removes the value associated with the given key. Returns true if a node was found for the given key. If the node or any of its ancestors becomes childless as a result, it is removed from the trie.

func (*RuneTrie) Get

func (trie *RuneTrie) Get(key string) interface{}

Get returns the value stored at the given key. Returns nil for internal nodes or for nodes with a value of nil.

func (*RuneTrie) Put

func (trie *RuneTrie) Put(key string, value interface{}) bool

Put inserts the value into the trie at the given key, replacing any existing items. It returns true if the put adds a new value, false if it replaces an existing value. Note that internal nodes have nil values so a stored nil value will not be distinguishable and will not be included in Walks.

func (*RuneTrie) Save

func (trie *RuneTrie) Save(out io.Writer) error

Save stores a rune-trie

func (*RuneTrie) Walk

func (trie *RuneTrie) Walk(walker WalkFunc) error

Walk iterates over each key/value stored in the trie and calls the given walker function with the key and value. If the walker function returns an error, the walk is aborted. The traversal is depth first with no guaranteed order.

type StringSegmenter

type StringSegmenter func(key string, start int) (segment string, nextIndex int)

StringSegmenter takes a string key with a starting index and returns the first segment after the start and the ending index. When the end is reached, the returned nextIndex should be -1. Implementations should NOT allocate heap memory as Trie Segmenters are called upon Gets. See PathSegmenter.

type Trier

type Trier interface {
	Get(key string) interface{}
	Put(key string, value interface{}) bool
	Delete(key string) bool
	Walk(walker WalkFunc) error
}

Trier exposes the Trie structure capabilities.

type WalkFunc

type WalkFunc func(key string, value interface{}) error

WalkFunc defines some action to take on the given key and value during a Trie Walk. Returning a non-nil error will terminate the Walk.