radix_trie

radix_trie is a generic radix trie (compressed prefix tree) implementation for Rust, providing an ordered map-like data structure keyed on byte-serializable types. It compresses shared key prefixes into single nodes, reducing memory overhead versus a naive trie while preserving fast lookup, insertion, and removal.

Beyond standard map operations, radix_trie exposes trie-specific queries — closest ancestor and closest descendant lookups, and immutable/mutable subtrie views — that make it well suited for prefix-based routing, autocomplete, and hierarchical key matching. Any type that implements the TrieKey trait (already provided for strings, byte vectors, integers, and filesystem paths) can be used as a key, with optional serde support behind a feature flag.

What You Get

• A generic Trie<K, V> map type with compressed (PATRICIA-style) nodes that merge common key prefixes
• Prefix-aware queries: get_ancestor, get_raw_ancestor, get_raw_descendant, and subtrie/subtrie_mut views
• A TrieKey trait with built-in implementations for String, &str, byte vectors/slices, all integer types, and Path/PathBuf
• Optional serde feature flag for serializing and deserializing tries
• In-order iteration via iter() plus dedicated iterator types for children and descendants

Common Use Cases

• Autocomplete and prefix search over a large dictionary of strings
• IP routing tables and CIDR-style longest-prefix-match lookups
• Building word-frequency counters or n-gram indexes over text
• Filesystem-path-keyed caches or config trees using the built-in Path/PathBuf key support

Under The Hood

Architecture The crate is organized as a small set of cooperating modules under src/: trie.rs holds the public Trie<K,V> API (get/insert/remove/subtrie/get_ancestor), trie_node.rs defines the core TrieNode<K,V> recursive structure with a fixed 16-way children array (BRANCH_FACTOR=16, matching nibble-based indexing) and node-level helpers, traversal.rs implements the actual node-walking algorithms (iterative_get, iterative_insert, recursive_remove, get_ancestor, get_raw_descendant) as free functions operating on TrieNode, keys.rs defines the TrieKey trait plus match_keys for comparing nibble-encoded key fragments, and subtrie.rs/iter.rs layer read/write views and iterators on top of TrieNode. This separation of public map API, traversal algorithms, and node storage keeps each layer independently testable; data flows from a caller’s key, through TrieKey::encode into a Nibblet, down through TrieNode’s fixed-size children array. Changing the core TrieNode shape would ripple through traversal.rs’s get/insert functions and iter.rs’s traversal order, but the public Trie/SubTrie/SubTrieMut types would be unaffected.

Tech Stack Pure Rust crate (edition 2024) with a minimal dependency footprint — nibble_vec for its NibbleVec/Nibblet byte-fragment representation and endian-type for the BigEndian/LittleEndian integer key wrappers, plus an optional serde (1.0) dependency gated behind a feature flag for (de)serialization. Dev-dependencies are criterion for benchmarking, quickcheck and rand for property-based testing, and serde_test for round-trip serde tests. No build scripts, no FFI, no async — it’s a straightforward lib crate published to crates.io/docs.rs, with GitHub Actions CI running cargo fmt —check and cargo test —release —all-features across Ubuntu, macOS, and Windows.

Code Quality The crate has substantial test coverage: a large table of unit tests exercises get/insert/remove/ancestor/descendant/iteration behavior directly, and a separate quickcheck property-test module compares Trie behavior against a reference HashMap-based model across random operation sequences — a strong signal for a data-structure crate where subtle invariant bugs are easy to introduce. CI enforces formatting checks and runs the full suite with all features enabled on three operating systems, treating warnings as errors. Error handling is idiomatic Option/Result for user-facing lookups, though the TrieKey trait intentionally panics on unimplemented trait methods and on key-encoding mismatches, which is a documented, deliberate design choice rather than a swallowed error. No linting or coverage automation was observed beyond formatting and warnings-as-errors.

API Design The public API centers on a single generic Trie<K, V> with a map-like surface (get/get_mut/insert/remove) plus trie-native operations (get_ancestor, get_raw_descendant, subtrie/subtrie_mut) not found in standard library collections — giving users longest-prefix-match semantics without hand-rolling tree-walking logic. The TrieKey trait requires implementing just one of two methods to key the trie with a custom type, and the crate ships implementations for the common cases so most consumers write no boilerplate. Documentation is doc-comment-driven with a runnable example demonstrating word-frequency counting and subtrie iteration; naming is consistent with standard collection conventions, which lowers the learning curve for anyone familiar with a typical map type. The main rough edge is that some raw ancestor/descendant lookups return bare result types rather than richer typed errors, and the crate’s own documentation frames itself as needing further maintenance.