Struct NibbleTrie 

pub struct NibbleTrie<K, T, PTR: TrieIndex = u32, LEN: TrieIndex = u16>
where
    K: ByteKey,
{ /* private fields */ }

Implementations

impl<K: ByteKey, T, PTR: TrieIndex, LEN: TrieIndex> NibbleTrie<K, T, PTR, LEN>

pub fn new() -> Self

pub fn len(&self) -> usize

pub fn is_empty(&self) -> bool

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>

if the key is guaranteed to be in the set, the final comparison can be skipped, improving perf substantially.

pub fn iter(&self) -> Cursor<'_, K, T, PTR, LEN>

Public forward cursor: parked before the first key (so current() is None and next() yields the first key). A linear scan over the sparse index, skipping None gaps.

pub fn iter_last(&self) -> Cursor<'_, K, T, PTR, LEN>

Public reverse cursor: parked on the last key (current() returns it, prev() walks backward). Linear scan over index.

pub fn iter_mut(&mut self) -> CursorMut<'_, K, T, PTR, LEN>

Public forward mutable cursor: parked before the first key, lending out &mut T borrows tied to the cursor (see CursorMut).

pub fn iter_mut_last(&mut self) -> CursorMut<'_, K, T, PTR, LEN>

Public reverse mutable cursor: parked on the last key, lending out &mut T borrows tied to the cursor (see CursorMut).

pub fn range<'q>( &self, bounds: impl RangeBounds<&'q [u8]>, ) -> Range<'_, K, T, PTR, LEN>

Iterate the keys in bounds in ascending order — a zero-allocation Range yielding (K::Borrowed<'_>, &T). Both bounds are resolved by O(keylen) seeks up front; the scan between them is then bounded by slot index (pos < end_pos), so no per-element key comparison is needed. Accepts any [RangeBounds<&[u8]>]: start..end, start.., ..end, .. (operands are &[u8]). The bounds’ byte slices are used only during the initial seeks and need not outlive the call.

pub fn range_bounds( &self, start: Bound<&[u8]>, end: Bound<&[u8]>, ) -> Range<'_, K, T, PTR, LEN>

Like range but with explicit Bounds — for mixed Included/Excluded bounds without the &&[u8] double-reference the RangeBounds tuple form would require.

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

pub fn near_capacity(&self) -> bool

pub fn optimize(&mut self)

Rewrite buf in DFS (key-sorted) order and re-spread index into a sparse layout: a fresh vec of capacity 2*n+1 with each key placed at slot 2*i+1 (DFS rank i), leaving even slots as None gaps. Forward iteration then hits buf in ascending memory order, and the gaps give future inserts room to shift into without re-sorting.

Also (re)establishes the leftmost-leaf invariant: every node’s leaf is set to the key index of the leftmost key in its subtree. The arena topology (child structure) is unchanged — only key indices are remapped. Idempotent.

pub fn flatten(&mut self)

Flatten small multi-Inode subtrees into single [FlatNode]s.

Rebuilds the arena top-down: any non-root subtree with ≤ [FNODE_CAP] keys and ≥ 2 Inodes (so collapsing it actually saves memory) is replaced by one Fnode built from a pre-order DFS of that subtree. The root stays an Inode. This is an arena-only rebuild — key indices (leaf children, each Inode’s leaf, and Fnode base/offsets) are unchanged; only internal-child arena indices are remapped. So index/buf are untouched and the existing get/iter/seek paths work unchanged.

Idempotent: an Fnode holds no arena refs, so a subtree already containing an Fnode can’t be re-flattened (the Fnode is copied verbatim and [build_fnode_subtree] rejects Fnode children). Calling flatten on an already-flat trie is a no-op topology copy.

Best called after optimize: the 2i+1 respread makes a ≤16-key subtree span exactly ≤32 index slots, so every offset fits in u8 with room (≤ 30 ≪ 0xFF), and offsets come out canonical even values 0, 2, 4, ….

impl<K: ByteKey, T, PTR: TrieIndex, LEN: TrieIndex> NibbleTrie<K, T, PTR, LEN>

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

impl<K: ByteKey, T, PTR: TrieIndex, LEN: TrieIndex> NibbleTrie<K, T, PTR, LEN>

pub fn promote<NewPTR: TrieIndex>(self) -> NibbleTrie<K, T, NewPTR, LEN>

Promote the arena index type to a wider PTR. All child indices and leaf key indices are widened via NewPTR::from_usize.

pub fn demote<NewPTR: TrieIndex>( self, ) -> Result<NibbleTrie<K, T, NewPTR, LEN>, Self>

Demote the arena index type to a narrower PTR. Returns Err(self) if any index doesn’t fit in the narrower type.

Trait Implementations

impl<K, T: Clone, PTR: Clone + TrieIndex, LEN: Clone + TrieIndex> Clone for NibbleTrie<K, T, PTR, LEN>

where K: ByteKey + Clone,

fn clone(&self) -> NibbleTrie<K, T, PTR, LEN>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<K: ByteKey, T, PTR: TrieIndex, LEN: TrieIndex> Default for NibbleTrie<K, T, PTR, LEN>

fn default() -> Self

Returns the “default value” for a type.