Documentation
¶
Overview ¶
Package ptrie provides a ptrie to store a mapping from bit strings to arbitrary values. Ptrie exposes a simple interface: Get(key), Put(key, value), Delete(key), and Scan(start, limit). Conceptually a ptrie can be thought of as a map[[]byte]interface{}, designed to support fast range queries and immutable views.
For performance reasons, bit strings are represented as byte slices. The ptrie consists of three concepts: a binary trie, path contraction and copy-on-write modifications.
1) A binary trie consists of nodes and arcs. Each node has a value and two children: 0 and 1. The value and the children might be nil. An arc connects a node with its child. A node N has a value V and S is the bit string of the path from the root to N iff the trie maps S to V. Using this rule we can build maps and sets. For example, a set of {'b', 'c'} can be represented as: 'b': 0110 0010 o 'c': 0110 0011 0/
1\ 1\ 0/ 0/ 0/ 1\ o 0/1\ o o
This trie has 10 nodes. This representation is not efficient. To reduce the number of nodes, we use the path contraction technique.
2) Path contraction. If a path consists only of nodes that have one child and don't have a value, then the path can be replaced with one arc. The new arc has the whole bit string written on the path. The example above becomes smaller: o
0110001/
o
0/1\
o o
This structure is stored in memory in a slightly different way. The trie consists of nodes, each node has a value and two children. Each non-nil child is a triple: the child node, the bit string written on the arc and the length of the bit string. For convenience, bits in the bit string are aligned so that the bit string might be a sub slice of a bit string representing a path from a root of the trie to the child.
3) Copy-on-write modifications. In order to support immutable views of the data in the ptrie, the Put() and the Delete() functions have the makeCopy flag. If the makeCopy flag is true, then the algorithm doesn't modify the current ptrie, but it returns a new ptrie with some nodes reused from the current one.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Stream ¶
type Stream struct {
// contains filtered or unexported fields
}
Stream is a struct for iterating through a ptrie. WARNING: The stream is not thread-safe.
The best way to walk through nodes of a tree is to perform a DFS. To support the Advance() method, we save the current state of the DFS by capturing the DFS stack.
func (*Stream) Advance ¶
Advance stages an element so the client can retrieve it with Key or Value. Advance returns true iff there is an element to retrieve. The client must call Advance before calling Key or Value.
func (*Stream) Key ¶
Key returns the key of the element that was staged by Advance. The returned slice may be a sub-slice of keybuf if keybuf was large enough to hold the entire key. Otherwise, a newly allocated slice will be returned. It is valid to pass a nil keybuf. Key may panic if Advance returned false or was not called at all.
func (*Stream) Value ¶
func (s *Stream) Value() interface{}
Value returns the value of the element that was staged by Advance. The client should not modify the returned value as the returned value points directly to the value stored in the ptrie. Value may panic if Advance returned false or was not called at all.
type T ¶
type T struct {
// contains filtered or unexported fields
}
T represents a ptrie.
func New ¶
New returns a new empty ptrie. If copyOnWrite is true, then the new ptrie performs copy-on-write modifications for Put/Delete operations and it is allowed to make a copy of the ptrie by calling Copy().
func (*T) Copy ¶
Copy returns a copy of the ptrie. This operation is only allowed if the ptrie was created with the copyOnWrite flag. Copy is a very fast operation since it just copies the pointer to the root of the ptrie. Panics if the ptrie was created with copyOnWrite=false.
func (*T) Get ¶
Get returns a value mapped to the given key. Get returns nil if the given key has no mapped value. The client must not modify the returned value as the returned value points directly to the value stored in the ptrie.
Source Files