Struct FixedLenNibbleTrie 

pub struct FixedLenNibbleTrie<T, PTR: TrieIndex = u32> {
    pub arena: Vec<FixedLenNode<PTR>>,
    pub buf: Vec<u8>,
    pub values: Vec<T>,
    pub lens: Vec<u16>,
    pub max_len: usize,
}

A fixed-length nibble trie map.

Keys are stored in fixed-size slots of max_len bytes, zero-padded on the right. Key length is recovered by scanning backward from the slot boundary for the first nonzero byte. Keys must not contain trailing zero bytes — a key like b"a\0" would be retrieved as b"a".

The PTR type parameter controls the width of arena/key indices and thus the maximum number of entries (~PTR::max_value() - 1).

Fields

arena: Vec<FixedLenNode<PTR>>

buf: Vec<u8>

values: Vec<T>

lens: Vec<u16>

max_len: usize

Implementations

impl<T, PTR: TrieIndex> FixedLenNibbleTrie<T, PTR>

pub fn new(max_len: usize) -> Self

Create a new empty trie with the given maximum key length.

Keys longer than max_len will be rejected by insert.

pub fn len(&self) -> usize

pub fn is_empty(&self) -> bool

pub fn key_slice(&self, ki: PTR) -> &[u8]

Return the actual (unpadded) key slice for key index ki. Uses the stored length for O(1) retrieval.

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

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

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

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

Unchecked value lookup — assumes the key is present in the trie.

Safety

The key must have been inserted into this trie. If the key is not present, the result is unspecified.

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

pub fn optimize(&mut self)

Rewrite buf and values so that keys appear in sorted order, with contiguous layout for sequential access during iteration.

After optimize(), a forward iteration visits keys in ascending memory order within buf. Leaf indices in arena nodes are remapped to reflect the new positions.

No-op for empty tries.

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

Insert and auto-optimize on power-of-two sizes.

pub fn iter(&self) -> FixedLenIter<'_, T, PTR>

pub fn iter_last(&self) -> FixedLenIter<'_, T, PTR>

pub fn into_keys_values(self) -> (Vec<Vec<u8>>, Vec<T>)

pub fn near_capacity(&self) -> bool

Trait Implementations

impl<T: Clone, PTR: Clone + TrieIndex> Clone for FixedLenNibbleTrie<T, PTR>

fn clone(&self) -> FixedLenNibbleTrie<T, PTR>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T, PTR: TrieIndex> Default for FixedLenNibbleTrie<T, PTR>

fn default() -> Self

Returns the “default value” for a type.