Crate bitmaptrie [−] [src]

A bitmapped vector trie with node compression and a path cache. Values are always sorted by their index; thus iterating is always in index order.

The trie does not prescribe a length or capacity beside the range of values of it's index: usize. It could be used to compose a data structure that does behave like Vec.

The branching factor is the word-size: 32 or 64. This makes the depth 6 for 32bit systems and 11 for 64bit systems. Because of the path cache, spatially dense indexes will not cause full depth traversal.

Performance improvements:

enable popcnt instruction when supported

Possible code improvements:

with better use of generics, some code duplication might be avoided

Usage

use bitmaptrie::Trie;

let mut t: Trie<String> = Trie::new();
t.set(123, "testing 123".to_owned());

if let Some(ref value) = t.get(123) {
    println!("value = {}", *value);
}

Structs

CompVec	A simple sparse vector. The `valid` word is a bitmap of which indeces have values. The maximum size of this vector is equal to the number of bits in a word (32 or 64).
Iter	Iterator over Trie
IterMut	Iterator over Trie
PathCache	A cached path into a trie
Trie	Path-cached bitmap trie.

Enums

TrieNode

An interior (branch) or exterior (leaf) trie node, defined recursively.

Constants

USIZE_BYTES
VALID_MAX	First value to use in CompVec::next(masked__valid, ...)
WORD_SIZE