radix_trie/lib.rs
1//! A wonderful, fast, safe, generic radix trie implementation.
2//!
3//! To get started, see the docs for `Trie` below.
4
5// #![warn(missing_docs)]
6
7extern crate endian_type;
8extern crate nibble_vec;
9#[cfg(test)]
10extern crate quickcheck;
11#[cfg(test)]
12extern crate rand;
13
14pub use keys::TrieKey;
15pub use nibble_vec::NibbleVec;
16pub use trie_common::TrieCommon;
17use trie_node::TrieNode;
18
19use nibble_vec::Nibblet;
20
21#[macro_use]
22mod macros;
23pub mod iter;
24mod keys;
25#[cfg(feature = "serde")]
26mod serde;
27mod subtrie;
28mod traversal;
29mod trie;
30mod trie_common;
31mod trie_node;
32
33#[cfg(test)]
34mod qc_test;
35#[cfg(test)]
36mod test;
37
38const BRANCH_FACTOR: usize = 16;
39
40/// Data-structure for storing and querying string-like keys and associated values.
41///
42/// Any keys which share a common *prefix* are stored below a single copy of that prefix.
43/// This saves space, and also allows the longest prefix of any given key to be found.
44///
45/// You can read more about Radix Tries on [Wikipedia][radix-wiki].
46///
47/// Lots of the methods on `Trie` return optional values - they can be composed
48/// nicely using `Option::and_then`.
49///
50/// [radix-wiki]: http://en.wikipedia.org/wiki/Radix_tree
51#[derive(Debug, Clone)]
52pub struct Trie<K, V> {
53 /// The number of values stored in this sub-trie (this node and all descendants).
54 length: usize,
55 /// The main content of this trie.
56 node: TrieNode<K, V>,
57}
58
59/// Immutable view of a sub-tree a larger trie.
60#[derive(Debug)]
61pub struct SubTrie<'a, K: 'a, V: 'a> {
62 prefix: Nibblet,
63 node: &'a TrieNode<K, V>,
64}
65
66/// Mutable view of a sub-tree of a larger trie.
67#[derive(Debug)]
68pub struct SubTrieMut<'a, K: 'a, V: 'a> {
69 prefix: Nibblet,
70 length: &'a mut usize,
71 node: &'a mut TrieNode<K, V>,
72}
73
74/// Wrapper for subtrie lookup results.
75///
76/// When fetching from a subtrie, if the prefix is wrong you'll get an `Err(())`.
77/// Otherwise you'll get an `Ok(_)`, where the contained option value is what would ordinarily
78/// be returned by get/insert/whatever.
79pub type SubTrieResult<T> = Result<Option<T>, ()>;