Documentation
¶
Index ¶
Constants ¶
This section is empty.
Variables ¶
var ValidCidrChars = NewValidChars([]byte{'0', '1'})
Functions ¶
func Prefix2bin128 ¶ added in v0.2.0
Types ¶
type Trie ¶
type Trie struct {
// contains filtered or unexported fields
}
Trie is a succinct, sorted and static string set impl with compacted trie as storage. The space cost is about half lower than the original data.
Implementation ¶
It stores sorted strings in a compacted trie(AKA prefix tree). A trie node has at most 256 outgoing labels. A label is just a single byte. E.g., [ab, abc, abcd, axy, buv] is represented with a trie like the following: (Numbers are node id)
^ -a-> 1 -b-> 3 $ | | `c-> 6 $ | | `d-> 9 $ | `x-> 4 -y-> 7 $ `b-> 2 -u-> 5 -v-> 8 $
Internally it uses a packed []byte and a bitmap with `len([]byte)` bits to describe the outgoing labels of a node,:
^: ab 00 1: bx 00 2: u 0 3: c 0 4: y 0 5: v 0 6: d 0 7: ø 8: ø 9: ø
In storage it packs labels together and bitmaps joined with separator `1`:
labels(ignore space): "ab bx u c y v d" label bitmap: 0010010101010101111
Finally leaf nodes are indicated by another bitmap `leaves`, in which a `1` at i-th bit indicates the i-th node is a leaf:
leaves: 0001001111
func NewTrie ¶
func NewTrie(keys []string, chars *ValidChars) (*Trie, error)
NewTrie creates a new *Trie struct, from a slice of sorted strings.
func NewTrieFromPrefixes ¶ added in v0.2.0
type ValidChars ¶
type ValidChars struct {
// contains filtered or unexported fields
}
func NewValidChars ¶
func NewValidChars(validChars []byte) (v *ValidChars)
func (*ValidChars) IsValidChar ¶
func (v *ValidChars) IsValidChar(c byte) bool
func (*ValidChars) Size ¶
func (v *ValidChars) Size() int
Source Files