internals.md

Internal Implementation

This document explains cedarwood's internal mechanics in detail: how free space is managed, how conflicts are resolved, and how the block heuristics work. This is intended for contributors or anyone curious about what happens beneath the public API.

Initialization

Cedar::new() sets up the initial state:

1. Array: 256 Node entries are allocated (one block). Index 0 is the root node with base_ = 0 (or -1 in reduced-trie mode) and check = -1. Indices 1-255 are linked into a free list: each node's base_ points backward and check points forward, forming a cyclic doubly-linked list.

2. NInfo: 256 default entries (all zeros -- no children, no siblings).

3. Blocks: One Block with num = 256, e_head = 1, and reject = 257. Block 0 contains 255 actual free slots plus the occupied root: its num convention counts the reserved root as one virtual free slot. Thus its actual free count is num - 1; all other blocks use num.

4. Reject table: reject[i] = i + 1 for i in 0..=256. This initializes the global pruning heuristic.

5. Block lists: All three list heads are 0, meaning empty. Block 0 never belongs to a category list. Root transitions can claim its slots directly; allocation searches use non-root blocks.

Free-List Structure Within a Block

Within each 256-element block, free nodes form a cyclic doubly-linked list using the base_ (backward pointer) and check (forward pointer) fields of the Node struct. Both pointers are stored as negated values to distinguish free nodes from active ones:

Free node at index e:
    base_ = -(previous free node index)
    check = -(next free node index)

Occupied non-root node at index e:
    check >= 0   (parent node index)
    base_        (branch base, stored value, or layout-specific sentinel)

When a block has free slots, its e_head points to one of them. To enumerate free nodes, follow the check chain (negating to get the actual index) until you loop back to e_head. A block with no actual free slots has no valid free-list head, even though block 0 still reports num = 1.

Allocating a free node (pop_e_node)

When a node is needed:

1. Determine the target index e (either from find_place/find_places, or directly from base XOR label).
2. If other free slots remain, remove e by linking its predecessor to its successor and advance e_head if needed. For the final actual free slot, no links remain to repair.
3. Decrement the block's num. Non-root blocks move from Closed to Full at num = 0, or from Open to Closed at num = 1 when they have not already exhausted max_trial. Removing the final actual free slot leaves no free-list links to repair; that happens at num = 1 in block 0.
4. Initialize the node: default layout sets base_ to -1 (or 0 for a terminal); reduced layout uses CEDAR_VALUE_LIMIT. Set check to the parent.
5. If this is the first child (base < 0), set the parent's logical base to e XOR label. Store that value directly in base_ for the default layout, or as -base - 1 for reduced-trie.

Freeing a node (push_e_node)

When a node is deleted:

1. Increment the block's num. For non-root blocks, transfer Full to Closed when num goes from 0 to 1, or Closed to Open when it goes from 1 to 2 (or trial == max_trial).
2. If this is the first actual free slot, create a singleton cyclic free list. This includes block 0 transitioning from num = 1 to num = 2. Otherwise insert the node immediately after e_head. Never follow a stale head left over from an exhausted free list.
3. Update the reject heuristic if needed.
4. Clear the node's NInfo.

Block Management

The Three Block Lists

Non-root blocks are organized into three cyclic doubly-linked lists based on their free slot count and placement trial count:

blocks_head_open ──→ [block A] ⇄ [block B] ⇄ [block C] ──→ (back to A)
                     num > 1     num > 1     num > 1

blocks_head_closed ─→ [block D] ⇄ [block E] ──→ (back to D)
                      num == 1    trial == max_trial, num > 1

blocks_head_full ───→ [block F] ──→ (back to F)
                      num == 0

A head value of 0 means the list is empty. Block 0 is excluded from all three lists. The prev and next fields in each non-root Block maintain the doubly-linked list. Open blocks must also have trial < max_trial; a demoted Closed block may have many free slots.

Block Transfer

When a block's num changes, it may need to move between lists:

Transition	Trigger	From	To
Allocation	num: 2 → 1	Open	Closed
Allocation	num: 1 → 0	Closed	Full
Deletion	num: 0 → 1	Full	Closed
Deletion	num: 1 → 2, or a demoted block gains a slot	Closed	Open
Max trial reached	trial == max_trial	Open	Closed

The transfer_block function handles this by calling pop_block (remove from source list) then push_block (insert at head of destination list).

Adding New Blocks

When no existing block can fit the needed children, add_block allocates a new 256-element block:

1. If size == capacity, double the capacity and resize all vectors.
2. Initialize the new block's nodes as a cyclic free list (same structure as initialization).
3. Push the new block onto the Open list.
4. Increment size by 256.

The array grows by doubling (capacity += capacity), giving amortized O(1) for growth.

Conflict Resolution (resolve)

A conflict occurs when follow tries to place a child at base[from] XOR label, but that slot is already owned by a different parent. The resolution strategy:

Direct sorted construction bypasses follow and resolve. Since each sorted prefix range reveals all sibling labels at once, allocate_bulk_siblings chooses one base with find_place or find_places, claims every label with pop_e_node, and writes the complete ordered NInfo chain. Using pop_e_node is essential: it keeps the per-block free list, free count, and Open/Closed/Full membership valid for later incremental mutation.

Step 1: Identify the Parties

from_n = the node trying to insert a new child
base_n = base[from_n]
label_n = the label being inserted

