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 ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
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 NewPathTrieWithConfig ¶
func NewPathTrieWithConfig(config *PathTrieConfig) *PathTrie
NewPathTrieWithConfig allocates and returns a new *PathTrie with the given *PathTrieConfig
func (*PathTrie) Delete ¶
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 ¶
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 ¶
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) Walk ¶
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 PathTrieConfig ¶
type PathTrieConfig struct {
Segmenter StringSegmenter
}
PathTrieConfig for building a path trie with different segmenter
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 (*RuneTrie) Delete ¶
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 ¶
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 ¶
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) Walk ¶
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 ¶
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.