Crate radix_immutable

Radix Trie

A radix trie implementation with structural sharing and fast prefix comparison.

This crate provides an immutable radix trie (also known as a patricia trie) that uses structural sharing via Arc to efficiently create new versions of the trie while sharing unchanged parts.

Features

• Immutable API: All modifying operations return a new trie instance
• Structural Sharing: Efficient memory usage through shared unchanged subtrees
• Fast Prefix Comparison: Compare subtrees efficiently using structural hashing
• Prefix Views: Create lightweight views into trie prefixes with fast comparison and lookup support

Example

use radix_immutable::StringTrie;

// Create a new trie
let trie = StringTrie::<String, i32>::new();

// Insert some values (each operation returns a new trie)
let trie = trie.insert("hello".to_string(), 1);
let trie = trie.insert("world".to_string(), 2);

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

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

PrefixView provides efficient views of subtries based on key prefixes. This enables fast comparison between subtries with the same prefix, as well as key lookups and existence checks.

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>)