Struct Tree 

pub struct Tree {
    pub tenant_char_count: DashMap<TenantId, usize>,
    /* private fields */
}

Fields

tenant_char_count: DashMap<TenantId, usize>

Per-tenant character count for size tracking. Using TenantId for consistency.

Implementations

impl Tree

pub fn new() -> Self

pub fn insert_text(&self, text: &str, tenant: &str)

pub fn match_prefix_with_counts(&self, text: &str) -> PrefixMatchResult

Performs prefix matching and returns detailed result with char counts. Optimized: no string allocations, deferred char counting.

pub fn match_and_insert(&self, text: &str, tenant: &str) -> PrefixMatchResult

Combined match + insert for a known tenant in a single descent.

Thin wrapper over Self::match_and_insert_with for callers that already know the tenant to insert for before matching (e.g. the imbalanced min-load path, which routes by worker load, not cache affinity). Returns the match result for any cache bookkeeping the caller needs.

pub fn match_and_insert_with<'t, F>( &self, text: &str, select: F, ) -> PrefixMatchResult

where F: FnOnce(&PrefixMatchResult) -> Option<&'t str>,

Match in a single descent, then choose the insert tenant from the match result and insert for it — still a SINGLE walk of the matched prefix.

String analogue of TokenTree::match_and_insert_with. The cache-aware router picks the worker it inserts for from the match outcome, so the tenant is unknown until the match finishes. select runs once, after the match, with the PrefixMatchResult; Some(tenant) inserts text for that tenant, None skips the insert (the router’s “no worker selected” branch).

How the single descent is achieved

The match phase walks the prefix exactly like Self::match_prefix_with_counts (including its single deferred, probabilistic timestamp touch on the resolved node — done via Self::finish_match_and_insert), while recording the chain of full-match nodes it descended through. After select yields the tenant we re-attach it to those recorded ancestor nodes directly (the epoch-0 intermediate attach insert_text performs while descending) and splice only the unmatched suffix at the fall-off node via Self::insert_from. The matched prefix is therefore compared once, not twice.

Preserved semantics

Identical to match_prefix_with_counts followed by insert_text(text, tenant): same matched/-input char counts, same resolved tenant and probabilistic touch, same node splits, same epoch-0 ancestor attaches, same final-leaf real timestamp, and same tenant_char_count accounting. Because the match phase runs fully before any insert mutation (just like the two separate calls), the tenant pick observes the un-polluted tree; only the exact monotonic timestamp values of insert’s writes shift by a few ticks, which is immaterial to LRU.

pub fn prefix_match_legacy(&self, text: &str) -> (String, String)

Legacy prefix_match API for backward compatibility. Note: This computes matched_text which has allocation overhead.

pub fn prefix_match_tenant(&self, text: &str, tenant: &str) -> String

pub fn evict_tenant_by_size(&self, max_size: usize)

pub fn get_tenant_char_count(&self) -> HashMap<String, usize>

pub fn get_used_size_per_tenant(&self) -> HashMap<String, usize>

pub fn evict_by_tenant(&self, tenant: &TenantId, max_chars: usize)

Evict entries for a specific tenant to reduce to max_chars.

pub fn remove_tenant_all(&self, tenant_id: &TenantId)

Remove a tenant from all nodes in the tree, including root. Used for mesh eviction propagation — when a remote node reports that a worker evicted all its cached prefixes.

pub fn tenant_char_size(&self, tenant: &TenantId) -> usize

Get the char count for a specific tenant.

pub fn clear(&self)

Clear the tree to empty state.

pub fn pretty_print(&self)

pub fn snapshot(&self) -> TreeSnapshot

Create a compact snapshot of the tree for mesh synchronization.

Walks the tree depth-first (pre-order) and emits each node’s edge label + tenant list. Shared prefixes are stored once — a tree with 2048 entries sharing 80% prefixes serializes to ~2-4 MB instead of ~40 MB as flat insert operations.

Concurrency

This traversal is NOT atomic — concurrent insert_text calls may split or replace nodes during the walk. The per-node DashMap and RwLock guards ensure individual reads are safe, but the snapshot may reflect a mix of pre-split and post-split state. This is acceptable for mesh sync (eventual consistency).

pub fn iter_entries(&self) -> EntriesIter

Lazily walk the tree in pre-order, yielding each node’s (prefix, [(tenant, epoch)]) pair without materializing the full tree as a single buffer. Empty-tenant nodes are skipped (they’re routing intermediates, not real entries). Children are visited in deterministic char-sorted order so callers paging the iterator can resume by re-running and skipping the first N items if the tree is unchanged.

Like Tree::snapshot, the walk is not atomic — concurrent insert_text may split or replace nodes mid-walk; the iterator may then reflect a mix of pre- and post-split state. Acceptable for mesh sync (eventual consistency).

impl Tree

pub fn from_snapshot(snapshot: &TreeSnapshot) -> Self

Reconstruct a tree from a snapshot.

The snapshot must be in pre-order (parent before children) with child_count fields indicating tree structure.

pub fn merge_snapshot(&self, snapshot: &TreeSnapshot)

Merge a remote snapshot into this tree.

Reconstructs the remote tree from the snapshot, then walks both trees recursively, handling three cases for each child:

1. Exact edge match → recurse into both subtrees
2. Local edge is prefix of remote → descend into local, continue with remainder
3. Shared prefix shorter than both → split local node, attach remote remainder

pub fn merge_tree(&self, remote: &Tree)

Merge another tree into this tree.

Walks both trees recursively. At each node, merges tenant maps (remote wins on newer epoch) and reconciles children using the three-case edge comparison.

Trait Implementations

impl Debug for Tree

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for Tree

fn default() -> Self

Returns the “default value” for a type.

impl RadixTree for Tree

type Key = str

The key type for this tree (e.g., &str or &u32)

type MatchResult = PrefixMatchResult

The result type returned by prefix matching

fn insert(&self, key: &Self::Key, tenant: &str)

Insert a key with associated tenant.

fn prefix_match(&self, key: &Self::Key) -> Option<TenantId>

Find the longest matching prefix and return the associated tenant.

fn prefix_match_with_counts(&self, key: &Self::Key) -> Self::MatchResult

Find the longest matching prefix with detailed match counts.

fn evict(&self, tenant: &TenantId, max_units: usize)

Evict cached entries for a tenant to reduce memory usage.

fn tenant_size(&self, tenant: &TenantId) -> usize

Get the current size (in units) for a tenant.

fn reset(&self)

Reset the tree to empty state.