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

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

CompVecIter

A type that implements Iterator for CompVec

CompVecIterMut

A type that implements Iterator for mutable values of CompVec

Iter

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

IterMut

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

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 type. The key is always a usize.

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