A generic, persistent (copy-on-write) radix trie with structural sharing — bring-your-own-key, no_std + alloc, parameterized over Rc/Arc.
iradix is a persistent (immutable, copy-on-write) radix trie keyed by an
arbitrary sequence of components. Each mutation returns a logically new trie;
unchanged subtrees are physically shared between versions, so a clone and a
snapshot are O(1) and a write copies only the path it touches.
It is the data-structure half of a filesystem-watch stack, but it has no dependency on any of it: it is a plain, reusable container.
- Bring-your-own-key.
RadixKeywalks a key into components. A walk yields a borrowedComponent<'a>and the trie stores an ownedOwned(the trie's component typeC);to_ownedproduces the owned form oninsert, andcompareorders a stored owned component against a walked borrowed one on descent. Each type keys on its natural element: sequences[C]/Vec<C>/Box<[C]>/[C; N]walk&C/ storeC;str/String→char; byte-addressedOsStr/OsString/CStr/CStringand the integer types (u8…u128,i8…i128, big-endian and order-preserving within one integer type — a numeric trie must be homogeneous) →u8; andPath/PathBufwalk borrowedstd::path::Components and storeOsStringpath components (so/a/bis an ancestor of/a/b/cbut not/a/bc). A walk — whatcomponents()does on every lookup, ancestor/descendant query, and removal — allocates nothing for every built-in key,Path/PathBufincluded (a slice key borrows&C, aPathyields borrowed components); onlyinsertallocates, turning each stored component into its owned form (for aPath, oneOsStringper stored component — never on a read). An operation's other costs are separate:insertallocates trie nodes, and the ordered/iterator reads (range,values,walk_*, …) allocate traversal state andVeckeys where they return keys. The stored-component bounds are justC: Ord(reads) andC: Ord + Clone(mutators); a method's key bound isRadixKey<Owned = C>. Astrkey and aVec<char>key over the same characters address the same path. - Persistent + structurally shared. A shared internal
nodecore mutates in place at refcount 1 and copies only when a node is shared, so old snapshots are never disturbed. The reference-counting pointer is an internal detail. - Sync / unsync split.
unsync::RadixusesRc(!Send, no atomics) and mutates in place via a direct&mut selfcopy-on-write handle.sync::RadixusesArc(Send + Sync, auto-derived) and is an immutable persistent tree (go-immutable-radix'sTree): mutate it through aTxn(an owned working copy — open withtxn(), edit, thencommit()into the next tree; a one-shot edit is justtxn()→ edit →commit()). Both faces share one copy-on-write core, so a.clone()and a snapshot areO(1)and structurally shared. - Path-compressed, ordered. Edges live in the parent's
Vec, sorted by their first component and located by binary search â 9EAD €” no hashing. - Prefix queries. Inclusive
get_ancestor(longest covered prefix),strict_ancestor,ancestors,descendants, and bulkremove_descendants/drain_descendants(strict) ordelete_prefix/drain_prefix(node-inclusive). - Ordered queries.
minimum/maximum, forward and reverse value iteration (values/values_rev,descendants/descendants_rev, plus node-inclusivedescendants_inclusive), and key-ordered(key, value)cursors in both directions:range(anyRangeBounds) /seek_lower_boundascending, andrange_rev/seek_reverse_lower_bounddescending. Key-carrying prefix and path walks —walk_prefix/walk_prefix_strictandwalk_path(each with a_revform) — mirror go-immutable-radix'sWalkPrefix/WalkPath. - Bring-your-own concurrency.
iradixships no built-in concurrent holder.sync::Radixis an immutable,O(1)-clone tree, so you publish new versions yourself — the lock-free pattern wraps it inarc_swap::ArcSwap<sync::Radix<…>>: readersload()a wait-free snapshot, and a writer opens atxn(),commit()s the next tree, and publishes it with a compare-and-swap retry loop (so a write is never silently lost). A worked example ships inexamples/sync.rs. - Watch (optional). With the
watchfeature, observe changes:watch(key)/watch_prefix(prefix)(orget_watch(key), which reads and arms against one immutable snapshot) return aWatchthat resolves once a change to the key — or anything in its subtree — is published — block withblock_wait()/block_wait_timeout(), orawaitchanged()(runtime-agnostic, viaevent-listener; thefuturefeature adds the boundedchanged_timeout::<R>()). Notification is at publish, not at commit (the commit → publish → notify discipline):commitbuilds the next tree but fires nothing; the winner of publication then callsnotify_changes_since(&base)(or folds both intopublish_to(&base, swap)), so a tree that loses a CAS is discarded without waking anyone. That notify fires only the events of the nodes the new version replaced (the diff prunes pointer-equal subtrees, scanning the changed paths and their siblings — not the whole tree); aWatchis single-use, may over-notify (re-read to confirm), and is meant for a reload-and-re-arm loop. The feature is zero-cost when off. A worked example ships inexamples/watch.rs. no_std+alloc.stdandallocare independent features.
[dependencies]
iradix = "0.3"For no_std (heap required):
[dependencies]
iradix = { version = "0.3", default-features = false, features = ["alloc"] }Runnable, self-contained examples live in examples/:
| example | what it shows |
|---|---|
unsync |
unsync::Radix — exact lookup; longest-covered-prefix queries (get_ancestor / strict_ancestor); ordered queries (minimum / maximum / range / seek_lower_bound); node-inclusive prefix removal; and O(1) snapshot isolation. |
sync |
sync::Radix — lock-free concurrent reads (Send + Sync); a one-shot txn() → edit → commit() and a batching Txn → commit; and the lock-free shared-holder pattern with arc_swap::ArcSwap<sync::Radix<…>> (load to read; txn → commit → CAS to publish). |
watch |
the watch feature — watch / watch_prefix / get_watch returning a Watch; blocking block_wait() and async changed().await; the commit → publish → notify loop over an ArcSwap (publish_to on a winning CAS, a lost CAS waking nobody, and reload-and-re-arm). Run with --features watch. |
Run them with:
cargo run --example unsync
cargo run --example sync
cargo run --example watch --features watch| feature | default | effect |
|---|---|---|
std |
yes | links the real standard library. |
alloc |
no | no_std + heap (the alloc-as-std alias). Independent of std. |
watch |
no | observe key/prefix changes on the sync face: watch / watch_prefix / get_watch → blocking Watch::{block_wait, block_wait_timeout} (need std) or async Watch::changed() (a named Changed future; no_std + alloc), with publish-time notification via notify_changes_since / publish_to. Pulls event-listener. |
future |
no | runtime-agnostic async timeout: Watch::changed_timeout::<R>(d) (R = TokioRuntime / SmolRuntime / WasmRuntime / EmbassyRuntime / …) → Result<(), Elapsed>. Built on agnostic-lite; re-exports the RuntimeLite trait as iradix::RuntimeLite. Implies watch; no_std + alloc. |
tokio / smol |
no | convenience: enable agnostic-lite's tokio / smol backend and re-export its runtime as iradix::TokioRuntime / iradix::SmolRuntime (each implies future), so a runtime is nameable from iradix alone. Other backends (async-io / wasm / embassy) — add agnostic-lite directly. |
triomphe |
no | back the sync face with triomphe's Arc (no weak count, more compact) instead of std::sync::Arc, via archery's ArcTK. Same public API; opt-in; no_std + alloc. |
std and alloc are independent (std does not imply alloc). The crate
always needs the heap, so the bare no-feature configuration does not compile —
build with at least alloc.
iradix upholds the strong exception guarantee for the recoverable panic a
generic container can actually encounter: a panicking user Clone, Ord, or
PartialEq. If insert, remove, remove_descendants, or drain_descendants
unwinds because user code panicked, the trie is left exactly as it was — len
stays accurate, every previously stored key still resolves, and no stored value is
dropped or lost (a value-returning call either returns its value or leaves it in
place).
Two failure modes are out of scope, both matching the standard library, which makes no guarantee across either:
- Panicking
Drop— a destructor that panics while unwinding aborts the process, so no container can stay sound across one. Removing an edge runs user destructors; if one panics, the operation may be left partially committed. Keep destructors panic-free. - Allocation failure — like
Vec/Box,iradixreaches the global allocator through infallible APIs, so out-of-memory invokes the allocation-error handler (an abort by default), not an unwind. There is therefore no recoverable allocation panic to be safe across; OOM does not corrupt the trie because it does not return.
benches/comparison.rs measures iradix against radix_trie, patricia_tree,
qp-trie, im's OrdMap, and std's BTreeMap across insert / get / iter /
remove / snapshot-then-insert, on random and path-like keysets — numbers and
methodology in benches/README.md. The shape of the results:
among ordered prefix maps iradix leads on insert/get/remove, and its
copy-on-write snapshot stays O(1) — a clone-then-insert runs in nanoseconds where
an ephemeral map deep-copies — which is the reason to reach for a persistent trie.
The crate is no_std with alloc. Build it with --no-default-features --features alloc.
Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in this crate by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.