Crate radix_immutable 

Radix Immutable

An immutable radix trie (patricia trie) with structural sharing via Arc. Each mutation returns a new trie, sharing unchanged subtrees with the original.

Features

• Immutable API: insert/remove return new tries; originals are unchanged
• Structural sharing: unchanged subtrees shared via Arc, making clones cheap
• Longest prefix match: find the most specific stored prefix for a key
• Prefix iteration: iterate entries under a prefix without scanning the full trie
• Prefix views: lightweight subtrie handles for comparison and lookup
• Structural hashing: lazily cached hashes for fast subtree equality checks
• Serde support: optional serde feature flag
• Key generic: supports any type convertible to bytes

Example

use radix_immutable::StringTrie;

let trie = StringTrie::<String, i32>::new()
    .insert("hello".to_string(), 1)
    .insert("help".to_string(), 2)
    .insert("world".to_string(), 3);

// Lookup
assert_eq!(trie.get(&"hello".to_string()), Some(&1));

// Longest prefix match
let trie = trie.insert("/api".to_string(), 10)
    .insert("/api/users".to_string(), 20);
assert_eq!(
    trie.longest_prefix_match(&"/api/users/123".to_string()),
    Some((&"/api/users".to_string(), &20))
);

// Prefix iteration
let hel_entries: Vec<_> = trie.iter_prefix("hel".to_string()).collect();
assert_eq!(hel_entries.len(), 2);

You can also use custom types with a specialized key converter:

use radix_immutable::{Trie, KeyToBytes};
use std::path::{Path, PathBuf};
use std::borrow::Cow;
use std::marker::PhantomData;

// Create a custom key converter for PathBuf
#[derive(Clone, Debug)]
struct PathKeyConverter<K>(PhantomData<K>);

impl<K> Default for PathKeyConverter<K> {
    fn default() -> Self {
        Self(PhantomData)
    }
}

impl<K: Clone + std::hash::Hash + Eq + AsRef<Path>> KeyToBytes<K> for PathKeyConverter<K> {
    fn convert<'a>(key: &'a K) -> Cow<'a, [u8]> {
        // Convert path to string and then to bytes
        let path_str = key.as_ref().to_string_lossy();
        Cow::Owned(path_str.as_bytes().to_vec())
    }
}

// Create a trie that uses PathBuf as keys with our custom converter
let trie = Trie::<PathBuf, i32, PathKeyConverter<PathBuf>>::new();

Re-exports

pub use crate::key_converter::BytesKeyConverter;

pub use crate::key_converter::KeyToBytes;

pub use crate::key_converter::StrKeyConverter;

pub use crate::node::TrieNode;

Modules

key_converter

Defines traits and structs for converting trie keys into byte sequences.

node

Internal node implementation for the radix trie.

Structs

PrefixView

A lightweight view into a subtrie defined by a key prefix.

PrefixViewArcIter

Arc-based iterator over the key-value pairs in a prefix view.

PrefixViewIter

An iterator over the entries of a PrefixView.

Trie

An immutable radix trie with structural sharing.

Enums

Error

Errors that can occur in trie operations

Type Aliases

BytesPrefixView

Type alias for a PrefixView of a BytesTrie

BytesTrie

Type alias for a Trie that uses byte-based keys (anything implementing AsRef<u8>)

StringPrefixView

Type alias for a PrefixView of a StringTrie

StringTrie

Type alias for a Trie that uses string-based keys (anything implementing AsRef<str>)