to_pn = base_n XOR label_n    (the contested slot)
from_p = check[to_pn]          (the current owner of the slot)
base_p = base[from_p]

Step 2: Choose Who to Relocate (consult)

consult races through the sibling chains of both nodes. Whichever chain ends first has fewer children -- that node gets relocated because it's cheaper. The function returns true if the new node (from_n) should be relocated, false if the existing node (from_p) should be.

Step 3: Collect Children (set_child)

set_child walks the sibling chain starting from the first child, collecting all labels into a SmallVec<[u8; 256]>. If relocating the new node, the new label is also included in the list. When ordered is true, the list stays sorted so common_prefix_predict returns results in byte-lexicographic order. Prediction also works with unordered siblings.

Step 4: Find Free Space

• If only one child: find_place returns the first free slot from any Closed or Open block.
• If multiple children: find_places searches Open blocks for a contiguous-enough region. It iterates free slots within a block, checking if all base XOR child[i] positions are free. The reject heuristic prunes blocks that can't possibly fit.

Step 5: Relocate

For each child in the list:

1. Allocate the new position via pop_e_node.
2. Copy base_ from the old position to the new one.
3. If the child has its own children (non-leaf), update all grandchildren's check to point to the new position.
4. Free the old position via push_e_node.
5. If the node being relocated was from_n, update from_n to track the new position.

The Reject Heuristic

The reject array records placement thresholds by free-slot count (0-256). Each block also has its own threshold. find_places searches only when the requested sibling count is below the block threshold and there are enough free slots:

if self.blocks[idx].num >= nc && nc < self.blocks[idx].reject {
    // Worth searching this block
} else {
    // Skip: either not enough free slots, or the heuristic avoids this probe.
}

The heuristic is updated whenever find_places leaves a block without a placement, including blocks skipped by the condition above:

self.blocks[idx].reject = nc;
if self.blocks[idx].reject < self.reject[self.blocks[idx].num] {
    self.reject[self.blocks[idx].num] = self.blocks[idx].reject;
}

Sibling labels determine whether their XOR positions fit; their count alone does not prove a placement impossible. This is a speed/space heuristic, not a memoized correctness fact. Deletion uses the global threshold to relax the block's rejection threshold, and can reopen demoted blocks.

Sibling Chain Management

push_sibling

Inserts a label into a node's child list. When ordered is true (the default), the label is inserted in sorted order by walking the sibling chain until the correct position is found. This maintains the invariant that common_prefix_predict_iter yields results in lexicographic order.

pop_sibling

Removes a label from the sibling chain. Walks the chain from child through sibling links until the target label is found, then splices it out.

max_trial Parameter

The max_trial field (default: 1) controls how many times a block can be probed by find_places before it is demoted from Open to Closed. A lower value makes the search faster but may waste more space; a higher value searches more thoroughly. Cedar::builder().max_trial(...) exposes this setting and rejects nonpositive values.

With max_trial = 1, a block gets at most one chance per insertion cycle. After being probed once unsuccessfully, it moves to Closed and won't be searched again for multi-child allocations until a deletion reopens it.

Reduced-Trie Mode

With the reduced-trie feature enabled, the key behavioral differences are:

1. Values in leaves: When a leaf node stores a value, it is placed directly in base_ (as a non-negative integer) instead of creating a separate terminal child. The sentinel CEDAR_VALUE_LIMIT = i32::MAX - 1 marks "allocated but no value yet."

   The public API reserves this sentinel and i32::MAX; accepted user values stop at i32::MAX - 2, matching the default layout's public contract.

2. Leaf-to-internal promotion: When inserting a key that extends an existing leaf, the existing value must be moved to a new terminal child before the leaf can become an internal node.

3. Base encoding: In reduced-trie mode, base() returns -(base_ + 1) instead of base_ directly. This encoding allows distinguishing between a leaf with value 0 and an internal node with base 0.

4. Deletion: erase__ checks whether the node is a leaf (base_ >= 0) or has a terminal child, and handles both cases.

These changes are scattered throughout the code as #[cfg(feature = "reduced-trie")] blocks, always paired with a #[cfg(not(feature = "reduced-trie"))] default.

Traversal for Predictive Search

The begin and next functions implement depth-first traversal over the trie's leaves:

begin(from, p)

From node from, follows child links all the way down to the leftmost leaf. Returns (value, leaf_node, depth).

next(from, p, root)

From a leaf node, finds the next leaf in depth-first order:

1. Check if the current terminal node has a sibling.
2. If not, walk up via check (parent pointer), checking for siblings at each level.
3. Once a sibling is found, call begin on it to descend to its leftmost leaf.
4. If we reach root without finding a sibling, the traversal is complete.

This gives an efficient in-order traversal without recursion or an explicit stack -- the trie's structure itself provides the traversal state through check (parent) and sibling links.

Unsafe traversal boundary

The exact and predictive query hot paths use unchecked vector indexing only after construction or deserialization has established the double-array invariants. Persistence first decodes into private wire records, applies allocation limits, converts into an unexposed trie, and validates array lengths, parent links, sibling chains, reachability, free lists, block lists, and value sentinels. Checked indexing remains in PrefixIter::next because the measured unchecked candidate did not produce a statistically significant scan improvement. Stateful reference-model tests, Miri, and bounded fuzzing cover both layouts.