inputHistoryTrie.hpp File Reference

Input-history strategy that stores each state's path as a single node id into a shared, reference-counted prefix trie (jaffarCommon::sequenceTrie). More...

#include "inputHistory.hpp"
#include <cstring>
#include <jaffarCommon/bitwise.hpp>
#include <jaffarCommon/exceptions.hpp>
#include <jaffarCommon/sequenceTrie.hpp>
#include <vector>

Go to the source code of this file.

Classes
class	jaffarPlus::InputHistoryTrie
	Stores each state's path as one node id into a shared, reference-counted prefix trie; sibling states share their common prefix, so per-state cold storage is just a node id + count. More...

Typedefs
using	jaffarPlus::SequenceInputTrie = jaffarCommon::sequenceTrie::SequenceTrie< uint16_t >
	The shared trie type backing every InputHistoryTrie instance of one search.

Detailed Description

Input-history strategy that stores each state's path as a single node id into a shared, reference-counted prefix trie (jaffarCommon::sequenceTrie).

Sibling states share their common prefix, so per-state cold storage is just 4 bytes and total path memory is far smaller than the raw bit-packed history. Selected with {"Type": "Trie", "Max Size": N} ("Max Size" bounds only the reconstructed snapshot/solution buffer; the live search path is unbounded).

Cold form (StateDb slot): [node id]. Full form (self-contained snapshot): the path reconstructed into a bit-packed buffer, so snapshots need no reference back into the trie. The runner's step counter is stored separately (prefixed by the runner), not by this strategy.

UNBOUNDED GROWTH + HARD CEILING (watch this): unlike Raw, the trie is a SEPARATE shared pool NOT counted in the State DB budget; it grows ~ live-states x depth and is capped at the trie's hard node ceiling (SequenceTrie::getMaxMemoryBytes, reserved by the engine RAM guard). When that ceiling is reached the trie soft-fails (extend() returns NONE, isExhausted() latches) rather than throwing inside the parallel region, and the driver stops the run gracefully (exit reason inputHistoryNearCapacity). Because prefix sharing fades with depth, Raw (per-state cost fixed by Max Size, bounded by the State DB) can beat Trie on very deep searches – compare the per-step "Input History (shared) ... raw would be ..." figures.

Definition in file inputHistoryTrie.hpp.

Typedef Documentation

SequenceInputTrie

using jaffarPlus::SequenceInputTrie = typedef jaffarCommon::sequenceTrie::SequenceTrie<uint16_t>

The shared trie type backing every InputHistoryTrie instance of one search.

The trie stores each path element as a 16-bit input index (not the full size_t inputIndex_t): this halves the node and, with the 16-bit refCount, makes the node 8 bytes -> the trie's hard memory ceiling drops from ~96 GiB to ~32 GiB. Valid because a search registers far fewer than 65536 distinct inputs (the constructor enforces this).

Definition at line 39 of file inputHistoryTrie.hpp.