A concurrent reference-counted prefix trie over sequences of Element.
More...
#include <sequenceTrie.hpp>
|
|
using | nodeId_t = uint32_t |
| | Handle identifying a node (a stored sequence). Stable for the node's lifetime.
|
| |
|
| | SequenceTrie (uint32_t numShards=1, uint32_t chunkSizeLog2=20) |
| | Constructs an empty trie containing only ROOT.
|
| |
|
| SequenceTrie (const SequenceTrie &)=delete |
| |
|
SequenceTrie & | operator= (const SequenceTrie &)=delete |
| |
| nodeId_t | extend (nodeId_t parent, Element element, uint32_t shard=0) |
| | Appends element after parent, returning a handle to the new sequence.
|
| |
| void | acquire (nodeId_t id) |
| | Adds one reference to id (when a new holder starts referencing it). Thread-safe.
|
| |
| void | release (nodeId_t id, uint32_t shard=0) |
| | Drops one reference from id. Thread-safe.
|
| |
| template<typename OutElem = Element> |
| void | reconstruct (nodeId_t id, std::vector< OutElem > &out) const |
| | Reconstructs the full sequence from ROOT to id, in root-first order.
|
| |
| size_t | getDepth (nodeId_t id) const |
| | Number of elements from ROOT to id (its depth in the trie).
|
| |
| size_t | getAllocatedNodeCount () const |
| | Total node slots ever bump-allocated (high-water of simultaneously-live nodes, since freed nodes are recycled before fresh ids are bumped). A good proxy for the trie's resident memory.
|
| |
| size_t | getApproxMemoryBytes () const |
| | Approximate resident memory of the trie's node storage, in bytes.
|
| |
| size_t | getMaxMemoryBytes () const |
| | Hard upper bound on the trie's node storage, in bytes: the most it can ever occupy before node allocation throws "exceeded maximum capacity". The live trie is otherwise unbounded (it grows ~ live-states x depth), so callers that must reserve RAM up front (e.g. the engine's memory guard) use this fixed ceiling. = MAX_CHUNKS * nodes-per-chunk * sizeof(Node).
|
| |
|
|
static constexpr nodeId_t | ROOT = 0 |
| | The empty sequence. Always valid, never recycled; the base of every path.
|
| |
|
static constexpr nodeId_t | NONE = 0xFFFFFFFFu |
| | Sentinel for "no node" (also the free-list terminator).
|
| |
template<typename Element>
class jaffarCommon::sequenceTrie::SequenceTrie< Element >
A concurrent reference-counted prefix trie over sequences of Element.
- Template Parameters
-
| Element | Trivially-copyable element type stored on each edge (e.g. an input index). |
◆ SequenceTrie()
template<typename Element >
Constructs an empty trie containing only ROOT.
- Parameters
-
| numShards | Number of independent free-list shards used to reduce contention (default 1). |
| chunkSizeLog2 | Log2 of the number of nodes per storage chunk (default 2^20 nodes/chunk). |
◆ acquire()
template<typename Element >
Adds one reference to id (when a new holder starts referencing it). Thread-safe.
- Parameters
-
| id | The node to add a reference to. |
◆ extend()
template<typename Element >
Appends element after parent, returning a handle to the new sequence.
- Parameters
-
| parent | A node the caller holds a reference to (e.g. ROOT, or a state's stored node). |
| element | The element to append. |
| shard | Free-list shard to allocate the new node from (default 0). |
- Returns
- The new node, carrying one reference owned by the caller (balance with release).
Thread-safe. The new node adds a child link to parent, which keeps parent alive for at least as long as the new node.
◆ getAllocatedNodeCount()
template<typename Element >
Total node slots ever bump-allocated (high-water of simultaneously-live nodes, since freed nodes are recycled before fresh ids are bumped). A good proxy for the trie's resident memory.
- Returns
- The number of node slots ever bump-allocated.
◆ getApproxMemoryBytes()
template<typename Element >
Approximate resident memory of the trie's node storage, in bytes.
- Returns
- The approximate node-storage footprint in bytes.
◆ getDepth()
template<typename Element >
Number of elements from ROOT to id (its depth in the trie).
- Parameters
-
| id | The node whose depth is measured. |
- Returns
- The number of elements on the path from ROOT to
id.
◆ getMaxMemoryBytes()
template<typename Element >
Hard upper bound on the trie's node storage, in bytes: the most it can ever occupy before node allocation throws "exceeded maximum capacity". The live trie is otherwise unbounded (it grows ~ live-states x depth), so callers that must reserve RAM up front (e.g. the engine's memory guard) use this fixed ceiling. = MAX_CHUNKS * nodes-per-chunk * sizeof(Node).
- Returns
- The hard upper bound on the trie's node-storage footprint, in bytes.
◆ reconstruct()
template<typename Element >
template<typename OutElem = Element>
Reconstructs the full sequence from ROOT to id, in root-first order.
- Parameters
-
| id | A node the caller keeps alive for the duration of the call. |
| out | Cleared and filled with the sequence (ROOT contributes no element). |
◆ release()
template<typename Element >
Drops one reference from id. Thread-safe.
- Parameters
-
| id | The node to drop a reference from. |
| shard | Free-list shard that recycled node slots are returned to (default 0). |
When a node's reference count reaches zero (no holders and no children) it is recycled and the drop cascades to its parent (whose child edge just disappeared). ROOT's permanent reference keeps the cascade from ever freeing it.
The documentation for this class was generated from the following file:
