The standard library has loose ends around failure. std::set::insert(first, last) has no defined behaviour on partial failure, and in practice an allocation failure leaves some elements inserted and the rest not:
struct budget_t { std::size_t used = 0, limit = 0; };
template <typename value_type_> // ? rebind, converting constructor, `deallocate` and the move-propagation trait elided
struct failing_allocator {
using value_type = value_type_;
budget_t *budget {};
value_type_ *allocate(std::size_t count) {
if (!budget || budget->used + count > budget->limit) throw std::bad_alloc {};
budget->used += count;
return static_cast<value_type_ *>(::operator new(count * sizeof(value_type_)));
}
};
int main() {
budget_t budget {0, 3};
std::set<int, std::less<>, failing_allocator<int>> values {std::less<> {}, failing_allocator<int> {&budget}};
try { for (int value : {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}) values.insert(value); }
catch (std::bad_alloc const &) { std::println("std::bad_alloc after {} allocations", budget.used); }
std::println("set contains {} elements:", values.size());
for (int value : values) std::print("{} ", value);
std::print("\n");
}Under Clang++ 21 and G++ 15 that prints:
std::bad_alloc after 3 allocations
set contains 3 elements:
0 1 2The same range through a container here answers with a status_t, and the destination is untouched:
using set_t = st::avl_set<int, std::less<>, failing_allocator<int>>;
set_t values(std::less<> {}, failing_allocator<int> {&budget});
int const range[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
st::status_t const inserted = values.insert(std::begin(range), std::end(range));Against the same three-allocation budget that prints:
insert(first, last) returned out_of_memory_heap_k
set contains 0 elementsA range modifier builds the whole range beside the destination and absorbs it in one step, so the allocation that fails has nothing to undo: it fails while the destination is still untouched. insert refuses over a key already there, insert_if_missing skips one and takes the rest, upsert overwrites — and all three refuse the whole range or take it.
The one way out of the promise is assume_reserved_t, which writes in place against room you have already secured, so a capacity it exhausts leaves the prefix written.
Where this matters is secondary-index consistency inside a storage engine — an id → slot map, a slot → vector map and a deleted set that have to move together, and where “the crash left index B disagreeing with index A” is a corruption bug someone has already debugged.
commit_stamp_tWhen a version became visible, or that it never has.enum commit_stamp_tThe sentinel is the maximum rather than zero so that visibility is a single comparison against a reader's snapshot: an uncommitted version is newer than every snapshot that will ever be taken, and so falls out of visible_at without a second branch asking whether it is still staged. Zero would have made "not yet visible" compare as "visible since the beginning of time".
uncommitted_k | std::numeric_limits<generation_t>::max() |
|---|
walk_control_tWhether a walk carries on after handing an element over.enum walk_control_tOne type for both sides. A caller's callback answers it, and so does every step inside a walk, because no boundary separates the two: basic_flat_set compares against halt_k directly, and probe_to_visit documents this as the return of a callback the caller supplies.
resume_k | The walk carries on with whatever it has next - the same probe run, or the merged order. | |
|---|---|---|
halt_k | Whoever answered has what it came for, and the walk stops here. |
cursor_seed_tWhere a cursor's next step begins, which is a different question before and after the first.enum cursor_seed_tthe_smallest_k | No bound was given and nothing has been handed over, so the walk starts at the least key. | |
|---|---|---|
the_given_bound_k | A bound was given and nothing has been handed over, so that bound is inclusive. | |
past_the_last_k | A key has been handed over, so the walk continues strictly above it. |
cursor_limit_tWhether a cursor stops at a key it was given, or only when the store runs out.enum cursor_limit_tCarried by the cursor rather than tested by the caller, because the comparator is the store's and a caller comparing a delivered key against a bound would be ordering keys the store owns.
the_whole_keyspace_k | ||
|---|---|---|
up_to_the_bound_k |
cursor_reach_tWhether an ordered cursor can still hand something over, once a step found it cannot.enum cursor_reach_tA step that runs out latches this rather than re-probing, because nothing can put a key back below where the walk stopped: the store is held for the walk, and a cursor never steps back.
walking_k | A step may still find a key. | |
|---|---|---|
spent_k | A step found the store spent or the bound reached, and every later step would too. |
staging_tWhether a transaction's writes are sitting in the store, invisible, or not there yet.enum staging_tA committed transaction returns to pending_k and is immediately reusable, so there is no third state to name - commit on a pending_k transaction already reports operation_not_permitted_k.
pending_k | Accepting writes; the store holds nothing of this transaction. | |
|---|---|---|
staged_k | The store has reserved every change, so commit allocates nothing and only stamps. |
presence_tWhether an entry says its key is there, or says it was taken away and when.enum presence_tpresent_k | The key is there and this is its value. | |
|---|---|---|
erased_k | The key was erased. |
unmask_outcome_tWhat a commit found when it went looking for the version it was asked to publish.enum unmask_outcome_talready_published_k is what makes a repeated identifier harmless: a commit listing one key twice finds the second pass settled rather than missing, which a two-state answer could only spell as the same success a fresh publish reports.
unmasked_k | The staged version was there and now carries this commit's stamp. | |
|---|---|---|
already_published_k | This commit had already published that version on an earlier pass. | |
version_missing_k | No entry carries that generation, so nothing became visible. |
watch_tWatch metadata for versioned elements.access_tHow one transaction reached one key, as independent claims rather than as a state.enum access_tA key can be read and be the endpoint of a range at once, so these are flags and not an enumeration. Nothing here dates anything: a transaction's snapshot is the only date its validator needs, which is what lets a read record no sampled value at all.
A range is an opening entry and the entry recorded next to it, which closes it: the adjacency is the pairing, which is what lets one sequence hold points and windows alike.
A window can also run off one end. An ordinal read depends on every key ordered before the one it lands on, and a bound read that finds nothing depends on everything above its bound, yet neither end has a key to name - there is no smallest std::string and no largest one. The unbounded flags say so, and the identifier stored beside such a flag is then ignored.
none_k | 0 | No claim on this key. |
|---|---|---|
read_k | 1u << 0 | Names exactly this key, so its whole version run is validated. |
opens_k | 1u << 1 | Begins a range read at this key, inclusive. |
closes_k | 1u << 2 | Ends the range the previous entry opened, exclusive of this key. |
from_the_lowest_k | 1u << 3 | On an opening entry, the range starts below every key. |
to_the_highest_k | 1u << 4 | On a closing entry, the range runs past every key. |
accessed_identifierOne key a transaction read, and in what way.template <typename identifier_type_>
struct accessed_identifierCarries no generation, so it orders by key alone and a validator dates it against the transaction's snapshot rather than against whatever the read happened to see.
identifier | identifier_t | |
|---|---|---|
access | access_t |
per_key_hasherHashes a version-decorated object by the identifier inside it, ignoring the metadata.template <typename hasher_type_>
struct per_key_hasherAn unordered store addresses an entry by hash rather than by order, so this is what versioned_comparator_t is to an ordered one.
hasher | hasher_type_ | The hasher this wrapper was built with, consulted for every element. |
|---|
per_key_equalsCompares version-decorated objects by the identifier inside them, ignoring the metadata.template <typename equals_type_>
struct per_key_equalsPaired with per_key_hasher, since an open-addressed table needs both to place an entry.
equals | equals_type_ | The equality this wrapper was built with, consulted for every comparison. |
|---|
no_order_tWhat a store keeping no stamps contributes to a shard set, which is nothing at all.struct no_order_torder_ofThe order a store is a member of, or no_order_t when it keeps no stamps.template <typename store_type_,
typename = void>
struct order_ofrebound_order_ofThe same store built into order_type_ instead, or the store itself where it names no such rebind.template <typename store_type_,
typename order_type_,
typename = void>
struct rebound_order_ofgroup_phase_tA phase a transaction group drives through every participant, one at a time.enum group_phase_tvalidate_k | ||
|---|---|---|
release_validation_k | ||
stage_k | ||
publish_k | ||
commit_k | ||
prune_k | ||
rollback_k | ||
reset_k |
basic_commit_orderThe order commits are published in, and the oldest snapshot readers can still name.18template <std::size_t commits_in_flight_ = 16,
std::size_t reader_buckets_ = 4,
order_sharing_t sharing_ = order_sharing_t::shared_k,
parking_waiting_policy<generation_t *, generation_t> waiting_policy_type_ = standard_waiting_policy_t>
class basic_commit_orderStores are constructed into one of these. A store never owns an order and never borrows one; it is a member of the order it was built with, and it says so once, at construction, which is why nothing here can be attached, replaced or set wrong afterwards. A shard set builds all of its partitions into one order, its own or the one it was itself built into, and a group over several stores is one commit exactly when they were built into the same order.
Nothing here is wall time. Both counters are logical in the sense a commit stamp is logical: monotone integers that order events, and nothing else.
Commits are a ring indexed by stamp. Drawing a stamp is one unconditional add, so a committer never waits for room; landing is what waits, and only for the stamp whose slot it is about to reuse. The watermark then walks forward through consecutive landed slots, so it stops one below the oldest commit still in flight and never covers a stamp whose versions are still being written. A later commit that finishes first stays invisible until the earlier one lands, when both appear together.
The ring is correct at every size down to one, where it degenerates to publishing in stamp order; commits_in_flight_ chooses only how often a committer waits, never what the watermark means. What bounds it is not the core count: a committer holds its locks across the whole span between begin_commit and end_commit, so two commits in flight hold disjoint lock sets, and the ceiling is the number of independently lockable regions the order serves. A shard set therefore names its own partition count, and a single locked store needs one.
Readers are counted by bucket rather than listed one by one. A bucket carries the watermark it was opened at, which is a floor for every reader that joins it, and the low-water mark is the least floor over occupied buckets. Running out of buckets refuses nothing and blocks nobody: readers share a bucket, the mark becomes a lower bound rather than exact, and reclamation is correspondingly conservative, which is already the only thing a caller may assume of it. That is what lets take_snapshot stay infallible, since three of its callers sit inside noexcept helpers with no channel to report a refusal.
A claim is therefore a bucket index and a stamp, never a pointer into caller memory, so a claim moves with its transaction between threads by copying two fields and touching this order not at all. Two buckets are the fewest that work: the head rotates into the other one as the watermark leaves its floor behind, so a reader handing over to the next never pins the first one's floor.
Three orderings carry the guarantees under shared_k, and the models in verification/commit_order/ drop each in turn. A reader joins its bucket and then reads the watermark through a read-modify-write, so a mark computed after the join counts it, and one computed before it stands at or below the stamp the reader is handed. A mark reads the watermark through a read-modify-write before scanning the buckets, never after, or a reader joining in between is missed. A landed commit reads the watermark through a read-modify-write before it walks the ring, or two commits landing at once store-buffer past each other and a mark is left for the next commit to find. A bucket is also retagged shut to arrivals before its floor is stored, which keeps the floor from moving under a member; a joiner the retag misses read the watermark before the opener did, so the floor stays at or below its snapshot either way.
Under solitary_k none of that applies, because there is no second thread to order against.
end_commit waits for older commits to land once commits_in_flight_ of them are ahead of the watermark, and await_published waits for another thread's publication. Every store and group here commits under the rule above.
end_commit and await_published are deadlock-free only for a committer that holds every lock it publishes under before it draws and takes none after.
ring_kCommits that may be in flight past the watermark before a landing one waits.std::size_t ring_k;buckets_kHow many floors are kept.std::size_t buckets_k;Readers past it share a bucket rather than being turned away.
sharing_kWhether several threads reach this order.order_sharing_t sharing_k;basic_commit_orderconstexpr basic_commit_order() noexcept=default;basic_commit_order(basic_commit_order const &)=delete;operator=basic_commit_order & operator=(basic_commit_order const &)=delete;next_generationHands out the next generation, which dates a transaction rather than its visibility, and which a shard set draws once so every one of its parts keys its private versions alike.generation_t next_generation() noexcept;published_stampThe newest stamp every part of which is written, which is what a fresh read answers at; acquired, so the versions it covers are visible to a reader that takes no lock.generation_t published_stamp() const noexcept;drawn_stampThe newest stamp any commit has drawn, landed or not, which is what a reader must validate against rather than the watermark.generation_t drawn_stamp() const noexcept;A commit in flight has already written its stamp onto its versions while the watermark still sits below it, so a validator asking whether anything moved has to compare against what was drawn. Under a shard set that overlap is ordinary rather than a corner case.
take_snapshotPoints claim at the newest whole stamp, giving back whatever it held first.generation_t take_snapshot(snapshot_claim_t & claim) noexcept;The snapshot the claim now reads at.
begin_commitDraws the stamp node publishes under.void begin_commit(commit_in_flight_t & node) noexcept;One add: a draw never waits and never refuses.
end_commitRecords that every version of node is written, and walks the watermark through every landed stamp above it: one below the oldest commit still in flight, or all the way to the newest drawn when none is.void end_commit(commit_in_flight_t & node) noexcept;await_publishedWaits until the watermark covers stamp, so a committer may read what it wrote.void await_published(commit_stamp_t stamp) noexcept;Blocks on another thread's publication, so no store lock may be held across it.
low_water_markThe oldest snapshot any reader can still name, so everything older is unreachable.generation_t low_water_mark() const noexcept;Raised whenever a bucket drains or the watermark moves, and a stale read is a lower mark.
open_snapshotsHow many readers currently hold a snapshot, summed over the buckets.std::size_t open_snapshots() const noexcept;resumeRestarts an order nothing has drawn from yet at published, so the stamps this process draws continue above every stamp an earlier one made durable.status_t resume(generation_t published) noexcept;Both counters, the watermark, the low-water mark and every bucket's floor start at published, so the next reader is answered there and the next commit draws above it.
A refusal changes nothing.
Ordered against no other call, so it runs before a second thread can reach this order at all.
invalid_argument_k published is negative or leaves no stamp to draw.operation_not_permitted_k A generation or stamp was drawn here, or a snapshot is open.adoptTakes over other's stamps, for a store that is being moved and has nothing open or in flight.void adopt(basic_commit_order const & other) noexcept;snapshot_claim_tOne reader's claim on a snapshot, which holds the low-water mark at or below it.class snapshot_claim_tWhile it is held the reader is one member of one bucket, whose floor is at or below the snapshot it reads at, so the reader itself pins retention and no separate mark has to be kept in step with it. Being a bucket index and a stamp, it moves between threads by copying two fields and reaches this order not at all, and it is given back exactly once.
dynamic_transaction_groupA two-phase commit over however many stores join at run time, published under one stamp.18template <optimistically_concurrent_store... store_types_>
class dynamic_transaction_groupWhere transaction_group fixes its participants in its type, this one names only the kinds of store that may take part, and opens a transaction on each store the first time it joins. Every participant reads at the one snapshot and generation the group drew from the order they share, so a reader at any snapshot sees the whole commit or none of it. Each transaction lives in a node of its own, so one handed out stays put however many stores join after it.
A successful commit and a reset destroy every participant before the claim moves to a newer snapshot. A store may therefore be freed once the low-water mark passes the stamp it was retired at, because no group keeps a participant past its own claim.
order_tThe order every joining store must be built into, whose stamp the group commits under.using order_t = typename order_of<std::tuple_element_t<0, std::tuple<store_types_...>>>::type;claim_tThe claim every participant reads under.using claim_t = typename order_t::snapshot_claim_t;kinds_kHow many kinds of store may join, which bounds nothing about how many stores do.std::size_t kinds_k;dynamic_transaction_groupTakes over other's participants and claim, leaving it with neither.dynamic_transaction_group(dynamic_transaction_group && other) noexcept;dynamic_transaction_group(dynamic_transaction_group const &)=delete;operator=Destroys this group's participants before its claim goes back, then takes over other.dynamic_transaction_group & operator=(
dynamic_transaction_group && other) noexcept;dynamic_transaction_group & operator=(
dynamic_transaction_group const &)=delete;~dynamic_transaction_groupDestroys every participant, unwinding what it staged, before the claim is given back.~dynamic_transaction_group() noexcept;joinOpens a transaction on store at the group's snapshot and generation, or answers the one opened when store joined before.template <typename store_type_>
expected<typename store_type_::transaction_t *> join(
store_type_ & store) noexcept;Stage, commit, roll back and reset the participant through the group alone, which is what keeps it on the group's claim and under the group's stamp.
The participant, which stays where it is until a commit succeeds, a reset, or the group goes away.
invalid_argument_k store is built into another order.operation_not_permitted_k The group is staged.store refuses the transaction with passes through unchanged.participantThe participant store joined as, or null where it has not joined since the last successful commit or reset.template <typename store_type_>
store_type_::transaction_t * participant(
store_type_ const & store) noexcept;snapshotThe stamp every participant reads at, which the group's claim pins.generation_t snapshot() const noexcept;generationThe generation the group drew for its participants, which later joins open at too.generation_t generation() const noexcept;participants_countHow many stores have joined since the last successful commit or reset.std::size_t participants_count() const noexcept;*× 2Whether the group's writes are sitting in their stores, invisible.staging_t staging() const noexcept;commit_stampThe stamp the last successful commit published every participant under, or zero where it had nothing to publish.generation_t commit_stamp() const noexcept;*× 2Validates every watch and reserves every write, undoing all of it if one refuses.status_t stage() noexcept;Participants are staged ascending by store address. A partial stage is never observable: the undo rolls the staged prefix back rather than resetting it, so the caller's pending writes survive and the group can be retried.
A partial stage is never observable. The undo rolls the staged prefix back rather than resetting it, so the caller's pending writes survive and the group can be retried.
operation_not_permitted_k The group is already staged.commitPublishes every participant under one stamp, then empties the group for new joins.status_t commit() noexcept;Every participant is asked before any of them writes, so a refusal publishes nothing and leaves the group staged, which is the one state rollback accepts. A success destroys every participant, then moves the claim to a snapshot covering the stamp and draws a fresh generation. A group nobody joined commits without drawing a stamp.
operation_not_permitted_k The group is not staged.*× 2Pulls every staged write back into its transaction, leaving the group retryable.status_t rollback() noexcept;Only a rollback that reached every participant clears the staged flag, so the next stage never stages a second time over a participant still staged.
Only a rollback that reached every participant clears the staged flag. Clearing it after a refusal would advertise a group whose later participants are still staged, and the next stage would stage a second time over the first.
operation_not_permitted_k The group is not staged.resetDestroys every participant, unwinding whatever it staged, then reads at a fresh snapshot under a fresh generation.status_t reset() noexcept;makeOpens an empty group at the newest snapshot of order, under a generation drawn for it.expected<dynamic_transaction_group> make(order_t & order) noexcept;monotonic_storeGeneric transactional store providing 2-phase commits and "watch" operations.39template <typename collection_type_>
class monotonic_storeCan be instantiated with AVL trees, weight-balanced trees, or open-addressed hash tables. Not thread-safe by itself. Entirely exception-free, with all methods marked noexcept.
A commit is all-or-nothing. When updating multiple values, you don't want to break in an intermediate state where only some updates succeeded. With two-phase commit transactions, you can stage many changes and commit them all at once, or rollback if something goes wrong. Common use case: synchronizing updates across multiple data stores. Nothing here is durable - there is no log and no fsync - so a commit means visible, not survived.
The API is simple, generalizable, and lightweight. This collection doesn't provide snapshots or full MVCC (Multi-Version Concurrency Control). If you start a transaction and "watch" values through it, there's no guarantee the value hasn't been updated before the transaction began and the entry was added to the watched list. Only "Monotonic Atomic View" is guaranteed, which is rung two of the five isolation_t names and so also gives "Read Committed". Transactions cannot observe writes from other uncommitted transactions.
The state management doesn't rely on entry pointers or iterators. Those could simplify the implementation, but introduce require validity constraints for re-allocations and modifications of the tree and underlying allocator behavior. So all entry identifiers must either be nothrow-copyable or provide a copy() member method returning an expected<T> to support safe copying for watch bookkeeping.
using is_transparent = void;, like std::map and std::set.noexcept.Four distinct modification strategies with different failure handling:
| Method | Existing key | Returns | Use case |
|---|---|---|---|
| insert() | fails | key_already_exists_k | strict: key must be new |
| insert_if_missing() | skips | success_k | lenient: skip if present |
| upsert() | overwrites | success_k | always writes |
| update() | fails | key_not_found_k | strict: key must exist |
storage_shape_tWhat this core family rebinds on, and how a decorated entry is reached inside it.using storage_shape_t = versioned_storage_for<collection_type_, value_t>;store_tWhat this store calls itself, so generic code spells an engine and a wrapper alike.using store_t = monotonic_store;isolation_kA commit publishes every staged version before any reader can run, and takes no snapshot.isolation_t isolation_k;monotonic_storeSeeds the underlying tree's allocator, which a stateful allocator needs.monotonic_store() noexcept;monotonic_store(allocator_t const & allocator) noexcept;Seeds the underlying tree's allocator, which a stateful allocator needs.
monotonic_store(
comparator_t const & comparator,
allocator_t const & allocator = {}) noexcept;Seeds the comparator too, needed when it carries state or a dispatch pointer.
monotonic_store(monotonic_store && other) noexcept;operator=monotonic_store & operator=(monotonic_store && other) noexcept;~monotonic_store~monotonic_store() noexcept;sizeReturns the number of visible (committed) non-deleted elements in the tree.emptyChecks if the tree has no visible elements.*× 2Returns the number of elements with key equal to the specified argument.template <typename comparable_type_ = identifier_t>
expected<std::size_t> count(
comparable_type_ && comparable) const noexcept;For unique-key containers like this, returns either 0 or 1.
comparable | in | Object comparable to value_t and convertible to identifier_t. |
|---|
Number of elements with key equal to comparable (0 or 1).
containsChecks if a member equal to the given comparable exists in the tree.template <typename comparable_type_ = identifier_t>
expected<bool> contains(comparable_type_ && comparable) const noexcept;comparable | in | Object comparable to value_t and convertible to identifier_t. |
|---|
True if element exists, false otherwise.
find_copyFinds and returns a copy of an element equal to comparable.template <typename comparable_type_ = identifier_t>
expected<value_t> find_copy(
comparable_type_ && comparable) const noexcept;Convenience method to avoid callback-based access in tests and simple use cases. Heterogeneous lookup supported if comparator defines is_transparent.
comparable | in | Object comparable to value_t and convertible to identifier_t. |
|---|
Result with copied element if found.
key_not_found_k No visible member equals comparable.copy returns passes through unchanged.lower_bound_copyFinds and returns a copy of the first element not less than (>=) comparable.template <typename comparable_type_ = identifier_t>
requires ordered_collection<versioned_chains_t>
expected<value_t> lower_bound_copy(
comparable_type_ && comparable) const noexcept;comparable | in | Object comparable to value_t. |
|---|
Result with copied element if found.
key_not_found_k No visible element orders at or after comparable.copy returns passes through unchanged.upper_bound_copyFinds and returns a copy of the first element greater than (>) comparable.template <typename comparable_type_ = identifier_t>
requires ordered_collection<versioned_chains_t>
expected<value_t> upper_bound_copy(
comparable_type_ && comparable) const noexcept;comparable | in | Object comparable to value_t. |
|---|
Result with copied element if found.
key_not_found_k No visible element orders after comparable.copy returns passes through unchanged.transactionCreates a new transaction with a fresh generation number.expected<transaction_t> transaction() noexcept;Transaction can be reset and reused after commit/rollback to avoid reallocations.
Transaction instance, wrapped in an expected that is always engaged - construction cannot fail.
insertAtomically inserts an element only if the key doesn't exist.status_t insert(value_t && value) noexcept;template <readable_iterator input_iterator_type_>
status_t insert(
input_iterator_type_ first,
input_iterator_type_ last) noexcept;Bulk insert from iterator range (atomic strict semantics).
Fails if key exists. This is the strict insert semantics matching std::set::insert().
value | in | Element to insert (moved into the tree). |
|---|---|---|
first | in | Beginning of range to insert. |
last | in | End of range to insert. |
key_already_exists_k The key exists.key_already_exists_k Any key exists.copy returns passes through unchanged.insert_if_missingInserts only if the key is absent, reporting which of the two outcomes occurred.template <typename callback_inserted_type_ = no_op_t, typename callback_existing_type_ = no_op_t>
status_t insert_if_missing(
value_t && value,
callback_inserted_type_ && callback_inserted = {},
callback_existing_type_ && callback_existing = {}) noexcept;template <readable_iterator input_iterator_type_>
status_t insert_if_missing(
input_iterator_type_ first,
input_iterator_type_ last) noexcept;Bulk insert from an iterator range with atomic lenient semantics.
Declining to overwrite is a success, so the status alone cannot distinguish the cases and a caller that needs to know would otherwise pay for a membership probe of its own.
value | in | Element to insert, moved into the tree when the key is absent. |
|---|---|---|
callback_inserted | in | Invoked with the stored element after a fresh insert. Must be noexcept. |
callback_existing | in | Invoked with the element already present, which keeps its value. Must be noexcept. |
first | in | Beginning of range to insert. |
last | in | End of range to insert. |
Reporting the fresh insert costs a copy of the identifier and a second lookup, so a caller that leaves callback_inserted at its default pays for neither.
upsertAtomically upserts an element (insert or update).status_t upsert(value_t && value) noexcept;template <readable_iterator input_iterator_type_>
status_t upsert(
input_iterator_type_ first,
input_iterator_type_ last) noexcept;Bulk upsert from iterator range (atomic insert or update semantics).
Always succeeds (unless OOM). Overwrites existing element if key exists (upsert semantics).
value | in | Element to upsert (moved into the tree). |
|---|---|---|
first | in | Beginning of range to upsert. |
last | in | End of range to upsert. |
Only the published version gives way. A version staged by an open transaction is that transaction's to publish or discard, and a direct write leaves it untouched.
copy returns passes through unchanged.updateAtomically updates an existing element.status_t update(value_t && value) noexcept;template <readable_iterator input_iterator_type_>
status_t update(
input_iterator_type_ first,
input_iterator_type_ last) noexcept;Updates elements with given range.
Fails if key doesn't exist. Unlike upsert(), this will not insert new keys.
value | in | Element to update (moved into the tree). |
|---|---|---|
first | in | Beginning of range to update. |
last | in | End of range to update. |
key_not_found_k The key doesn't exist.key_not_found_k Any key is missing.copy returns passes through unchanged.*× 2Finds a member equal to the given comparable.template <typename comparable_type_ = identifier_t, typename callback_found_type_ = no_op_t, typename callback_missing_type_ = no_op_t>
status_t find(
comparable_type_ && comparable,
callback_found_type_ && callback_found,
callback_missing_type_ && callback_missing = {}) const noexcept;comparable | in | Object comparable to value_t and convertible to identifier_t. |
|---|---|---|
callback_found | in | Callback to receive an value_t const &. Must be noexcept. |
callback_missing | in | Callback triggered if nothing was found. Must be noexcept. |
key_compHow this store orders its keys, so a bounded walk can stop without guessing.comparator_t key_comp() const noexcept;The one ordering every read here descends on; a caller comparing keys any other way is ordering them differently from the store that holds them.
smallestHands callback_found the smallest member any committed write left visible.template <typename callback_found_type_ = no_op_t, typename callback_missing_type_ = no_op_t>
requires ordered_collection<versioned_chains_t>
status_t smallest(
callback_found_type_ && callback_found,
callback_missing_type_ && callback_missing = {}) const noexcept;The unbounded case of lower_bound, and the one a merged walk over several stores opens with: it asks for a first key, not an ordinal, so a core keeping no subtree counts answers.
callback_found | in | Callback to receive an value_t const &. Must be noexcept. |
|---|---|---|
callback_missing | in | Callback triggered when nothing is readable. Must be noexcept. |
pop_smallestRemoves the smallest member and hands it over, or reports the store is empty.template <typename callback_found_type_ = no_op_t, typename callback_missing_type_ = no_op_t>
requires ordered_collection<versioned_chains_t> && std::is_copy_constructible_v<identifier_t>
status_t pop_smallest(
callback_found_type_ && callback_found = {},
callback_missing_type_ && callback_missing = {}) noexcept;key_not_found_k Nothing was there, so emptiness needs no second probe.lower_*_bound× 2Finds the first member greater or equal to the given comparable.template <typename comparable_type_ = identifier_t, typename callback_found_type_ = no_op_t, typename callback_missing_type_ = no_op_t>
requires ordered_collection<versioned_chains_t>
status_t lower__bound(
comparable_type_ && comparable,
callback_found_type_ && callback_found,
callback_missing_type_ && callback_missing = {}) const noexcept;comparable | in | Object comparable to value_t and convertible to identifier_t. |
|---|---|---|
callback_found | in | Callback to receive an value_t const &. Must be noexcept. |
callback_missing | in | Callback triggered if nothing was found. Must be noexcept. |
equal_*_range× 2Finds all elements equal to a single key.template <typename comparable_type_ = identifier_t, typename callback_type_ = no_op_t>
status_t equal__range(
comparable_type_ && comparable,
callback_type_ && callback) const noexcept;Invokes callback for each matching element. For trees with unique keys, this returns at most one element (0 or 1).
Invokes callback for each matching element. For sets with unique keys, this returns at most one element (0 or 1).
comparable | in | Object comparable to value_t and convertible to identifier_t. |
|---|---|---|
callback | in | Callback invoked for each element equal to the key. Must be noexcept. |
A callback answering walk_control_t stops the walk where it says to.
for_*_each× 2Hands callback every element the store shows, in the order the core holds them.template <typename callback_type_ = no_op_t>
status_t for__each(callback_type_ && callback) const noexcept;The one walk an unordered core can offer, so it promises no ordering even where the core has one. Every element a find would answer with at the moment of the call is visited exactly once - a committed tombstone and every version no commit has published yet are both left out. Nothing may write to the store while the walk runs.
callback | in | Callback invoked for each element. Must be noexcept. |
|---|
A callback answering walk_control_t stops the walk where it says to.
rangeHands callback every visible member of [ lower, upper ), or fewer if it halts.template <typename lower_type_ = identifier_t, typename upper_type_ = identifier_t, typename callback_type_ = no_op_t>
requires ordered_collection<versioned_chains_t>
status_t range(
lower_type_ && lower,
upper_type_ && upper,
callback_type_ && callback = {}) const noexcept;template <typename from_type_ = identifier_t, typename until_type_ = identifier_t, typename callback_type_ = no_op_t>
requires ordered_collection<versioned_chains_t>
status_t range(
from_type_ const & from,
until_type_ const & until,
callback_type_ && callback,
descending_t) const noexcept;Hands callback every visible member of ( until, from ], greatest first, or fewer if it halts.
Either bound may be unbounded, which runs to that end.
update_rangeHands callback the mapped half of every visible element in [ lower, upper ).template <typename lower_type_ = identifier_t, typename upper_type_ = identifier_t, typename callback_type_ = no_op_t>
requires is_mapping<value_t> && ordered_collection<versioned_chains_t>
status_t update_range(
lower_type_ && lower,
upper_type_ && upper,
callback_type_ && callback) noexcept;lower | in | Lower bound, inclusive. |
|---|---|---|
upper | in | Upper bound, exclusive. |
callback | in | Callback invoked with (key const &, mapped &) per element. Must be noexcept. |
Always success here, since the revision is written in place; the status is reported so a sibling engine that has to copy the value first has the same channel.
erase_rangeRetires every published version ordered in [ lower, upper), handing each to callback.template <typename lower_type_ = identifier_t, typename upper_type_ = identifier_t, typename callback_type_ = no_op_t>
requires ordered_collection<versioned_chains_t>
status_t erase_range(
lower_type_ && lower,
upper_type_ && upper,
callback_type_ && callback = {}) noexcept;Always success; the status is reported so a wrapper that allocates can answer alike.
erase_fromRetires every published version ordered at or after lower, with no upper bound.template <typename lower_type_ = identifier_t, typename callback_type_ = no_op_t>
requires ordered_collection<versioned_chains_t>
status_t erase_from(
lower_type_ && lower,
callback_type_ && callback = {}) noexcept;lower | in | Lower bound of the range, inclusive - a key equal to it is erased, which is the same end erase_range() includes. |
|---|---|---|
callback | in | Callback handed each element about to be retired. Must be noexcept. |
Always success; the status is reported so a wrapper that allocates can answer alike.
erase_up_toRetires every published version ordered before upper, with no lower bound at all.template <typename upper_type_ = identifier_t, typename callback_type_ = no_op_t>
requires ordered_collection<versioned_chains_t>
status_t erase_up_to(
upper_type_ && upper,
callback_type_ && callback = {}) noexcept;upper | in | Upper bound of the range, exclusive - a key equal to it is kept, which is the same end erase_range() excludes. |
|---|---|---|
callback | in | Callback handed each element about to be retired. Must be noexcept. |
Always success; the status is reported so a wrapper that allocates can answer alike.
vacuumFrees every entry no reader can reach: a committed tombstone with nothing staged.expected<std::size_t> vacuum() noexcept;template <typename lower_type_, typename upper_type_>
requires ordered_collection<versioned_chains_t>
expected<std::size_t> vacuum(
lower_type_ && lower,
upper_type_ && upper) noexcept;Frees the unreachable entries ordered in [ lower, upper), so a caller can step through the keyspace instead of paying for one pass over all of it.
A committed erase leaves the key in the index so that a watch can still observe it, and nothing ever takes it back out. Reclaiming one changes nothing observable: size() already discounted it, no lookup ever saw it, and on the unordered core it stops holding a slot against the load factor.
How many entries were reclaimed.
selectFinds the ordinal -th smallest visible, committed element, counting from zero.template <typename callback_found_type_ = no_op_t, typename callback_missing_type_ = no_op_t>
requires supports_order_statistics<versioned_chains_t>
status_t select(
std::size_t ordinal,
callback_found_type_ && callback_found,
callback_missing_type_ && callback_missing = {}) const noexcept;Walks every entry in order, as a subtree weight counts versions, not visible values.
Instantiates only for a core carrying order statistics, which excludes the AVL aliases.
ordinal | in | Zero-based position among the visible elements. |
|---|---|---|
callback_found | in | Callback to receive the element. Must be noexcept. |
callback_missing | in | Callback triggered when fewer elements are visible. Must be noexcept. |
rankFinds the rank (position) of an element among visible (committed) elements.template <typename comparable_type_ = identifier_t, typename callback_found_type_ = no_op_t, typename callback_missing_type_ = no_op_t>
requires supports_order_statistics<versioned_chains_t>
status_t rank(
comparable_type_ && comparable,
callback_found_type_ && callback_found,
callback_missing_type_ && callback_missing = {}) const noexcept;Walks every entry in order, since a subtree weight counts versions rather than visible values. Instantiates only for a core carrying order statistics, which excludes the AVL aliases.
comparable | in | Object comparable to value_t and convertible to identifier_t. |
|---|---|---|
callback_found | in | Callback to receive the rank (size_t). Must be noexcept. |
callback_missing | in | Callback triggered if element not found. Must be noexcept. |
*× 2Erases a single entry matching the given comparable.template <typename comparable_type_ = identifier_t, typename callback_found_type_ = no_op_t, typename callback_missing_type_ = no_op_t>
status_t erase(
comparable_type_ && comparable,
callback_found_type_ && callback_found = {},
callback_missing_type_ && callback_missing = {}) noexcept;comparable | in | Object comparable to value_t and convertible to identifier_t. |
|---|---|---|
callback_found | in | Callback to receive the erased entry. Must be noexcept. |
callback_missing | in | Callback triggered if nothing was found. Must be noexcept. |
callback_missing and reports key_not_found_k, so a caller may read the answer from whichever suits it and never needs a membership probe of its own beforehand.key_not_found_k No visible entry matched.reserveAsks the core to make room for size more entries.status_t reserve(std::size_t size) noexcept;Honoured wherever the core has one allocation to grow - the open-addressed table reserves its slab here, and a later write lands in a slot already paid for. A node-based core allocates one node per write and has nothing to prepay, so there the hint is accepted and nothing happens. Either way a later write may still report out_of_memory_heap_k.
size | in | How many more entries to make room for. |
|---|
clearRemoves all elements from the tree, refusing while any transaction has staged work.status_t clear() noexcept;The generation counter keeps running. Rewinding it would hand a future transaction a stamp an open one already carries, and a watch compares stamps by value.
operation_not_permitted_k A staged version would be dropped from under the transaction that is about to publish it.printDebug utility to print tree contents.template <typename stream_type_>
requires ordered_collection<versioned_chains_t>
void print(stream_type_ & stream);Templated on the sink so the header never pulls in a stream of its own.
makeFactory method to create a new transactional binary tree without throwing exceptions.expected<store_t> make(allocator_t const & allocator = {}) noexcept;expected<store_t> make(
comparator_t const & comparator,
allocator_t const & allocator) noexcept;Builds a container around a specific comparator, for comparators that carry state.
allocator | in | Optional allocator instance. |
|---|---|---|
comparator | in | The instance every comparison will consult. |
Container instance in an always-engaged expected, as construction cannot fail.
transaction_tA transaction that buffers writes, stages them invisibly and publishes them in one commit.class transaction_treference_storeTransactional set providing 2-phase commit and watch/CAS at Monotonic Atomic View.32template <typename value_type_,
typename comparator_type_ = less_t,
typename allocator_type_ = std::allocator<std::uint8_t>>
class reference_storeBuilt on std::set as a baseline reference implementation. Not thread-safe by itself.
A commit is all-or-nothing. When updating multiple values, you don't want to break in an intermediate state where only some updates succeeded. With two-phase commit transactions, you can stage many changes and commit them all at once, or rollback if something goes wrong. Common use case: synchronizing updates across multiple data stores. Nothing here is durable - there is no log and no fsync - so a commit means visible, not survived.
The API is simple, generalizable, and lightweight. This collection doesn't provide snapshots or full MVCC (Multi-Version Concurrency Control). If you start a transaction and "watch" values through it, there's no guarantee the value hasn't been updated before the transaction began and the entry was added to the watched list. Only "Monotonic Atomic View" is guaranteed, which is rung two of the five isolation_t names and so also gives "Read Committed". Transactions cannot observe writes from other uncommitted transactions.
value_type_. Your comparator must define using is_transparent = void; to enable it, as std::map and std::set both do.noexcept wrappers, avoiding raw pointers.Three distinct insert strategies with different failure handling:
| Method | Existing key | Returns |
|---|---|---|
| insert() | fails | key_already_exists_k |
| insert_if_missing() | skips, succeeds | success_k |
| insert_or_assign() | overwrites | success_k |
The upsert method is an alias for insert_or_assign, following a more DBMS-like naming convention. The try_emplace is deleted in favor of the more explicit insert_if_missing.
.copy() const->expected<T> for safe copying of identifiers.bool operator()(value_type const &, value_type const &) constusing is_transparent = void; and using value_type = ...;, optional but recommended.std::set nodes and std::vector arraysstore_tWhat this store calls itself, so generic code spells an engine and a wrapper alike.using store_t = reference_store;isolation_kA commit publishes every staged version before any reader can run, and takes no snapshot.isolation_t isolation_k;reference_storeSeeds the comparator, which an instance carrying state or a dispatch pointer needs.reference_store();reference_store(comparator_t const & comparator);Seeds the comparator, which an instance carrying state or a dispatch pointer needs.
reference_store(reference_store const &)=delete;reference_store(reference_store &&) noexcept=default;operator=reference_store & operator=(reference_store const &)=delete;reference_store & operator=(reference_store &&) noexcept=default;sizeReturns the number of visible (committed) non-deleted elements in the container.emptyChecks if the container has no visible elements.transactionCreates a new transaction with a fresh generation number, resettable and reusable after commit or rollback to avoid reallocations.expected<transaction_t> transaction() noexcept;Returns an error on allocation failure.
Transaction instance.
insertAtomically inserts an element, refusing the key that is already there.template <typename callback_inserted_type_ = no_op_t, typename callback_existing_type_ = no_op_t>
status_t insert(
value_t && element,
callback_inserted_type_ && callback_inserted = {},
callback_existing_type_ && callback_existing = {}) noexcept;element | in | Element to insert (moved into the container). |
|---|---|---|
callback_inserted | in | Invoked with the stored element. Must be noexcept. |
callback_existing | in | Invoked with the element already under the key, which keeps its value. Must be noexcept. |
key_already_exists_k The key is taken.insert_if_missingAtomically inserts an element, leaving the key that is already there untouched.template <typename callback_inserted_type_ = no_op_t, typename callback_existing_type_ = no_op_t>
status_t insert_if_missing(
value_t && element,
callback_inserted_type_ && callback_inserted = {},
callback_existing_type_ && callback_existing = {}) noexcept;template <readable_iterator elements_begin_type_, iterator_sentinel<elements_begin_type_> elements_end_type_ = elements_begin_type_>
status_t insert_if_missing(
elements_begin_type_ begin,
elements_end_type_ end) noexcept;Atomically inserts a batch, leaving already-present keys untouched.
element | in | Element to insert (moved into the container). |
|---|---|---|
callback_inserted | in | Invoked with the stored element. Must be noexcept. |
callback_existing | in | Invoked with the element already under the key, which keeps its value. Must be noexcept. |
begin | in | Iterator to the first element. |
end | in | Iterator past the last element. |
copy returns passes through unchanged.insert_or_assignAtomically writes an element, taking the key whether or not it was there.template <typename callback_inserted_type_ = no_op_t, typename callback_existing_type_ = no_op_t>
status_t insert_or_assign(
value_t && element,
callback_inserted_type_ && callback_inserted = {},
callback_existing_type_ && callback_existing = {}) noexcept;template <readable_iterator elements_begin_type_, iterator_sentinel<elements_begin_type_> elements_end_type_ = elements_begin_type_>
status_t insert_or_assign(
elements_begin_type_ begin,
elements_end_type_ end) noexcept;Atomically inserts or assigns a batch of elements.
Either all succeed or all fail. Iterator dereferencing should return R-value references (use std::make_move_iterator()).
element | in | Element to insert or assign (moved into the container). |
|---|---|---|
callback_inserted | in | Invoked with the stored element when the key was free. Must be noexcept. |
callback_existing | in | Invoked with the element that was replaced. Must be noexcept. |
begin | in | Iterator to the first element. |
end | in | Iterator past the last element. |
upsertAlias for insert_or_assign().status_t upsert(value_t && element) noexcept;template <readable_iterator elements_begin_type_, iterator_sentinel<elements_begin_type_> elements_end_type_ = elements_begin_type_>
status_t upsert(
elements_begin_type_ begin,
elements_end_type_ end) noexcept;Alias for batch insert_or_assign(), atomically inserting or assigning a batch.
Atomically inserts or updates an element.
element | in | Element to insert or assign (moved into the container). |
|---|---|---|
begin | in | Iterator to the first element. |
end | in | Iterator past the last element. |
updateAtomically writes an element, refusing a key that is not already there.status_t update(value_t && element) noexcept;template <readable_iterator elements_begin_type_, iterator_sentinel<elements_begin_type_> elements_end_type_ = elements_begin_type_>
status_t update(
elements_begin_type_ begin,
elements_end_type_ end) noexcept;Atomically writes a batch, refusing the group if any key is absent.
The strict counterpart to insert_or_assign(), which takes the key either way.
element | in | Element to write (moved into the container when the key is present). |
|---|---|---|
begin | in | Iterator to the first element. |
end | in | Iterator past the last element. |
key_not_found_k The key is missing.key_not_found_k Any key is absent.copy returns passes through unchanged.try_emplaceDeleted, use insert_if_missing() instead.template <typename... args_types_>
status_t try_emplace(args_types_ && ...) noexcept=delete;std::map::try_emplace() does not name its insert failure strategy, so this type spells out three alternatives: insert() fails on an existing key, insert_if_missing() skips it, and insert_or_assign() overwrites it.
find_copyCopies out the member equal to comparable, for callers that cannot use a callback.template <typename comparable_type_ = identifier_t>
expected<value_t> find_copy(
comparable_type_ && comparable) const noexcept;comparable | in | Object comparable to value_t and convertible to identifier_t. |
|---|
The copied element.
key_not_found_k No visible member equals comparable.copy returns passes through unchanged.containsChecks if a member equal to the given comparable exists.template <typename comparable_type_ = identifier_t>
expected<bool> contains(comparable_type_ && comparable) const noexcept;Convenience wrapper around find() for existence checks.
comparable | in | Object comparable to value_t and convertible to identifier_t. |
|---|
True if the element exists, false otherwise.
upper_boundFinds the first member greater than the given comparable.template <typename comparable_type_ = identifier_t, typename callback_found_type_ = no_op_t, typename callback_missing_type_ = no_op_t>
status_t upper_bound(
comparable_type_ && comparable,
callback_found_type_ && callback_found,
callback_missing_type_ && callback_missing = {}) const noexcept;lower_bound_copyCopies out the first visible element ordered at or after comparable.template <typename comparable_type_ = identifier_t>
expected<value_t> lower_bound_copy(
comparable_type_ && comparable) const noexcept;key_not_found_k No visible element orders at or after comparable.copy returns passes through unchanged.upper_bound_copyCopies out the first visible element ordered strictly after comparable.template <typename comparable_type_ = identifier_t>
expected<value_t> upper_bound_copy(
comparable_type_ && comparable) const noexcept;key_not_found_k No visible element orders after comparable.copy returns passes through unchanged.selectHands callback_found the zero-based ordinal -th smallest visible element.template <typename callback_found_type_ = no_op_t, typename callback_missing_type_ = no_op_t>
status_t select(
std::size_t ordinal,
callback_found_type_ && callback_found,
callback_missing_type_ && callback_missing = {}) const noexcept;A linear walk of the whole store, and deliberately so: this is the oracle the ranked engines are checked against, so it is written to be obviously right rather than fast. Nothing here is augmented, and an ordinal read from a plain ordered walk cannot disagree with the walk.
ordinal | in | Zero-based position among the visible elements. |
|---|---|---|
callback_found | in | Callback to receive a value_t const &. Must be noexcept. |
callback_missing | in | Callback triggered when fewer elements are visible. Must be noexcept. |
rankHands callback_found how many visible elements the store orders before comparable.template <typename comparable_type_ = identifier_t, typename callback_found_type_ = no_op_t, typename callback_missing_type_ = no_op_t>
status_t rank(
comparable_type_ && comparable,
callback_found_type_ && callback_found,
callback_missing_type_ && callback_missing = {}) const noexcept;A linear walk, for the reason select() takes one.
comparable | in | Object comparable to value_t and convertible to identifier_t. |
|---|---|---|
callback_found | in | Callback to receive a std::size_t. Must be noexcept. |
callback_missing | in | Callback triggered when comparable is not visible. Must be noexcept. |
rangeIterates over all entries in the range [ lower, upper).template <typename lower_type_ = identifier_t, typename upper_type_ = identifier_t, typename callback_type_ = no_op_t>
status_t range(
lower_type_ && lower,
upper_type_ && upper,
callback_type_ && callback = {}) const noexcept;Const version. Unlike equal_range(), this takes two keys and returns all entries between them.
lower | in | Lower bound (inclusive). |
|---|---|---|
upper | in | Upper bound (exclusive). |
callback | in | Callback invoked for each element in range. Must be noexcept. |
A callback answering walk_control_t stops the walk where it says to.
update_rangeHands callback each visible member of [ lower, upper ) to revise and stamp.template <typename lower_type_ = identifier_t, typename upper_type_ = identifier_t, typename callback_type_ = no_op_t>
requires is_mapping<value_t>
status_t update_range(
lower_type_ && lower,
upper_type_ && upper,
callback_type_ && callback) noexcept;lower | in | Lower bound (inclusive). |
|---|---|---|
upper | in | Upper bound (exclusive). |
callback | in | Invoked with identifier_t const & and mapped_t &. Must be noexcept. |
Always success here; the status is reported so a mutator that can fail on a sibling engine has the same channel on all three.
erase_rangeErases all the entries falling in between the lower and the upper.template <typename lower_type_ = identifier_t, typename upper_type_ = identifier_t, typename callback_type_ = no_op_t>
status_t erase_range(
lower_type_ && lower,
upper_type_ && upper,
callback_type_ && callback = {}) noexcept;lower | in | Lower bound of the range. |
|---|---|---|
upper | in | Upper bound of the range (exclusive). |
callback | in | Optional callback invoked for each erased element. Must be noexcept. |
Always succeeds.
erase_fromErases every entry ordered at or after lower, with no upper bound at all.template <typename lower_type_ = identifier_t, typename callback_type_ = no_op_t>
status_t erase_from(
lower_type_ && lower,
callback_type_ && callback = {}) noexcept;lower | in | Lower bound of the range, inclusive - an entry equal to it is erased, which is the same end erase_range() includes. |
|---|---|---|
callback | in | Optional callback invoked for each erased element. Must be noexcept. |
Always succeeds.
erase_up_toErases every entry ordered before upper, with no lower bound at all.template <typename upper_type_ = identifier_t, typename callback_type_ = no_op_t>
status_t erase_up_to(
upper_type_ && upper,
callback_type_ && callback = {}) noexcept;upper | in | Upper bound of the range, exclusive - an entry equal to it is kept, which is the same end erase_range() excludes. |
|---|---|---|
callback | in | Optional callback invoked for each erased element. Must be noexcept. |
Always succeeds.
clearRemoves every element, refusing while any transaction has something staged.status_t clear() noexcept;The generation and stamp counters keep running. Rewinding either would hand a future transaction a number an open one already carries, and both are compared by value.
operation_not_permitted_k A staged version would be dropped.reserveAccepts a capacity hint and does nothing with it.status_t reserve(std::size_t) noexcept;Every allocation this store makes is one node at a time, drawn when the write happens: the entries live in a node-based ordered set, and the vectors it also holds belong to transactions rather than to the store, which is why the transaction-level reserve() does real work while this one has nothing to reserve. Reserving here would therefore promise a later insert cannot run out of memory, which it still can.
Always succeeds.
vacuumFrees every entry no reader can reach.expected<std::size_t> vacuum() noexcept;template <typename lower_type_, typename upper_type_>
expected<std::size_t> vacuum(
lower_type_ && lower,
upper_type_ && upper) noexcept;Frees the unreachable entries ordered in [ lower, upper), so a caller can step through the keyspace instead of paying for one pass over all of it.
Returns how many were reclaimed.
sample_oneDraws one visible entry uniformly from [ lower, upper), handing it to callback.template <typename lower_type_, typename upper_type_, typename generator_type_, typename callback_type_ = no_op_t>
requires uniform_random_bits<std::remove_cvref_t<generator_type_>>
status_t sample_one(
lower_type_ && lower,
upper_type_ && upper,
generator_type_ && generator,
callback_type_ && callback) const noexcept;Counts the window, then walks it again to the drawn offset - linear both times, and meant to be: this is the oracle the descending engines are checked against.
lower | in | Lower bound (inclusive). |
|---|---|---|
upper | in | Upper bound (exclusive). |
generator | inout | Random number generator (e.g., std::mt19937). |
callback | in | Callback to receive the sampled element. Must be noexcept. Invoked at most once, and never when the window shows nothing. |
sample_reservoirReservoir-samples entries from [ lower, upper), filling a reservoir buffer with up to reservoir_capacity randomly selected elements.template <typename lower_type_, typename upper_type_, typename generator_type_, indexed_writable_iterator<value_t> output_iterator_type_>
requires uniform_random_bits<std::remove_cvref_t<generator_type_>>
status_t sample_reservoir(
lower_type_ && lower,
upper_type_ && upper,
generator_type_ && generator,
std::size_t & seen,
std::size_t reservoir_capacity,
output_iterator_type_ && reservoir) const noexcept;lower | in | Lower bound (inclusive). |
|---|---|---|
upper | in | Upper bound (exclusive). |
generator | inout | Random number generator (e.g., std::mt19937). |
seen | inout | Count of entries processed (can span multiple calls). |
reservoir_capacity | in | Maximum number of samples to collect. |
reservoir | out | Buffer the samples land in, written by index. |
makeBuilds a store around a specific comparator, for comparators that carry state.expected<store_t> make(comparator_t const & comparator) noexcept;expected<store_t> make() noexcept;Factory method to create a new transactional set without throwing exceptions.
Returns error status on allocation failure.
transaction_tA transaction that buffers writes, stages them invisibly and publishes them in one commit.class transaction_ttransaction_groupA two-phase commit over several stores at once.13template <optimistically_concurrent_store... store_types_>
class transaction_groupStores built into one order are committed under one stamp, drawn before any of them is written and published once the last one is, so a reader at any snapshot sees the whole group or none of it. Stores in orders of their own, or in none, publish a stamp each.
order_tThe order the first participant was built into, or no_order_t where it keeps no stamps.using order_t = typename order_of<std::tuple_element_t<0, std::tuple<store_types_...>>>::type;claim_tThe claim every participant reads under where they share an order, and nothing where they do not.using claim_t = typename order_t::snapshot_claim_t;asks_before_writing_kWhether this group asks every participant before letting any of them write.bool asks_before_writing_k;Needs all of them to offer the split, since one participant deciding and writing in the same call puts a refusal from a later one over writes an earlier one already published. A lone participant is excluded because it has nothing to tear against, and asking it separately would only widen the window a wrapper's own lock closes when it commits in one call.
transaction_grouptransaction_group(transaction_group &&) noexcept=default;transaction_group(transaction_group const &)=delete;operator=transaction_group & operator=(transaction_group &&) noexcept=default;transaction_group & operator=(transaction_group const &)=delete;participantThis group's participant in store_index_, counted in the caller's argument order.template <std::size_t store_index_>
auto & participant() noexcept;participantsEvery participant at once, in the order the caller named their stores, for binding with auto [a, b] =.auto participants() noexcept;commit_withRuns body over the participants, then stages and commits the group.template <typename body_type_>
status_t commit_with(body_type_ && body) noexcept;The three calls a group always makes in the same order, so a caller cannot forget the stage or leave a refused group staged: anything short of success resets every participant before returning; its sibling commit_with_retries takes a conflict as a reason to try again.
body | in | Invoked as body(participants...), answering a status_t. Must be noexcept. |
|---|
operation_not_permitted_k The group was already staged.body returns, or a participant refuses the stage or the commit with, passes through unchanged.commit_stampThe stamp the last commit published every participant under, or zero where each stamped its own.generation_t commit_stamp() const noexcept;commitPublishes the participants, drawing each one's commit stamp.status_t commit() noexcept;Where asks_before_writing_k, every participant is asked before any writes, so a refusal publishes nothing and the group stays staged, which is the one state rollback accepts. A participant may still be committed over between the two passes - what the split buys is that the second pass cannot refuse, not that nothing can change beneath it.
Where it does not hold, each participant is committed in turn. A refusal by the first has published nothing and leaves the group staged too. A refusal by any later one drops the group to pending, which refuses both commit and rollback - the position decides that, not whether anything was published, since a torn commit cannot be told apart from an untorn one without asking every participant what it did. Only reset then clears the rest.
Where shares_one_order_k, the participants are asked first as well, and then written under one stamp drawn from the order they share, which the watermark covers only once the last of them has published.
operation_not_permitted_k The group is not staged.resetDiscards every participant's staged and pending changes, at one fresh snapshot where they share an order.status_t reset() noexcept;makeOpens one transaction per store, or none at all.expected<transaction_group> make(store_types_ &... stores) noexcept;A store named twice would take two participants over one snapshot, neither seeing the other's writes, so the later commit overwrites the earlier one and no conflict is reported.
The group.
invalid_argument_k One store is named twice, or stores meant to share one order are built into different orders.stores refuses its transaction with passes through unchanged, the first in argument order winning, and every transaction opened goes to its destructor.conflictedWhether status turned a transaction away over what another one published, which a retry can overcome.bool conflicted(status_t status) noexcept;stage_eachHands stage_one every element of [ first, last ), duplicated outside the target.template <typename value_type_, readable_iterator input_iterator_type_, typename stage_one_type_>
status_t stage_each(
input_iterator_type_ first,
input_iterator_type_ last,
stage_one_type_ && stage_one) noexcept;A range handing over lvalues duplicates through copy_safely, so an element refusing its own copy stops the batch with that reason rather than with the allocator's; a range handing over rvalues moves, which is what a move iterator asks for. Nothing here reaches the destination - what stage_one does with an element is where a batch decides whether it can still be undone.
first | in | Beginning of range to stage. |
|---|---|---|
last | in | End of range to stage. |
stage_one | in | Receives one element by rvalue and reports where it landed. Must be noexcept. |
copy or stage_one returns passes through unchanged.hand_overHands args to callback and answers whether the walk carries on.template <typename callback_type_, typename... args_types_>
walk_control_t hand_over(
callback_type_ && callback,
args_types_ &&... args) noexcept;A callback that cannot say resumes it, so a walk asks here instead of branching on the shape.
missing_watchWhat a watch on a key with no entry at all records.watch_t missing_watch() noexcept;A key erased through a transaction carries a committed tombstone and dates its absence by that tombstone's generation, which is what tells an absence nothing disturbed apart from one an insert and an erase closed over again. This constant is what remains with no tombstone to date.
An erase taken outside a transaction drops the entry outright, and vacuum, clear and the ranged erases reclaim one a watch may still hold. Neither monotonic_store nor reference_store pins reclamation behind an open reader the way snapshot_store does.
Absence is dated only while a tombstone survives, so a watch can miss drift once its tombstone is gone, and can report drift that is only the reclamation.
watch_shape_ofThe watch a read resolving to resolved should record, or missing_watch when it resolves to nothing at all.template <typename versioned_type_>
watch_t watch_shape_of(versioned_type_ const *resolved) noexcept;A committed tombstone keeps its own generation rather than collapsing onto the constant, so two absences separated by a commit do not compare equal.
Both ends of a watch must resolve through the same finder, or a tombstone one end cannot see reads as drift on the other. Both engines therefore watch through the finder validation uses.
watch_driftedWhether a watched key moved between recorded and what it resolves to now.bool watch_drifted(watch_t recorded, watch_t now) noexcept;Not equality: an absence a vacuum stripped of its date is the absence that was already read.
validate_watchesRe-reads every watched identifier and reports whether any drifted since it was sampled.template <typename watches_type_, typename resolver_type_>
status_t validate_watches(
watches_type_ const & watches,
resolver_type_ && resolve_latest) noexcept;watches | in | The identifier-and-watch pairs a transaction accumulated. |
|---|---|---|
resolve_latest | in | Invoked as resolve_latest(identifier, on_found, on_missing); must be noexcept. |
read_conflict_k A watch drifted since it was sampled.holdsWhether mask carries flag, spelled out because a scoped enum has no operator&.bool holds(access_t mask, access_t flag) noexcept;operator|Both claims at once, for a key that is read and also opens a range.access_t operator|(access_t first, access_t second) noexcept;identifier_ofThe identifier a version-decorated object is addressed by, with the metadata peeled off.template <typename type_>
decltype(auto) identifier_of(type_ const & object) noexcept;A chain defers to the version it holds, a version to the value it wraps, and a dated identifier to the identifier inside it, so a plain key is reached from any of the shapes a store stores.
commit_with_retriesStages stage_changes into transaction and commits it, at most attempts times.template <typename transaction_type_, typename stage_changes_type_>
status_t commit_with_retries(
transaction_type_ & transaction,
std::size_t attempts,
stage_changes_type_ && stage_changes) noexcept;Every failed attempt is reset before the next is made or the failure is returned, so nothing it staged stays behind and a retry recomputes from the newest snapshot. What a conflict means and when one is raised is the store's isolation level, which this neither weakens nor strengthens.
transaction | inout | The transaction to stage into and commit, reset on a failed try. |
|---|---|---|
attempts | in | Most commits to try. |
stage_changes | in | Invoked as stage_changes(transaction) on every attempt; must be noexcept. |
A transaction opened at an older snapshot, such as one adopting a reader's, reads at the newest one from its second attempt on.
operation_would_block_k Every attempt met a conflict, or attempts is zero.stage_changes or transaction returns passes through unchanged.make_transaction_groupDeduces the store types, so a caller names the stores and not their spellings.template <optimistically_concurrent_store... store_types_>
expected<transaction_group<store_types_...>> make_transaction_group(
store_types_ &... stores) noexcept;halts_the_walkWhether callback_type_ can stop a walk, rather than taking every element offered.bool halts_the_walk;A callback answering walk_control_t is asked whether to carry on; one answering void is asking for everything. The difference is resolved where the walk runs rather than by a flag.
Member types35monotonic_store::value_t | typename owned_value_of<collection_type_>::type |
|---|---|
monotonic_store::value_type | value_t |
monotonic_store::key_t | typename collection_type_::key_type |
monotonic_store::key_type | key_t |
monotonic_store::mapped_t | typename collection_type_::mapped_type |
monotonic_store::mapped_type | mapped_t |
monotonic_store::is_associative | typename collection_type_::is_associative |
monotonic_store::is_transactional | std::true_type |
monotonic_store::allocator_t | typename collection_type_::allocator_type |
monotonic_store::comparator_t | typename storage_shape_t::addressing_source_t |
monotonic_store::versioning_t | typename storage_shape_t::versioning_t |
monotonic_store::identifier_t | typename versioning_t::identifier_t |
monotonic_store::generation_t | typename versioning_t::generation_t |
monotonic_store::watch_t | typename versioning_t::watch_t |
monotonic_store::watched_identifier_t | typename versioning_t::watched_identifier_t |
monotonic_store::dated_identifier_t | typename versioning_t::dated_identifier_t |
monotonic_store::versioned_t | typename versioning_t::versioned_t |
monotonic_store::versioned_entry_t | versioned_t |
reference_store::value_t | value_type_ |
reference_store::value_type | value_t |
reference_store::comparator_t | comparator_type_ |
reference_store::allocator_t | allocator_type_ |
reference_store::key_type | typename mapping_key_type_or_itself<value_t>::type |
reference_store::mapped_type | typename mapped_value_type_or_void<value_t>::type |
reference_store::is_associative | std::bool_constant<is_mapping<value_t>> |
reference_store::is_transactional | std::true_type |
reference_store::versioning_t | versioning_for<value_t, comparator_t> |
reference_store::identifier_t | typename versioning_t::identifier_t |
reference_store::generation_t | typename versioning_t::generation_t |
reference_store::dated_identifier_t | typename versioning_t::dated_identifier_t |
reference_store::watch_t | typename versioning_t::watch_t |
reference_store::watched_identifier_t | typename versioning_t::watched_identifier_t |
reference_store::versioned_entry_t | typename versioning_t::versioned_entry_t |
reference_store::versioned_comparator_t | typename versioning_t::versioned_comparator_t |
transaction_group::transactions_t | std::tuple<typename store_types_::transaction_t...> |