Crate fast_radix_trie 

Memory-efficient trie data structures based on radix tree.

A radix tree compresses nodes such that common prefixes are shared. This minimizes memory usage for storing large sets of strings/bytes. Additionally, this library optimizes memory layout/padding to further reduce memory consumption, leading to significant memory savings and fast traversal time for large data sets.

fast_radix_trie has a benchmark suite run against std’s HashMap/BTreeMap and other popular rust trie libraries, and fast_radix_trie seems to use (much) less memory than most while also being faster or on par for insert/remove/retrieve operations.

See Radix tree for more details.

Examples

use fast_radix_trie::RadixMap;

let mut map = RadixMap::new();
map.insert("a", 1);
map.insert("apple", 2);
map.insert("applesauce", 3);
map.insert("apply", 4);
map.insert("abort", 5);
map.insert("abs", 6);
map.insert("box", 7);

// &map = "" (-)
//      ├─"a" (1)
//            ├─"b" (-)
//                  ├─"ort" (5)
//                  └─"s" (6)
//            └─"ppl" (-)
//                  ├─"e" (2)
//                        └─"sauce" (3)
//                  └─"y" (4)
//      └─"box" (7)

assert_eq!(map.len(), 7);

assert_eq!(map.get("a"), Some(&1));
assert_eq!(map.get("apple"), Some(&2));
assert_eq!(map.get("applesauce"), Some(&3));
assert_eq!(map.get("applebees"), None);

// You can split by prefix also to create separate the tree:
let other = map.split_by_prefix("ap");
dbg!(&map);
// &map = "" (-)
//      ├─"a" (1)
//            └─"b" (-)
//                  ├─"ort" (5)
//                  └─"s" (6)
//      └─"box" (7)
dbg!(&other);
// &other = "" (-)
//     └─"appl" (-)
//         ├─"e" (2)
//             └─"sauce" (3)
//         └─"y" (4)

// You can also use `common_prefixes` to return an iterator over all matching entries
// as you traverse:

let mut t = RadixMap::new();
t.insert("a", vec!["a"]);
t.insert("x", vec!["x"]);
t.insert("ab", vec!["b"]);
t.insert("abc", vec!["c"]);
t.insert("abcd", vec!["d"]);
t.insert("abcdf", vec!["f"]);

assert!(t
    .common_prefixes(b"abcde")
    .map(|(_, v)| v)
    .flatten()
    .eq(vec![&"a", &"b", &"c", &"d"].into_iter()));

assert_eq!(
    t.entry("ab")
        .and_modify(|v| {
            v.push("g");
        })
        .or_insert_with(Vec::new),
    &vec!["b", "g"]
);

Re-exports

pub use map::GenericRadixMap;

pub use map::RadixMap;

pub use map::StringRadixMap;

pub use set::GenericRadixSet;

pub use set::RadixSet;

pub use set::StringRadixSet;

pub use node::Node;

Modules

entry

entry module

map

A map based on a patricia tree.

node

A node which represents a subtree of a patricia tree.

set

A set based on a patricia tree.

Traits

BorrowedBytes

Borrowed type of Bytes.

Bytes

This trait represents a bytes type that can be used as the key type of patricia trees.

Functions

longest_common_prefix

returns index of where a & b differ, and the ordering of the differing bit otherwise returns None

longest_common_prefix_by_byte

returns index of where a & b differ, and the ordering of the differing bit otherwise returns None

strip_prefix

uses memchr to strip the prefix from the haystack if it is a valid prefix