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 (all free), e_head = 1, and reject = 257.

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

5. Block lists: blocks_head_open = 0 (block 0 is the only open block). blocks_head_closed = 0 and blocks_head_full = 0 (both empty -- the head value 0 is overloaded since block 0 is special).

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)

Active node at index e:
    base_ >= 0   (base value for child transitions)
    check >= 0   (parent node index)

The block's e_head points to the first free node. To enumerate free nodes, follow the check chain (negating to get the actual index) until you loop back to e_head.

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. Remove e from its block's free list by linking its predecessor to its successor.
3. Decrement the block's num. If num drops to 0, transfer the block from Closed to Full. If num drops to 1 (and trial < max_trial), transfer from Open to Closed.
4. Initialize the node: set base_ to -1 (or 0 for terminal) and check to the parent.
5. If this is the first child (base < 0), set the parent's base_ to e XOR label.

Freeing a node (push_e_node)

When a node is deleted:

1. Increment the block's num. If num goes from 0 to 1, transfer the block from Full to Closed. If num goes from 1 to 2 (or trial == max_trial), transfer from Closed to Open.
2. Insert the node back into the block's free list, immediately after e_head.
3. Update the reject heuristic if needed.
4. Clear the node's NInfo.

Block Management

The Three Block Lists

Blocks are organized into three cyclic doubly-linked lists based on their free slot 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    num == 1

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

A head value of 0 means the list is empty (except for block 0, which is special-cased). The prev and next fields in each Block struct maintain the doubly-linked list.

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	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:

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. The list is kept in sorted order (when ordered is true) to maintain the invariant needed by common_prefix_predict.

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 is a global optimization that records, for each possible num value (0-256), the minimum number of children that failed to fit in any block with that many free slots. This lets find_places skip blocks early:

if self.blocks[idx].num >= nc && nc < self.blocks[idx].reject {
    // Worth searching this block
} else {
    // Skip: either not enough free slots, or previous experience
    // says nc children won't fit in a block with this many free slots
}

The heuristic is updated whenever a find_places search fails on a block:

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;
}

This is a form of memoized pruning: once we learn that 5 children can't fit in a block with 10 free slots, we propagate that knowledge globally so that no future search even attempts it.

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.

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."

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.