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