# Isolation > SmashTable for C++ `#include ` `#include ` `#include ` `#include ` ## opened_at_t Where a transaction opens: the snapshot it reads, and the generation dating its versions. ```cpp struct opened_at_t ``` One struct rather than two parameters, because both are `generation_t` and a caller swapping them compiles today. Named members make the swap ill-formed wherever a designated initializer spells them, since the language requires those in declaration order. - `snapshot` `generation_t`: The stamp every read under this transaction is answered at. - `generation` `generation_t`: The stamp dating the versions it stages, which orders nothing anyone else sees. ## isolation_t What a reader is promised, named as Jepsen names it and ordered by strength. ```cpp enum isolation_t ``` The top two differ only in when a commit becomes visible, never in what they refuse: both validate every read, so neither admits write skew or a phantom. [`strict_serializable_k`](#strict_serializable_k) additionally waits for its own publication before returning, so a transaction opening after a commit returned cannot be ordered before it. A transaction commit waits at both levels, so the difference reaches only a sharded commit and a write made outside a transaction. - `read_committed_k` = `0` - `monotonic_atomic_view_k` = `1` - `snapshot_k` = `2` - `serializable_k` = `3` - `strict_serializable_k` = `4` See also: [https://jepsen.io/consistency](https://jepsen.io/consistency) ## versioning_for Decorates a value type with generation and visibility metadata for transactional containers. ```cpp template struct versioning_for ``` #### Template Requirements - `value_type_` must be a value type (no references), nothrow default-constructible, and nothrow move constructible/assignable so that transactional staging can remain noexcept. - `comparator_type_` must expose `value_type` describing the identifier used for ordering, and that identifier type must be nothrow copy-constructible to support watch bookkeeping. - `value_type_` must be convertible to the identifier type and constructible from it, enabling the containers to extract keys for lookups and manufacture key-only tombstones for erases. ## per_version_equals Compares version-decorated objects by identifier __and__ generation, so versions do not collapse. ```cpp template struct per_version_equals ``` A bare key matches every version of that key - which is what a visibility walk asks - while a dated identifier matches exactly one, which is what a commit asks. Paired with `[per_key_hasher](https://www.unum.cloud/docs/smashtable/cpp/transactions.md#per_key_hasher)`, which keeps peeling to the bare key so every version of a key shares one probe run; only equality widens. The ordered core needs no counterpart, since `versioned_comparator_t::less` already routes to `per_version_compare` when both operands carry a date. - `equals` `equals_type_`: The equality this wrapper was built with, consulted for every comparison. ## bare_waiting_policy_t The policy a spin takes when nobody names one: no instruction at all between attempts. ```cpp struct bare_waiting_policy_t ``` Leaves a spin the bare retry loop it reads as, which is the one choice needing neither an architecture nor a runtime probe, and the only one that compiles for every target this header reaches, a device included. A deployment that knows what its cores are names a policy stalling them properly - `PAUSE`, `YIELD`, `UMWAIT`, `WFET` - and one that does not pays nothing. ## spin_shared_mutex A reader-writer lock that spins briefly, then parks. ```cpp template waiting_policy_type_ = standard_waiting_policy_t, template class atomic_reference_ = atomic_ref> class spin_shared_mutex ``` Both acquires are bounded adds rather than compare-exchange loops, which is what the word's layout buys: every writer bit sits above the reader tally, so _no_ _writer_ _here_ and _room_ _for_ _one_ _more_ _reader_ is the single question does the sum stay inside the tally. A reference satisfying `extended_atomic_ref` answers it in one instruction and, when the answer is no, without taking the line at all; `atomic_ref` answers it with the loop that question replaces. Dropping the held bit reads nothing back, so it is posted rather than waited on. Releasing a reader is the one path that cannot be either, since the count it returns is what tells the last reader out to wake a writer. Locks here are held across user code - callbacks, comparators, allocators, a whole commit loop - so a pure spinner would burn a core while a holder walks a range, and pure parking would pay a syscall for the uncontended case that dominates. Waiting writers are counted, and a non-zero count turns new readers away, so a steady read load cannot starve any of them indefinitely. Offers exactly what `std::shared_mutex` is used for here, and nothing else: no recursion, no timed acquisition, no upgrading. ## unique_lock Holds `mutex_type_` exclusively for the enclosing scope, or for as long as whoever it is moved into keeps it; an empty one holds nothing, so a hold can outlive one call. ```cpp template class unique_lock ``` ## shared_lock Holds `mutex_type_` for shared reading over the enclosing scope. ```cpp template class shared_lock ``` ## order_sharing_t Whether an order is reached from several threads, which decides both its atomics and its padding. ```cpp enum order_sharing_t ``` - `solitary_k`: One thread, so every word is plain and nothing is padded apart from the object itself. - `shared_k`: Several threads, so every word moves atomically and the contended ones own a cache line. ## liveness_t Whether an entry is the newest committed-and-present version of its key, as of right now. ```cpp enum liveness_t ``` - `superseded_k`: Something newer speaks for the key, or this entry says the key was taken away. - `survivor_k`: This is the version the newest published stamp reads for the key. ## live_tagged A stored version carrying the one bit an order-statistic descent reads off the entry. ```cpp template struct live_tagged ``` A rotation recomputes a subtree sum at a moment nobody chose, so the predicate the sum is kept over has to be answerable from the entry alone rather than from the store around it. - `liveness` `liveness_t`: Whether this entry is the one the newest published stamp reads for its key. ## liveness_augmentation_t Counts one entry per key the newest published stamp reads, for the tree to sum per subtree. ```cpp struct liveness_augmentation_t ``` Answers zero for an undecorated element, which is what the bare core rebinds from holds. ## locked_store Wraps and protects any transactional store under a shared mutex. ```cpp template > class locked_store ``` The store becomes __thread-safe__; a single transaction does __not__ - it belongs to the thread that opened it, and its staged changes live outside the mutex entirely. The rule is one line and holds for every entry point, present and future: a call takes the lock exactly when it reaches the wrapped store, shared where it only reads that store and exclusive where it writes to it, and a call answered from the transaction's own staged state takes no lock at all. One mutex means one commit in flight, so the order this store makes for itself is sized for exactly that, and the wrapped store is rebound to whichever order this one is a member of. [`stage`](https://www.unum.cloud/docs/smashtable/cpp/transactions.md#stage) and [`commit`](https://www.unum.cloud/docs/smashtable/cpp/transactions.md#commit) take the mutex separately and drop it in between, so the lock is not what spans them. The store-side reservation is: staging claims every key the transaction wrote, and no other transaction can take those keys until this one publishes or unwinds, which is what carries the inner store's isolation level across the gap. A value's destructor also runs under the mutex wherever the store displaces or reclaims what it holds, so a value whose teardown can re-enter must record the drop and perform it afterwards. Warnings: Every callback runs with the mutex held, and it is not recursive, so a callback that calls back into this store - or into anything that eventually does - deadlocks against itself. Copy out what a callback needs and do the rest after it returns. Warnings: Moving a store leaves every open transaction pointing at the husk, whose contents are empty and whose mutex guards nothing, so commits land nowhere and report success. Move only a store no transaction is open on and no other thread is touching. ## rebind_order The same store in another order, which is how a shard set builds its partitions into its own. ```cpp template using rebind_order = locked_store; ``` ## isolation_k The staging reservation carries the inner store's promise over, not the mutex; see the class note. ```cpp isolation_t isolation_k; ``` ## inner_transaction_shards_k Whether the wrapped transaction can be driven as one part of a commit under a stamp drawn elsewhere. ```cpp bool inner_transaction_shards_k; ``` ## inner_transaction_splits_commit_k Whether the wrapped transaction decides and writes in two steps rather than one. ```cpp bool inner_transaction_splits_commit_k; ``` ## locked_store Builds a store that is a member of [`order`](#order) rather than of one it made for itself. ```cpp locked_store() noexcept; ``` ```cpp locked_store(order_t & order) noexcept; ``` Builds a store that is a member of [`order`](#order) rather than of one it made for itself. ```cpp locked_store(locked_store && other) noexcept; ``` Warnings: `other` must be untouched: no open transaction, no other thread; see class notes. ## join_order Makes this store, and the store it wraps, a member of [`order`](#order). ```cpp void join_order(order_t & order) noexcept; ``` Called once, by the wrapper that owns both, before any transaction opens. A shard set seats every partition this way, which is what makes one stamp mean the same thing across them. ## size How many entries the store holds, read under the shared lock. ```cpp std::size_t size() const noexcept; ``` ## empty Whether the store holds no entries, read under the shared lock. ```cpp bool empty() const noexcept; ``` ## transaction Opens a transaction over the wrapped store. ```cpp expected transaction() noexcept; ``` ## upsert Inserts or overwrites `element` in one locked write. ```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; ``` Inserts or overwrites every element of a range in one locked write. ## erase Erases whatever equals `comparable`, reporting through the callbacks so presence needs no second probe. ```cpp template status_t erase( comparable_type_ && comparable, callback_found_type_ && callback_found = {}, callback_missing_type_ && callback_missing = {}) noexcept; ``` Takes any type the inner store compares against, not only an identifier. ## insert_if_missing Inserts `element` only if its key is absent, leaving an incumbent untouched. ```cpp status_t insert_if_missing(value_t && element) noexcept; ``` ```cpp template status_t insert_if_missing( value_t && element, callback_inserted_type_ && callback_inserted, callback_existing_type_ && callback_existing) noexcept; ``` Inserts `element` only if its key is absent, and says which branch was taken. ```cpp template elements_end_type_ = elements_begin_type_> status_t insert_if_missing( elements_begin_type_ begin, elements_end_type_ end) noexcept; ``` Inherits the inner store's all-or-nothing batch, held under this store's write lock throughout. - `callback_inserted` (in): Receives the element once stored. - `callback_existing` (in): Receives the element present, which declined the insert. ## insert Inserts `element` only if its key is free, refusing with the inner store's own status. ```cpp requires offers_insert status_t insert(value_t && element) noexcept; ``` ```cpp template requires offers_insert_naming_occupant status_t insert( value_t && element, callback_inserted_type_ && callback_inserted, callback_existing_type_ && callback_existing) noexcept; ``` Inserts `element` only if its key is free, and says which branch was taken. - `callback_inserted` (in): Receives the element once stored. - `callback_existing` (in): Receives the already-present element that refused the insert. ## update Writes `element` only if its key is already taken, refusing to create one. ```cpp requires offers_update status_t update(value_t && element) noexcept; ``` ## find Looks `comparable` up, under the shared lock. ```cpp template status_t find( comparable_type_ && comparable, callback_found_type_ && callback_found, callback_missing_type_ && callback_missing = {}) const noexcept; ``` ## contains Existence check, expressed through [`find`](#find) so the lock discipline stays in one place. ```cpp template expected contains(comparable_type_ && comparable) const noexcept; ``` ## * Number of elements matching `comparable`, which is 0 or 1 for unique keys. ```cpp template expected count( comparable_type_ && comparable) const noexcept; ``` ## lower_bound Finds the first key not ordered before `comparable`, under the shared lock. ```cpp template requires offers_lower_bound status_t lower_bound( comparable_type_ && comparable, callback_found_type_ && callback_found, callback_missing_type_ && callback_missing = {}) const noexcept; ``` ## * A walk of every member in ascending order, resumable and holding no lock between steps. ```cpp requires offers_both_bounds && offers_smallest ordered_cursor_t cursor() const noexcept; ``` ## cursor_*_from The same walk, begun at the first member ordered at or after `from`. ```cpp requires offers_both_bounds ordered_cursor_t cursor__from(identifier_t from) const noexcept; ``` ## cursor_up_*_up_to The same walk, stopping before `upper`. ```cpp requires offers_both_bounds && offers_smallest ordered_cursor_t cursor_up__up_to(identifier_t upper) const noexcept; ``` ## cursor_*_range The same walk over [ `from`, `upper` ). ```cpp requires offers_both_bounds ordered_cursor_t cursor__range( identifier_t from, identifier_t upper) const noexcept; ``` ## smallest Hands `callback_found` the smallest member, or reports the store is empty. ```cpp template requires offers_smallest status_t smallest( callback_found_type_ && callback_found, callback_missing_type_ && callback_missing = {}) const noexcept; ``` ## pop_smallest Removes the smallest member and hands it over, or reports the store is empty. ```cpp template requires offers_pop_smallest status_t pop_smallest( callback_found_type_ && callback_found = {}, callback_missing_type_ && callback_missing = {}) noexcept; ``` The choice and the removal happen under one exclusive hold, so no writer can slip in between. ## pop_smallest_*_smallest_copy Copies out the smallest member and removes it, or reports [`key_not_found_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#key_not_found_k). ```cpp requires offers_pop_smallest expected pop_smallest__smallest_copy() noexcept; ``` ## smallest_*_copy Copies out the smallest member, or reports [`key_not_found_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#key_not_found_k). ```cpp requires offers_smallest expected smallest__copy() const noexcept; ``` ## find_*_copy Copies out the member equal to `comparable`, or reports [`key_not_found_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#key_not_found_k). ```cpp template expected find__copy( comparable_type_ && comparable) const noexcept; ``` ## lower_bound_*_bound_copy Copies out the first element ordered at or after `comparable`. ```cpp template requires offers_lower_bound expected lower_bound__bound_copy( comparable_type_ && comparable) const noexcept; ``` ## upper_bound_*_bound_copy Copies out the first element ordered strictly after `comparable`. ```cpp template requires offers_upper_bound expected upper_bound__bound_copy( comparable_type_ && comparable) const noexcept; ``` ## upper_bound Finds the first key after `comparable`, under the shared lock. ```cpp template requires offers_upper_bound status_t upper_bound( comparable_type_ && comparable, callback_found_type_ && callback_found, callback_missing_type_ && callback_missing = {}) const noexcept; ``` ## range Hands `callback` every member of [ `lower`, `upper` ), one shared lock held. ```cpp template requires offers_range status_t range( lower_type_ && lower, upper_type_ && upper, callback_type_ && callback) const noexcept; ``` ```cpp template requires offers_descending_range status_t range( from_type_ const & from, until_type_ const & until, callback_type_ && callback, descending_t) const noexcept; ``` Hands `callback` every member of ( `until`, `from` ] greatest first. Notes: A callback answering `[walk_control_t](https://www.unum.cloud/docs/smashtable/cpp/transactions.md#walk_control_t)` stops the walk where it says to. ## erase_range Erases the keys between `lower` and `upper` as the wrapped store bounds them, in one locked write. ```cpp template requires offers_erase_range status_t erase_range( lower_type_ && lower, upper_type_ && upper, callback_type_ && callback = {}) noexcept; ``` ## erase_from Erases every element at or after `lower`, reporting each to `callback`. ```cpp template requires offers_erase_from status_t erase_from( lower_type_ && lower, callback_type_ && callback = {}) noexcept; ``` ## erase_up_to Erases every element before `upper`, reporting each to `callback`. ```cpp template requires offers_erase_up_to status_t erase_up_to( upper_type_ && upper, callback_type_ && callback = {}) noexcept; ``` ## update_range Rewrites the mapped side of every element in [ `lower`, `upper` ). ```cpp template requires offers_update_range 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 (key const &, mapped &) per element. Must be `noexcept`. ## for_each Hands `callback` every member the store holds, in whatever order it keeps them. ```cpp template requires offers_for_each status_t for_each(callback_type_ && callback) const noexcept; ``` The one walk an unordered core can offer, and the whole of it runs under one shared lock, so a writer is held off for its length and the enumeration is a consistent snapshot: every element present when the call began is visited exactly once, and no element inserted during it is seen. Notes: A callback answering `[walk_control_t](https://www.unum.cloud/docs/smashtable/cpp/transactions.md#walk_control_t)` stops the walk where it says to, which also ends the shared hold early. ## vacuum Frees every version no reader can still reach. ```cpp requires offers_vacuum expected vacuum() noexcept; ``` ```cpp template requires offers_vacuum_window expected vacuum( lower_type_ && lower, upper_type_ && upper) noexcept; ``` Frees the unreachable versions of every key in [ `lower`, `upper` ), so a caller can step through the keyspace instead of paying for one pass over all of it. ## select Hands `callback_found` the element at zero-based position `ordinal`. ```cpp template requires offers_select status_t select( std::size_t ordinal, callback_found_type_ && callback_found, callback_missing_type_ && callback_missing = {}) const noexcept; ``` - `ordinal` (in): Zero-based position among the visible elements. - `callback_found` (in): Callback to receive a [`value_t`](https://www.unum.cloud/docs/smashtable/cpp/containers.md#value_t) const &. Must be `noexcept`. - `callback_missing` (in): Fires when fewer elements are there. Must be `noexcept`. ## * Hands `callback_found` how many elements the store orders before `comparable`. ```cpp template requires offers_rank status_t rank( comparable_type_ && comparable, callback_found_type_ && callback_found, callback_missing_type_ && callback_missing = {}) const noexcept; ``` Counted by the same merge [`select`](#select) walks, so it costs the rank rather than a descent. - `comparable` (in): Any key comparable with stored entries. - `callback_found` (in): Callback to receive a `std::size_t`. Must be `noexcept`. - `callback_missing` (in): Fires when `comparable` is not there at all. Must be `noexcept`. ## clear Erases every entry, under the exclusive lock. ```cpp status_t clear() noexcept; ``` ## reserve Reserves room for [`size`](#size) entries in the wrapped store. ```cpp status_t reserve(std::size_t size) noexcept; ``` ## sample_one Draws one entry between `lower` and `upper` with `generator`, under the shared lock. ```cpp template requires offers_sample_one && uniform_random_bits> status_t sample_one( lower_type_ && lower, upper_type_ && upper, generator_type_ && generator, callback_type_ && callback) const noexcept; ``` ## sample_reservoir Samples entries between `lower` and `upper` into `reservoir`, under the shared lock. ```cpp template output_iterator_type_> requires offers_sample_reservoir && 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; ``` ## equal_range Hands `callback` every member equal to `comparable`, which for a unique-key store is one or none. ```cpp template requires offers_equal_range status_t equal_range( comparable_type_ && comparable, callback_type_ && callback) const noexcept; ``` Notes: A callback answering `[walk_control_t](https://www.unum.cloud/docs/smashtable/cpp/transactions.md#walk_control_t)` stops the walk where it says to. ## ranked_size How many keys the ordinal surface indexes, which is what [`select`](#select) counts against. ```cpp requires offers_ranked_size std::size_t ranked_size() const noexcept; ``` ## versions_count How many versions the store holds across every key, published and staged alike. ```cpp requires offers_versions_count std::size_t versions_count() const noexcept; ``` ```cpp template requires offers_versions_count std::size_t versions_count( comparable_type_ const & comparable) const noexcept; ``` How many versions of `comparable` the store still holds. ## low_water_*_water_mark The newest snapshot no open transaction sits below, which is what [`vacuum`](#vacuum) prunes to. ```cpp requires offers_low_water_mark generation_t low_water__water_mark() const noexcept; ``` The oldest of the partitions' answers, so no partition prunes past a reader another still counts, which for partitions sharing one order is the single answer all of them give. Pruning frees no version committed above it, so a version walk from a stamp at or above the mark misses nothing. Only ever raised, and pruning frees no version committed above it, so every version above a stamp at or above the mark is still held. ## insert_or_assign Writes `element` whether or not its key is taken, spelled as the inner store spells it. ```cpp requires offers_insert_or_assign status_t insert_or_assign(value_t && element) noexcept; ``` ## transaction_at Opens one part of a sharded transaction on [`snapshot`](https://www.unum.cloud/docs/smashtable/cpp/transactions.md#snapshot) and [`generation`](https://www.unum.cloud/docs/smashtable/cpp/transactions.md#generation) drawn elsewhere. ```cpp requires draws_from_a_shared_order expected transaction_at(opened_at_t opened) noexcept; ``` ## order The order the wrapped store is a member of, which is fixed at construction and needs no lock. ```cpp order_t & order() noexcept; ``` ```cpp order_t const & order() const noexcept; ``` The order this store draws stamps from, read-only. ## make Builds the inner store from `arguments` and takes ownership of it. ```cpp template expected make(arguments_type_ &&... arguments) noexcept; ``` Forwards whatever the core needs - a comparator for a tree, a hasher and equality for a table - so a store whose comparator has no default constructor is still constructible. ## transaction_t A transaction over the wrapped store, taking the store's mutex for each call that touches it. ```cpp class transaction_t ``` ## ordered_cursor_t A resumable walk in ascending key order, holding no lock between its steps. ```cpp class ordered_cursor_t ``` The position is a key rather than an iterator, so a write between two steps cannot invalidate it: the next step re-probes from the last key handed over. That is what lets the walk survive concurrent change, and it is why a step costs a lookup, not an increment. ## partitioned_store Hashes inputs to route them into separate sets, which can be concurrent, or have a separate state-full allocator attached. ```cpp template , typename shared_mutex_type_ = spin_shared_mutex_t, std::size_t partitions_count_ = 16> class partitioned_store ``` Every partition is a member of one order, so a stamp means the same thing in each and sixteen partitions embed one order rather than sixteen. As many commits may be in flight as there are partitions to hold disjoint lock sets, and no more, which is what sizes it. The set owns that order, unless it was built into one it shares with other stores, which a `[transaction_group](https://www.unum.cloud/docs/smashtable/cpp/transactions.md#transaction_group)` then commits under one stamp. The walks that revise or erase a window hold every partition at once, while the enumerating and sampling walks hold one at a time, each saying which in its own docblock. Warnings: Every callback runs with at least one partition lock held, and the mutex is not recursive, so a callback that calls back into this store - or into anything that eventually does - deadlocks against itself. Copy out what it needs and do the rest after it returns. Warnings: Moving a store leaves every open transaction pointing at the husk, whose partitions are empty and whose mutexes guard nothing, so commits land nowhere and report success. Move only a store no transaction is open on and no other thread is touching. ## refusal_policy_t What an all-partition walk does with a partition that refuses. ```cpp enum refusal_policy_t ``` - `stop_at_first_k`: The walk returns the first refusal, leaving every partition after it untouched. - `attempt_every_k`: Every partition is attempted whatever its neighbours answered, and the last refusal is reported. - `all_or_nothing_k`: Every partition stages before one stamp publishes them all, so a refusal publishes nothing. ## epoch_t How many times each partition has been written, so a cached read can be told it is stale. ```cpp using epoch_t = std::size_t; ``` ## epoch_counts_t A cursor's own copy of every partition's write count, which it alone reads and so needs no padding. ```cpp using epoch_counts_t = std::array; ``` ## isolation_k A reader takes and releases one partition's lock at a time, so it can catch a commit half-applied however the commit itself was written - unless what a reader sees is decided by a stamp rather than by what happens to be published when it looks. ```cpp isolation_t isolation_k; ``` A part in a shared order is stamped, and one stamp spans every partition of a commit: a reader that fixed its snapshot below that stamp sees none of the commit and one at or above it sees all of it, whatever order the partitions were written in. Such a part keeps its own promise whole. A part deciding visibility any other way is capped at [`read_committed_k`](#read_committed_k), which is the weakest level named and so the floor a cap can reach. ## inner_transaction_splits_commit_k Whether the wrapped transaction decides and writes in two steps rather than one. ```cpp bool inner_transaction_splits_commit_k; ``` ## inner_reads_at_a_stamp_k Whether a partition answers reads at a stamp somebody else pinned, registering nothing itself. ```cpp bool inner_reads_at_a_stamp_k; ``` ## inner_publishes_under_a_stamp_k Whether a partition stages a window's writes invisibly and publishes them under a stamp it is handed, letting one stamp span every partition of a store-level window write. ```cpp bool inner_publishes_under_a_stamp_k; ``` ## inner_transaction_walks_unrecorded_k Whether an open transaction walks reads unrecorded, and records a window on demand, so a merged walk records only the handed-off prefix. ```cpp bool inner_transaction_walks_unrecorded_k; ``` One gate over several methods, unlike the surfaces in `shared.hpp:` a cursor without the watches records nothing a commit can validate, so only the pair is the capability. ## window_writes_policy_k What every store-level window write keeps, which one stamp across the partitions makes whole. ```cpp refusal_policy_t window_writes_policy_k; ``` ## clear_policy_k What a refusal from each all-partition method says about the partitions it skipped. ```cpp refusal_policy_t clear_policy_k; ``` Two behaviours live under one type, and the returned status cannot tell them apart: under [`stop_at_first_k`](#stop_at_first_k) the partitions after the refusal are untouched, while under [`attempt_every_k`](#attempt_every_k) every partition was attempted and an unknown subset applied. Naming the policy per method is what lets a caller — and a test — know which answer it just received. ## partitioned_store Builds an empty store into [`order`](#order), which it shares with every other store built into it, so a `[transaction_group](https://www.unum.cloud/docs/smashtable/cpp/transactions.md#transaction_group)` over them publishes under one stamp. ```cpp partitioned_store() noexcept; ``` ```cpp requires draws_from_a_shared_order partitioned_store(order_t & order) noexcept; ``` Builds an empty store into [`order`](#order), which it shares with every other store built into it, so a `[transaction_group](https://www.unum.cloud/docs/smashtable/cpp/transactions.md#transaction_group)` over them publishes under one stamp. ```cpp partitioned_store(partitioned_store && other) noexcept; ``` Warnings: `other` must have no open transaction and no other thread touching it. ## size How many entries the partitions hold together, read with every partition held shared. ```cpp std::size_t size() const noexcept; ``` ## empty Whether every partition is empty. ```cpp bool empty() const noexcept; ``` ## transaction Opens one transaction per partition, or none at all. ```cpp expected transaction() noexcept; ``` ```cpp requires inner_reads_at_a_stamp_k expected transaction(reader_t const & reader) noexcept; ``` Opens a transaction reading every partition at `reader's` stamp, not the newest one. Each partition is taken exclusively while its transaction is built, since opening one reads the live container and draws a fresh generation from it. ## transaction_at Opens one transaction per partition at a snapshot and a generation a group drew. ```cpp requires draws_from_a_shared_order expected transaction_at(opened_at_t opened) noexcept; ``` Registers nothing: the group's claim pins the snapshot for every store it spans, so the transaction must not outlive the group. ## * Opens a reader pinned at the newest published stamp, which records and settles nothing. ```cpp requires inner_reads_at_a_stamp_k reader_t reader() const noexcept; ``` ## reader_at A reader at `stamp` that registers nothing, for a store sharing its order with the reader or transaction whose claim pins `stamp`, and which it must not outlive. ```cpp requires inner_reads_at_a_stamp_k reader_t reader_at(generation_t stamp) const noexcept; ``` ## order The order this store is a member of, which it owns unless it was built into a shared one. ```cpp requires draws_from_a_shared_order order_t & order() noexcept; ``` ```cpp requires draws_from_a_shared_order order_t const & order() const noexcept; ``` The order every partition draws stamps from, read-only. ## upsert Inserts or overwrites `element` in its partition, under that partition's lock. ```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; ``` Inserts or overwrites every element of a range through one transaction. ## erase Removes one element, reporting whether it was there. ```cpp template status_t erase( comparable_type_ && comparable, callback_found_type_ && callback_found = {}, callback_missing_type_ && callback_missing = {}) noexcept; ``` Touches only the partition that owns the key, so the rest stay unlocked. - `comparable` (in): Anything the inner store compares against, convertible to identifiers. - `callback_found` (in): Receives the element that was removed. - `callback_missing` (in): Fires when no such element existed. Statuses: - [`key_not_found_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#key_not_found_k) The element is absent, so the answer is available without a second probe. - Any other status the owning partition's [`erase`](#erase) returns passes through unchanged. ## partition_of Which partition owns `comparable`, so a bulk writer buckets its rows by partition. ```cpp template std::size_t partition_of( comparable_type_ const & comparable) const noexcept; ``` ## find Looks `comparable` up in its partition, under that partition's shared lock. ```cpp template status_t find( comparable_type_ && comparable, callback_found_type_ && callback_found, callback_missing_type_ && callback_missing = {}) const noexcept; ``` ## contains Whether `comparable` is there, asking only the partition that owns it. ```cpp template expected contains(comparable_type_ && comparable) const noexcept; ``` ## insert_if_missing Inserts one element only if its key is absent, leaving an incumbent untouched. ```cpp status_t insert_if_missing(value_t && element) noexcept; ``` ```cpp template status_t insert_if_missing( value_t && element, callback_inserted_type_ && callback_inserted, callback_existing_type_ && callback_existing) noexcept; ``` Inserts one element, saying which of the two happened rather than leaving it implied. ```cpp template elements_end_type_ = elements_begin_type_> status_t insert_if_missing( elements_begin_type_ begin, elements_end_type_ end) noexcept; ``` Inserts every element of [ [`begin`](https://www.unum.cloud/docs/smashtable/cpp/containers.md#begin), [`end`](https://www.unum.cloud/docs/smashtable/cpp/containers.md#end) ) whose key is free, keeping incumbents. All-or-nothing across every partition the batch reaches: nothing is visible until the commit, and a refusal before it unwinds every reservation the batch took. Writing element by element under a partition lock would publish a prefix another thread could read. - `callback_inserted` (in): Receives the element once stored. - `callback_existing` (in): Receives the element present, which declined the insert. ## insert Inserts one element, refusing with the inner store's own status when the key is taken. ```cpp requires offers_insert status_t insert(value_t && element) noexcept; ``` ```cpp template requires offers_insert_naming_occupant status_t insert( value_t && element, callback_inserted_type_ && callback_inserted, callback_existing_type_ && callback_existing) noexcept; ``` Inserts one element, saying which of the two happened rather than leaving it implied. One key lives in one partition, so the refusal is decided under a single lock and carries the inner store's promise whole. - `callback_inserted` (in): Receives the element once stored. - `callback_existing` (in): Receives the element present, which refused the insert. ## update Writes one element only if its key is already taken, refusing to create one. ```cpp requires offers_update status_t update(value_t && element) noexcept; ``` ## upper_bound The first element ordered strictly after `comparable`, which may live in any partition. ```cpp template requires offers_upper_bound status_t upper_bound( comparable_type_ && comparable, callback_found_type_ && callback_found, callback_missing_type_ && callback_missing = {}) const noexcept; ``` ## smallest The smallest member of the merged order, which may live in any partition. ```cpp template requires offers_both_bounds && (offers_a_merged_walk) status_t smallest( callback_found_type_ && callback_found, callback_missing_type_ && callback_missing = {}) const noexcept; ``` Every partition is held shared for the one answer, so the minimum and the read of it happen at the same moment rather than in two probes a writer can slip between. ## pop_smallest Removes the smallest member of the merged order and hands it over. ```cpp template requires offers_both_bounds && offers_pop_smallest && (offers_a_merged_walk) status_t pop_smallest( callback_found_type_ && callback_found = {}, callback_missing_type_ && callback_missing = {}) noexcept; ``` A pop-heavy workload therefore serializes against every other writer, the one operation here that sharding cannot make cheaper. Warnings: Every partition is held __exclusively__ for the one removal, because the winning partition must not lose its front between being chosen and being popped. ## lower_bound The first element at or after `comparable`, which may live in any partition. ```cpp template requires offers_lower_bound status_t lower_bound( comparable_type_ && comparable, callback_found_type_ && callback_found, callback_missing_type_ && callback_missing = {}) const noexcept; ``` Every partition is asked for its own bound under one set of locks, so the exact match and the cross-partition minimum are read at the same moment rather than in two probes a writer can slip between. ## range Hands `callback` every member of [ `lower`, `upper` ) in one ascending order. ```cpp template requires offers_range status_t range( lower_type_ && lower, upper_type_ && upper, callback_type_ && callback) const noexcept; ``` ```cpp template requires offers_descending_range status_t range( from_type_ const & from, until_type_ const & until, callback_type_ && callback, descending_t) const noexcept; ``` Hands `callback` every member of ( `until`, `from` ] in one descending order, the merge [`range`](#range) runs, greatest first. The partitions are merged rather than concatenated, so the sequence is the one an ordered container promises whatever the key's hash happened to be. Each element costs a comparison per partition and one descent to refill the front it came from, against the single iterator step a concatenated walk would take - the price of the order being right. Notes: A callback answering `[walk_control_t](https://www.unum.cloud/docs/smashtable/cpp/transactions.md#walk_control_t)` stops the walk where it says to. Warnings: Every partition is held shared for the length of the walk, so every writer waits, and `callback` runs under all of them: reaching back into this store deadlocks. Warnings: Every partition is held shared for the length of the walk, as [`range`](#range) holds them. ## erase_range Erases the half-open range from every partition. ```cpp template requires offers_erase_range status_t erase_range( lower_type_ && lower, upper_type_ && upper, callback_type_ && callback = {}) noexcept; ``` Over parts in one order one stamp covers the window, so no reader sees it half-erased. Statuses: - Any status a partition's [`erase_range`](#erase_range) returns passes through as `erase_range_policy_k` scopes it: the first refusal where parts publish under a stamp, publishing nothing, and elsewhere the last, after every partition was tried and an unreported subset erased. ## erase_from Erases every element at or after `lower` from every partition. ```cpp template requires offers_erase_from status_t erase_from( lower_type_ && lower, callback_type_ && callback = {}) noexcept; ``` Statuses: - Any status a partition's [`erase_from`](#erase_from) returns passes through unchanged, scoped by the policy `erase_from_policy_k` exactly as [`erase_range`](#erase_range) scopes its own. ## erase_up_to Erases every element before `upper` from every partition. ```cpp template requires offers_erase_up_to status_t erase_up_to( upper_type_ && upper, callback_type_ && callback = {}) noexcept; ``` Statuses: - Any status a partition's [`erase_up_to`](#erase_up_to) returns passes through unchanged, scoped by the policy `erase_up_to_policy_k` exactly as [`erase_range`](#erase_range) scopes its own. ## update_range Rewrites the mapped side over [ `lower`, `upper` ) in every partition. ```cpp template requires offers_update_range status_t update_range( lower_type_ && lower, upper_type_ && upper, callback_type_ && callback) noexcept; ``` Every partition is held exclusively for the length of the walk, as [`erase_range`](#erase_range) holds them, so the window is revised as one write rather than sixteen; over parts in one order it also goes out under one stamp, so no reader sees it half revised. - `lower` (in): Lower bound (inclusive). - `upper` (in): Upper bound (exclusive). - `callback` (in): Invoked with (key const &, mapped &) per element. Must be `noexcept`. Statuses: - Any status a partition's [`update_range`](#update_range) returns passes through unchanged, scoped by the policy `update_range_policy_k` exactly as [`erase_range`](#erase_range) scopes its own. A partition whose own walk cannot fail always succeeds. ## for_each Hands `callback` every member the store holds, in no particular order. ```cpp template requires offers_for_each status_t for_each(callback_type_ && callback) const noexcept; ``` One partition is locked shared at a time, ascending, as [`sample_reservoir`](#sample_reservoir) takes them - holding all sixteen for the length of an enumeration would stall every writer in the store for as long as the caller takes to consume it. What that buys and what it costs, stated rather than left to be inferred: a key's partition is fixed by its hash and never changes, so an element present in the store for the whole walk is visited __exactly__ __once__ - it cannot be missed by being moved ahead of the cursor, nor seen twice by being moved behind it, and the partition holding it is locked while it is read. An element inserted or erased during the walk __may__ __or__ __may__ __not__ be seen, according to whether its partition had already been visited. The first guarantee is the one a caller enumerating a container depends on; the second is the one it has to tolerate. Notes: A callback answering `[walk_control_t](https://www.unum.cloud/docs/smashtable/cpp/transactions.md#walk_control_t)` stops the walk where it says to, leaving the partitions above the one it stopped in unvisited. ## vacuum Frees every version no reader can still reach, one partition at a time. ```cpp requires offers_vacuum expected vacuum() noexcept; ``` ```cpp template requires offers_vacuum_window expected vacuum( lower_type_ && lower, upper_type_ && upper) noexcept; ``` Frees the unreachable versions of every key in [ `lower`, `upper` ), one partition at a time. Statuses: - Any status a partition's [`vacuum`](#vacuum) returns passes through unchanged. A partition whose sweep cannot refuse always answers with a count. Statuses: - Any status a partition's [`vacuum`](#vacuum) returns passes through unchanged. ## select Hands `callback_found` the element at zero-based `ordinal` in merged order. ```cpp template requires offers_select status_t select( std::size_t ordinal, callback_found_type_ && callback_found, callback_missing_type_ && callback_missing = {}) const noexcept; ``` A partition knows only its own ordinals, so the global one is reached by merging the partitions rather than by descending a subtree count: linear in `ordinal`, not logarithmic in the size. Every partition is held shared for the length of that merge, so the position is answered against one order rather than sixteen probes. - `ordinal` (in): Zero-based position in merged order. - `callback_found` (in): Callback to receive a [`value_t`](https://www.unum.cloud/docs/smashtable/cpp/containers.md#value_t) const &. Must be `noexcept`. - `callback_missing` (in): Fires when fewer elements are there. Must be `noexcept`. ## sample_one Hands one element of the range to `callback`, drawn from a single random partition. ```cpp template requires offers_sample_one && uniform_random_bits> status_t sample_one( lower_type_ && lower, upper_type_ && upper, generator_type_ && generator, callback_type_ && callback) const noexcept; ``` Warnings: The draw is uniform only if every partition holds a similar number of in-range entries, and it takes one lock. The reservoir overload below walks all of them instead, so a call site that needs the whole range weighted correctly wants that one. ## sample_reservoir Fills `reservoir` with up to `reservoir_capacity` elements of the range, weighting every partition by how many in-range entries it actually holds. ```cpp template output_iterator_type_> requires offers_sample_reservoir && 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; ``` Warnings: One partition is locked at a time rather than all of them, so a writer moving an entry between partitions can have it sampled twice or not at all. ## clear Empties every partition in place, stopping where one refuses. ```cpp status_t clear() noexcept; ``` Each partition clears itself rather than being replaced by a fresh one: a replacement leaves an open transaction referring to contents that are gone, and it would have to rebuild the comparator and allocator the partition was given. Statuses: - Any status a partition's [`clear`](#clear) returns passes through unchanged and stops the walk, after which the partitions above the refusing one still hold everything they held. ## reserve Sizes every partition for its share of [`size`](#size), stopping where one refuses. ```cpp status_t reserve(std::size_t size) noexcept; ``` Statuses: - Any status a partition's [`reserve`](#reserve) returns passes through unchanged and stops the walk, after which the partitions above the refusing one are sized as they were. ## equal_range Hands `callback` every member equal to `comparable`, which one partition owns outright. ```cpp template requires offers_equal_range status_t equal_range( comparable_type_ && comparable, callback_type_ && callback) const noexcept; ``` ## versions_count How many versions every partition holds together, published and staged alike. ```cpp requires offers_versions_count std::size_t versions_count() const noexcept; ``` ```cpp template requires offers_versions_count std::size_t versions_count( comparable_type_ const & comparable) const noexcept; ``` How many versions of `comparable` are still held, by the one partition that owns it. ## insert_or_assign Writes `element` whether or not its key is taken, spelled as a partition spells it. ```cpp requires offers_insert_or_assign status_t insert_or_assign(value_t && element) noexcept; ``` ## make Builds a store with every partition allocated, reporting a failed allocation as a status. ```cpp expected make() noexcept; ``` ```cpp expected make( comparator_t const & comparator, hash_t const & hasher) noexcept; ``` Builds a store whose every partition shares one comparator and one hasher. ```cpp template requires requires(allocator_type_ const &allocator) { inner_store_t::make(allocator); } expected make( allocator_type_ const & allocator) noexcept; ``` Builds a store whose every partition allocates through a copy of [`allocator`](https://www.unum.cloud/docs/smashtable/cpp/containers.md#allocator). ```cpp template requires requires(comparator_t const &comparator, allocator_type_ const &allocator) { inner_store_t::make(comparator, allocator); } expected make( comparator_t const & comparator, hash_t const & hasher, allocator_type_ const & allocator) noexcept; ``` Builds partitions sharing a comparator, a hasher and copies of one allocator. - `comparator` (in): The instance every comparison consults, within and across partitions. - `hasher` (in): The instance that maps an identifier to its partition. - `allocator` (in): Copied once per partition, so a stateful one accounts for each apart. Statuses: - Any status a partition's [`make`](#make) returns passes through unchanged. ## padded_mutex_t One partition's lock, alone on its cache line so taking it does not invalidate the other partitions'. ```cpp struct padded_mutex_t ``` ## padded_epoch_t One partition's write count, alone on its cache line for the same reason its lock is. ```cpp struct padded_epoch_t ``` - `writes` `epoch_t` ## ordered_cursor_t A resumable walk of the merged order that holds no lock between its steps. ```cpp class ordered_cursor_t ``` The position is held by value rather than as an iterator, which is what makes erasing the key the cursor stands on harmless: the next step asks for the first key at or after it and is answered by the successor. Each partition's smallest unvisited key is cached beside the write count it was read under, so a step re-probes only the partitions somebody has written since - none of them, in a store nobody is writing, which is where the cost goes from sixteen probes per element to one. What it promises: no key is handed over twice, nothing fails, and every key present for the whole walk is handed over exactly once. A key inserted ahead of the cursor is seen, because the insert moved the count its partition's front was cached under. A key inserted behind it is missed, which is what walking without holding the store means. ## reader_t A read-only view of all partitions at one stamp that records and settles nothing. ```cpp class reader_t ``` One claim on the shared order pins the stamp for every partition, and each read asks the partition owning its key at that stamp. No read writes to the reader, so any number of threads may read through one reader at once with no lock of their own; the partition locks every read already takes shared are what keep a writer out of the partition being read. #### Costs Opening counts a snapshot into a bucket of the order, and closing takes it back out. A point read takes one partition's lock shared, which uncontended is one compare-exchange to acquire and one subtraction to release; a range read takes every partition shared, ascending, for the length of its walk, as [`range`](#range) does. Neither touches the order, marks a partition, allocates or validates anything. The claim holds the low-water mark at or below the stamp, so no partition prunes a version published after it while the reader is open: retention grows by one entry per commit to a key for as long as the reader lives, and commits pay for it in longer version runs to step over and validate. Closing gives nothing back at once - a key's tail goes on the next commit touching it, or on [`vacuum`](#vacuum). A transaction adopting the stamp takes a claim of its own beside this one. ## transaction_t A transaction spanning every partition, taking each partition's lock only for the calls that reach it. ```cpp class transaction_t ``` ## snapshot_store Transactional store answering every read at one snapshot, over any key-addressable core. ```cpp template class snapshot_store ``` `isolation_` picks the rung: [`snapshot_k`](#snapshot_k), [`serializable_k`](#serializable_k) or [`strict_serializable_k`](#strict_serializable_k). Not thread-safe by itself. Entirely exception-free, with all methods marked `noexcept`. #### Design Goals A transaction fixes one commit stamp when it opens and answers every read at it, so a value read twice reads the same both times and a range walked twice admits no key that was not there the first time. Writes are checked first-committer-wins: a transaction is refused if anything committed to a key it wrote or watched after its snapshot was taken. At [`snapshot_k`](#snapshot_k) only a watched key is re-checked; from [`serializable_k`](#serializable_k) up, every read and window read is too. `[monotonic_store](https://www.unum.cloud/docs/smashtable/cpp/transactions.md#monotonic_store)` keeps one published version per key and promises only Monotonic Atomic View. This store keeps every version a live snapshot can still reach, which is what buys the stronger promise and what the reclamation machinery below has to give back. #### Representation One entry per ____(key,generation) pair, uniformly for ordered and unordered cores. An ordered core needs no new comparator - `versioned_comparator_t` already breaks a tie on the generation, so a key's versions occupy one contiguous run. An unordered core rebinds on `[per_version_equals](#per_version_equals)`, which widens equality to the pair while the hasher keeps peeling to the bare key, so a key's versions share one probe run. Neither shape carries a chain, so visibility, rollback and reclamation each have exactly one implementation. A version's [`generation`](https://www.unum.cloud/docs/smashtable/cpp/transactions.md#generation) is half of its key and is never rewritten after insertion: re-keying would relocate a tree node and could overflow a table, and a commit that can fail is not a commit. Only `committed` is ever written in place. #### Reclamation Versions are pruned on write against a low-water mark, and an explicit [`vacuum`](#vacuum) sweeps the rest. There is no background thread, no epoch registry and no hidden global state: registering and retiring a snapshot is linking a node the caller already owns, so a destructor may do it. The mark is a floor at or below every snapshot the order counts open, which cannot pass one somebody still holds and follows the oldest reader up as readers leave. With nothing open the mark equals the published stamp, so a key falls to one entry on the next commit touching it. #### Ranking A core that sums a second per-subtree count carries [`select`](#select) and [`rank`](#rank), descending on a survivor tag written into each entry beside its stamp. Those two answer at the newest published stamp and only there: the tag says "survives now", and one scalar per node cannot also answer for a reader holding an older snapshot, which is why a transaction's own [`select`](#select) walks its merged order instead. See also: [https://jepsen.io/consistency/models/snapshot-isolation](https://jepsen.io/consistency/models/snapshot-isolation) See also: [https://jepsen.io/consistency/models/serializable](https://jepsen.io/consistency/models/serializable) See also: [https://jepsen.io/consistency/models/strict-serializable](https://jepsen.io/consistency/models/strict-serializable) ## order_t Where stamps and snapshots come from, which a shard set shares across its partitions. ```cpp using order_t = order_type_; ``` ## rebind_order This same store, built into `other_order_type_` instead, for a wrapper that shares one across its parts. ```cpp template using rebind_order = snapshot_store; ``` ## 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; ``` ## versioned_t One stored version, decorated with a survivor tag only where a core descends on it. ```cpp using versioned_t = std::conditional_t, typename versioning_t::versioned_t>; ``` An unranked core keeps the bare entry, so nothing pays for a bit nothing reads. ## store_t What this store calls itself, so generic code spells an engine and a wrapper alike. ```cpp using store_t = snapshot_store; ``` ## isolation_k Every read of a transaction is answered at the stamp the transaction opened on. ```cpp isolation_t isolation_k; ``` ## awaits_publication_k Whether a write outside a transaction waits for its own publication before returning. ```cpp bool awaits_publication_k; ``` A transaction's own commit waits at every level, so this gates the direct write paths alone. Without the wait such a write can return while an older commit still writing itself out holds the watermark below the stamp just drawn, so a transaction opening afterwards reads at a snapshot that predates it - serializable, but not in real time. ## ranked_core_k Whether the core sums a second per-subtree count, unlocking [`select`](#select) and [`rank`](#rank). ```cpp bool ranked_core_k; ``` ## snapshot_store Builds a store into [`order`](#order), which every stamp and every snapshot then comes from. ```cpp snapshot_store() noexcept; ``` ```cpp requires (!owns_its_order_k) snapshot_store(order_type_ & order) noexcept; ``` Builds a store into [`order`](#order), which every stamp and every snapshot then comes from. ```cpp requires (!owns_its_order_k) snapshot_store( order_type_ & order, allocator_t const & allocator) noexcept; ``` The same, with an allocator for the entries. ```cpp snapshot_store(allocator_t const & allocator) noexcept; ``` Seeds the underlying core's allocator, which a stateful allocator needs. ```cpp snapshot_store( comparator_t const & comparator, allocator_t const & allocator = {}) noexcept; ``` Seeds the addressing as well, for a comparator carrying state or a dispatch pointer. ```cpp snapshot_store(snapshot_store && other) noexcept; ``` Takes over `other's` versions and its place in its order. ```cpp snapshot_store(snapshot_store const &)=delete; ``` A store in somebody's order keeps pointing at it; one whose order is its own copies the counters across, since the moved-from object it lives in is about to stop speaking for anything. ## operator= ```cpp snapshot_store & operator=(snapshot_store && other) noexcept; ``` ```cpp snapshot_store & operator=(snapshot_store const &)=delete; ``` ## ~snapshot_store ```cpp ~snapshot_store() noexcept; ``` ## size How many keys the newest published version says are there. ```cpp std::size_t size() const noexcept; ``` ## empty Whether no key is currently readable. ```cpp bool empty() const noexcept; ``` ## versions_count How many versions the store holds across every key, published and staged alike. ```cpp std::size_t versions_count() const noexcept; ``` ```cpp template std::size_t versions_count( comparable_type_ const & comparable) const noexcept; ``` How many versions of `comparable` the store still holds. ## published_stamp The newest stamp a fully written commit left behind. ```cpp generation_t published_stamp() const noexcept; ``` ## open_snapshots How many transactions currently hold a snapshot. ```cpp std::size_t open_snapshots() const noexcept; ``` ## contains Whether a member equal to `comparable` is readable now. ```cpp template expected contains(comparable_type_ && comparable) const noexcept; ``` ## count How many members equal `comparable`, which for a unique-key store is zero or one. ```cpp template expected count( comparable_type_ && comparable) const noexcept; ``` ## transaction Opens a transaction, fixing the snapshot every one of its reads will be answered at. ```cpp expected transaction() noexcept; ``` ```cpp expected transaction(reader_t const & reader) noexcept; ``` Opens a transaction reading at `reader's` stamp rather than at the newest one. The transaction takes a claim of its own beside the reader's, so either may close first. What it reads and writes is validated at commit exactly as any transaction's is, against everything published after that stamp: an older stamp meets more refusals, from [`serializable_k`](#serializable_k) up for every read and at [`snapshot_k`](#snapshot_k) for what it watched and wrote. ## transaction_at Opens one shard's part of a transaction at an outside [`snapshot`](https://www.unum.cloud/docs/smashtable/cpp/transactions.md#snapshot) and [`generation`](https://www.unum.cloud/docs/smashtable/cpp/transactions.md#generation). ```cpp expected transaction_at(opened_at_t opened) noexcept; ``` Joins no bucket of its own: the snapshot's owner holds the one claim answering for every part, so a claim per part would only count the same reader many times over. ## reader_at A reader at a `stamp` somebody else pinned, for one partition of a sharded reader. ```cpp reader_t reader_at(generation_t stamp) const noexcept; ``` Registers nothing, so it must not outlive the claim that holds `stamp`. ## join_order Seats the order this store is a member of, for a wrapper that builds its parts and then moves them into place. ```cpp requires (!owns_its_order_k) void join_order(order_type_ & order) noexcept; ``` Only a store whose order is somebody else's has one to seat, so a solitary store cannot be re-seated at all. Called once, by the wrapper that owns both, before any transaction opens. ## order The order this store was built into. ```cpp order_type_ & order() noexcept; ``` ```cpp order_type_ const & order() const noexcept; ``` ## find Finds a member __equal__ to `comparable` as of the newest published commit. ```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 a `value_t const &`. Must be `noexcept`. - `callback_missing` (in): Callback triggered if nothing was found. Must be `noexcept`. ## find_copy Copies out the member equal to `comparable`, or reports why it could not. ```cpp template expected find_copy( comparable_type_ && comparable) const 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 the newest published commit shows. ```cpp template requires ordered_core_k status_t smallest( callback_found_type_ && callback_found, callback_missing_type_ && callback_missing = {}) const noexcept; ``` The unbounded case of [`lower_bound`](#lower_bound), and the one a merged walk over several stores opens with. It asks for a first key rather than an ordinal, so a core without subtree counts answers it too. - `callback_found` (in): Callback to receive a `value_t const &`. Must be `noexcept`. - `callback_missing` (in): Callback triggered when nothing is readable. Must be `noexcept`. ## make Builds a store around an allocator, reported as a result rather than thrown. ```cpp expected make(allocator_t const & allocator = {}) noexcept; ``` ```cpp expected make( comparator_t const & comparator, allocator_t const & allocator) noexcept; ``` Builds a store around a specific comparator, for comparators that carry state. ## visible_cursor_t A resumable walk over the keys one snapshot reads, yielding each key exactly once. ```cpp class visible_cursor_t ``` A key's versions occupy one contiguous run ordered by generation rather than by stamp, so the version a reader sees is whichever of them carries the greatest visible stamp - which no binary search inside the run can find. The cursor therefore stands on one whole run at a time and steps to the next, and that is what a callback loop cannot be paused between. Only ordered cores have a successor to resume from, so the open-addressed core does not offer this: its probe order is a function of the table's capacity, which writes may change. Notes: Every read is delivered through `peek`, so nothing addressing the store escapes. Any write to the store abandons the cursor. ## reader_t A read-only view pinned at one stamp, which records nothing and settles nothing. ```cpp class reader_t ``` Every read answers at the stamp the reader opened on, whatever commits after it, and no read writes to the reader - so any number of threads may read through one reader at once without a lock of their own. They still need the store not to be written while they read, which a bare store leaves to its caller and `[partitioned_store](#partitioned_store)` provides with its partition locks. #### Costs Opening a reader counts a snapshot into one bucket of the order and closing it takes that back, which on that count. A read takes no lock and touches no atomic of its own; a point read costs a descent plus a step over every version its key still holds, and a range read a step over every version inside the window. The claim holds the low-water mark at or below the reader's stamp, so every version published after that stamp survives pruning for as long as the reader is open - one entry per commit to a key rather than one per key, since a version is freed only once it is visible at the mark. Commits keep publishing and validating as usual, and pay for the retention in longer version runs. Closing the reader frees nothing by itself: a key's tail goes on the next commit touching that key, or on [`vacuum`](#vacuum). ## transaction_t A transaction reading at one snapshot and publishing under one commit stamp. ```cpp class transaction_t ``` ## publication_t A group of writes over many keys that becomes visible under one stamp. ```cpp class publication_t ``` Publishing key by key draws a stamp per key, so a reader that opens between two of them sees the operation half applied. This files every version invisibly first and stamps them all at once, which is the same two-step shape [`transaction_t::commit`](https://www.unum.cloud/docs/smashtable/cpp/transactions.md#commit) has, without the validation a store-level write never had to do. Anything staged and not published is dropped when the publication goes away, so a failure part way through a group leaves the store exactly as it was. ## standard_waiting_policy Parks a spent spin on `std::atomic::wait`, leaving the spin itself to `pausing_policy_type_`. ```cpp template struct standard_waiting_policy ``` This is how a pause hint reaches a path that also parks: the hint answers for the spin and the standard library answers for the sleep, so a policy that only knows how to stall a core needs to say nothing about parking to be usable on a lock that parks. ## pausing What a core does between attempts, asked once per attempt the spin spends. ```cpp pausing_policy_type_ pausing; ``` ## operator() Hands one spent attempt to the pausing policy, which is the whole of the spin here. ```cpp template void operator()( watched_type_ const & watched, value_type_ const observed, attempts_type_ const attempts_spent) const noexcept; ``` ## wait_until_changed Parks until `watched` stops reading `observed`, or until the wait returns spuriously. ```cpp template void wait_until_changed( value_type_ const *watched, value_type_ const observed) const noexcept; ``` ## notify_waiters Wakes every thread parked on `watched`. ```cpp template void notify_waiters(value_type_ *watched) const noexcept; ``` ## versioned_storage_for How a container family restates itself over version-decorated elements, and how one such entry is reached, replaced and taken back out. ```cpp template struct versioned_storage_for ``` An ordered core addresses an entry by a comparator and rebinds on one; an unordered core addresses it by a hasher paired with an equality and rebinds on both. Everything a transactional store does that is not itself ordered - staging, committing, reading one key - goes through this, so the store never names either shape. ## rebind_dated The same storage keyed by identifier __and__ generation, holding one entry per version. ```cpp template using rebind_dated = rebind; ``` Unchanged here, since the ordered comparator already breaks a tie on the generation. ## build Builds an empty storage over `element_type_`, seeded from a bare comparator. ```cpp template rebind build( addressing_source_t const & source, allocator_type_ const & allocator) noexcept; ``` ```cpp template rebind build(allocator_type_ const & allocator) noexcept; ``` Builds an empty storage over `element_type_`, leaving the addressing defaulted. ## sibling Builds an empty storage over `element_type_` addressed exactly as `existing` is. ```cpp template rebind sibling(storage_type_ const & existing) noexcept; ``` ## allocator_of The allocator a storage of this family was built with. ```cpp template decltype(auto) allocator_of(storage_type_ const & storage) noexcept; ``` ## prepare A node-based core has nothing to prepay; the placeholder pass reserves it. ```cpp template status_t prepare(storage_type_ &, std::size_t) noexcept; ``` ## upsert Files `element` under its own key, overwriting whatever shared it. ```cpp template status_t upsert( storage_type_ & storage, element_type_ && element) noexcept; ``` ## extract_payload Takes the entry filed under `identifier` out whole, handing its payload to `destination`. ```cpp template bool extract_payload( storage_type_ & storage, identifier_type_ const & identifier, payload_type_ & destination) noexcept; ``` Notes: The entry leaves the index before anything is moved out of it, since its key lives inside the payload and a moved-from key neither compares nor hashes. ## visible_at Whether a version stamped `stamp` is visible to a reader holding [`snapshot`](https://www.unum.cloud/docs/smashtable/cpp/transactions.md#snapshot). ```cpp bool visible_at(commit_stamp_t stamp, generation_t snapshot) noexcept; ``` ## visible_now Whether `stamp` was drawn at all, which is what a reader taking no snapshot asks. ```cpp bool visible_now(commit_stamp_t stamp) noexcept; ``` ## at_least Whether `offered` is at least as strong a promise as `required`. ```cpp bool at_least(isolation_t offered, isolation_t required) noexcept; ``` ## absent_generation_k The generation no stored entry can carry, standing for a key that is not there. ```cpp generation_t absent_generation_k; ``` Generations are handed out pre-incremented, so the first is 1 and zero is free to mean absence. A watch on an absent key must be anchored to this rather than to the watching transaction's own generation, which [`rollback`](https://www.unum.cloud/docs/smashtable/cpp/transactions.md#rollback) reassigns - otherwise the watch stops matching itself. ## latest_snapshot_k The snapshot a reader that takes none holds: every stamp a commit can ever draw is at or below it, and only [`commit_stamp_t::uncommitted_k`](https://www.unum.cloud/docs/smashtable/cpp/transactions.md#uncommitted_k) sits above. ```cpp generation_t latest_snapshot_k; ``` ## Overview Can be instantiated with any key-addressable core - AVL trees, weight-balanced trees, open-addressed tables - and gates its ordered surface behind the cores that supply an ordering. Exception-free, with all reads delivered through callbacks.