Struct DynTrie 

pub struct DynTrie<T> { /* private fields */ }

A nibble trie that starts with compact u8 arena indices and automatically promotes to u16/u32/u64 as needed.

Node sizes by PTR width:

• u8: 32 bytes (fits half a cache line)
• u16: 48 bytes (fits a cache line)
• u32: 80 bytes
• u64: 152 bytes

Promotion is transparent: insert checks capacity and promotes before the underlying trie overflows. No vtable dispatch or heap allocation on promotion — just an enum variant swap.

Implementations

impl<T> DynTrie<T>

pub fn new() -> Self

Create an empty DynTrie starting with u8 arena indices (32-byte nodes).

pub fn get(&self, key: &[u8]) -> Option<&T>

Look up a key. Returns the value if found.

pub fn get_mut(&mut self, key: &[u8]) -> Option<&mut T>

Look up a key’s value for mutation. Returns the value if found.

pub fn insert(&mut self, key: Vec<u8>, value: T) -> Result<usize, ()>

Insert a key-value pair. Automatically promotes to a wider PTR type if the current one is approaching capacity. Returns the key index on success, or Err(()) on duplicate key.

pub fn len(&self) -> usize

Number of entries in the trie.

pub fn is_empty(&self) -> bool

Returns true if the trie is empty.

pub fn optimize(&mut self)

Optimize the trie’s memory layout for cache locality.

pub fn ptr_size(&self) -> usize

Returns the size of the current PTR type in bytes (1, 2, 4, or 8). Useful for debugging and testing promotion.

pub fn iter_fwd(&self, f: &mut dyn FnMut(&[u8], &T))

Iterate all key-value pairs in forward (ascending) order.

pub fn iter_rev(&self, f: &mut dyn FnMut(&[u8], &T))

Iterate all key-value pairs in reverse (descending) order.

pub fn demote(&mut self) -> Result<(), ()>

Manually demote to a narrower PTR type if the trie is small enough. Returns Ok(()) on success, Err(()) if the trie is too large or already at the minimum width (u8).

Trait Implementations

impl<T> Default for DynTrie<T>

fn default() -> Self

Returns the “default value” for a type.