bitmaptrie 1.3.1

Bitmapped vector trie (mutable, not persistent). Word-size path-cached indexing into essentially a sparse vector. Requires rust-nightly.

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


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);



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.


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.


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).


A type that implements Iterator for CompVec


A type that implements Iterator for mutable values of CompVec


Iterator over (key, &T)s of Trie<T>


Iterator over mutable (key, &mut T)s of Trie<T>


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.


Path-cached bitmap trie type. The key is always a usize.



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



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