Crate bitmaptrie

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

BorrowSplit	Type that borrows a Trie mutably, giving an iterable type that returns interior nodes on which structure-mutating operations can be performed. This can be used to parallelize destructive operations.
BorrowSync	Borrows a Trie mutably, exposing a Sync-safe subset of it's methods. No structure modifying methods are included. Each borrow gets it's own path cache. The lifetime of this type is the lifetime of the mutable borrow. This can be used to parallelize structure-immutant changes.
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
SubTrie	A type that references an interior Trie node. For splitting a Trie into sub-nodes, each of which can be passed to a different thread for mutable structural changes.
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