A concurrent, reference-counted trie that stores many sequences compactly by sharing their common prefixes. Each stored sequence is identified by a small integer node handle; the full sequence is recovered by walking parent links back to the root. More...
#include "exceptions.hpp"#include <algorithm>#include <array>#include <atomic>#include <cstdint>#include <mutex>#include <vector>
Go to the source code of this file.
Classes | |
| class | jaffarCommon::sequenceTrie::SequenceTrie< Element > |
A concurrent reference-counted prefix trie over sequences of Element. More... | |
Detailed Description
A concurrent, reference-counted trie that stores many sequences compactly by sharing their common prefixes. Each stored sequence is identified by a small integer node handle; the full sequence is recovered by walking parent links back to the root.
Motivation: a best-first search keeps a large frontier of states, each of which needs to remember the path (sequence of moves/inputs) that produced it. Storing the whole path in every state duplicates the long prefixes that sibling states share. This trie stores each path once: a state keeps only a 4-byte nodeId_t, and extend(parent, element) adds one element on top of an existing path. Nodes are reference counted so the structure stays bounded by the paths of live states: when the last holder of a leaf releases it, the leaf (and any ancestors that become childless and unreferenced) are recycled.
Concurrency: extend, acquire, release and reconstruct are all safe to call concurrently. Node storage is a fixed array of lazily-allocated fixed-size chunks (handles are stable indices that never move), recycled through a lock-free (ABA-tagged) free list; only the rare allocation of a brand-new chunk takes a mutex. The reference-count invariant is the usual one: you may only extend from, or acquire, a node you already hold a reference to, so a node at refcount zero can never be revived.
