Expand description
Bit Trie — a binary radix trie indexed by individual key bits.
Each node has exactly two children (bit 0 and bit 1), stored inline as
[u32; 2]. Because both children are always present in a binary trie,
there are no empty slots and no mask needed for child enumeration —
just children[bit].
§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].
§High-Bit Leaf Encoding
Bit 31 of each children[i] indicates whether the value is a leaf key
index (bit set) or an arena index (bit clear). Bit 31 of leaf indicates
whether the node is terminal. This packs the leaf/terminal flags into
existing fields, eliminating the separate leaf_mask byte.
§Per-Child Prefix Lengths
Each node stores prefix_lens: [u16; 2] — the prefix length (in bits) for
each child. The node’s own prefix length comes from its parent. The root’s
prefix length is stored in BitTrie.root_prefix_len.
§Key Index Encoding
A dummy entry at index[0] = (0, 0) points at buf[0] (empty key).
Real keys start at index 1. This allows 0 to be used as a sentinel for
“empty” in children[] slots.