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.
opened_at_tWhere a transaction opens: the snapshot it reads, and the generation dating its versions.struct opened_at_tOne 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_tWhat a reader is promised, named as Jepsen names it and ordered by strength.enum isolation_tThe 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 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 |
versioning_forDecorates a value type with generation and visibility metadata for transactional containers.template <typename value_type_,
typename comparator_type_>
struct versioning_forvalue_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_equalsCompares version-decorated objects by identifier and generation, so versions do not collapse.template <typename equals_type_>
struct per_version_equalsA 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, 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_tThe policy a spin takes when nobody names one: no instruction at all between attempts.struct bare_waiting_policy_tLeaves 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.
unique_lockHolds 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.template <typename mutex_type_>
class unique_lockorder_sharing_tWhether an order is reached from several threads, which decides both its atomics and its padding.enum order_sharing_tsolitary_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_tWhether an entry is the newest committed-and-present version of its key, as of right now.enum liveness_tsuperseded_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_taggedA stored version carrying the one bit an order-statistic descent reads off the entry.template <typename versioned_type_>
struct live_taggedA 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_tCounts one entry per key the newest published stamp reads, for the tree to sum per subtree.struct liveness_augmentation_tAnswers zero for an undecorated element, which is what the bare core rebinds from holds.
locked_storeWraps and protects any transactional store under a shared mutex.53template <typename store_type_,
typename shared_mutex_type_ = spin_shared_mutex_t,
typename order_type_ = basic_commit_order<1>>
class locked_storeThe 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 and 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.
rebind_orderThe same store in another order, which is how a shard set builds its partitions into its own.template <typename other_order_type_>
using rebind_order = locked_store<store_type_, shared_mutex_type_, other_order_type_>;isolation_kThe staging reservation carries the inner store's promise over, not the mutex; see the class note.isolation_t isolation_k;inner_transaction_shards_kWhether the wrapped transaction can be driven as one part of a commit under a stamp drawn elsewhere.bool inner_transaction_shards_k;inner_transaction_splits_commit_kWhether the wrapped transaction decides and writes in two steps rather than one.bool inner_transaction_splits_commit_k;locked_storeBuilds a store that is a member of order rather than of one it made for itself.locked_store() noexcept;locked_store(order_t & order) noexcept;Builds a store that is a member of order rather than of one it made for itself.
locked_store(locked_store && other) noexcept;other must be untouched: no open transaction, no other thread; see class notes.
join_orderMakes this store, and the store it wraps, a member of order.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.
sizeHow many entries the store holds, read under the shared lock.std::size_t size() const noexcept;emptyWhether the store holds no entries, read under the shared lock.bool empty() const noexcept;transactionOpens a transaction over the wrapped store.expected<transaction_t> transaction() noexcept;upsertInserts or overwrites element in one locked write.status_t upsert(value_t && element) noexcept;template <readable_iterator elements_begin_type_, iterator_sentinel<elements_begin_type_> elements_end_type_ = elements_begin_type_>
status_t upsert(
elements_begin_type_ begin,
elements_end_type_ end) noexcept;Inserts or overwrites every element of a range in one locked write.
eraseErases whatever equals comparable, reporting through the callbacks so presence needs no second probe.template <typename comparable_type_ = identifier_t, typename callback_found_type_ = no_op_t, typename callback_missing_type_ = no_op_t>
status_t erase(
comparable_type_ && comparable,
callback_found_type_ && callback_found = {},
callback_missing_type_ && callback_missing = {}) noexcept;Takes any type the inner store compares against, not only an identifier.
insert_if_missingInserts element only if its key is absent, leaving an incumbent untouched.status_t insert_if_missing(value_t && element) noexcept;template <typename callback_inserted_type_, typename callback_existing_type_>
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.
template <readable_iterator elements_begin_type_, iterator_sentinel<elements_begin_type_> elements_end_type_ = elements_begin_type_>
status_t insert_if_missing(
elements_begin_type_ begin,
elements_end_type_ end) noexcept;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. |
insertInserts element only if its key is free, refusing with the inner store's own status.requires offers_insert<inner_store_t>
status_t insert(value_t && element) noexcept;template <typename callback_inserted_type_, typename callback_existing_type_>
requires offers_insert_naming_occupant<inner_store_t>
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. |
updateWrites element only if its key is already taken, refusing to create one.requires offers_update<inner_store_t>
status_t update(value_t && element) noexcept;findLooks comparable up, under the shared lock.template <typename comparable_type_ = identifier_t, typename callback_found_type_ = no_op_t, typename callback_missing_type_ = no_op_t>
status_t find(
comparable_type_ && comparable,
callback_found_type_ && callback_found,
callback_missing_type_ && callback_missing = {}) const noexcept;containsExistence check, expressed through find so the lock discipline stays in one place.template <typename comparable_type_ = identifier_t>
expected<bool> contains(comparable_type_ && comparable) const noexcept;*× 2Number of elements matching comparable, which is 0 or 1 for unique keys.template <typename comparable_type_ = identifier_t>
expected<std::size_t> count(
comparable_type_ && comparable) const noexcept;lower_boundFinds the first key not ordered before comparable, under the shared lock.template <typename comparable_type_ = identifier_t, typename callback_found_type_ = no_op_t, typename callback_missing_type_ = no_op_t>
requires offers_lower_bound<inner_store_t>
status_t lower_bound(
comparable_type_ && comparable,
callback_found_type_ && callback_found,
callback_missing_type_ && callback_missing = {}) const noexcept;*× 2A walk of every member in ascending order, resumable and holding no lock between steps.requires offers_both_bounds<inner_store_t> && offers_smallest<inner_store_t>
ordered_cursor_t cursor() const noexcept;cursor_*_from× 2The same walk, begun at the first member ordered at or after from.requires offers_both_bounds<inner_store_t>
ordered_cursor_t cursor__from(identifier_t from) const noexcept;cursor_up_*_up_to× 2The same walk, stopping before upper.requires offers_both_bounds<inner_store_t> && offers_smallest<inner_store_t>
ordered_cursor_t cursor_up__up_to(identifier_t upper) const noexcept;cursor_*_range× 2The same walk over [ from, upper ).requires offers_both_bounds<inner_store_t>
ordered_cursor_t cursor__range(
identifier_t from,
identifier_t upper) const noexcept;smallestHands callback_found the smallest member, or reports the store is empty.template <typename callback_found_type_ = no_op_t, typename callback_missing_type_ = no_op_t>
requires offers_smallest<inner_store_t>
status_t smallest(
callback_found_type_ && callback_found,
callback_missing_type_ && callback_missing = {}) const noexcept;pop_smallestRemoves the smallest member and hands it over, or reports the store is empty.template <typename callback_found_type_ = no_op_t, typename callback_missing_type_ = no_op_t>
requires offers_pop_smallest<inner_store_t>
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× 2Copies out the smallest member and removes it, or reports key_not_found_k.requires offers_pop_smallest<inner_store_t>
expected<value_t> pop_smallest__smallest_copy() noexcept;smallest_*_copy× 2Copies out the smallest member, or reports key_not_found_k.requires offers_smallest<inner_store_t>
expected<value_t> smallest__copy() const noexcept;find_*_copy× 2Copies out the member equal to comparable, or reports key_not_found_k.template <typename comparable_type_ = identifier_t>
expected<value_t> find__copy(
comparable_type_ && comparable) const noexcept;lower_bound_*_bound_copy× 2Copies out the first element ordered at or after comparable.template <typename comparable_type_ = identifier_t>
requires offers_lower_bound<inner_store_t>
expected<value_t> lower_bound__bound_copy(
comparable_type_ && comparable) const noexcept;upper_bound_*_bound_copy× 2Copies out the first element ordered strictly after comparable.template <typename comparable_type_ = identifier_t>
requires offers_upper_bound<inner_store_t>
expected<value_t> upper_bound__bound_copy(
comparable_type_ && comparable) const noexcept;upper_boundFinds the first key after comparable, under the shared lock.template <typename comparable_type_ = identifier_t, typename callback_found_type_ = no_op_t, typename callback_missing_type_ = no_op_t>
requires offers_upper_bound<inner_store_t>
status_t upper_bound(
comparable_type_ && comparable,
callback_found_type_ && callback_found,
callback_missing_type_ && callback_missing = {}) const noexcept;rangeHands callback every member of [ lower, upper ), one shared lock held.template <typename lower_type_ = identifier_t, typename upper_type_ = identifier_t, typename callback_type_ = no_op_t>
requires offers_range<inner_store_t>
status_t range(
lower_type_ && lower,
upper_type_ && upper,
callback_type_ && callback) const noexcept;template <typename from_type_ = identifier_t, typename until_type_ = identifier_t, typename callback_type_ = no_op_t>
requires offers_descending_range<inner_store_t>
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.
A callback answering walk_control_t stops the walk where it says to.
erase_rangeErases the keys between lower and upper as the wrapped store bounds them, in one locked write.template <typename lower_type_ = identifier_t, typename upper_type_ = identifier_t, typename callback_type_ = no_op_t>
requires offers_erase_range<inner_store_t>
status_t erase_range(
lower_type_ && lower,
upper_type_ && upper,
callback_type_ && callback = {}) noexcept;erase_fromErases every element at or after lower, reporting each to callback.template <typename lower_type_ = identifier_t, typename callback_type_ = no_op_t>
requires offers_erase_from<inner_store_t>
status_t erase_from(
lower_type_ && lower,
callback_type_ && callback = {}) noexcept;erase_up_toErases every element before upper, reporting each to callback.template <typename upper_type_ = identifier_t, typename callback_type_ = no_op_t>
requires offers_erase_up_to<inner_store_t>
status_t erase_up_to(
upper_type_ && upper,
callback_type_ && callback = {}) noexcept;update_rangeRewrites the mapped side of every element in [ lower, upper ).template <typename lower_type_ = identifier_t, typename upper_type_ = identifier_t, typename callback_type_ = no_op_t>
requires offers_update_range<inner_store_t>
status_t update_range(
lower_type_ && lower,
upper_type_ && upper,
callback_type_ && callback) noexcept;lower | in | Lower bound (inclusive). |
|---|---|---|
upper | in | Upper bound (exclusive). |
callback | in | Invoked with (key const &, mapped &) per element. Must be noexcept. |
Success, or an allocation failure. A store whose walk cannot fail always succeeds.
for_eachHands callback every member the store holds, in whatever order it keeps them.template <typename callback_type_ = no_op_t>
requires offers_for_each<inner_store_t>
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.
A callback answering walk_control_t stops the walk where it says to, which also ends the shared hold early.
vacuumFrees every version no reader can still reach.requires offers_vacuum<inner_store_t>
expected<std::size_t> vacuum() noexcept;template <typename lower_type_ = identifier_t, typename upper_type_ = identifier_t>
requires offers_vacuum_window<inner_store_t>
expected<std::size_t> 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.
How many versions were reclaimed, or why none could be. A store whose sweep cannot refuse always answers with a count.
selectHands callback_found the element at zero-based position ordinal.template <typename callback_found_type_ = no_op_t, typename callback_missing_type_ = no_op_t>
requires offers_select<inner_store_t>
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 const &. Must be noexcept. |
callback_missing | in | Fires when fewer elements are there. Must be noexcept. |
*× 2Hands callback_found how many elements the store orders before comparable.template <typename comparable_type_ = identifier_t, typename callback_found_type_ = no_op_t, typename callback_missing_type_ = no_op_t>
requires offers_rank<inner_store_t>
status_t rank(
comparable_type_ && comparable,
callback_found_type_ && callback_found,
callback_missing_type_ && callback_missing = {}) const noexcept;Counted by the same merge 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. |
clearErases every entry, under the exclusive lock.status_t clear() noexcept;reserveReserves room for size entries in the wrapped store.status_t reserve(std::size_t size) noexcept;sample_oneDraws one entry between lower and upper with generator, under the shared lock.template <typename lower_type_, typename upper_type_, typename generator_type_, typename callback_type_ = no_op_t>
requires offers_sample_one<inner_store_t> && uniform_random_bits<std::remove_cvref_t<generator_type_>>
status_t sample_one(
lower_type_ && lower,
upper_type_ && upper,
generator_type_ && generator,
callback_type_ && callback) const noexcept;sample_reservoirSamples entries between lower and upper into reservoir, under the shared lock.template <typename lower_type_, typename upper_type_, typename generator_type_, indexed_writable_iterator<value_t> output_iterator_type_>
requires offers_sample_reservoir<inner_store_t> && uniform_random_bits<std::remove_cvref_t<generator_type_>>
status_t sample_reservoir(
lower_type_ && lower,
upper_type_ && upper,
generator_type_ && generator,
std::size_t & seen,
std::size_t reservoir_capacity,
output_iterator_type_ && reservoir) const noexcept;equal_rangeHands callback every member equal to comparable, which for a unique-key store is one or none.template <typename comparable_type_ = identifier_t, typename callback_type_ = no_op_t>
requires offers_equal_range<inner_store_t>
status_t equal_range(
comparable_type_ && comparable,
callback_type_ && callback) const noexcept;A callback answering walk_control_t stops the walk where it says to.
ranked_sizeHow many keys the ordinal surface indexes, which is what select counts against.requires offers_ranked_size<inner_store_t>
std::size_t ranked_size() const noexcept;versions_countHow many versions the store holds across every key, published and staged alike.requires offers_versions_count<inner_store_t>
std::size_t versions_count() const noexcept;template <typename comparable_type_ = identifier_t>
requires offers_versions_count<inner_store_t>
std::size_t versions_count(
comparable_type_ const & comparable) const noexcept;How many versions of comparable the store still holds.
low_water_*_water_mark× 3The newest snapshot no open transaction sits below, which is what vacuum prunes to.requires offers_low_water_mark<inner_store_t>
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_assignWrites element whether or not its key is taken, spelled as the inner store spells it.requires offers_insert_or_assign<inner_store_t>
status_t insert_or_assign(value_t && element) noexcept;transaction_atOpens one part of a sharded transaction on snapshot and generation drawn elsewhere.requires draws_from_a_shared_order<inner_store_t>
expected<transaction_t> transaction_at(opened_at_t opened) noexcept;orderThe order the wrapped store is a member of, which is fixed at construction and needs no lock.order_t & order() noexcept;order_t const & order() const noexcept;The order this store draws stamps from, read-only.
makeBuilds the inner store from arguments and takes ownership of it.template <typename... arguments_type_>
expected<locked_store> 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_tA transaction over the wrapped store, taking the store's mutex for each call that touches it.class transaction_tordered_cursor_tA resumable walk in ascending key order, holding no lock between its steps.class ordered_cursor_tThe 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_storeHashes inputs to route them into separate sets, which can be concurrent, or have a separate state-full allocator attached.51template <typename store_type_,
typename hash_type_ = hash<typename store_type_::identifier_t>,
typename shared_mutex_type_ = spin_shared_mutex_t,
std::size_t partitions_count_ = 16>
class partitioned_storeEvery 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 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.
refusal_policy_tWhat an all-partition walk does with a partition that refuses.enum refusal_policy_tstop_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_tHow many times each partition has been written, so a cached read can be told it is stale.using epoch_t = std::size_t;epoch_counts_tA cursor's own copy of every partition's write count, which it alone reads and so needs no padding.using epoch_counts_t = std::array<epoch_t, partitions_k>;isolation_kA 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.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, which is the weakest level named and so the floor a cap can reach.
inner_transaction_splits_commit_kWhether the wrapped transaction decides and writes in two steps rather than one.bool inner_transaction_splits_commit_k;inner_reads_at_a_stamp_kWhether a partition answers reads at a stamp somebody else pinned, registering nothing itself.bool inner_reads_at_a_stamp_k;inner_publishes_under_a_stamp_kWhether 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.bool inner_publishes_under_a_stamp_k;inner_transaction_walks_unrecorded_kWhether an open transaction walks reads unrecorded, and records a window on demand, so a merged walk records only the handed-off prefix.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_kWhat every store-level window write keeps, which one stamp across the partitions makes whole.refusal_policy_t window_writes_policy_k;clear_policy_kWhat a refusal from each all-partition method says about the partitions it skipped.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 the partitions after the refusal are untouched, while under 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_storeBuilds an empty store into order, which it shares with every other store built into it, so a transaction_group over them publishes under one stamp.partitioned_store() noexcept;requires draws_from_a_shared_order<inner_store_t>
partitioned_store(order_t & order) noexcept;Builds an empty store into order, which it shares with every other store built into it, so a transaction_group over them publishes under one stamp.
partitioned_store(partitioned_store && other) noexcept;other must have no open transaction and no other thread touching it.
sizeHow many entries the partitions hold together, read with every partition held shared.std::size_t size() const noexcept;emptyWhether every partition is empty.bool empty() const noexcept;transactionOpens one transaction per partition, or none at all.expected<transaction_t> transaction() noexcept;requires inner_reads_at_a_stamp_k
expected<transaction_t> 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_atOpens one transaction per partition at a snapshot and a generation a group drew.requires draws_from_a_shared_order<inner_store_t>
expected<transaction_t> 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.
*× 2Opens a reader pinned at the newest published stamp, which records and settles nothing.requires inner_reads_at_a_stamp_k
reader_t reader() const noexcept;reader_atA 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.requires inner_reads_at_a_stamp_k
reader_t reader_at(generation_t stamp) const noexcept;orderThe order this store is a member of, which it owns unless it was built into a shared one.requires draws_from_a_shared_order<inner_store_t>
order_t & order() noexcept;requires draws_from_a_shared_order<inner_store_t>
order_t const & order() const noexcept;The order every partition draws stamps from, read-only.
upsertInserts or overwrites element in its partition, under that partition's lock.status_t upsert(value_t && element) noexcept;template <readable_iterator elements_begin_type_, iterator_sentinel<elements_begin_type_> elements_end_type_ = elements_begin_type_>
status_t upsert(
elements_begin_type_ begin,
elements_end_type_ end) noexcept;Inserts or overwrites every element of a range through one transaction.
eraseRemoves one element, reporting whether it was there.template <typename comparable_type_ = identifier_t, typename callback_found_type_ = no_op_t, typename callback_missing_type_ = no_op_t>
status_t erase(
comparable_type_ && comparable,
callback_found_type_ && callback_found = {},
callback_missing_type_ && callback_missing = {}) noexcept;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. |
key_not_found_k The element is absent, so the answer is available without a second probe.erase returns passes through unchanged.partition_ofWhich partition owns comparable, so a bulk writer buckets its rows by partition.template <typename comparable_type_ = identifier_t>
std::size_t partition_of(
comparable_type_ const & comparable) const noexcept;findLooks comparable up in its partition, under that partition's shared lock.template <typename comparable_type_ = identifier_t, typename callback_found_type_ = no_op_t, typename callback_missing_type_ = no_op_t>
status_t find(
comparable_type_ && comparable,
callback_found_type_ && callback_found,
callback_missing_type_ && callback_missing = {}) const noexcept;containsWhether comparable is there, asking only the partition that owns it.template <typename comparable_type_ = identifier_t>
expected<bool> contains(comparable_type_ && comparable) const noexcept;insert_if_missingInserts one element only if its key is absent, leaving an incumbent untouched.status_t insert_if_missing(value_t && element) noexcept;template <typename callback_inserted_type_, typename callback_existing_type_>
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.
template <readable_iterator elements_begin_type_, iterator_sentinel<elements_begin_type_> elements_end_type_ = elements_begin_type_>
status_t insert_if_missing(
elements_begin_type_ begin,
elements_end_type_ end) noexcept;Inserts every element of [ begin, 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. |
insertInserts one element, refusing with the inner store's own status when the key is taken.requires offers_insert<inner_store_t>
status_t insert(value_t && element) noexcept;template <typename callback_inserted_type_, typename callback_existing_type_>
requires offers_insert_naming_occupant<inner_store_t>
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. |
updateWrites one element only if its key is already taken, refusing to create one.requires offers_update<inner_store_t>
status_t update(value_t && element) noexcept;upper_boundThe first element ordered strictly after comparable, which may live in any partition.template <typename comparable_type_ = identifier_t, typename callback_found_type_ = no_op_t, typename callback_missing_type_ = no_op_t>
requires offers_upper_bound<inner_store_t>
status_t upper_bound(
comparable_type_ && comparable,
callback_found_type_ && callback_found,
callback_missing_type_ && callback_missing = {}) const noexcept;smallestThe smallest member of the merged order, which may live in any partition.template <typename callback_found_type_ = no_op_t, typename callback_missing_type_ = no_op_t>
requires offers_both_bounds<inner_store_t> && (offers_a_merged_walk<inner_store_t>)
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_smallestRemoves the smallest member of the merged order and hands it over.template <typename callback_found_type_ = no_op_t, typename callback_missing_type_ = no_op_t>
requires offers_both_bounds<inner_store_t> && offers_pop_smallest<inner_store_t> && (offers_a_merged_walk<inner_store_t>)
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.
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_boundThe first element at or after comparable, which may live in any partition.template <typename comparable_type_ = identifier_t, typename callback_found_type_ = no_op_t, typename callback_missing_type_ = no_op_t>
requires offers_lower_bound<inner_store_t>
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.
rangeHands callback every member of [ lower, upper ) in one ascending order.template <typename lower_type_ = identifier_t, typename upper_type_ = identifier_t, typename callback_type_ = no_op_t>
requires offers_range<inner_store_t>
status_t range(
lower_type_ && lower,
upper_type_ && upper,
callback_type_ && callback) const noexcept;template <typename from_type_ = identifier_t, typename until_type_ = identifier_t, typename callback_type_ = no_op_t>
requires offers_descending_range<inner_store_t>
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 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.
A callback answering walk_control_t stops the walk where it says to.
callback runs under all of them: reaching back into this store deadlocks.range holds them.erase_rangeErases the half-open range from every partition.template <typename lower_type_ = identifier_t, typename upper_type_ = identifier_t, typename callback_type_ = no_op_t>
requires offers_erase_range<inner_store_t>
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.
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_fromErases every element at or after lower from every partition.template <typename lower_type_ = identifier_t, typename callback_type_ = no_op_t>
requires offers_erase_from<inner_store_t>
status_t erase_from(
lower_type_ && lower,
callback_type_ && callback = {}) noexcept;erase_from returns passes through unchanged, scoped by the policy erase_from_policy_k exactly as erase_range scopes its own.erase_up_toErases every element before upper from every partition.template <typename upper_type_ = identifier_t, typename callback_type_ = no_op_t>
requires offers_erase_up_to<inner_store_t>
status_t erase_up_to(
upper_type_ && upper,
callback_type_ && callback = {}) noexcept;erase_up_to returns passes through unchanged, scoped by the policy erase_up_to_policy_k exactly as erase_range scopes its own.update_rangeRewrites the mapped side over [ lower, upper ) in every partition.template <typename lower_type_ = identifier_t, typename upper_type_ = identifier_t, typename callback_type_ = no_op_t>
requires offers_update_range<inner_store_t>
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 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. |
update_range returns passes through unchanged, scoped by the policy update_range_policy_k exactly as erase_range scopes its own. A partition whose own walk cannot fail always succeeds.for_eachHands callback every member the store holds, in no particular order.template <typename callback_type_ = no_op_t>
requires offers_for_each<inner_store_t>
status_t for_each(callback_type_ && callback) const noexcept;One partition is locked shared at a time, ascending, as 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.
A callback answering walk_control_t stops the walk where it says to, leaving the partitions above the one it stopped in unvisited.
vacuumFrees every version no reader can still reach, one partition at a time.requires offers_vacuum<inner_store_t>
expected<std::size_t> vacuum() noexcept;template <typename lower_type_ = identifier_t, typename upper_type_ = identifier_t>
requires offers_vacuum_window<inner_store_t>
expected<std::size_t> vacuum(
lower_type_ && lower,
upper_type_ && upper) noexcept;Frees the unreachable versions of every key in [ lower, upper ), one partition at a time.
How many versions were reclaimed across all partitions.
selectHands callback_found the element at zero-based ordinal in merged order.template <typename callback_found_type_ = no_op_t, typename callback_missing_type_ = no_op_t>
requires offers_select<inner_store_t>
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 const &. Must be noexcept. |
callback_missing | in | Fires when fewer elements are there. Must be noexcept. |
sample_oneHands one element of the range to callback, drawn from a single random partition.template <typename lower_type_, typename upper_type_, typename generator_type_, typename callback_type_ = no_op_t>
requires offers_sample_one<inner_store_t> && uniform_random_bits<std::remove_cvref_t<generator_type_>>
status_t sample_one(
lower_type_ && lower,
upper_type_ && upper,
generator_type_ && generator,
callback_type_ && callback) const noexcept;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_reservoirFills reservoir with up to reservoir_capacity elements of the range, weighting every partition by how many in-range entries it actually holds.template <typename lower_type_, typename upper_type_, typename generator_type_, indexed_writable_iterator<value_t> output_iterator_type_>
requires offers_sample_reservoir<inner_store_t> && uniform_random_bits<std::remove_cvref_t<generator_type_>>
status_t sample_reservoir(
lower_type_ && lower,
upper_type_ && upper,
generator_type_ && generator,
std::size_t & seen,
std::size_t reservoir_capacity,
output_iterator_type_ && reservoir) const noexcept;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.
clearEmpties every partition in place, stopping where one refuses.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.
clear returns passes through unchanged and stops the walk, after which the partitions above the refusing one still hold everything they held.reserveSizes every partition for its share of size, stopping where one refuses.status_t reserve(std::size_t size) noexcept;reserve returns passes through unchanged and stops the walk, after which the partitions above the refusing one are sized as they were.equal_rangeHands callback every member equal to comparable, which one partition owns outright.template <typename comparable_type_ = identifier_t, typename callback_type_ = no_op_t>
requires offers_equal_range<inner_store_t>
status_t equal_range(
comparable_type_ && comparable,
callback_type_ && callback) const noexcept;versions_countHow many versions every partition holds together, published and staged alike.requires offers_versions_count<inner_store_t>
std::size_t versions_count() const noexcept;template <typename comparable_type_ = identifier_t>
requires offers_versions_count<inner_store_t>
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_assignWrites element whether or not its key is taken, spelled as a partition spells it.requires offers_insert_or_assign<inner_store_t>
status_t insert_or_assign(value_t && element) noexcept;makeBuilds a store with every partition allocated, reporting a failed allocation as a status.expected<partitioned_store> make() noexcept;expected<partitioned_store> make(
comparator_t const & comparator,
hash_t const & hasher) noexcept;Builds a store whose every partition shares one comparator and one hasher.
template <typename allocator_type_>
requires requires(allocator_type_ const &allocator) { inner_store_t::make(allocator); }
expected<partitioned_store> make(
allocator_type_ const & allocator) noexcept;Builds a store whose every partition allocates through a copy of allocator.
template <typename allocator_type_>
requires requires(comparator_t const &comparator, allocator_type_ const &allocator) { inner_store_t::make(comparator, allocator); }
expected<partitioned_store> 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. |
make returns passes through unchanged.padded_mutex_tOne partition's lock, alone on its cache line so taking it does not invalidate the other partitions'.struct padded_mutex_tpadded_epoch_tOne partition's write count, alone on its cache line for the same reason its lock is.ordered_cursor_tA resumable walk of the merged order that holds no lock between its steps.class ordered_cursor_tThe 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_tA read-only view of all partitions at one stamp that records and settles nothing.class reader_tOne 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.
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 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. A transaction adopting the stamp takes a claim of its own beside this one.
transaction_tA transaction spanning every partition, taking each partition's lock only for the calls that reach it.class transaction_tsnapshot_storeTransactional store answering every read at one snapshot, over any key-addressable core.32template <typename collection_type_,
isolation_t isolation_ = isolation_t::snapshot_k,
typename order_type_ = solitary_commit_order_t>
class snapshot_storeisolation_ picks the rung: snapshot_k, serializable_k or strict_serializable_k. Not thread-safe by itself. Entirely exception-free, with all methods marked noexcept.
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 only a watched key is re-checked; from serializable_k up, every read and window read is too.
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.
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, 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 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.
Versions are pruned on write against a low-water mark, and an explicit 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.
A core that sums a second per-subtree count carries select and 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 walks its merged order instead.
order_tWhere stamps and snapshots come from, which a shard set shares across its partitions.using order_t = order_type_;rebind_orderThis same store, built into other_order_type_ instead, for a wrapper that shares one across its parts.template <typename other_order_type_>
using rebind_order = snapshot_store<collection_type_, isolation_, other_order_type_>;storage_shape_tWhat this core family rebinds on, and how a decorated entry is reached inside it.using storage_shape_t = versioned_storage_for<collection_type_, value_t>;versioned_tOne stored version, decorated with a survivor tag only where a core descends on it.using versioned_t = std::conditional_t<ranked_core_k, live_tagged<typename versioning_t::versioned_t>, typename versioning_t::versioned_t>;An unranked core keeps the bare entry, so nothing pays for a bit nothing reads.
store_tWhat this store calls itself, so generic code spells an engine and a wrapper alike.using store_t = snapshot_store;isolation_kEvery read of a transaction is answered at the stamp the transaction opened on.isolation_t isolation_k;awaits_publication_kWhether a write outside a transaction waits for its own publication before returning.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_kWhether the core sums a second per-subtree count, unlocking select and rank.bool ranked_core_k;snapshot_storeBuilds a store into order, which every stamp and every snapshot then comes from.snapshot_store() noexcept;requires (!owns_its_order_k)
snapshot_store(order_type_ & order) noexcept;Builds a store into order, which every stamp and every snapshot then comes from.
requires (!owns_its_order_k)
snapshot_store(
order_type_ & order,
allocator_t const & allocator) noexcept;The same, with an allocator for the entries.
snapshot_store(allocator_t const & allocator) noexcept;Seeds the underlying core's allocator, which a stateful allocator needs.
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.
snapshot_store(snapshot_store && other) noexcept;Takes over other's versions and its place in its order.
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=snapshot_store & operator=(snapshot_store && other) noexcept;snapshot_store & operator=(snapshot_store const &)=delete;~snapshot_store~snapshot_store() noexcept;sizeHow many keys the newest published version says are there.std::size_t size() const noexcept;emptyWhether no key is currently readable.bool empty() const noexcept;versions_countHow many versions the store holds across every key, published and staged alike.std::size_t versions_count() const noexcept;template <typename comparable_type_ = identifier_t>
std::size_t versions_count(
comparable_type_ const & comparable) const noexcept;How many versions of comparable the store still holds.
published_stampThe newest stamp a fully written commit left behind.generation_t published_stamp() const noexcept;open_snapshotsHow many transactions currently hold a snapshot.std::size_t open_snapshots() const noexcept;containsWhether a member equal to comparable is readable now.template <typename comparable_type_ = identifier_t>
expected<bool> contains(comparable_type_ && comparable) const noexcept;countHow many members equal comparable, which for a unique-key store is zero or one.template <typename comparable_type_ = identifier_t>
expected<std::size_t> count(
comparable_type_ && comparable) const noexcept;transactionOpens a transaction, fixing the snapshot every one of its reads will be answered at.expected<transaction_t> transaction() noexcept;expected<transaction_t> 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 up for every read and at snapshot_k for what it watched and wrote.
transaction_atOpens one shard's part of a transaction at an outside snapshot and generation.expected<transaction_t> 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_atA reader at a stamp somebody else pinned, for one partition of a sharded reader.reader_t reader_at(generation_t stamp) const noexcept;Registers nothing, so it must not outlive the claim that holds stamp.
join_orderSeats the order this store is a member of, for a wrapper that builds its parts and then moves them into place.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.
orderThe order this store was built into.order_type_ & order() noexcept;order_type_ const & order() const noexcept;findFinds a member equal to comparable as of the newest published commit.template <typename comparable_type_ = identifier_t, typename callback_found_type_ = no_op_t, typename callback_missing_type_ = no_op_t>
status_t find(
comparable_type_ && comparable,
callback_found_type_ && callback_found,
callback_missing_type_ && callback_missing = {}) const noexcept;comparable | in | Object comparable to value_t and convertible to identifier_t. |
|---|---|---|
callback_found | in | Callback to receive a value_t const &. Must be noexcept. |
callback_missing | in | Callback triggered if nothing was found. Must be noexcept. |
find_copyCopies out the member equal to comparable, or reports why it could not.template <typename comparable_type_ = identifier_t>
expected<value_t> find_copy(
comparable_type_ && comparable) const noexcept;key_compHow this store orders its keys, so a bounded walk can stop without guessing.comparator_t key_comp() const noexcept;The one ordering every read here descends on; a caller comparing keys any other way is ordering them differently from the store that holds them.
smallestHands callback_found the smallest member the newest published commit shows.template <typename callback_found_type_ = no_op_t, typename callback_missing_type_ = no_op_t>
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, 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. |
makeBuilds a store around an allocator, reported as a result rather than thrown.expected<store_t> make(allocator_t const & allocator = {}) noexcept;expected<store_t> make(
comparator_t const & comparator,
allocator_t const & allocator) noexcept;Builds a store around a specific comparator, for comparators that carry state.
visible_cursor_tA resumable walk over the keys one snapshot reads, yielding each key exactly once.class visible_cursor_tA 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.
Every read is delivered through peek, so nothing addressing the store escapes. Any write to the store abandons the cursor.
reader_tA read-only view pinned at one stamp, which records nothing and settles nothing.class reader_tEvery 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 provides with its partition locks.
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.
transaction_tA transaction reading at one snapshot and publishing under one commit stamp.class transaction_tpublication_tA group of writes over many keys that becomes visible under one stamp.class publication_tPublishing 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 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_policyParks a spent spin on std::atomic::wait, leaving the spin itself to pausing_policy_type_.4template <typename pausing_policy_type_ = bare_waiting_policy_t>
struct standard_waiting_policyThis 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.
pausingWhat a core does between attempts, asked once per attempt the spin spends.pausing_policy_type_ pausing;operator()Hands one spent attempt to the pausing policy, which is the whole of the spin here.template <typename watched_type_, typename value_type_, typename attempts_type_>
void operator()(
watched_type_ const & watched,
value_type_ const observed,
attempts_type_ const attempts_spent) const noexcept;wait_until_changedParks until watched stops reading observed, or until the wait returns spuriously.template <typename value_type_>
void wait_until_changed(
value_type_ const *watched,
value_type_ const observed) const noexcept;notify_waitersWakes every thread parked on watched.template <typename value_type_>
void notify_waiters(value_type_ *watched) const noexcept;versioned_storage_forHow a container family restates itself over version-decorated elements, and how one such entry is reached, replaced and taken back out.7template <typename collection_type_,
typename value_type_,
typename = void>
struct versioned_storage_forAn 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_datedThe same storage keyed by identifier and generation, holding one entry per version.template <typename element_type_>
using rebind_dated = rebind<element_type_>;Unchanged here, since the ordered comparator already breaks a tie on the generation.
buildBuilds an empty storage over element_type_, seeded from a bare comparator.template <typename element_type_, typename allocator_type_>
rebind<element_type_> build(
addressing_source_t const & source,
allocator_type_ const & allocator) noexcept;template <typename element_type_, typename allocator_type_>
rebind<element_type_> build(allocator_type_ const & allocator) noexcept;Builds an empty storage over element_type_, leaving the addressing defaulted.
siblingBuilds an empty storage over element_type_ addressed exactly as existing is.template <typename element_type_, typename storage_type_>
rebind<element_type_> sibling(storage_type_ const & existing) noexcept;allocator_ofThe allocator a storage of this family was built with.template <typename storage_type_>
decltype(auto) allocator_of(storage_type_ const & storage) noexcept;prepareA node-based core has nothing to prepay; the placeholder pass reserves it.template <typename storage_type_>
status_t prepare(storage_type_ &, std::size_t) noexcept;upsertFiles element under its own key, overwriting whatever shared it.template <typename storage_type_, typename element_type_>
status_t upsert(
storage_type_ & storage,
element_type_ && element) noexcept;extract_payloadTakes the entry filed under identifier out whole, handing its payload to destination.template <typename storage_type_, typename identifier_type_, typename payload_type_>
bool extract_payload(
storage_type_ & storage,
identifier_type_ const & identifier,
payload_type_ & destination) noexcept;Whether an entry was there to take.
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_atWhether a version stamped stamp is visible to a reader holding snapshot.bool visible_at(commit_stamp_t stamp, generation_t snapshot) noexcept;visible_nowWhether stamp was drawn at all, which is what a reader taking no snapshot asks.bool visible_now(commit_stamp_t stamp) noexcept;at_leastWhether offered is at least as strong a promise as required.bool at_least(isolation_t offered, isolation_t required) noexcept;absent_generation_kThe generation no stored entry can carry, standing for a key that is not there.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 reassigns - otherwise the watch stops matching itself.
latest_snapshot_kThe 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 sits above.generation_t latest_snapshot_k;Member types55locked_store::store_t | locked_store |
|---|---|
locked_store::order_t | order_type_ |
locked_store::inner_store_t | typename rebound_order_of<store_type_, order_t>::type |
locked_store::inner_transaction_t | typename inner_store_t::transaction_t |
locked_store::mutex_t | shared_mutex_type_ |
locked_store::value_t | typename inner_store_t::value_t |
locked_store::value_type | value_t |
locked_store::key_type | typename mapping_key_type_or_itself<value_t>::type |
locked_store::mapped_type | typename mapped_value_type_or_void<value_t>::type |
locked_store::is_associative | std::bool_constant<is_mapping<value_t>> |
locked_store::is_transactional | std::true_type |
locked_store::comparator_t | typename inner_store_t::comparator_t |
locked_store::identifier_t | typename inner_store_t::identifier_t |
locked_store::generation_t | typename inner_store_t::generation_t |
partitioned_store::store_t | partitioned_store |
partitioned_store::hash_t | hash_type_ |
partitioned_store::order_t | basic_commit_order<partitions_count_> |
partitioned_store::inner_store_t | typename rebound_order_of<store_type_, order_t>::type |
partitioned_store::inner_transaction_t | typename inner_store_t::transaction_t |
partitioned_store::mutex_t | shared_mutex_type_ |
partitioned_store::shared_lock_t | shared_lock<mutex_t> |
partitioned_store::unique_lock_t | unique_lock<mutex_t> |
partitioned_store::mutexes_t | std::array<padded_mutex_t, partitions_k> |
partitioned_store::epochs_t | std::array<padded_epoch_t, partitions_k> |
partitioned_store::partitions_t | std::array<inner_store_t, partitions_k> |
partitioned_store::partition_transactions_t | std::array<inner_transaction_t, partitions_k> |
partitioned_store::value_t | typename inner_store_t::value_t |
partitioned_store::value_type | value_t |
partitioned_store::key_type | typename mapping_key_type_or_itself<value_t>::type |
partitioned_store::mapped_type | typename mapped_value_type_or_void<value_t>::type |
partitioned_store::is_associative | std::bool_constant<is_mapping<value_t>> |
partitioned_store::is_transactional | std::true_type |
partitioned_store::comparator_t | typename inner_store_t::comparator_t |
partitioned_store::identifier_t | typename inner_store_t::identifier_t |
partitioned_store::generation_t | typename inner_store_t::generation_t |
snapshot_store::value_t | typename owned_value_of<collection_type_>::type |
snapshot_store::value_type | value_t |
snapshot_store::key_t | typename collection_type_::key_type |
snapshot_store::key_type | key_t |
snapshot_store::mapped_t | typename collection_type_::mapped_type |
snapshot_store::mapped_type | mapped_t |
snapshot_store::is_associative | typename collection_type_::is_associative |
snapshot_store::is_transactional | std::true_type |
snapshot_store::allocator_t | typename collection_type_::allocator_type |
snapshot_store::comparator_t | typename storage_shape_t::addressing_source_t |
snapshot_store::versioning_t | typename storage_shape_t::versioning_t |
snapshot_store::identifier_t | typename versioning_t::identifier_t |
snapshot_store::generation_t | typename versioning_t::generation_t |
snapshot_store::accessed_identifier_t | typename versioning_t::accessed_identifier_t |
snapshot_store::dated_identifier_t | typename versioning_t::dated_identifier_t |
snapshot_store::versioned_entry_t | versioned_t |
versioned_storage_for::versioning_t | versioning_for<value_type_, typename collection_type_::comparator_t> |
versioned_storage_for::addressing_source_t | typename collection_type_::comparator_t |
versioned_storage_for::addressing_t | typename versioning_t::versioned_comparator_t |
versioned_storage_for::rebind | typename collection_type_::template rebind<element_type_, addressing_t> |