tiny_trie/lib.rs
1#![feature(portable_simd)]
2
3//! Compact arena-based radix tries with SIMD-accelerated lookup.
4//!
5//! This crate provides several trie data structures optimized for different use cases:
6//!
7//! - [`NibbleTrie`] — 16-way radix trie (nibble-indexed), the flagship implementation
8//! - [`NibTrie`] — 4-way radix trie (2-bit indexed)
9//! - [`BitTrie`] — Binary radix trie (bit-indexed)
10//! - [`DynTrie`] — Auto-promoting wrapper around NibbleTrie (requires the `dyn` feature)
11//! - [`FixedLenNibbleTrie`] — NibbleTrie variant for fixed-length keys (requires the
12//! `fixed-len` feature)
13//!
14//! All tries use arena-based node allocation for cache-friendly memory layout and
15//! SIMD-accelerated child lookup where applicable.
16//!
17//! Each tree exposes a seekable cursor over `(&[u8], &T)` pairs via its `iter()` /
18//! `iter_last()` methods (`nibble_trie::Cursor`, `nib_trie::Cursor`, `bit_trie::Cursor`).
19
20mod simd;
21pub mod nibble_trie;
22pub mod nib_trie;
23pub mod bit_trie;
24#[cfg(feature = "dyn")]
25pub mod dyn_trie;
26#[cfg(feature = "fixed-len")]
27pub mod fixed_len_nibble_trie;
28mod key_store;
29mod tiny_array;
30
31// The three public trees.
32pub use nibble_trie::{NibbleTrie, TrieIndex};
33pub use nib_trie::NibTrie;
34pub use bit_trie::BitTrie;
35
36// Key trait bounds and the non-zero key type used by BitTrie / null-terminator tries.
37pub use key_store::{ByteKey, TrieKey};
38
39// Internal-only re-export: `KeyStore` is the bound on `TrieKey::Store` and is used
40// by tree modules to call store methods (`push`/`key_bytes`/`rollback`/`len`). Not
41// part of the public surface.
42pub(crate) use key_store::KeyStore;
43
44// Optional, non-default trees gated behind cargo features.
45#[cfg(feature = "dyn")]
46pub use dyn_trie::DynTrie;
47#[cfg(feature = "fixed-len")]
48pub use fixed_len_nibble_trie::FixedLenNibbleTrie;