# Transactions > SmashTable for C++ ### Why the C++ Library 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: ```cpp struct budget_t { std::size_t used = 0, limit = 0; }; template // ? 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(::operator new(count * sizeof(value_type_))); } }; int main() { budget_t budget {0, 3}; std::set, failing_allocator> values {std::less<> {}, failing_allocator {&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: ```text std::bad_alloc after 3 allocations set contains 3 elements: 0 1 2 ``` The same range through a container here answers with a `status_t`, and the destination is untouched: ```cpp using set_t = st::avl_set, failing_allocator>; set_t values(std::less<> {}, failing_allocator {&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: ```text insert(first, last) returned out_of_memory_heap_k set contains 0 elements ``` A 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. `#include ` `#include ` `#include ` ## commit_stamp_t When a version became visible, or that it never has. ```cpp enum commit_stamp_t ``` The 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`](https://www.unum.cloud/docs/smashtable/cpp/isolation.md#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::max()` ## walk_control_t Whether a walk carries on after handing an element over. ```cpp enum walk_control_t ``` One 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](https://www.unum.cloud/docs/smashtable/cpp/containers.md#basic_flat_set)` compares against [`halt_k`](#halt_k) directly, and [`probe_to_visit`](https://www.unum.cloud/docs/smashtable/cpp/containers.md#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_t Where a cursor's next step begins, which is a different question before and after the first. ```cpp enum cursor_seed_t ``` - `the_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_t Whether a cursor stops at a key it was given, or only when the store runs out. ```cpp enum cursor_limit_t ``` Carried 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_t Whether an ordered cursor can still hand something over, once a step found it cannot. ```cpp enum cursor_reach_t ``` A 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_t Whether a transaction's writes are sitting in the store, invisible, or not there yet. ```cpp enum staging_t ``` A committed transaction returns to [`pending_k`](#pending_k) and is immediately reusable, so there is no third state to name - [`commit`](#commit) on a [`pending_k`](#pending_k) transaction already reports [`operation_not_permitted_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#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`](#commit) allocates nothing and only stamps. ## presence_t Whether an entry says its key is there, or says it was taken away and when. ```cpp enum presence_t ``` - `present_k`: The key is there and this is its value. - `erased_k`: The key was erased. ## unmask_outcome_t What a commit found when it went looking for the version it was asked to publish. ```cpp enum unmask_outcome_t ``` [`already_published_k`](#already_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_t Watch metadata for versioned elements. ```cpp struct watch_t ``` - `generation` `generation_t` - `presence` `presence_t` ## access_t How one transaction reached one key, as independent claims rather than as a state. ```cpp enum access_t ``` A 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_identifier One key a transaction read, and in what way. ```cpp template struct accessed_identifier ``` Carries 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_hasher Hashes a version-decorated object by the identifier inside it, ignoring the metadata. ```cpp template struct per_key_hasher ``` An 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_equals Compares version-decorated objects by the identifier inside them, ignoring the metadata. ```cpp template struct per_key_equals ``` Paired with `[per_key_hasher](#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_t What a store keeping no stamps contributes to a shard set, which is nothing at all. ```cpp struct no_order_t ``` ## order_of The order a store is a member of, or `[no_order_t](#no_order_t)` when it keeps no stamps. ```cpp template struct order_of ``` ## rebound_order_of The same store built into `order_type_` instead, or the store itself where it names no such rebind. ```cpp template struct rebound_order_of ``` ## group_phase_t A phase a transaction group drives through every participant, one at a time. ```cpp enum group_phase_t ``` - `validate_k` - `release_validation_k` - `stage_k` - `publish_k` - `commit_k` - `prune_k` - `rollback_k` - `reset_k` ## basic_commit_order The order commits are published in, and the oldest snapshot readers can still name. ```cpp template waiting_policy_type_ = standard_waiting_policy_t> class basic_commit_order ``` Stores 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. #### Publication 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`](#begin_commit) and [`end_commit`](#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. #### Open Snapshots 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`](#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. #### Ordering Three orderings carry the guarantees under [`shared_k`](https://www.unum.cloud/docs/smashtable/cpp/isolation.md#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`](https://www.unum.cloud/docs/smashtable/cpp/isolation.md#solitary_k) none of that applies, because there is no second thread to order against. [`end_commit`](#end_commit) waits for older commits to land once `commits_in_flight_` of them are ahead of the watermark, and [`await_published`](#await_published) waits for another thread's publication. Every store and group here commits under the rule above. Warnings: [`end_commit`](#end_commit) and [`await_published`](#await_published) are deadlock-free only for a committer that holds every lock it publishes under before it draws and takes none after. ## ring_k Commits that may be in flight past the watermark before a landing one waits. ```cpp std::size_t ring_k; ``` ## buckets_k How many floors are kept. ```cpp std::size_t buckets_k; ``` Readers past it share a bucket rather than being turned away. ## sharing_k Whether several threads reach this order. ```cpp order_sharing_t sharing_k; ``` ## basic_commit_order ```cpp constexpr basic_commit_order() noexcept=default; ``` ```cpp basic_commit_order(basic_commit_order const &)=delete; ``` ## operator= ```cpp basic_commit_order & operator=(basic_commit_order const &)=delete; ``` ## next_generation Hands 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. ```cpp generation_t next_generation() noexcept; ``` ## published_stamp The 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. ```cpp generation_t published_stamp() const noexcept; ``` ## drawn_stamp The newest stamp any commit has drawn, landed or not, which is what a reader must validate against rather than the watermark. ```cpp 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_snapshot Points `claim` at the newest whole stamp, giving back whatever it held first. ```cpp generation_t take_snapshot(snapshot_claim_t & claim) noexcept; ``` ## share_snapshot Points `claim` at the snapshot `held` reads, giving back what `claim` held first. ```cpp generation_t share_snapshot( snapshot_claim_t & held, snapshot_claim_t & claim) noexcept; ``` `held` is live, so its bucket carries at least one member and cannot have been recycled, and its floor is already at or below the snapshot being shared. One more member of that same bucket therefore needs no re-read: either claim retiring leaves the other pinning retention. ## begin_commit Draws the stamp `node` publishes under. ```cpp void begin_commit(commit_in_flight_t & node) noexcept; ``` One add: a draw never waits and never refuses. ## end_commit Records 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. ```cpp void end_commit(commit_in_flight_t & node) noexcept; ``` ## await_published Waits until the watermark covers `stamp`, so a committer may read what it wrote. ```cpp void await_published(commit_stamp_t stamp) noexcept; ``` Warnings: Blocks on another thread's publication, so no store lock may be held across it. ## low_water_mark The oldest snapshot any reader can still name, so everything older is unreachable. ```cpp 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_snapshots How many readers currently hold a snapshot, summed over the buckets. ```cpp std::size_t open_snapshots() const noexcept; ``` ## resume Restarts an order nothing has drawn from yet at `published`, so the stamps this process draws continue above every stamp an earlier one made durable. ```cpp 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. Warnings: Ordered against no other call, so it runs before a second thread can reach this order at all. Statuses: - [`invalid_argument_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#invalid_argument_k) `published` is negative or leaves no stamp to draw. - [`operation_not_permitted_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#operation_not_permitted_k) A generation or stamp was drawn here, or a snapshot is open. ## adopt Takes over `other's` stamps, for a store that is being moved and has nothing open or in flight. ```cpp void adopt(basic_commit_order const & other) noexcept; ``` ## snapshot_claim_t One reader's claim on a snapshot, which holds the low-water mark at or below it. ```cpp class snapshot_claim_t ``` While 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_group A two-phase commit over however many stores join at run time, published under one stamp. ```cpp template class dynamic_transaction_group ``` Where `[transaction_group](#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`](#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_t The order every joining store must be built into, whose stamp the group commits under. ```cpp using order_t = typename order_of>>::type; ``` ## claim_t The claim every participant reads under. ```cpp using claim_t = typename order_t::snapshot_claim_t; ``` ## kinds_k How many kinds of store may join, which bounds nothing about how many stores do. ```cpp std::size_t kinds_k; ``` ## dynamic_transaction_group Takes over `other's` participants and claim, leaving it with neither. ```cpp dynamic_transaction_group(dynamic_transaction_group && other) noexcept; ``` ```cpp dynamic_transaction_group(dynamic_transaction_group const &)=delete; ``` ## operator= Destroys this group's participants before its claim goes back, then takes over `other`. ```cpp dynamic_transaction_group & operator=( dynamic_transaction_group && other) noexcept; ``` ```cpp dynamic_transaction_group & operator=( dynamic_transaction_group const &)=delete; ``` ## ~dynamic_transaction_group Destroys every participant, unwinding what it staged, before the claim is given back. ```cpp ~dynamic_transaction_group() noexcept; ``` ## join Opens a transaction on `store` at the group's snapshot and generation, or answers the one opened when `store` joined before. ```cpp template expected 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. Statuses: - [`invalid_argument_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#invalid_argument_k) `store` is built into another order. - [`operation_not_permitted_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#operation_not_permitted_k) The group is staged. - Any status `store` refuses the transaction with passes through unchanged. ## participant The participant `store` joined as, or null where it has not joined since the last successful commit or reset. ```cpp template store_type_::transaction_t * participant( store_type_ const & store) noexcept; ``` ## snapshot The stamp every participant reads at, which the group's claim pins. ```cpp generation_t snapshot() const noexcept; ``` ## generation The generation the group drew for its participants, which later joins open at too. ```cpp generation_t generation() const noexcept; ``` ## participants_count How many stores have joined since the last successful commit or reset. ```cpp std::size_t participants_count() const noexcept; ``` ## * Whether the group's writes are sitting in their stores, invisible. ```cpp staging_t staging() const noexcept; ``` ## commit_stamp The stamp the last successful commit published every participant under, or zero where it had nothing to publish. ```cpp generation_t commit_stamp() const noexcept; ``` ## * Validates every watch and reserves every write, undoing all of it if one refuses. ```cpp 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. Statuses: - [`operation_not_permitted_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#operation_not_permitted_k) The group is already staged. - Any status a participant refuses its stage with passes through unchanged. - Any status a rollback of the staged prefix reports replaces the refusal, and the whole group is reset, since that rollback lost a write. ## commit Publishes every participant under one stamp, then empties the group for new joins. ```cpp 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`](#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. Statuses: - [`operation_not_permitted_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#operation_not_permitted_k) The group is not staged. - Any status a participant refuses its validation with passes through unchanged. ## * Pulls every staged write back into its transaction, leaving the group retryable. ```cpp status_t rollback() noexcept; ``` Only a rollback that reached every participant clears the staged flag, so the next [`stage`](#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`](#stage) would stage a second time over the first. Statuses: - [`operation_not_permitted_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#operation_not_permitted_k) The group is not staged. - Any status a participant refuses its rollback with passes through unchanged, and the rollback stops there. ## reset Destroys every participant, unwinding whatever it staged, then reads at a fresh snapshot under a fresh generation. ```cpp status_t reset() noexcept; ``` ## make Opens an empty group at the newest snapshot of [`order`](https://www.unum.cloud/docs/smashtable/cpp/isolation.md#order), under a generation drawn for it. ```cpp expected make(order_t & order) noexcept; ``` ## monotonic_store Generic transactional store providing 2-phase commits and "watch" operations. ```cpp template class monotonic_store ``` Can 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`. #### Design Goals 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](https://www.unum.cloud/docs/smashtable/cpp/isolation.md#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` to support safe copying for watch bookkeeping. #### API Overview - All lookups are heterogeneous, taking any type comparable to the element type, as long as the comparator defines `using is_transparent = void;`, like `std::map` and `std::set`. - No iterators are provided to keep the implementation simple and avoid complexity of maintaining persistent iterator validity across transactions and modifications. - All operations use callback-based APIs for consistency, with all callbacks expected to be `noexcept`. #### Insert Strategies 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 | See also: [https://jepsen.io/consistency/models/monotonic-atomic-view](https://jepsen.io/consistency/models/monotonic-atomic-view) See also: [https://jepsen.io/consistency/models/read-committed](https://jepsen.io/consistency/models/read-committed) ## storage_shape_t What this core family rebinds on, and how a decorated entry is reached inside it. ```cpp using storage_shape_t = versioned_storage_for; ``` ## store_t What this store calls itself, so generic code spells an engine and a wrapper alike. ```cpp using store_t = monotonic_store; ``` ## isolation_k A commit publishes every staged version before any reader can run, and takes no snapshot. ```cpp isolation_t isolation_k; ``` ## monotonic_store Seeds the underlying tree's allocator, which a stateful allocator needs. ```cpp monotonic_store() noexcept; ``` ```cpp monotonic_store(allocator_t const & allocator) noexcept; ``` Seeds the underlying tree's allocator, which a stateful allocator needs. ```cpp monotonic_store( comparator_t const & comparator, allocator_t const & allocator = {}) noexcept; ``` Seeds the comparator too, needed when it carries state or a dispatch pointer. ```cpp monotonic_store(monotonic_store && other) noexcept; ``` ## operator= ```cpp monotonic_store & operator=(monotonic_store && other) noexcept; ``` ## ~monotonic_store ```cpp ~monotonic_store() noexcept; ``` ## size Returns the number of visible (committed) non-deleted elements in the tree. ```cpp std::size_t size() const noexcept; ``` ## empty Checks if the tree has no visible elements. ```cpp bool empty() const noexcept; ``` ## * Returns the number of elements with key equal to the specified argument. ```cpp template expected count( comparable_type_ && comparable) const noexcept; ``` For unique-key containers like this, returns either 0 or 1. - `comparable` (in): Object comparable to [`value_t`](https://www.unum.cloud/docs/smashtable/cpp/containers.md#value_t) and convertible to `identifier_t`. ## contains Checks if a member __equal__ to the given `comparable` exists in the tree. ```cpp template expected contains(comparable_type_ && comparable) const noexcept; ``` - `comparable` (in): Object comparable to [`value_t`](https://www.unum.cloud/docs/smashtable/cpp/containers.md#value_t) and convertible to `identifier_t`. ## find_copy Finds and returns a copy of an element equal to `comparable`. ```cpp template expected 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`](https://www.unum.cloud/docs/smashtable/cpp/containers.md#value_t) and convertible to `identifier_t`. Statuses: - [`key_not_found_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#key_not_found_k) No visible member equals `comparable`. - Any status the element's [`copy`](https://www.unum.cloud/docs/smashtable/cpp/containers.md#copy) returns passes through unchanged. ## lower_bound_copy Finds and returns a copy of the first element not less than (>=) `comparable`. ```cpp template requires ordered_collection expected lower_bound_copy( comparable_type_ && comparable) const noexcept; ``` - `comparable` (in): Object comparable to [`value_t`](https://www.unum.cloud/docs/smashtable/cpp/containers.md#value_t). Statuses: - [`key_not_found_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#key_not_found_k) No visible element orders at or after `comparable`. - Any status the element's [`copy`](https://www.unum.cloud/docs/smashtable/cpp/containers.md#copy) returns passes through unchanged. ## upper_bound_copy Finds and returns a copy of the first element greater than (>) `comparable`. ```cpp template requires ordered_collection expected upper_bound_copy( comparable_type_ && comparable) const noexcept; ``` - `comparable` (in): Object comparable to [`value_t`](https://www.unum.cloud/docs/smashtable/cpp/containers.md#value_t). Statuses: - [`key_not_found_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#key_not_found_k) No visible element orders after `comparable`. - Any status the element's [`copy`](https://www.unum.cloud/docs/smashtable/cpp/containers.md#copy) returns passes through unchanged. ## transaction Creates a new transaction with a fresh generation number. ```cpp expected transaction() noexcept; ``` Transaction can be reset and reused after commit/rollback to avoid reallocations. ## insert Atomically inserts an element only if the key doesn't exist. ```cpp status_t insert(value_t && value) noexcept; ``` ```cpp template 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. Statuses: - [`key_already_exists_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#key_already_exists_k) The key exists. Statuses: - [`key_already_exists_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#key_already_exists_k) Any key exists. - Any status the element's [`copy`](https://www.unum.cloud/docs/smashtable/cpp/containers.md#copy) returns passes through unchanged. ## insert_if_missing Inserts only if the key is absent, reporting which of the two outcomes occurred. ```cpp template status_t insert_if_missing( value_t && value, callback_inserted_type_ && callback_inserted = {}, callback_existing_type_ && callback_existing = {}) noexcept; ``` ```cpp template 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. Notes: 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. Statuses: - Any status the key's [`copy`](https://www.unum.cloud/docs/smashtable/cpp/containers.md#copy) returns passes through unchanged. Statuses: - Any status the element's [`copy`](https://www.unum.cloud/docs/smashtable/cpp/containers.md#copy) returns passes through unchanged. ## upsert Atomically upserts an element (insert or update). ```cpp status_t upsert(value_t && value) noexcept; ``` ```cpp template 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. Notes: 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. Statuses: - Any status the element's [`copy`](https://www.unum.cloud/docs/smashtable/cpp/containers.md#copy) returns passes through unchanged. ## update Atomically updates an existing element. ```cpp status_t update(value_t && value) noexcept; ``` ```cpp template 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. Statuses: - [`key_not_found_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#key_not_found_k) The key doesn't exist. Statuses: - [`key_not_found_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#key_not_found_k) Any key is missing. - Any status the element's [`copy`](https://www.unum.cloud/docs/smashtable/cpp/containers.md#copy) returns passes through unchanged. ## * Finds a member __equal__ to the given `comparable`. ```cpp template 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`](https://www.unum.cloud/docs/smashtable/cpp/containers.md#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_comp How this store orders its keys, so a bounded walk can stop without guessing. ```cpp 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. ## smallest Hands `callback_found` the smallest member any committed write left visible. ```cpp template requires ordered_collection status_t smallest( callback_found_type_ && callback_found, callback_missing_type_ && callback_missing = {}) const noexcept; ``` The unbounded case of [`lower_bound`](https://www.unum.cloud/docs/smashtable/cpp/isolation.md#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_smallest Removes the smallest member and hands it over, or reports the store is empty. ```cpp template requires ordered_collection && std::is_copy_constructible_v status_t pop_smallest( callback_found_type_ && callback_found = {}, callback_missing_type_ && callback_missing = {}) noexcept; ``` Statuses: - [`key_not_found_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#key_not_found_k) Nothing was there, so emptiness needs no second probe. ## lower_*_bound Finds the first member __greater__ or equal to the given `comparable`. ```cpp template requires ordered_collection 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`](https://www.unum.cloud/docs/smashtable/cpp/containers.md#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 Finds all elements equal to a single key. ```cpp template 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`](https://www.unum.cloud/docs/smashtable/cpp/containers.md#value_t) and convertible to `identifier_t`. - `callback` (in): Callback invoked for each element equal to the key. Must be `noexcept`. Notes: A callback answering `[walk_control_t](#walk_control_t)` stops the walk where it says to. ## for_*_each Hands `callback` every element the store shows, in the order the core holds them. ```cpp template 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`](https://www.unum.cloud/docs/smashtable/cpp/isolation.md#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`. Notes: A callback answering `[walk_control_t](#walk_control_t)` stops the walk where it says to. ## range Hands `callback` every visible member of [ `lower`, `upper` ), or fewer if it halts. ```cpp template requires ordered_collection status_t range( lower_type_ && lower, upper_type_ && upper, callback_type_ && callback = {}) const noexcept; ``` ```cpp template requires ordered_collection 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_range Hands `callback` the mapped half of every visible element in [ `lower`, `upper` ). ```cpp template requires is_mapping && ordered_collection 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`. ## erase_range Retires every published version ordered in [ `lower`, `upper`), handing each to `callback`. ```cpp template requires ordered_collection status_t erase_range( lower_type_ && lower, upper_type_ && upper, callback_type_ && callback = {}) noexcept; ``` ## erase_from Retires every published version ordered at or after `lower`, with no upper bound. ```cpp template requires ordered_collection 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`. ## erase_up_to Retires every published version ordered before `upper`, with no lower bound at all. ```cpp template requires ordered_collection 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`. ## vacuum Frees every entry no reader can reach: a committed tombstone with nothing staged. ```cpp expected vacuum() noexcept; ``` ```cpp template requires ordered_collection expected 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. ## select Finds the `ordinal` -th smallest visible, committed element, counting from zero. ```cpp template requires supports_order_statistics 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`. ## rank Finds the rank (position) of an element among visible (committed) elements. ```cpp template requires supports_order_statistics 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`](https://www.unum.cloud/docs/smashtable/cpp/containers.md#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`. ## * Erases a single entry matching the given `comparable`. ```cpp template status_t erase( comparable_type_ && comparable, callback_found_type_ && callback_found = {}, callback_missing_type_ && callback_missing = {}) noexcept; ``` - `comparable` (in): Object comparable to [`value_t`](https://www.unum.cloud/docs/smashtable/cpp/containers.md#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`. Notes: Both channels agree: an absent key fires `callback_missing` __and__ reports [`key_not_found_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#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. Statuses: - [`key_not_found_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#key_not_found_k) No visible entry matched. Notes: A committed tombstone is not a match, but it is still reclaimed here - nothing else would reach it, and leaving it behind lets a key erased twice keep its memory forever. ## reserve Asks the core to make room for [`size`](https://www.unum.cloud/docs/smashtable/cpp/isolation.md#size) more entries. ```cpp 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`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#out_of_memory_heap_k). - `size` (in): How many more entries to make room for. ## clear Removes all elements from the tree, refusing while any transaction has staged work. ```cpp status_t clear() noexcept; ``` Notes: 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. Statuses: - [`operation_not_permitted_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#operation_not_permitted_k) A staged version would be dropped from under the transaction that is about to publish it. ## print Debug utility to print tree contents. ```cpp template requires ordered_collection void print(stream_type_ & stream); ``` Templated on the sink so the header never pulls in a stream of its own. ## make Factory method to create a new transactional binary tree without throwing exceptions. ```cpp expected make(allocator_t const & allocator = {}) noexcept; ``` ```cpp expected 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. ## transaction_t A transaction that buffers writes, stages them invisibly and publishes them in one commit. ```cpp class transaction_t ``` ## reference_store Transactional set providing 2-phase commit and watch/CAS at Monotonic Atomic View. ```cpp template > class reference_store ``` Built on `std::set` as a baseline reference implementation. Not thread-safe by itself. #### Design Goals 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](https://www.unum.cloud/docs/smashtable/cpp/isolation.md#isolation_t)` names and so also gives "Read Committed". Transactions cannot observe writes from other uncommitted transactions. #### API Overview - All lookups are heterogeneous: you can provide any type comparable to `value_type_`. Your comparator must define `using is_transparent = void;` to enable it, as `std::map` and `std::set` both do. - No iterators are provided to keep the implementation simple and avoid the complexity of maintaining persistent iterator validity across transactions and modifications. - All operations use callback-based APIs for consistency and exception safety via `noexcept` wrappers, avoiding raw pointers. #### Insert Strategies 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`](https://www.unum.cloud/docs/smashtable/cpp/isolation.md#upsert) method is an alias for [`insert_or_assign`](https://www.unum.cloud/docs/smashtable/cpp/isolation.md#insert_or_assign), following a more DBMS-like naming convention. The [`try_emplace`](#try_emplace) is deleted in favor of the more explicit [`insert_if_missing`](https://www.unum.cloud/docs/smashtable/cpp/isolation.md#insert_if_missing). #### Requirements #### Element Type - Nothrow default-constructible and nothrow move constructible/assignable, required - For watch operations: Nothrow copy-constructible OR provides `.copy() const->expected` for safe copying of identifiers. #### Comparator Type - Must define `bool operator()(value_type const &, value_type const &) const` - For heterogeneous lookups: add `using is_transparent = void;` and `using value_type = ...;`, optional but recommended. #### Allocator Type - Must be "rebindable" for internal structures, which are `std::set` nodes and `std::vector` arrays - Standard allocator propagation traits respected for move/copy operations See also: [https://jepsen.io/consistency/models/monotonic-atomic-view](https://jepsen.io/consistency/models/monotonic-atomic-view) See also: [https://jepsen.io/consistency/models/read-committed](https://jepsen.io/consistency/models/read-committed) ## store_t What this store calls itself, so generic code spells an engine and a wrapper alike. ```cpp using store_t = reference_store; ``` ## isolation_k A commit publishes every staged version before any reader can run, and takes no snapshot. ```cpp isolation_t isolation_k; ``` ## reference_store Seeds the comparator, which an instance carrying state or a dispatch pointer needs. ```cpp reference_store(); ``` ```cpp reference_store(comparator_t const & comparator); ``` Seeds the comparator, which an instance carrying state or a dispatch pointer needs. ```cpp reference_store(reference_store const &)=delete; ``` ```cpp reference_store(reference_store &&) noexcept=default; ``` ## operator= ```cpp reference_store & operator=(reference_store const &)=delete; ``` ```cpp reference_store & operator=(reference_store &&) noexcept=default; ``` ## size Returns the number of visible (committed) non-deleted elements in the container. ```cpp std::size_t size() const noexcept; ``` ## empty Checks if the container has no visible elements. ```cpp bool empty() const noexcept; ``` ## transaction Creates a new transaction with a fresh generation number, resettable and reusable after commit or rollback to avoid reallocations. ```cpp expected transaction() noexcept; ``` Returns an error on allocation failure. ## insert Atomically inserts an element, refusing the key that is already there. ```cpp template 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`. Statuses: - [`key_already_exists_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#key_already_exists_k) The key is taken. ## insert_if_missing Atomically inserts an element, leaving the key that is already there untouched. ```cpp template status_t insert_if_missing( value_t && element, callback_inserted_type_ && callback_inserted = {}, callback_existing_type_ && callback_existing = {}) noexcept; ``` ```cpp template 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. Statuses: - Any status the element's or the key's [`copy`](https://www.unum.cloud/docs/smashtable/cpp/containers.md#copy) returns passes through unchanged. ## insert_or_assign Atomically writes an element, taking the key whether or not it was there. ```cpp template status_t insert_or_assign( value_t && element, callback_inserted_type_ && callback_inserted = {}, callback_existing_type_ && callback_existing = {}) noexcept; ``` ```cpp template 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. ## upsert Alias for `insert_or_assign()`. ```cpp status_t upsert(value_t && element) noexcept; ``` ```cpp template 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. ## update Atomically writes an element, refusing a key that is not already there. ```cpp status_t update(value_t && element) noexcept; ``` ```cpp template 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. Statuses: - [`key_not_found_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#key_not_found_k) The key is missing. Statuses: - [`key_not_found_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#key_not_found_k) Any key is absent. - Any status the key's [`copy`](https://www.unum.cloud/docs/smashtable/cpp/containers.md#copy) returns passes through unchanged. ## try_emplace Deleted, use `insert_if_missing()` instead. ```cpp template 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_copy Copies out the member equal to `comparable`, for callers that cannot use a callback. ```cpp template expected find_copy( comparable_type_ && comparable) const noexcept; ``` - `comparable` (in): Object comparable to [`value_t`](https://www.unum.cloud/docs/smashtable/cpp/containers.md#value_t) and convertible to `identifier_t`. Statuses: - [`key_not_found_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#key_not_found_k) No visible member equals `comparable`. - Any status the element's [`copy`](https://www.unum.cloud/docs/smashtable/cpp/containers.md#copy) returns passes through unchanged. ## contains Checks if a member __equal__ to the given `comparable` exists. ```cpp template expected contains(comparable_type_ && comparable) const noexcept; ``` Convenience wrapper around `find()` for existence checks. - `comparable` (in): Object comparable to [`value_t`](https://www.unum.cloud/docs/smashtable/cpp/containers.md#value_t) and convertible to `identifier_t`. ## upper_bound Finds the first member __greater__ than the given `comparable`. ```cpp template status_t upper_bound( comparable_type_ && comparable, callback_found_type_ && callback_found, callback_missing_type_ && callback_missing = {}) const noexcept; ``` - `comparable` (in): Object comparable to [`value_t`](https://www.unum.cloud/docs/smashtable/cpp/containers.md#value_t) and convertible to `identifier_t`. - `callback_found` (in): Callback to receive an [`value_t`](https://www.unum.cloud/docs/smashtable/cpp/containers.md#value_t) const &. Must be `noexcept`. - `callback_missing` (in): Callback triggered if nothing was found. Must be `noexcept`. ## lower_bound_copy Copies out the first visible element ordered at or after `comparable`. ```cpp template expected lower_bound_copy( comparable_type_ && comparable) const noexcept; ``` Statuses: - [`key_not_found_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#key_not_found_k) No visible element orders at or after `comparable`. - Any status the element's [`copy`](https://www.unum.cloud/docs/smashtable/cpp/containers.md#copy) returns passes through unchanged. ## upper_bound_copy Copies out the first visible element ordered strictly after `comparable`. ```cpp template expected upper_bound_copy( comparable_type_ && comparable) const noexcept; ``` Statuses: - [`key_not_found_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#key_not_found_k) No visible element orders after `comparable`. - Any status the element's [`copy`](https://www.unum.cloud/docs/smashtable/cpp/containers.md#copy) returns passes through unchanged. ## select Hands `callback_found` the zero-based `ordinal` -th smallest visible element. ```cpp template 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`. ## rank Hands `callback_found` how many visible elements the store orders before `comparable`. ```cpp template 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`](https://www.unum.cloud/docs/smashtable/cpp/containers.md#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`. ## range Iterates over all entries in the range [ `lower`, `upper`). ```cpp template 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`. Notes: A callback answering `[walk_control_t](#walk_control_t)` stops the walk where it says to. ## update_range Hands `callback` each visible member of [ `lower`, `upper` ) to revise and stamp. ```cpp template requires is_mapping 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`. ## erase_range Erases all the entries falling in between the `lower` and the `upper`. ```cpp template 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`. ## erase_from Erases every entry ordered at or after `lower`, with no upper bound at all. ```cpp template 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`. ## erase_up_to Erases every entry ordered before `upper`, with no lower bound at all. ```cpp template 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`. ## clear Removes every element, refusing while any transaction has something staged. ```cpp status_t clear() noexcept; ``` Notes: 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. Statuses: - [`operation_not_permitted_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#operation_not_permitted_k) A staged version would be dropped. ## reserve Accepts a capacity hint and does nothing with it. ```cpp 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. ## vacuum Frees every entry no reader can reach. ```cpp expected vacuum() noexcept; ``` ```cpp template expected 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_one Draws one visible entry uniformly from [ `lower`, `upper`), handing it to `callback`. ```cpp template requires uniform_random_bits> 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_reservoir Reservoir-samples entries from [ `lower`, `upper`), filling a reservoir buffer with up to `reservoir_capacity` randomly selected elements. ```cpp template output_iterator_type_> requires uniform_random_bits> 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. ## make Builds a store around a specific comparator, for comparators that carry state. ```cpp expected make(comparator_t const & comparator) noexcept; ``` ```cpp expected make() noexcept; ``` Factory method to create a new transactional set without throwing exceptions. Returns error status on allocation failure. ## transaction_t A transaction that buffers writes, stages them invisibly and publishes them in one commit. ```cpp class transaction_t ``` ## transaction_group A two-phase commit over several stores at once. ```cpp template class transaction_group ``` Stores 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_t The order the first participant was built into, or `[no_order_t](#no_order_t)` where it keeps no stamps. ```cpp using order_t = typename order_of>>::type; ``` ## claim_t The claim every participant reads under where they share an order, and nothing where they do not. ```cpp using claim_t = typename order_t::snapshot_claim_t; ``` ## shares_one_order_k Whether every participant was built into one order, so the group can stamp all of them once. ```cpp bool shares_one_order_k; ``` ## asks_before_writing_k Whether this group asks every participant before letting any of them write. ```cpp 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_group ```cpp transaction_group(transaction_group &&) noexcept=default; ``` ```cpp transaction_group(transaction_group const &)=delete; ``` ## operator= ```cpp transaction_group & operator=(transaction_group &&) noexcept=default; ``` ```cpp transaction_group & operator=(transaction_group const &)=delete; ``` ## participant This group's participant in `store_index_`, counted in the caller's argument order. ```cpp template auto & participant() noexcept; ``` ## participants Every participant at once, in the order the caller named their stores, for binding with `auto [a, b] =`. ```cpp auto participants() noexcept; ``` ## commit_with Runs `body` over the participants, then stages and commits the group. ```cpp template 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`](#commit_with_retries) takes a conflict as a reason to try again. - `body` (in): Invoked as `body(participants...)`, answering a `[status_t](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#status_t)`. Must be `noexcept`. Statuses: - [`operation_not_permitted_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#operation_not_permitted_k) The group was already staged. - Any status `body` returns, or a participant refuses the stage or the commit with, passes through unchanged. ## commit_stamp The stamp the last commit published every participant under, or zero where each stamped its own. ```cpp generation_t commit_stamp() const noexcept; ``` ## commit Publishes the participants, drawing each one's commit stamp. ```cpp status_t commit() noexcept; ``` Where [`asks_before_writing_k`](#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`](#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`](#commit) and [`rollback`](#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`](#reset) then clears the rest. Where [`shares_one_order_k`](#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. Statuses: - [`operation_not_permitted_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#operation_not_permitted_k) The group is not staged. - Any status a participant refuses its validation or its commit with passes through unchanged. ## reset Discards every participant's staged and pending changes, at one fresh snapshot where they share an order. ```cpp status_t reset() noexcept; ``` ## make Opens one transaction per store, or none at all. ```cpp expected 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. Statuses: - [`invalid_argument_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#invalid_argument_k) One store is named twice, or stores meant to share one order are built into different orders. - Any status a store in `stores` refuses its transaction with passes through unchanged, the first in argument order winning, and every transaction opened goes to its destructor. ## conflicted Whether [`status`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#status) turned a transaction away over what another one published, which a retry can overcome. ```cpp bool conflicted(status_t status) noexcept; ``` ## stage_each Hands `stage_one` every element of [ `first`, `last` ), duplicated outside the target. ```cpp template 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`](https://www.unum.cloud/docs/smashtable/cpp/stored-types.md#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`. Statuses: - Any status an element's [`copy`](https://www.unum.cloud/docs/smashtable/cpp/containers.md#copy) or `stage_one` returns passes through unchanged. ## hand_over Hands `args` to `callback` and answers whether the walk carries on. ```cpp template 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_watch What a watch on a key with no entry at all records. ```cpp 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`](https://www.unum.cloud/docs/smashtable/cpp/isolation.md#vacuum), [`clear`](https://www.unum.cloud/docs/smashtable/cpp/isolation.md#clear) and the ranged erases reclaim one a watch may still hold. Neither `[monotonic_store](#monotonic_store)` nor `[reference_store](#reference_store)` pins reclamation behind an open reader the way `[snapshot_store](https://www.unum.cloud/docs/smashtable/cpp/isolation.md#snapshot_store)` does. Warnings: 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_of The watch a read resolving to `resolved` should record, or [`missing_watch`](#missing_watch) when it resolves to nothing at all. ```cpp template 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_drifted Whether a watched key moved between `recorded` and what it resolves to `now`. ```cpp 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_watches Re-reads every watched identifier and reports whether any drifted since it was sampled. ```cpp template 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`. Statuses: - [`read_conflict_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#read_conflict_k) A watch drifted since it was sampled. ## holds Whether `mask` carries `flag`, spelled out because a scoped enum has no `operator&`. ```cpp 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. ```cpp access_t operator|(access_t first, access_t second) noexcept; ``` ## identifier_of The identifier a version-decorated object is addressed by, with the metadata peeled off. ```cpp template 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_retries Stages `stage_changes` into [`transaction`](https://www.unum.cloud/docs/smashtable/cpp/isolation.md#transaction) and commits it, at most `attempts` times. ```cpp template 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`. Warnings: A transaction opened at an older snapshot, such as one adopting a reader's, reads at the newest one from its second attempt on. Statuses: - [`operation_would_block_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#operation_would_block_k) Every attempt met a conflict, or `attempts` is zero. - Any status but a conflict that `stage_changes` or [`transaction`](https://www.unum.cloud/docs/smashtable/cpp/isolation.md#transaction) returns passes through unchanged. ## make_transaction_group Deduces the store types, so a caller names the stores and not their spellings. ```cpp template expected> make_transaction_group( store_types_ &... stores) noexcept; ``` ## halts_the_walk Whether `callback_type_` can stop a walk, rather than taking every element offered. ```cpp bool halts_the_walk; ``` A callback answering `[walk_control_t](#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.