Module nibble_trie 

Nibble Trie — a fixed-fanout radix trie indexed by nibbles (half-bytes).

Each node has 16 child slots (one per nibble value 0–15), addressed by direct indexing rather than binary search or SIMD. This trades space for simplicity and lookup speed: no comparison loops, no branch misprediction on the child search path.

Terminal Nodes

Keys that are prefixes of other keys (e.g. “ab” in {“ab”, “abc”}) are represented by a terminal flag on the node where the key ends, rather than a null-byte leaf child. This eliminates null terminators, allows 0x00 bytes in keys, and makes get() accept plain &[u8].

Empty-slot encoding (OptNz)

Child slots and the leaf field use OptNz<PTR> — a #[repr(transparent)] newtype over PTR where the value 0 means “empty” and any nonzero value is a real arena index or key index. [OptNz<PTR>; 16] is layout-identical to [PTR; 16], so the SIMD children_mask path is reused via a single repr(transparent) pointer cast. Real arena child addresses are >= 1 (the root at arena[0] is never a child target) and real key indices are >= 1 (index[0] is a dummy entry), so 0 is free as the sentinel.

Key Index Encoding

Real keys start at index 1 (index 0 is the dummy entry pointing at buf[0], an unused byte). values[i] corresponds to index[i+1] (i.e. key index ki maps to values[ki - 1]).

Structs

Cursor

Public iteration cursor over a NibbleTrie: a linear scan of the sparse index, skipping None gaps. This is correct because the index is kept sorted by invariant — occupied slots appear in non-decreasing key order (enforced by the Stage B shift-and-bump insert, and checked by the invariant-oracle tests).

CursorMut

Mutable counterpart to Cursor: a linear scan of the sparse index that lends out &mut T borrows over the stored values.

NibbleTrie

Range

Ascending iterator over a half-open key interval of a NibbleTrie, yielding (K::Borrowed<'a>, &'a T) with no allocation.

Traits

TrieIndex

Trait for types used as arena/key indices and prefix lengths in NibbleTrie.

Type Aliases

Slot

One slot of the sparse index: the buf offset (>= 1; buf[0] is the dummy byte), the key length, and the value inline. None slots are gaps.