# Containers

> SmashTable for C++

Terminology first, since both words are overloaded:

- "Concurrency" does not imply threads.
  Several transactions can be open on one thread.
- "Consistency" does not imply [strict serializability](https://jepsen.io/consistency/models/strict-serializable).
  [Weaker levels exist](https://jepsen.io/consistency/models), and each store here names the one it targets as a compile-time `isolation_k` rather than leaving you to infer it.

Headers group as:

```bash
  basic_*               → Cores. Own their memory, no transactions, one thread.
    ├─ basic_vector<T, Alloc>
    ├─ basic_avl_tree<T, Comparator, Alloc>
    ├─ basic_wb_tree<T, Comparator, Alloc>          # also `rank` and `select`
    ├─ basic_hash_table<T, Hash, Equals, Alloc>     # grows, iterates, rehashes
    ├─ basic_flat_set<T, Comparator, Kit, Alloc>    # sorted, one allocation, searched a row at a time
    ├─ basic_ring<T, Alloc>                         # first-in first-out, capacity fixed at `make`
    ├─ basic_hash_index<T, Index, Hash, Alloc, Kit> # keys to record positions, capacity fixed, no tombstones
    ├─ basic_fixed_pool<T, Index, Alloc>             # records taken and vacated by index, handles that go stale
    ├─ basic_growing_pool<T, Index, Alloc>     # the same in chunks that never move, read beside its growth
    └─ intrusive_list<Index>                        # first-in first-out through the records' own `next`

  Immutable, built once and never written
    ├─ immutable_b_tree<T, KeysPerRow, Kit, Alloc>     # keys on every level
    ├─ immutable_splus_tree<T, KeysPerRow, Kit, Alloc> # every key in the leaves, separators above
    ├─ immutable_elias_fano<T, Alloc>                  # non-decreasing integers in a few bits apiece
    └─ immutable_packed_array<T, Alloc>                # integers as distances from a base, one width each

  atomic_*              → Pinned core. Fixed capacity, atomic per slot, callback reads.
    └─ atomic_hash_table<T, Hash, Equals, Alloc>    # the one type that runs on a GPU
       ↑ ::adopt(std::move(growable).release())     ↓ ::adopt(std::move(pinned).release())

  atomic_intrusive_stack<T, Ref>  → any thread pushes, one takes all, no capacity

  *_store               → 2-phase commit, watch and CAS.
    ├─ monotonic_store<Core>                        # one visible version per key
    ├─ snapshot_store<Core>                         # every version a live reader can still name
    └─ reference_store<T, Comparator, Alloc>        # the same contract over `std::set`, kept as the oracle
       ↓ either of the first two wraps a core; either of these wraps a store
    ├─ locked_store<Store, Mutex>                   # one lock spans a whole commit
    └─ partitioned_store<Store, Hash, Mutex, N>     # one lock per partition, one shared commit order

  transaction_group<Stores...>  → One 2-phase commit spanning several stores
```

### Choosing a Container for a Concurrency Shape

The __Writers__ column of the table in [What's Inside](/docs/smashtable/#whats-inside) names how many threads may write, and the reader rule follows from it rather than standing beside it: a core's `const` methods are safe from any number of threads only while no thread is writing, since a probe reads slot metadata and node links a write is midway through changing.
The shape that gets this wrong most often is a cache behind a `mutable` member, filled on what its caller calls a read — a reader-writer lock held in shared mode admits several such calls at once, and each of them is a writer as far as the container is concerned.

Growth is the other half of the rule.
A core that can grow repoints the regions every live slot reference and every node pointer has already cached, so a container a second thread can reach must either be pinned at a capacity nobody exceeds, or reached through a wrapper that excludes.
`basic_growing_pool` is the one core whose growth repoints nothing: it adds chunks and never moves a record, so readers by index or handle need no claim while its one writer takes, vacates and grows.

|                                             | Reach for                                                            | Wrap in                              |
| :------------------------------------------ | :------------------------------------------------------------------- | :----------------------------------- |
| One thread, or many readers and no writer   | `basic_vector` · `basic_ring` · `basic_flat_set` · `basic_fixed_pool` | …                                    |
| The same, and ordered                       | `basic_avl_tree` · `basic_wb_tree`                                   | …                                    |
| The same, and keyed                         | `basic_hash_table` · `basic_hash_index`                              | …                                    |
| Built once from sorted keys, read forever   | `immutable_b_tree` · `immutable_splus_tree`                          | …                                    |
| Built once from sorted integers, compressed | `immutable_elias_fano`                                               | …                                    |
| Built once from integers in a narrow band   | `immutable_packed_array`                                             | …                                    |
| One writer growing, readers by index        | `basic_growing_pool`                                            | …                                    |
| Many threads, capacity fixed up front       | `atomic_hash_table`                                                  | …                                    |
| Many producers, one consumer draining whole | `atomic_intrusive_stack`                                             | …                                    |
| Many threads, and the container still grows | any core above                                                       | `locked_store` · `partitioned_store` |
| Versions a reader can still name            | `monotonic_store` · `snapshot_store` · `reference_store`             | either wrapper                       |
| One commit spanning several stores          | `transaction_group`                                                  | inherits its participants'           |

Both wrappers take their mutex as a template parameter, and that mutex takes two of its own: the reference its word is owned through, and the policy a waiting core follows.
The pinned table takes the same two directly, since its slot lock is the mutex it has.
A deployment that knows its hardware names both: a reference whose conditional add decides an acquire in one instruction, and a stall its cores actually have.
One that does not pays nothing for the question.

Transactions and thread-safety are two independent axes, not one ladder.
A wrapper takes its mutex per __call__, not across a transaction: `stage` and `commit` each take it and drop it in between, and only a group holds it from its validation to its publication.
What carries the inner store's level across that gap is the reservation staging made, since no other transaction can claim those keys until this one publishes or unwinds.
A store in no order gives its reader no stamp to hold, so a monotonic reader spanning partitions can catch a commit half-applied and only [Read Committed](https://jepsen.io/consistency/models/read-committed) survives — but a snapshot reader answers at its own stamp, and every partition belongs to one order, so it keeps Snapshot across all sixteen.
Every container publishes what it promises as `isolation_k`, so the level is checkable rather than folklore.
`atomic_hash_table` has no transactions at all — it offers per-__operation__ atomicity, which is a different product, and is why it is not a `*_store`.

`status_t` reports `out_of_memory_heap_k == ENOMEM`, `invalid_argument_k == EINVAL`, `key_not_found_k == ENOENT` and others, and is `[[nodiscard]]` on every mutating API.

### Making `std::set` Transactional

> `smashtable/reference_store.hpp`

The baseline reference design, and the yardstick the tree containers are held against — it runs the same test suites they do.
Updates group into transactions that stage and roll back before committing, which is what lets inter-dependent updates span several stores.

Reads are consistent at the [Monotonic Atomic View](https://jepsen.io/consistency/models/monotonic-atomic-view) level, so a transaction never sees another's partial update.
That is weaker than [Snapshot Isolation](https://jepsen.io/consistency/models/snapshot-isolation): there is no guarantee that every read within one transaction sees the same snapshot.
It keeps a version per key all the same, dated by a generation rather than by a shared commit stamp, which is why a watch is re-resolved at commit instead of compared against one.
`snapshot_store` is the sibling that does make that guarantee, and the section below states what it costs.

### Adelson-Velsky and Landis Trees

> `smashtable/basic_avl_tree.hpp`

Rarely called by its full name, the AVL tree is the simplest clean self-balancing binary search tree, from 1962.
`basic_avl_tree<value, comparator, allocator>` is an ordered store in the shape of `std::set` or `std::map`.
Standard libraries usually pick Red-Black trees; AVL balances more rigidly, trading slightly slower updates for faster lookups.

Its API differs from the STL where exception-free reporting demands it:

- `insert()` returns `std::pair<iterator, bool>`, as the STL does.
- `erase(iterator)` returns `erase_result_t { iterator next; status_t status; }`.
- Range `insert(first, last)` returns `status_t`.
- Hint-based `insert(hint, value)` and `emplace_hint()` are deleted, since AVL trees gain nothing from a hint.

### Weight-Balanced Trees

> `smashtable/basic_wb_tree.hpp`

`basic_wb_tree` balances on subtree sizes rather than heights, using Δ=3 and Γ=2 — the only proven integer solution, per Hirai and Yamamoto.
Storing sizes buys __order statistics__: `select(k)` finds the k-th smallest and `rank(x)` finds a key's position, both in O(log n).
That is what pagination, percentiles and quantiles need, and it is the one thing the AVL tree cannot offer.

Expect depth around 1.88 log₂(n) against AVL's 1.44, in exchange for O(1) amortized rotations per update.

### Flat Sets & Rings

> `smashtable/basic_flat_set.hpp` · `smashtable/basic_ring.hpp`

`basic_flat_set` is an ordered set in one contiguous allocation, growable and allocator-aware like `basic_avl_tree`, differing only in where elements live.
Inserting and erasing shift the tail, so it suits a few hundred elements rather than millions, in exchange for a search that reads adjacent memory and allocates nothing.
That search is the same row search the immutable trees below use, wherever the element is a `row_searchable_key` ordered by `less_t`, and a plain binary search otherwise — `basic_flat_set` takes the kit as its third template argument.
It answers the same `ordered_collection` surface the trees do — bounds, ranges and half-open erasure — so the shared suites hold it to the same contract.

`basic_ring` is a first-in first-out queue over one allocation whose capacity is a power of two fixed at `make`, for batching and read-ahead.
Two 32-bit counters of pushes and pops wrap together, so their difference is the size and a full ring is told from an empty one without a spare slot.

### Immutable B & S+ Trees

> `smashtable/immutable_b_tree.hpp` · `smashtable/immutable_splus_tree.hpp` · `smashtable/row_layout.hpp` · `smashtable/row_search.hpp`

Both are built once from a sorted span and never written again, so any number of threads may read one at once with no synchronization at all.
Both search a __row__ at a time rather than a key at a time — a row being a span wide enough to be worth one vectorized pass, 512 bytes by default, which is `default_row_bytes_k`.
`row_layout.hpp` says what a key may be and where each one sits in a row; `row_search.hpp` says how a row is searched.

`immutable_b_tree` stores nodes breadth-first with implicit children: node `i` holds one row of `B` keys and its children are nodes `i*(B+1)+j+1`.
A lookup reads one row per level and the rank adds up as the descent goes, with no subtree sizes stored.

`immutable_splus_tree` keeps every key in sorted leaves and copies separators onto the levels above.
A lookup lands on the leaf whose position __is__ the rank, so `select` is an index into the leaves.

Every kit the compiler can emit is compiled into the same artifact, each under its own target attributes, so no global instruction-set flag is needed.
`detect_row_kit()` probes the processor once and `visit_row_kit` hands the answer over as a __type__, so a tree instantiated over it calls its kit with no table and no branch per key.

```cpp
visit_row_kit(detect_row_kit(), [&](auto kit) {
    using tree_t = immutable_b_tree<std::uint64_t, 64, decltype(kit)>;
    // …built once, then read from any number of threads
});
```

Keys may be 32- or 64-bit of either signedness, or 16 bytes ordered as `memcmp`.
A 16-byte key is stored either interleaved or split into a column of high words and a column of low words, the low column read only where a high word ties.

`immutable_b_set` and `immutable_splus_set` hold bare keys; `immutable_b_map` and `immutable_splus_map` pair each key with a value.
A map keeps the rows byte-identical to its set twin and puts the values in one array the rank indexes, so every kit still loads a row of nothing but keys, and `mapped_at(rank)` costs one further cache line.

### Elias-Fano Sequences

> `smashtable/immutable_elias_fano.hpp`

`immutable_elias_fano` keeps non-decreasing integers - the offsets of variable-length rows, say - in at most 2 + ⌈log₂(universe / count)⌉ bits apiece, and `select(i)` reads the `i`-th one back in constant time.
The low bits of every value are packed side by side and the high bits are stored in unary, with every 256th set bit's position sampled, so a `select` jumps to a sample and counts a handful of words.
`make` takes the values whole, or pulls them in order through a callback, so a column of offsets streams in from storage without ever sitting in memory at full width.

```cpp
std::uint64_t const offsets[] = {0, 3, 3, 10, 42};
auto sequence = immutable_elias_fano<>::make(std::span<std::uint64_t const>(offsets));
std::uint64_t const row_bytes = sequence->select(3) - sequence->select(2); // 7
```

### Packed Arrays

> `smashtable/immutable_packed_array.hpp`

`immutable_packed_array` keeps unsigned integers between a base and a maximum as their distance from the base, in `bit_width(maximum - base)` bits apiece, and `array[i]` reads the `i`-th one back in constant time.
Values that all equal the base cost no words at all, so a column of commit stamps coded against the oldest live snapshot is free once nobody reads below it.
`immutable_elias_fano` keeps its low parts in one, based at zero.
`save` writes a three-word header and the packed words, and `immutable_packed_array_view` reads them in place from borrowed bytes at any alignment, so a memory-mapped file is read without a copy.

```cpp
std::uint64_t const stamps[] = {1000, 1003, 1001, 1007};
auto packed = immutable_packed_array<>::make(std::span<std::uint64_t const>(stamps)); // base 1000, 3 bits apiece
std::vector<std::byte> bytes(packed->saved_bytes());
_ = packed->save(bytes);
auto view = immutable_packed_array_view<>::make(bytes);
std::uint64_t const third = (*view)[2]; // 1001
```

### Transactional Stores

> `smashtable/monotonic_store.hpp`

`monotonic_store<Core>` adds two-phase commit, watches and CAS on top of any key-addressable core.
`monotonic_avl_set`, `monotonic_avl_map`, `monotonic_wb_set` and `monotonic_wb_map` are the aliases you'll name directly.
`monotonic_hash_set` and `monotonic_hash_map` back the same store with the open-addressed table, which supplies no ordering, so bounds, ranges and order statistics are gated out of those instantiations at compile time.

Which version a reader sees is decided by one number, stamped when a transaction commits.
A version that has not committed carries no stamp, so it is invisible to readers and cannot make anyone else's validation fail — a transaction that stages and then rolls back costs its peers nothing.
Two writers on one key are ordered by their stamps, and the later one wins.
That is a [lost update](https://jepsen.io/consistency/phenomena/p4), which this level permits: Monotonic Atomic View constrains what a reader observes, not what two writers do to each other, and a level that is available under partition provably cannot prevent it.
A writer that needs the first commit to win must `watch()` the key, or use a snapshot container, where the write set is validated whether you ask or not.

`find` never records what it read, here.
A read set is memory, and a read that allocates is a read that can fail, so on this engine the recording variant is a different name:

```cpp
_ = transaction.find(key, on_found, on_missing);             // answers, and records nothing
_ = transaction.find_and_watch(key, on_found, on_missing);   // records, and can report out of memory
```

Both return `status_t`, because a read that cannot write down what it read has to say so where it happened rather than poisoning the transaction silently until commit.
`snapshot_store` at `serializable_k` and above needs no second name: every read records, and every read reports.

An erase leaves a tombstone that readers skip, and `vacuum()` is what returns that space:

```cpp
expected<std::size_t> const reclaimed = store.vacuum();          // everything no reader can name
expected<std::size_t> const window = store.vacuum(lower, upper); // ordered cores, one slice at a time
```

### Snapshot Isolation

> `smashtable/snapshot_store.hpp`

`snapshot_store<Core>` is the sibling that fixes a transaction's reads to one instant, and it is where [multi-version concurrency control](https://en.wikipedia.org/wiki/Multiversion_concurrency_control) is at its most literal here: a transaction draws a snapshot when it opens, every read is answered from the newest version at or below that snapshot, and a writer never overwrites what a reader can still name.
It rebinds the same cores, exports `snapshot_avl_set`, `_avl_map`, `_wb_set`, `_wb_map`, `_hash_set` and `_hash_map`, and publishes `isolation_k == snapshot_k`.
A repeated read returns what it first saw, a repeated range admits no phantoms, and neither holds in its sibling.

The same template answers at three levels, selected by a second parameter rather than by a second implementation, and each has aliases of its own:

```cpp
snapshot_store<Core>                        // isolation_k == snapshot_k
serializable_store<Core>                    // reads validated too
strict_serializable_store<Core>             // and a commit waits for its own publication

serializable_avl_map<Key, Value>            // and `_avl_set`, `_wb_*`, `_hash_*`
strict_serializable_avl_map<Key, Value>     // the same six for the top rung
```

Versions are kept as ordinary entries keyed by `(key, generation)` rather than chained off one entry, on ordered and unordered cores alike.
The hash core still hashes the bare key, so every version of a key shares one probe run and a lookup walks that run instead of stopping at the first match.

Reclamation is the other half of multi-version concurrency control, and the whole of it here: old versions are freed against a low-water mark that sits at the oldest open snapshot, so it can never pass a snapshot somebody still holds, and it advances as soon as the oldest reader leaves rather than waiting for the last.
Pruning happens on every commit, and `vacuum()` reaches the keys nobody writes again.
There is no background thread and no epoch registry.
`clear()` refuses while a reader is open rather than dropping versions out from under it.

Range writes publish under one stamp, so a reader on an older snapshot sees all of a range erase or none of it.
`update_range` builds new versions rather than rewriting the visible one, which is what open readers make unsound.
`select` and `rank` descend on the weight-balanced tree's augmented count, exact at the newest commit — a reader at an older snapshot gets the merged walk instead, because one number per node cannot answer for an unbounded parameter.

What it costs, on an AVL core over `mapping<key, int>`:

|                               | `monotonic_store` | `snapshot_store`    |
| :---------------------------- | :---------------- | :------------------ |
| Resident per key, one version | 80 B              | 72 B                |
| Each retained older version   | 48 B chain node   | 72 B, a full entry  |
| Read of one key               | one chain head    | the key's whole run |

At rest it is the cheaper of the two, because a key carries no chain-head pointer and no per-entry allocator.
It becomes the more expensive one exactly when a long-lived reader pins history — and on the hash core a pinned version occupies a real slot, so it lengthens the probe runs of its neighbours as well.
With no transaction open the low-water mark sits at the newest commit and the whole version tail is freed on the next write, so a store nobody is reading costs what its sibling costs.

### Hash Tables

> `smashtable/basic_hash_table.hpp`

`hash_set<key>` and `hash_map<key, value>` are open-addressing containers with linear probing.
They differ from `google::dense_hash_map` and `tsl::robin_map` by not reserving sentinel key values for tombstones, by unpacking keys and values into disjoint arrays, and by carrying two bits of metadata per slot rather than a byte.

Keys and values live in separate regions, so a lookup that only compares keys never pulls values into cache — which is most of them, since a miss touches no value at all.
Thirty-two slots share one 64-bit header holding two parallel bitmasks, encoding free, deleted, populated and locked in two bits each.
Sixty-four bits is the widest atomic every target supports, which is what lets a whole bucket header move in one instruction.

Growing repoints the key, value and header regions that every live slot reference has cached, so a table that can grow can never be read concurrently.
The type system enforces that rather than a sentence: two types, neither of which includes the other's header.
`basic_hash_table` grows, iterates and rehashes; `atomic_hash_table` is pinned and atomic over the slot each operation touches.
What passes between them is the allocation itself — a `hash_storage` — so the hand-off is a move of a value rather than one table reaching into the other:

```cpp
_ = growable.reserve(1u << 20);                                          // pin the capacity first
auto pinned = atomic_hash_map<key_t, value_t>::adopt(std::move(growable).release());

_ = pinned.find(key, [](auto const &slot) noexcept { use(slot.value()); });
if (failed(pinned.emplace(key, value))) report_full();                   // a pinned table can fill up

auto compacted = hash_map<key_t, value_t>::adopt(std::move(pinned).release());   // iterators return
```

Every operation on the pinned table is atomic over the slot it touches: it takes that slot by setting both its bits with a `fetch_or` and releases it by posting the xor of the difference to the desired state, which reads nothing back, so neither path needs a compare-and-swap loop.
It is not lock-free, though — `fetch_or` spins until it wins the slot, so a thread descheduled while holding one blocks every other prober that walks onto it.
No global lock and no reallocation is what the pinning buys; a stalled thread stalling its neighbours is what it does not.
Reads take a callback rather than returning a reference or an iterator, since both would dangle the moment another thread erased the slot.
Tombstones only accumulate while pinned, because compaction needs a rehash — `deleted_count()` is what says it is time to hand the storage back.

Readers take the slot lock like writers do.
A reader that merely loaded the header would be unsound, and measurably so: the two bits per slot cannot distinguish "untouched" from "locked, rewritten and unlocked", because a completed write cycle restores exactly the bits the reader first saw.
Adding a per-bucket version counter would fix it and would cost half the slots per bucket, which is not worth breaking the one-warp-per-bucket geometry for.

Order-dependent operations are absent by construction: there is no `range`, `erase_range`, `lower_bound` or `select`.

> `smashtable/basic_hash_index.hpp`

`basic_hash_index` is the same layout serving another job: a fixed-capacity map from 4-, 8- or 16-byte keys to the positions of records kept elsewhere, such as a fixed pool's.
Its keys sit in the keys region, so a probe compares a window of them without loading a record, and a key may repeat, since it is often a hash of something longer: `find` takes a check that reads the record behind each match, and `erase` names the exact position.
A tombstone would make every later probe walk past the erased slot until a rehash, which a fixed-capacity index never runs, so an erase shifts the rest of its run back over the hole instead.
Every key stays reachable from its home, the deletion bits stay zero, and capacity is at most half the slots, so a run always ends at a free one and a table under constant churn probes no further than a fresh one.

`#include <smashtable/atomic_hash_table.hpp>`

`#include <smashtable/atomic_intrusive_stack.hpp>`

`#include <smashtable/basic_avl_tree.hpp>`

`#include <smashtable/basic_fixed_pool.hpp>`

`#include <smashtable/basic_flat_set.hpp>`

`#include <smashtable/basic_growing_pool.hpp>`

`#include <smashtable/basic_hash_index.hpp>`

`#include <smashtable/basic_hash_table.hpp>`

`#include <smashtable/basic_ring.hpp>`

`#include <smashtable/basic_vector.hpp>`

`#include <smashtable/basic_wb_tree.hpp>`

`#include <smashtable/hash_layout.hpp>`

`#include <smashtable/immutable_b_tree.hpp>`

`#include <smashtable/immutable_elias_fano.hpp>`

`#include <smashtable/immutable_packed_array.hpp>`

`#include <smashtable/immutable_splus_tree.hpp>`

`#include <smashtable/shared.hpp>`

`#include <smashtable/intrusive_list.hpp>`

`#include <smashtable/row_search.hpp>`

`#include <smashtable/partitioned_store.hpp>`

## hash_table_iterator

Forward iterator for hash tables using simplified slot-based addressing.

```cpp
template <typename value_type_,
          typename hasher_type_>
struct hash_table_iterator
```

Inherits the three region pointers and the slot index from `[hash_slot_ref](#hash_slot_ref)`, and adds a counter of unvisited slots. Implements `std::forward_iterator_tag` for sequential traversal.

`slots_remaining` counts the slots left to visit and reaching zero __is__ the end, which is what `is_end` and `isnt_end` report and what the `[end_sentinel_t](#end_sentinel_t)` comparisons consult. Two iterators compare equal when they name the same slot of the same keys region. `advance` steps to the next populated slot and must not run at the end, while `skip_non_populated` walks past free, deleted and locked slots until a populated one or the end is reached.

- `slots_remaining` `offset_t`

## no_augmentation_t

Marks a tree that keeps only [`size`](https://www.unum.cloud/docs/smashtable/cpp/isolation.md#size), leaving nodes byte-identical to an unaugmented build.

```cpp
struct no_augmentation_t
```

## no_augmented_count_t

Stand-in for the augmented counter in an unaugmented tree, occupying no bytes.

```cpp
struct no_augmented_count_t
```

## default_allocator

The allocator every container defaults to, over `::operator` `new` asked not to throw.

```cpp
template <typename value_type_>
struct default_allocator
```

[`std::allocator`](#allocator) would serve, and costs `<memory>`, some fifty thousand preprocessed lines, in headers that want nothing else from it. Exhaustion is reported by returning null, which is the shape every caller here already checks, rather than by an exception nothing would catch.

## less_t

Transparent ordering and equality, so a container needs no `<functional>`.

```cpp
struct less_t
```

Both are heterogeneous - the `is_transparent` tag is what lets a lookup compare a key against something merely comparable to it, without materializing a key first - which is the only property the containers here relied on `std::less` and `std::equal_to` for.

## hash

The hash a container uses unless told otherwise.

```cpp
template <typename key_type_,
          typename = void>
struct hash
```

Specialize it for your own key.

Deliberately not a forward to `std::hash:` that would drag `<functional>` into every header, and the point of a named trait is that an unhashable key says so at compile time. Hashing the bytes of an arbitrary type instead would be worse than an error - padding, or an equality that ignores some field, would give two equal keys different hashes and quietly lose lookups.

## moving_pointer

Reads a contiguous run as rvalues, so a bulk write moves its staged copies rather than copying them again.

```cpp
template <typename value_type_>
struct moving_pointer
```

- `position` `value_type_ *`

## reversed_iterator

Walks a bidirectional `iterator_type_` backwards, standing one position past the element it reads, so the reversed begin is the forward end.

```cpp
template <typename iterator_type_>
class reversed_iterator
```

## end_sentinel_t

Sentinel type for range-based iteration end conditions.

```cpp
struct end_sentinel_t
```

## assume_reserved_t

Tag to assume capacity is pre-allocated, skip null checks.

```cpp
struct assume_reserved_t
```

Similar to `std::adopt_lock` for assuming preconditions are met.

See also: [https://en.cppreference.com/w/cpp/thread/lock_tag_t](https://en.cppreference.com/w/cpp/thread/lock_tag_t)

## assume_uninitialized_t

Tag to leave new elements unconstructed, for storage a kernel or a byte copy writes first.

```cpp
struct assume_uninitialized_t
```

## assume_unique_t

Tag to assume elements are unique, skip equality comparisons.

```cpp
struct assume_unique_t
```

Similar to Boost.Container's `ordered_unique_range_t`.

## assume_sorted_t

Tag to assume the input range is ascending, which buys an O(n) bulk build.

```cpp
struct assume_sorted_t
```

Warnings: An unsorted range is undefined behaviour, not a refusal.

## descending_t

Asks an ordered walk for its members greatest first.

```cpp
struct descending_t
```

## unbounded_t

Stands for the missing upper end of a range, so a walk bounded above runs to the last member.

```cpp
struct unbounded_t
```

## incumbent_policy_t

What an absorbed batch does with a key the destination already holds.

```cpp
enum incumbent_policy_t
```

Implementation vocabulary rather than a tag: a caller picks between these by naming a verb, and the three verbs share one staging helper that this tells apart.

- `keeps_the_incumbent_k`: The element already stored stays, and the newcomer is dropped.
- `takes_the_newcomer_k`: The newcomer takes the key, overwriting what was stored under it.
- `refuses_the_newcomer_k`: Neither is stored: a key arriving over one already there refuses the whole batch.

## algebra_t

Which members of the two sides a walk keeps.

```cpp
enum algebra_t
```

- `union_k`
- `intersection_k`
- `difference_k`
- `symmetric_difference_k`

## membership_t

Whether the side being walked is the only one holding a member, or both are.

```cpp
enum membership_t
```

- `on_one_side_k`
- `on_both_sides_k`

## ring_eviction_t

Whether [`push_evicting`](#push_evicting) had to drop the oldest element to make room.

```cpp
enum ring_eviction_t
```

- `kept_every_element_k`
- `evicted_oldest_k`

## hash_bucket_head_t

Bucket header containing metadata for [`hash_bucket_capacity_k`](#hash_bucket_capacity_k) slots.

```cpp
union hash_bucket_head_t
```

Two parallel 32-bit bitmasks - population, deletion - give each slot two bits, four states.

#### Slot State Encoding

Each slot's state is determined by corresponding bits in both masks:

- `00` (populations=0, deletions=0): Free slot, never used or fully freed
- `01` (populations=0, deletions=1): Deleted slot, tombstone from lazy deletion
- `10` (populations=1, deletions=0): Populated slot with valid key-value pair
- `11` (populations=1, deletions=1): Locked slot, temporarily held for atomic operations
`lanes` exposes the two 32-bit halves separately - `populations` has a set bit for every populated or locked slot, `deletions` one for every deleted or locked slot. `u64` views both at once, which is what enables atomic operations on the entire header (2 × 32 bits = 64 bits).

- `lanes` `struct ashvardanian::smashtable::hash_bucket_head_t::@376061242304273247160011120072252265272354277145`
- `u64` `std::uint64_t`

## hash_slot_state_t

The four states a slot can be in, spelled out by the two header lanes.

```cpp
enum hash_slot_state_t
```

- `free_k` = `0`: Never used, or fully freed.
- `deleted_k` = `1`: Tombstone left behind by a lazy deletion.
- `populated_k` = `2`: Holds a live key, and a value when the table is a map.
- `locked_k` = `3`: Temporarily held by a thread performing an atomic operation.

## hash_slots_count_t

Scaling schema that computes the required number of slots for a target element count.

```cpp
struct hash_slots_count_t
```

Caps the load factor at 75%, through a 4/3 multiplier, so linear probing cannot degenerate, and rounds every slot count up to a power of two so the modulo is a bitwise AND.

The 75% load factor strikes a balance between memory efficiency and probe length:

- Too high (>85%): Linear probing degrades into long search chains
- Too low (<60%): Wastes memory without significant performance gain
- 75%: Industry standard, keeps average probe length under 2 hops`raw` carries the widened count itself. The primary constructor budgets for a target __element__ count and applies the load factor, while `from_slots` takes the slot count directly, for callers that already sized the storage. `is_addressable` reports whether the probe masks can address the count, which requires a power of two.

A request too large to round up to a power of two keeps `unrepresentable_k`, which is not a power of two and therefore not addressable, so the factories refuse it instead of silently handing back the smallest possible table.

- `unrepresentable_k` `std::size_t`: A count that no power of two covers, and which `is_addressable` therefore rejects.
- `raw` `std::size_t`

Notes: The minimum slot count equals [`hash_bucket_capacity_k`](#hash_bucket_capacity_k), at least one full bucket.

## hash_layout_for

Metadata extraction template that derives type information for hash table elements.

```cpp
template <typename value_type_,
          typename hasher_type_>
struct hash_layout_for
```

Computes element types, sizes and alignment requirements from the element and hasher parameters, and takes the hasher's return type as the `offset_t` that indexes slots.

Provides three views of a stored element:

- `value_t:` mutable reference pair `mapping<key const&, mapped&>` for iteration.
- `value_const_t:` immutable reference pair `mapping<key const&, mapped const&>` for lookups.
- `value_copy_t:` owned pair `mapping<key, mapped>` for extraction.

- `has_values_k` `bool`
- `bytes_for_keys_k` `std::size_t`
- `bytes_for_values_k` `std::size_t`
- `bytes_in_bucket_k` `std::size_t`

See also: std::hash reference: [https://en.cppreference.com/w/cpp/utility/hash](https://en.cppreference.com/w/cpp/utility/hash)

## default_hash_t

Defers to [`hash`](#hash) for whatever key arrives, rather than fixing one at declaration.

```cpp
struct default_hash_t
```

## hash_slot_ref

Smart reference to a hash table slot, addressing it as base pointers plus a slot index.

```cpp
template <typename value_type_,
          typename hasher_type_>
struct hash_slot_ref
```

Probing advances `slot_` by one, so a step costs a single integer increment rather than three pointer recomputations. Sets carry no values region and leave `values_` null.

`keys_`, `values_` and `headers_` are the bases of the three regions, the first two indexed by the absolute `slot_` and the last by the bucket that owns it. The aliases restate the layout's own key, value, element and offset types, plus `dereference_t`, which is the element view for maps and a key reference for sets.

[`header_ref`](#header_ref) and `mask_in_bucket` resolve the owning header and the single bit inside it; `key`, `key_ref`, `value` and `value_ref` reach the two payload regions; the `is_` and `mark_` families read and write the slot's two bits. Locking is what a threaded reference overrides, so here [`lock`](#lock), [`unlock`](#unlock) and `try_lock` collapse to nothing.

- `has_values_k` `bool`

## hash_window_slots_t

The slots of a window a probe may still match, and whether a free slot ends the probe there.

```cpp
struct hash_window_slots_t
```

- `candidates` `hash_bucket_mask_t`
- `ends_probe` `bool`

## packed_array_header_t

What [`save`](#save) writes ahead of the packed words, one 64-bit word per field, so a view needs nothing else to read them.

```cpp
struct packed_array_header_t
```

- `count` `std::uint64_t`: How many values the array holds.
- `base` `std::uint64_t`: The distance every stored value is measured from.
- `bits` `std::uint64_t`: How many bits each value takes.

## splus_tree_header_t

What [`save`](#save) writes ahead of the rows, one 64-bit word per field, so a view refuses a tree of another shape.

```cpp
struct splus_tree_header_t
```

- `count` `std::uint64_t`: How many keys the tree holds.
- `keys_per_row` `std::uint64_t`: How many keys one row holds.
- `key_bytes` `std::uint64_t`: How many bytes one key takes.
- `mapped_bytes` `std::uint64_t`: How many bytes one mapped value takes, zero for a set.

## row_kit_t

The kits, one enumerator per microarchitecture, newest instruction sets after the baseline.

```cpp
enum row_kit_t
```

- `serial_k`
- `haswell_k`
- `skylake_k`
- `icelake_k`
- `neon_k`
- `sve_k`
- `rvv_k`
- `v128_k`

## haswell_row_kit_t

AVX2 over four 64-bit or eight 32-bit keys per load, unsigned order by flipping the sign bit.

```cpp
struct haswell_row_kit_t
```

- `kit_k` `row_kit_t`
- `compiled_k` `bool`
- `mask_equal_width_k` `std::size_t`

## skylake_row_kit_t

AVX-512 over eight 64-bit or sixteen 32-bit keys per load, masked loads over a scalar tail.

```cpp
struct skylake_row_kit_t
```

- `kit_k` `row_kit_t`
- `compiled_k` `bool`
- `mask_equal_width_k` `std::size_t`

## icelake_row_kit_t

The Skylake kit plus `VPOPCNTQ`, counting eight words of a bit vector per instruction, and a `PDEP` every such core runs in hardware, unlike the microcoded one of the Zen 2 parts the Haswell kit also serves.

```cpp
struct icelake_row_kit_t
```

- `kit_k` `row_kit_t`

## neon_row_kit_t

Advanced SIMD over two 64-bit or four 32-bit keys per load, deinterleaving keys as it loads.

```cpp
struct neon_row_kit_t
```

- `kit_k` `row_kit_t`
- `compiled_k` `bool`
- `mask_equal_width_k` `std::size_t`

## sve_row_kit_t

Scalable vectors sized to whatever the processor offers, a loop predicate over a scalar tail.

```cpp
struct sve_row_kit_t
```

- `kit_k` `row_kit_t`
- `compiled_k` `bool`
- `mask_equal_width_k` `std::size_t`

## rvv_row_kit_t

RISC-V vectors at whatever length the processor grants per step, with no tail.

```cpp
struct rvv_row_kit_t
```

- `kit_k` `row_kit_t`
- `compiled_k` `bool`
- `mask_equal_width_k` `std::size_t`

## v128_row_kit_t

WebAssembly SIMD over two 64-bit or four 32-bit keys per load; unsigned 64-bit order by flipping the sign bit, since the instruction set compares 64-bit lanes only as signed.

```cpp
struct v128_row_kit_t
```

- `kit_k` `row_kit_t`
- `compiled_k` `bool`
- `mask_equal_width_k` `std::size_t`

## atomic_hash_table

A fixed-capacity open-addressed table whose operations are atomic over the slot they touch, through per-slot spin locks, and over nothing wider.

```cpp
template <typename value_type_,
          typename hasher_type_ = default_hash_t,
          typename equals_type_ = equal_to_t,
          allocator_of<std::byte> allocator_type_ = default_allocator_t,
          waiting_policy<std::uint64_t const *, std::uint64_t> waiting_policy_type_ = bare_waiting_policy_t,
          template<typename> class atomic_reference_ = atomic_ref>
class atomic_hash_table
```

Built by adopting an allocation someone else sized, which is what guarantees the capacity was reserved before any thread could observe the table.

Warnings: Not lock-free. A slot is held between [`lock`](#lock) and [`unlock`](#unlock), so a thread stopped in between blocks every other prober that reaches that slot; see the file header.

## value_t

Every stored element: the key itself for a set, a [`mapping`](https://www.unum.cloud/docs/smashtable/cpp/stored-types.md#mapping) of both halves for a map.

```cpp
using value_t = typename layout_t::value_t;
```

## key_t

The key half, which is the whole element for a set.

```cpp
using key_t = typename layout_t::key_t;
```

## mapped_t

The mapped half, `void` for a set.

```cpp
using mapped_t = typename layout_t::mapped_t;
```

## key_type

STL-compatibility definitions, narrowed to what a pinned table can honestly provide.

```cpp
using key_type = key_t;
```

## is_associative

Traits the transactional adapters dispatch on.

```cpp
using is_associative = std::bool_constant<has_values_k>;
```

## atomic_hash_table

```cpp
atomic_hash_table(hasher_t hasher = {}, equals_t equals = {}) noexcept;
```

```cpp
atomic_hash_table(atomic_hash_table && other) noexcept;
```

```cpp
atomic_hash_table(atomic_hash_table const &)=delete;
```

## operator=

```cpp
atomic_hash_table & operator=(atomic_hash_table && other) noexcept;
```

```cpp
atomic_hash_table & operator=(atomic_hash_table const &)=delete;
```

## *

Surrenders the allocation, leaving this table empty.

```cpp
storage_t release() &&noexcept;
```

## swap

A cheap copy-less exchange of the allocation and the two functors.

```cpp
void swap(atomic_hash_table & other) noexcept;
```

## size

Live elements.

```cpp
offset_t size() const noexcept;
```

Read atomically but relaxed, so it may lag a concurrent writer - the count is a statistic here, and other threads are moving it while this returns.

## capacity

Slots this table will never exceed, since it cannot grow.

```cpp
offset_t capacity() const noexcept;
```

## deleted_count

Tombstones left by [`erase`](https://www.unum.cloud/docs/smashtable/cpp/isolation.md#erase), which only ever grow while the table is pinned.

```cpp
offset_t deleted_count() const noexcept;
```

Compaction needs a rehash, so this is the signal to hand the storage to a growable table.

## find

Invokes one of the two callbacks, the found one under the matching slot's lock.

```cpp
template <typename comparable_key_type_, typename callback_found_type_, typename callback_missing_type_ = no_op_t>
status_t find(
    comparable_key_type_ && wanted,
    callback_found_type_ && callback_found,
    callback_missing_type_ && callback_missing = {}) const noexcept;
```

Reads arrive through a callback rather than a reference, since a concurrent erase would invalidate anything handed back.

## contains

Reports whether a key equivalent to `wanted` is present.

```cpp
template <typename comparable_key_type_>
expected<bool> contains(comparable_key_type_ && wanted) const noexcept;
```

- `wanted` (in): Key to probe for.

## at

Deleted: a reference into a slot is invalid the moment another thread erases it.

```cpp
template <typename comparable_key_type_ = key_t const &>
void at(comparable_key_type_ &&)=delete;
```

## begin

Deleted: a snapshot of a table other threads are mutating is not a snapshot.

```cpp
void begin()=delete;
```

## emplace

Inserts, or overwrites the value when the key is already present.

```cpp
template <typename convertible_key_type_, typename convertible_mapped_type_>
status_t emplace(
    convertible_key_type_ && key,
    convertible_mapped_type_ && value) noexcept;
```

```cpp
template <typename convertible_key_type_>
status_t emplace(convertible_key_type_ && key) noexcept;
```

Inserts the key, doing nothing when an equal one is already present.

Statuses: - [`capacity_exhausted_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#capacity_exhausted_k) No slot along the probe sequence was free. A pinned table can genuinely fill up, so this reports rather than asserts.

Statuses: - [`capacity_exhausted_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#capacity_exhausted_k) No slot along the sequence was free.

## update

Overwrites the value of an existing key, doing nothing when it is absent.

```cpp
template <typename comparable_key_type_, typename convertible_mapped_type_>
status_t update(
    comparable_key_type_ && key,
    convertible_mapped_type_ && new_value) noexcept;
```

Notes: Contention has no status of its own: a taken slot is waited on rather than refused.

Statuses: - [`key_not_found_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#key_not_found_k) No equal key was there.

## erase

Leaves a tombstone rather than freeing the slot, so probe sequences stay intact.

```cpp
template <typename comparable_key_type_>
status_t erase(comparable_key_type_ && key) noexcept;
```

Notes: Contention has no status of its own: a taken slot is waited on rather than refused.

Statuses: - [`key_not_found_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#key_not_found_k) No equal key was there.

## *

Takes ownership of an allocation another table built.

```cpp
atomic_hash_table adopt(
    storage_t && storage,
    hasher_t hasher = {},
    equals_t equals = {}) noexcept;
```

## atomic_intrusive_stack

The newest of a stack of records linked newest first, pushed from any thread and taken whole by one.

```cpp
template <pointer_linked record_type_,
          template<typename> class atomic_reference_ = atomic_ref>
class atomic_intrusive_stack
```

## push

Pushes `record`, which no other thread may reach until it is taken.

```cpp
void push(record_t & record) noexcept;
```

## push_chain

Pushes the records linked from [`newest`](#newest) down to [`oldest`](#oldest), whose `next` is overwritten, in one step, so the taker meets them together and in that order.

```cpp
void push_chain(record_t & newest, record_t & oldest) noexcept;
```

## take_all

Takes every record pushed so far, the newest first and linked through `next`, or null.

```cpp
record_t * take_all() noexcept;
```

## basic_avl_node

Non-owning tree node structure for the AVL-Tree implementation, unaware of memory management.

```cpp
template <typename value_type_,
          typename comparator_type_>
class basic_avl_node
```

Provides static methods for all tree operations: search, insertion, deletion, and traversal. All operations are exception-free and `noexcept`.

#### Implementation Notes

AVL trees are self-balancing binary search trees where the height difference between left and right subtrees is at most 1. This "node" class implements the core tree logic including rotations and rebalancing, but doesn't participate in memory management or promise anything all-or-nothing - `[basic_avl_tree](#basic_avl_tree)` does both.

Features:

- Never throws exceptions, even on allocation failure
- Implements [`lower_bound`](https://www.unum.cloud/docs/smashtable/cpp/isolation.md#lower_bound) and [`upper_bound`](https://www.unum.cloud/docs/smashtable/cpp/isolation.md#upper_bound) for iterator-free navigation
- Supports random sampling within ranges for statistical operations
- All methods are static and work on raw node pointers for flexibility
Layout: `payload` is the stored entry, `left`, `right` and `parent` the links, and [`height`](#height) the longest downward path to a leaf. The root carries the biggest [`height`](#height) in the tree, a non-NULL node has at least one, and zero occurs only in the uninitialized detached state - which makes `1` << height an upper bound on the branch size.

## node_placement_t

What a walk that may create a node did with the key it was handed.

```cpp
enum node_placement_t
```

- `refused_k`: No node was available to store the key, so nothing was stored.
- `matched_k`: An equal key was already there, and `match` names the node holding it.
- `made_k`: A fresh node took the key, and `match` names it.

## is_balanced

Whether `node's` children differ in height by one at most, and link back to it.

```cpp
bool is_balanced(node_t *node) noexcept;
```

## find_successor

Finds the next node in in-order traversal (successor).

```cpp
node_t * find_successor(node_t *node) noexcept;
```

- `node` (in): The node to find the successor for.

## find_predecessor

Finds the previous node in in-order traversal (predecessor).

```cpp
node_t * find_predecessor(node_t *node) noexcept;
```

- `node` (in): The node to find the predecessor for.

## lowest_common_ancestor

Searches for the lowest common ancestor of two keys.

```cpp
template <typename comparable_a_type_, typename comparable_b_type_>
node_t * lowest_common_ancestor(
    node_t *node,
    comparable_a_type_ && a,
    comparable_b_type_ && b,
    comparator_t const & comparator) noexcept;
```

- `node` (in): The root of the subtree to search.
- `a` (in): The first key.
- `b` (in): The second key.
- `comparator` (in): The comparator instance (may be stateful).

## range

Iterates over a range of entries.

```cpp
template <typename lower_type_, typename upper_type_, typename callback_type_>
walk_control_t range(
    node_t *node,
    lower_type_ && low,
    upper_type_ && high,
    comparator_t const & comparator,
    callback_type_ && callback) noexcept;
```

- `node` (in): The root of the subtree to search.
- `low` (in): The lower bound of the range, included.
- `high` (in): The upper bound of the range, excluded.
- `comparator` (in): The comparator instance (may be stateful).
- `callback` (in): The function to call for each node in the range.

## equal_range

Locates the nodes bounding all entries equal to `comparable`.

```cpp
template <typename comparable_type_>
node_interval_t equal_range(
    node_t *node,
    comparable_type_ && comparable,
    comparator_t const & comparator) noexcept;
```

## sample

Random samples a single node using reservoir sampling for uniform distribution.

```cpp
template <typename generator_type_>
requires uniform_random_bits<std::remove_cvref_t<generator_type_>>
node_t * sample(node_t *node, generator_type_ && generator) noexcept;
```

- `node` (in): Root of subtree.
- `generator` (inout): Any STL-compatible random number generator.

Notes: Uses single-pass reservoir sampling for O(n) time with true uniform distribution.

## sample_range

Random samples nodes within a given range of keys using reservoir sampling.

```cpp
template <typename generator_type_, typename lower_type_, typename upper_type_, typename predicate_type_>
requires uniform_random_bits<std::remove_cvref_t<generator_type_>> && std::predicate<predicate_type_ &, node_t *>
node_t * sample_range(
    node_t *node,
    lower_type_ && low,
    upper_type_ && high,
    comparator_t const & comparator,
    generator_type_ && generator,
    predicate_type_ && predicate) noexcept;
```

```cpp
template <typename generator_type_, typename lower_type_, typename upper_type_, typename predicate_type_, indexed_writable_iterator<value_t> output_iterator_type_>
requires uniform_random_bits<std::remove_cvref_t<generator_type_>> && std::predicate<predicate_type_ &, node_t *>
void sample_range(
    node_t *node,
    lower_type_ && low,
    upper_type_ && high,
    comparator_t const & comparator,
    generator_type_ && generator,
    predicate_type_ && predicate,
    std::size_t & seen,
    std::size_t reservoir_capacity,
    output_iterator_type_ && reservoir) noexcept;
```

Multi-sample reservoir sampling for k uniform random nodes in range.

- `node` (in): Root of subtree.
- `low` (in): Lower bound.
- `high` (in): Upper bound.
- `comparator` (in): Comparator instance (may be stateful).
- `generator` (inout): Any STL-compatible random number generator.
- `predicate` (in): Predicate to filter nodes.
- `seen` (inout): Count of matching nodes processed (can span multiple calls).
- `reservoir_capacity` (in): Maximum number of samples to collect.
- `reservoir` (out): Buffer the samples land in, written by index.

Notes: Uses single-pass reservoir sampling for O(n) time with uniform distribution.

Notes: Uses Algorithm R (reservoir sampling) for uniform k-sample in single pass.

## build_from_sorted

Builds a balanced AVL tree from sorted range in O(n) time.

```cpp
template <multipass_iterator iterator_type_, allocator_of<node_t> node_allocator_type_>
build_result_t build_from_sorted(
    iterator_type_ first,
    std::size_t count,
    node_allocator_type_ & allocator) noexcept;
```

Precondition: Range [first, first+count) must be sorted according to comparator.

- `first` (in): Iterator to beginning of sorted range.
- `count` (in): Number of elements in range.
- `allocator` (inout): Hands back a raw node, or `nullptr` when it cannot.

Notes: Complexity: O(n) time, O(log n) recursion depth. Builds perfectly balanced tree by recursively picking middle element as root.

Warnings: If precondition violated (unsorted input), resulting tree has undefined structure.

Notes: A range handing out rvalues, as a move iterator does, gives its elements up.

Statuses: - Any status an element's [`copy`](#copy) returns passes through unchanged.

## extract

Pops the root replacing it with one of descendants, if present.

```cpp
extract_result_t extract(
    node_t *node,
    comparator_t const & comparator) noexcept;
```

```cpp
template <typename comparable_type_>
extract_result_t extract(
    node_t *node,
    comparable_type_ && comparable,
    comparator_t const & comparator) noexcept;
```

Searches for a matching ancestor and extracts it out.

- `node` (in): Node to extract.
- `comparator` (in): Comparator for element comparison.
- `comparable` (in): Any key comparable with stored entries.

## join_with_root

Joins two trees with a root node between them.

```cpp
node_t * join_with_root(
    node_t *left,
    node_t *root_node,
    node_t *right,
    comparator_t const & comparator) noexcept;
```

Precondition: All elements in left < root < all elements in right. Maintains AVL balance property.

- `left` (in): Left subtree (all elements < root).
- `root_node` (in): Root node to insert between subtrees.
- `right` (in): Right subtree (all elements > root).
- `comparator` (in): Comparator for element comparison.

## join

Joins two AVL trees into one.

```cpp
node_t * join(
    node_t *left,
    node_t *right,
    comparator_t const & comparator) noexcept;
```

Precondition: All elements in left < all elements in right. Maintains AVL balance property.

- `left` (in): Left tree (smaller elements).
- `right` (in): Right tree (larger elements).
- `comparator` (in): Comparator for element comparison.

## split

Splits an AVL tree at a key: elements less than it go to the left tree, `>=` to the right tree, and both keep the AVL balance property.

```cpp
template <typename comparable_type_>
split_result_t split(
    node_t *node,
    comparable_type_ && comparable,
    comparator_t const & comparator) noexcept;
```

- `node` (in): Root of the tree to split.
- `comparable` (in): Key to split at.
- `comparator` (in): Comparator for element comparison.

## merge_split_based

Merges two AVL trees using split-based divide-and-conquer.

```cpp
node_t * merge_split_based(
    node_t *small,
    node_t *large,
    comparator_t const & comparator) noexcept;
```

Optimal for unbalanced sizes: O(m log(n/m + 1)) where m <= n. Takes root of smaller tree, splits larger tree around it, recursively merges.

- `small` (in): Smaller tree to merge (will be consumed).
- `large` (in): Larger tree to merge into (will be consumed).
- `comparator` (in): Comparator for element comparison.

Notes: Both input trees are consumed, ownership transferred, balance kept throughout.

See also: Blelloch et al., "Just Join for Parallel Ordered Sets", 2016

## tree_to_spine

Converts AVL tree to right-leaning spine (degenerate vine).

```cpp
node_t * tree_to_spine(node_t *root, std::size_t & count) noexcept;
```

A spine is a sorted linked list using right pointers, all left pointers null.

- `root` (in): Tree to convert.
- `count` (out): Number of nodes in resulting spine.

Notes: Uses rotations to flatten tree: O(n) time, O(1) space.

## merge_spines

Merges two sorted spines into one sorted spine.

```cpp
node_t * merge_spines(
    node_t *first_spine,
    node_t *second_spine,
    comparator_t const & comparator) noexcept;
```

- `first_spine` (in): First sorted spine.
- `second_spine` (in): Second sorted spine.
- `comparator` (in): Comparator for element comparison.

Notes: O(n+m) time, O(1) space. Just like merging sorted linked lists.

## spine_to_balanced

Converts sorted spine back to balanced AVL tree (Day-Stout-Warren algorithm).

```cpp
node_t * spine_to_balanced(node_t *spine, std::size_t count) noexcept;
```

- `spine` (in): Head of spine.
- `count` (in): Number of nodes in spine.

Notes: O(n) time using rotations to build perfectly balanced tree.

See also: Stout & Warren, "Tree Rebalancing in Optimal Time and Space", 1986

## merge_dsw

Merges two AVL trees using Day-Stout-Warren spine algorithm.

```cpp
node_t * merge_dsw(
    node_t *first_tree,
    node_t *second_tree,
    comparator_t const & comparator,
    std::size_t & out_size) noexcept;
```

Best for large similarly-sized trees: O(n+m) time, O(1) space. Flattens both trees to spines, merges spines, rebuilds balanced tree.

- `first_tree` (in): First tree to merge (will be consumed).
- `second_tree` (in): Second tree to merge (will be consumed).
- `comparator` (in): Comparator for element comparison.
- `out_size` (out): Total number of nodes in result.

Notes: High constant factor due to many rotations, but O(1) space. Both input trees are consumed, ownership transferred.

See also: Stout & Warren, "Tree Rebalancing in Optimal Time and Space", 1986

See also: [https://en.wikipedia.org/wiki/Day%E2%80%93Stout%E2%80%93Warren_algorithm](https://en.wikipedia.org/wiki/Day%E2%80%93Stout%E2%80%93Warren_algorithm)

## *

The node of the subtree at `node` holding `comparable`, or `nullptr`.

```cpp
node_t * find(
    node_t *node,
    comparable_type_ const & comparable,
    comparator_t const & comparator) noexcept;
```

- `find`: node `node_t`, comparator `comparator_t &`
- `find`: node `node_t`, comparator `comparator_t &`
- `find`: node `node_type_`, comparator `comparator_type_ &`

## lower_*_bound

The first node of the subtree at `node` not ordered below `comparable`, or `nullptr`.

```cpp
node_t * lower__bound(
    node_t *node,
    comparable_type_ const & comparable,
    comparator_t const & comparator) noexcept;
```

- `lower_bound`: node `node_t`, comparator `comparator_t &`
- `lower_bound`: node `node_t`, comparator `comparator_t &`
- `lower_bound`: node `node_type_`, comparator `comparator_type_ &`

## upper_*_bound

The first node of the subtree at `node` ordered above `comparable`, or `nullptr`.

```cpp
node_t * upper__bound(
    node_t *node,
    comparable_type_ const & comparable,
    comparator_t const & comparator) noexcept;
```

- `upper_bound`: node `node_t`, comparator `comparator_t &`
- `upper_bound`: node `node_t`, comparator `comparator_t &`
- `upper_bound`: node `node_type_`, comparator `comparator_type_ &`

## build_result_t

What a bulk build produced, and why it stopped where it did.

```cpp
struct build_result_t
```

Not an [`expected`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#expected), which holds a value or a reason and never both: a refused build still owns every node it made, and whoever asked for it has to free them.

- `root` `node_t *`: Everything that was built, which the owner frees whether the build finished or not.
- `status` `status_t`: Why the build stopped: a refused node, a refused element copy, or [`success_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#success_k).
- `count` `std::size_t`: How many nodes hang off [`root`](#root), short of the range length on a partial build.

## split_result_t

Result of a split operation.

```cpp
struct split_result_t
```

- `left` `node_t *`: Subtree with all elements ordered before the split key.
- `right` `node_t *`: Subtree with all elements not ordered before the split key.

## basic_avl_tree

Exception-free AVL tree container with ordered storage similar to `std::set`, managing allocation and providing high-level tree operations with status-based error handling.

```cpp
template <typename value_type_,
          typename comparator_type_ = less_t,
          typename allocator_type_ = std::allocator<basic_avl_node<value_type_, comparator_type_>>>
class basic_avl_tree
```

#### API Design

This AVL tree provides an STL-compatible interface:

- Bidirectional iterators for in-order traversal (begin/end/rbegin/rend)
- Returns `[status_t](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#status_t)` for some operations instead of throwing exceptions
- Supports heterogeneous lookups when comparator defines `is_transparent`
- Provides both [`insert`](https://www.unum.cloud/docs/smashtable/cpp/isolation.md#insert) (fails if exists) and [`upsert`](https://www.unum.cloud/docs/smashtable/cpp/isolation.md#upsert) (always succeeds) semantics
- Allows custom allocators for all internal nodes
- Iterator invalidation: only iterators to erased elements are invalidated
Callback-based APIs are also provided for convenience (find, range, equal_range). The tree maintains O(log n) height through automatic rebalancing after modifications.

#### Entry Constraints

Entries stored in the tree must be comparable using the provided comparator. They must also be `noexcept` move-constructible and assignable to ensure safety. When dealing with bulk-insertions of non-copyable types, make sure to use a moving iterator, like the `std::move_iterator`.

#### Insert Strategies

Four distinct modification strategies with different failure handling:

| Method | Key Exists | Returns | Use Case |
|:-|:-|:-|:-|
| insert() | Fails | invalid_arg_k | Strict, ensure key is new |
| insert_if_missing() | Skips | success_k | Lenient, insert only if absent |
| upsert() | Overwrites | success_k | Always succeeds, insert or overwrite |
| update() | Fails | key_not_found_k | Strict, key must already exist |

## key_t

Extracts a map's key_type through SFINAE, or falls back to value_type for a set.

```cpp
using key_t = typename mapping_key_type_or_itself<value_t>::type;
```

## mapped_t

Extracts a map's mapped_type through SFINAE, or falls back to void for a set.

```cpp
using mapped_t = typename mapped_value_type_or_void<value_t>::type;
```

## rebind

Rebind this tree type to different entry and comparator types.

```cpp
template <typename other_value_type_, typename other_comparator_type_>
using rebind = basic_avl_tree<other_value_type_, other_comparator_type_, typename std::allocator_traits<allocator_t>::template rebind_alloc<basic_avl_node<other_value_type_, other_comparator_type_>>>;
```

Follows STL allocator rebind pattern for type transformations.

## basic_avl_tree

Seeds both policies, which a stateful comparator needs to survive a rebind.

```cpp
basic_avl_tree() noexcept=default;
```

```cpp
basic_avl_tree(allocator_t allocator) noexcept;
```

```cpp
basic_avl_tree(comparator_t comparator, allocator_t allocator) noexcept;
```

Seeds both policies, which a stateful comparator needs to survive a rebind.

```cpp
basic_avl_tree(basic_avl_tree && other) noexcept;
```

```cpp
basic_avl_tree(basic_avl_tree const &)=delete;
```

## operator=

```cpp
basic_avl_tree & operator=(basic_avl_tree const &)=delete;
```

```cpp
basic_avl_tree & operator=(basic_avl_tree && other) noexcept;
```

## ~basic_avl_tree

```cpp
~basic_avl_tree() noexcept;
```

## copy

Creates a deep copy of the tree.

```cpp
expected<basic_avl_tree> copy() const noexcept;
```

Notes: This operation may fail due to allocation errors during node duplication. The returned tree uses a copy of this tree's allocator.

Statuses: - [`out_of_memory_heap_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#out_of_memory_heap_k) An element refused its own copy.

## *

Returns the number of elements in the tree.

```cpp
std::size_t size() const noexcept;
```

## height

Returns the height of the tree (number of edges in longest path from root to leaf).

```cpp
std::size_t height() noexcept;
```

## root

Returns raw pointer to the root node.

```cpp
node_t * root() const noexcept;
```

For internal use.

## allocator

Returns the allocator associated with the tree.

```cpp
allocator_t & allocator() noexcept;
```

```cpp
allocator_t const & allocator() const noexcept;
```

Returns the allocator associated with the tree (const version).

## begin

Returns an iterator to the first element (minimum) in the tree.

```cpp
iterator begin() noexcept;
```

```cpp
const_iterator begin() const noexcept;
```

Returns a const iterator to the first element (minimum) in the tree.

## cbegin

Returns a const iterator to the first element (minimum) in the tree.

```cpp
const_iterator cbegin() const noexcept;
```

## end

Returns an iterator to one past the last element.

```cpp
iterator end() noexcept;
```

```cpp
const_iterator end() const noexcept;
```

Returns a const iterator to one past the last element.

## cend

Returns a const iterator to one past the last element.

```cpp
const_iterator cend() const noexcept;
```

## rbegin

Returns a reverse iterator to the reversed tree's first element, the maximum.

```cpp
reverse_iterator rbegin() noexcept;
```

```cpp
const_reverse_iterator rbegin() const noexcept;
```

Returns a const reverse iterator to the reversed tree's first element, the maximum.

## crbegin

Returns a const reverse iterator to the reversed tree's first element, the maximum.

```cpp
const_reverse_iterator crbegin() const noexcept;
```

## rend

Reverse iterator one past the reversed tree's last element, just before the minimum.

```cpp
reverse_iterator rend() noexcept;
```

```cpp
const_reverse_iterator rend() const noexcept;
```

Returns a const reverse iterator to one past the last element of the reversed tree, before the minimum.

## crend

Returns a const reverse iterator to one past the last element of the reversed tree, before the minimum.

```cpp
const_reverse_iterator crend() const noexcept;
```

## find

Finds an element equal to the given `comparable`.

```cpp
template <typename comparable_type_>
iterator find(comparable_type_ && comparable) noexcept;
```

```cpp
template <typename comparable_type_>
const_iterator find(comparable_type_ && comparable) const noexcept;
```

Finds an element equal to the given `comparable` (const version).

Heterogeneous lookup supported if comparator defines `is_transparent`.

- `comparable` (in): Object comparable to [`value_t`](#value_t).

## find_copy

Finds and returns a copy of an element equal to `comparable`.

```cpp
template <typename comparable_type_>
expected<value_t> find_copy(
    comparable_type_ && comparable) const noexcept;
```

Convenience method to avoid callback-based access in tests and simple use cases. Heterogeneous lookup supported if comparator defines `is_transparent`.

- `comparable` (in): Object comparable to [`value_t`](#value_t).

Statuses: - [`key_not_found_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#key_not_found_k) No element is equal to `comparable`.
- Any status the element's [`copy`](#copy) returns passes through unchanged.

## lower_bound_copy

Finds and returns a copy of the first element not less than (>=) `comparable`.

```cpp
template <typename comparable_type_>
expected<value_t> lower_bound_copy(
    comparable_type_ && comparable) const noexcept;
```

- `comparable` (in): Object comparable to [`value_t`](#value_t).

Statuses: - [`key_not_found_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#key_not_found_k) Every element is less than `comparable`.
- Any status the element's [`copy`](#copy) returns passes through unchanged.

## upper_bound_copy

Finds and returns a copy of the first element greater than (>) `comparable`.

```cpp
template <typename comparable_type_>
expected<value_t> upper_bound_copy(
    comparable_type_ && comparable) const noexcept;
```

- `comparable` (in): Object comparable to [`value_t`](#value_t).

Statuses: - [`key_not_found_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#key_not_found_k) No element is greater than `comparable`.
- Any status the element's [`copy`](#copy) returns passes through unchanged.

## contains

Checks if an element equal to `comparable` exists in the tree.

```cpp
template <typename comparable_type_>
expected<bool> contains(comparable_type_ && comparable) const noexcept;
```

Heterogeneous lookup supported if comparator defines `is_transparent`.

- `comparable` (in): Object comparable to [`value_t`](#value_t).

## lower_bound

Finds the first element not less than (>=) the given `comparable`.

```cpp
template <typename comparable_type_>
iterator lower_bound(comparable_type_ && comparable) noexcept;
```

```cpp
template <typename comparable_type_>
const_iterator lower_bound(
    comparable_type_ && comparable) const noexcept;
```

Finds the first element not less than (>=) the given `comparable` (const version).

Heterogeneous lookup supported if comparator defines `is_transparent`.

- `comparable` (in): Object comparable to [`value_t`](#value_t).

## upper_bound

Finds the first element greater than (>) the given `comparable`.

```cpp
template <typename comparable_type_>
iterator upper_bound(comparable_type_ && comparable) noexcept;
```

```cpp
template <typename comparable_type_>
const_iterator upper_bound(
    comparable_type_ && comparable) const noexcept;
```

Finds the first element greater than (>) the given `comparable` (const version).

Heterogeneous lookup supported if comparator defines `is_transparent`.

- `comparable` (in): Object comparable to [`value_t`](#value_t).

## count

Returns the number of elements with key equal to the specified argument.

```cpp
template <typename comparable_type_>
expected<std::size_t> count(
    comparable_type_ && comparable) const noexcept;
```

For unique-key containers like this, returns either 0 or 1.

- `comparable` (in): Object comparable to [`value_t`](#value_t) and convertible to search key.

## empty

Checks if the tree has no elements.

```cpp
bool empty() const noexcept;
```

## equal_range

Returns a range of elements matching a specific key.

```cpp
template <typename comparable_type_>
std::pair<iterator, iterator> equal_range(
    comparable_type_ && comparable) noexcept;
```

```cpp
template <typename comparable_type_>
std::pair<const_iterator, const_iterator> equal_range(
    comparable_type_ && comparable) const noexcept;
```

Returns a range of elements matching a specific key (const version).

```cpp
template <typename comparable_type_ = value_t, typename callback_type_ = no_op_t>
status_t equal_range(
    comparable_type_ && comparable,
    callback_type_ && callback) const noexcept;
```

Finds all elements equal to a single key.

For unique-key containers, returns range containing at most one element.

- `comparable` (in): Object comparable to [`value_t`](#value_t).
- `callback` (in): Callback invoked for each element equal to the key. Must be `noexcept`.

## range

Iterates over all entries in the range [ `lower`, `upper`).

```cpp
template <typename lower_type_ = value_t, typename upper_type_ = value_t, typename callback_type_ = no_op_t>
status_t range(
    lower_type_ && lower,
    upper_type_ && upper,
    callback_type_ && callback) const noexcept;
```

```cpp
template <typename lower_type_ = value_t, typename upper_type_ = value_t, typename callback_type_ = no_op_t>
status_t range(
    lower_type_ && lower,
    upper_type_ && upper,
    callback_type_ && callback) noexcept;
```

Iterates over all entries in the range [ `lower`, `upper`), allowing in-place modification.

Const version. Invokes callback for each element in the specified range.

- `lower` (in): Lower bound of the range (inclusive).
- `upper` (in): Upper bound of the range (exclusive).
- `callback` (in): Callback invoked for each element in range. Must be `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.

## erase_range

Erases a range of elements [lower, upper).

```cpp
template <typename lower_type_, typename upper_type_, typename callback_type_ = no_op_t>
void erase_range(
    lower_type_ && lower,
    upper_type_ && upper,
    callback_type_ && callback = {}) noexcept;
```

Invokes callback for each erased element. Complexity: O(log N + K), where K is the number of elements in the range.

- `lower` (in): Lower bound of the range (inclusive).
- `upper` (in): Upper bound of the range (exclusive).
- `callback` (in): Optional callback invoked for each erased element.

## insert_if_missing

Inserts an entry only if the key doesn't exist.

```cpp
template <typename comparable_type_>
inserted_iterator_t insert_if_missing(
    comparable_type_ && comparable) noexcept;
```

```cpp
template <readable_iterator input_iterator_type_, typename... tags_types_>
requires (promises_about_the_range<tags_types_> && ...)
status_t insert_if_missing(
    input_iterator_type_ first,
    input_iterator_type_ last,
    tags_types_... tags) noexcept;
```

Inserts every element of [ `first`, `last` ) whose key is free, keeping incumbents.

```cpp
status_t insert_if_missing(
    std::initializer_list<value_t> ilist) noexcept;
```

Inserts elements from an initializer list if keys don't exist.

Matches `std::set::insert()` semantics. Leaves any incumbent alone, and leaves `comparable` alone unless a node was made for it.

- `comparable` (in): Entry to insert (moved into the tree).
- `first` (in): Beginning of range to insert.
- `last` (in): End of range to insert.
- `tags` (in): Markers promising something about the range, such as `[assume_sorted_t](#assume_sorted_t)`.
- `ilist` (in): Initializer list of entries to insert.

Statuses: - [`refused_k`](#refused_k) The key is absent and the allocator refused its node, so nothing was stored.

Notes: Complexity: O(n log n) to build, or O(n) under `[assume_sorted_t](#assume_sorted_t)`, then O(merge).

Statuses: - Any status an element's [`copy`](#copy) returns passes through unchanged.

## insert

Atomically inserts an entry only if the key doesn't exist.

```cpp
template <typename comparable_type_>
expected<iterator> insert(comparable_type_ && comparable) noexcept;
```

```cpp
iterator insert(const_iterator, value_t const &) noexcept=delete;
```

Deleted: Hint-based insert is not supported.

```cpp
iterator insert(const_iterator, value_t &&) noexcept=delete;
```

Deleted: Hint-based insert is not supported.

```cpp
template <readable_iterator input_iterator_type_, typename... tags_types_>
requires (promises_about_the_range<tags_types_> && ...)
status_t insert(
    input_iterator_type_ first,
    input_iterator_type_ last,
    tags_types_... tags) noexcept;
```

Inserts every element of [ `first`, `last` ), refusing the batch over a taken key.

Fails with error if key exists. This is strict insert semantics - ensures key is new.

Callers that want the incumbent's position ask `insert_if_missing()` instead, which hands back both.

- `comparable` (in): Entry to insert, moved into the tree only when a node is made for it.
- `first` (in): Beginning of range to insert.
- `last` (in): End of range to insert.
- `tags` (in): Markers promising something about the range, such as `[assume_sorted_t](#assume_sorted_t)`.

Statuses: - [`key_already_exists_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#key_already_exists_k) An incumbent holds the key, or an inconsistent comparator matched one while linking the node.

Notes: Complexity: O(n log n) to build or O(n) under `[assume_sorted_t](#assume_sorted_t)`, plus O(m+n) checks.

Statuses: - [`key_already_exists_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#key_already_exists_k) A key repeats inside an unsorted range or is already in this tree.
- Any status an element's [`copy`](#copy) returns passes through unchanged.

## upsert

Atomically inserts or updates an entry.

```cpp
template <typename comparable_type_>
upserted_node_t upsert(comparable_type_ && comparable) noexcept;
```

```cpp
template <readable_iterator input_iterator_type_, typename... tags_types_>
requires (promises_about_the_range<tags_types_> && ...)
status_t upsert(
    input_iterator_type_ first,
    input_iterator_type_ last,
    tags_types_... tags) noexcept;
```

Upserts a range of entries (inserts new keys or updates existing ones).

```cpp
status_t upsert(std::initializer_list<value_t> ilist) noexcept;
```

Upserts elements from initializer list (insert or update semantics).

Overwrites existing entry if key exists (upsert semantics).

- `comparable` (in): Entry to upsert (moved into the tree).
- `first` (in): Beginning of range to upsert.
- `last` (in): End of range to upsert.
- `tags` (in): Markers promising something about the range, such as `[assume_sorted_t](#assume_sorted_t)`.
- `ilist` (in): Initializer list of entries to upsert.

Statuses: - [`refused_k`](#refused_k) The key is absent and the allocator refused its node, so nothing was stored.

Notes: With `[assume_sorted_t](#assume_sorted_t)` : Range must be sorted (ascending order).

Notes: With `[assume_unique_t](#assume_unique_t)` : Range must have no duplicate keys with existing tree; violating it is undefined behavior.

Notes: Atomicity: every failure happens while the staging tree is built, leaving this tree unchanged; the merge itself only relinks nodes, so it cannot fail part-way. Duplicate keys are UPDATED during the merge, not skipped.

Statuses: - Any status an element's [`copy`](#copy) returns passes through unchanged.

## emplace

Constructs an element in-place.

```cpp
template <typename... args_types_>
std::pair<iterator, bool> emplace(args_types_ &&... args) noexcept;
```

Matches `std::set::emplace()` semantics. Does not insert if key already exists.

- `args` (in): Arguments to forward to value_t constructor.

Notes: The STL shape collapses a refused allocation and a matched incumbent into the same `false`, so `insert_if_missing()` is the call that tells them apart.

## emplace_hint

Deleted: Hint-based emplace is not supported.

```cpp
template <typename... args_types_>
iterator emplace_hint(
    const_iterator,
    args_types_ && ...) noexcept=delete;
```

AVL trees don't benefit from position hints, and providing unused hints is misleading. Use `emplace()` instead.

## update

Updates a range of existing entries, all-or-nothing on failure.

```cpp
template <readable_iterator input_iterator_type_, typename... tags_types_>
requires (promises_about_the_range<tags_types_> && ...)
status_t update(
    input_iterator_type_ first,
    input_iterator_type_ last,
    tags_types_... tags) noexcept;
```

```cpp
status_t update(std::initializer_list<value_t> ilist) noexcept;
```

Updates elements from an initializer list (all keys must exist).

Builds a temporary tree from the range, validates all keys exist, then updates in one step. On allocation failure or any missing key, this tree remains unchanged.

- `first` (in): Beginning of range to update.
- `last` (in): End of range to update.
- `tags` (in): Markers promising something about the range, such as `[assume_sorted_t](#assume_sorted_t)`.
- `ilist` (in): Initializer list of entries to update.

Notes: Complexity:

- With `[assume_sorted_t](#assume_sorted_t)` : O(n) build + O(m+n) validation + O(m log n) update
- Without: O(n log n) build + O(m+n) validation + O(m log n) update

Notes: With `[assume_sorted_t](#assume_sorted_t)` : Range must be sorted (ascending order).

Notes: All-or-nothing on failure: if any key is missing, nothing is updated. Temporary tree is destroyed via RAII, this tree remains unchanged.

Statuses: - [`key_not_found_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#key_not_found_k) A key of the range is absent from this tree.
- Any status an element's [`copy`](#copy) returns passes through unchanged.

Statuses: - [`key_not_found_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#key_not_found_k) A key of the list is absent from this tree.
- Any status an element's [`copy`](#copy) returns passes through unchanged.

## key_comp

Returns the function object that compares keys.

```cpp
comparator_t key_comp() const noexcept;
```

## value_comp

Returns the function object that compares values, for sets the same as key_comp().

```cpp
comparator_t value_comp() const noexcept;
```

## max_size

Returns the maximum possible number of elements.

```cpp
std::size_t max_size() const noexcept;
```

## swap

Exchanges the contents of this tree with another.

```cpp
status_t swap(basic_avl_tree & other) noexcept;
```

Swaps tree structure, size, comparator, and (if propagating) allocators. For non-propagating allocators (when `propagate_on_container_swap` is `false`), the allocators must be equal, otherwise [`invalid_argument_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#invalid_argument_k) is returned.

- `other` (inout): Tree to swap with.

Statuses: - [`invalid_argument_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#invalid_argument_k) The allocators are unequal and do not propagate on swap.

## erase

Erases a single entry matching the given `comparable`.

```cpp
template <typename comparable_type_ = value_t, typename callback_found_type_ = no_op_t, typename callback_missing_type_ = no_op_t>
void erase(
    comparable_type_ && comparable,
    callback_found_type_ && callback_found,
    callback_missing_type_ && callback_missing) noexcept;
```

```cpp
template <typename comparable_type_>
bool erase(comparable_type_ && comparable) noexcept;
```

```cpp
erase_result_t erase(iterator position) noexcept;
```

Erases the element at the specified iterator position.

```cpp
erase_result_t erase(const_iterator position) noexcept;
```

Erases the element at the specified [const_iterator](#const_iterator) position.

```cpp
erase_result_t erase(iterator first, iterator last) noexcept;
```

Erases all elements in the range [first, last).

```cpp
erase_result_t erase(
    const_iterator first,
    const_iterator last) noexcept;
```

Erases all elements in the range [first, last) using const_iterators.

No callbacks.

- `comparable` (in): Object comparable to [`value_t`](#value_t) and convertible to search key.
- `callback_found` (in): Callback to receive the erased entry. Must be `noexcept`.
- `callback_missing` (in): Callback triggered if nothing was found. Must be `noexcept`.
- `position` (in): Iterator to element to erase. Must be valid and dereferenceable.
- `first` (in): Beginning of range to erase.
- `last` (in): End of range to erase (not erased).

Notes: If `position` is end(), returns {end(), success} without modifying the tree.

## reserve

Hints to the tree to pre-allocate memory.

```cpp
void reserve(std::size_t) noexcept;
```

No-op for AVL tree implementation. Provided for API consistency with other containers. Doesn't guarantee subsequent insertions won't fail with "out of memory".

Suggested capacity (ignored for AVL trees).

Notes: This is a no-op because AVL trees don't support reserving capacity efficiently.

## clear

Removes all elements from the tree and frees their memory.

```cpp
void clear() noexcept;
```

## for_each

Visits every element in sorted order; a callback can stop it early via `[walk_control_t](https://www.unum.cloud/docs/smashtable/cpp/transactions.md#walk_control_t)`.

```cpp
template <typename callback_type_>
status_t for_each(callback_type_ && callback) noexcept;
```

## merge

Merges another tree into this one, transferring all nodes.

```cpp
void merge(basic_avl_tree & other) noexcept;
```

```cpp
void merge(basic_avl_tree & other, assume_unique_t) noexcept;
```

Merges another tree into this one with optimized algorithm for disjoint trees.

```cpp
void merge(extract_result_t other) noexcept;
```

Merges a single extracted node into this tree, deallocating it if the key exists.

Elements with keys that already exist in this tree are deallocated (not kept in source).

- `other` (inout): Tree to merge from. Will be empty after merge.

Notes: Unlike `std::set::merge()`, nodes with duplicate keys are deallocated rather than remaining in the source container. This ensures no memory leaks in a noexcept context.

Notes: Complexity: O(m log n) where m = other.size(), n = this.size(). For disjoint trees, use `merge(other, assume_unique)` for faster O(m log(n/m+1)) or O(m+n).

Notes: Complexity: O(m log(n/m + 1)) for unbalanced sizes, O(m+n) for similar sizes.

Warnings: If precondition violated (duplicate keys exist), behavior is undefined.

Notes: Unlike `std::set::merge()`, a node with a duplicate key is deallocated rather than being returned. This ensures no memory leaks in a noexcept context.

## split

Splits the tree at a given key into two trees.

```cpp
template <typename comparable_type_>
split_result_t split(comparable_type_ && comparable) noexcept;
```

Elements < key go to left tree, elements >= key go to right tree. This tree becomes empty after the split.

- `comparable` (in): Key to split at.

Notes: This operation is O(log n) and maintains AVL balance in both resulting trees. The current tree is emptied (moved-from state).

## join

Joins this tree with another tree.

```cpp
void join(basic_avl_tree & other) noexcept;
```

Precondition: All elements in this tree < all elements in other tree. The other tree becomes empty after the join.

- `other` (inout): Tree to join with (must have all larger elements).

Notes: This operation is O(log n) and maintains AVL balance. If the precondition is violated, the resulting tree structure is undefined.

## erase_result_t

Result of an erase operation on an iterator: the next-element iterator plus the outcome status.

```cpp
struct erase_result_t
```

- `next` `iterator`: Iterator to the element following the erased one, or `end()`.
- `status` `status_t`: Status of the erase operation.

## iterator

Bidirectional iterator for AVL tree.

```cpp
class iterator
```

Provides in-order traversal of tree elements.

## const_iterator

Const bidirectional iterator for AVL tree, providing read-only in-order traversal of tree elements.

```cpp
class const_iterator
```

## upserted_node_t

The node an upsert settled on, and how it got there.

```cpp
struct upserted_node_t
```

Assigning to the result overwrites that node's entry, which is what makes it usable as a handle rather than a report.

- `node` `node_t *`
- `placement` `node_t::node_placement_t`

## inserted_iterator_t

Where an insertion settled, and how it got there.

```cpp
struct inserted_iterator_t
```

Names the same three outcomes as `[upserted_node_t](#upserted_node_t)`, one level up from the nodes.

- `position` `iterator`: The element's position, which is `end()` when nothing was stored.
- `placement` `node_t::node_placement_t`: Whether the entry was made, matched an incumbent, or refused for want of memory.

## split_result_t

Result of a split operation on a tree.

```cpp
struct split_result_t
```

- `left` `basic_avl_tree`: Tree with all elements ordered before the split key.
- `right` `basic_avl_tree`: Tree with all elements not ordered before the split key.

## basic_fixed_pool

At most [`capacity`](#capacity) records of `value_type_`, taken and vacated by index.

```cpp
template <typename value_type_,
          std::unsigned_integral index_type_ = std::uint32_t,
          allocator_of<std::byte> allocator_type_ = default_allocator_t>
class basic_fixed_pool
```

## absent_k

What [`take`](#take) answers when every record is taken.

```cpp
index_t absent_k;
```

## basic_fixed_pool

```cpp
basic_fixed_pool() noexcept=default;
```

```cpp
basic_fixed_pool(allocator_t allocator) noexcept;
```

```cpp
basic_fixed_pool(basic_fixed_pool && other) noexcept;
```

```cpp
basic_fixed_pool(basic_fixed_pool const &)=delete;
```

## ~basic_*_pool

```cpp
~basic_fixed_pool() noexcept;
```

- `~basic_fixed_pool`
- `~basic_growing_pool`

## operator=

```cpp
basic_fixed_pool & operator=(basic_fixed_pool && other) noexcept;
```

```cpp
basic_fixed_pool & operator=(basic_fixed_pool const &)=delete;
```

## records

Every record, taken or free, in index order.

```cpp
std::span<value_t> records() noexcept;
```

```cpp
std::span<value_t const> records() const noexcept;
```

## operator[]

The record at `index`, taken or not, without bounds checking.

```cpp
value_t & operator[](index_t index) noexcept;
```

```cpp
value_t const & operator[](index_t index) const noexcept;
```

## index_of

The index of `record`, which must be one of [`records`](#records).

```cpp
index_t index_of(value_t const & record) const noexcept;
```

## take

Takes a free record, as its last holder left it, or answers [`absent_k`](#absent_k) when none is.

```cpp
index_t take() noexcept;
```

## *

Frees the taken record at `index`, stepping its generation so older handles go stale.

```cpp
void vacate(index_t index) noexcept;
```

## handle_*_of

A handle to the record at `index`, which [`at`](#at) answers until it is vacated.

```cpp
requires generation_tagged<value_t, index_t>
handle_t handle__of(index_t index) const noexcept;
```

## at

The record `handle` names, or null once that record was vacated.

```cpp
requires generation_tagged<value_t, index_t>
value_t * at(handle_t handle) noexcept;
```

```cpp
requires generation_tagged<value_t, index_t>
value_t const * at(handle_t handle) const noexcept;
```

## make

A pool of [`capacity`](#capacity) default-constructed records, all of them free.

```cpp
expected<basic_fixed_pool> make(
    std::size_t capacity,
    allocator_t allocator = {}) noexcept;
```

Statuses: - [`invalid_argument_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#invalid_argument_k) A capacity reaching [`absent_k`](#absent_k), or too large to count in bytes.

## handle_t

A record's index and the generation it was taken at, for a tagged record only.

```cpp
struct handle_t
```

- `index` `index_t`
- `generation` `index_t`

## basic_flat_set

A sorted set of unique `value_type_` ordered by `comparator_type_`.

```cpp
template <typename value_type_,
          typename comparator_type_ = less_t,
          row_kit row_kit_type_ = native_row_kit_t,
          typename allocator_type_ = default_allocator<value_type_>>
class basic_flat_set
```

The rank search goes through `row_kit_type_` when the element is a `row_searchable_key` ordered by `[less_t](#less_t)`, and through a binary search with the comparator otherwise.

## key_t

The key half, which for a set is the whole element.

```cpp
using key_t = value_t;
```

## mapped_t

The mapped half, which a set never has.

```cpp
using mapped_t = void;
```

## basic_flat_set

```cpp
basic_flat_set() noexcept=default;
```

```cpp
basic_flat_set(
    comparator_t comparator,
    allocator_t allocator = {}) noexcept;
```

```cpp
basic_flat_set(basic_flat_set &&) noexcept=default;
```

```cpp
basic_flat_set(basic_flat_set const &)=delete;
```

## operator=

```cpp
basic_flat_set & operator=(basic_flat_set &&) noexcept=default;
```

```cpp
basic_flat_set & operator=(basic_flat_set const &)=delete;
```

## copy

A deep copy.

```cpp
expected<basic_flat_set> copy() const noexcept;
```

Statuses: - Any status an element's [`copy`](#copy) returns passes through unchanged.

## operator[]

The element at position `ordinal` in sorted order.

```cpp
value_t const & operator[](std::size_t ordinal) const noexcept;
```

## rank

How many elements order below `wanted`, which is also where it is or would be inserted.

```cpp
template <typename comparable_type_>
std::size_t rank(comparable_type_ const & wanted) const noexcept;
```

## find

The element equivalent to `wanted`, or null.

```cpp
template <typename comparable_type_>
value_t const * find(comparable_type_ const & wanted) const noexcept;
```

## contains

Whether an element equivalent to `wanted` is here.

```cpp
template <typename comparable_type_>
expected<bool> contains(comparable_type_ const & wanted) const noexcept;
```

Always success; a sorted array cannot refuse a read.

## lower_bound

The first element not below `wanted`, or [`end`](#end).

```cpp
template <typename comparable_type_>
value_t const * lower_bound(
    comparable_type_ const & wanted) const noexcept;
```

## upper_bound

The first element above `wanted`, or [`end`](#end).

```cpp
template <typename comparable_type_>
value_t const * upper_bound(
    comparable_type_ const & wanted) const noexcept;
```

## find_copy

Copies out the element equivalent to `wanted`.

```cpp
template <typename comparable_type_>
expected<value_t> find_copy(
    comparable_type_ const & wanted) const noexcept;
```

Statuses: - [`key_not_found_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#key_not_found_k) No element is equivalent to `wanted`.
- Any status the element's [`copy`](#copy) returns passes through unchanged.

## lower_bound_copy

Copies out the first element not below `wanted`.

```cpp
template <typename comparable_type_>
expected<value_t> lower_bound_copy(
    comparable_type_ const & wanted) const noexcept;
```

Statuses: - [`key_not_found_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#key_not_found_k) Every element is below `wanted`.
- Any status the element's [`copy`](#copy) returns passes through unchanged.

## upper_bound_copy

Copies out the first element above `wanted`.

```cpp
template <typename comparable_type_>
expected<value_t> upper_bound_copy(
    comparable_type_ const & wanted) const noexcept;
```

Statuses: - [`key_not_found_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#key_not_found_k) No element is above `wanted`.
- Any status the element's [`copy`](#copy) returns passes through unchanged.

## range

Visits every element in [lower, upper) in sorted order, or fewer if the callback halts.

```cpp
template <typename lower_type_ = value_t, typename upper_type_ = value_t, typename callback_type_ = no_op_t>
status_t range(
    lower_type_ const & lower,
    upper_type_ const & upper,
    callback_type_ && callback) const noexcept;
```

## insert

Adds `element`, or leaves the set alone.

```cpp
status_t insert(value_t element) noexcept;
```

```cpp
template <readable_iterator input_iterator_type_>
status_t insert(
    input_iterator_type_ first,
    input_iterator_type_ last) noexcept;
```

Adds every element of [ `first`, `last` ), refusing the batch over any taken key.

All-or-nothing over this set from the first element on, a taken key included: the whole range is staged and checked before the merge absorbing it allocates anything.

Statuses: - [`key_already_exists_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#key_already_exists_k) An equivalent element is here.

Statuses: - [`key_already_exists_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#key_already_exists_k) A key repeats inside the range or is already in this set.
- Any status an element's [`copy`](#copy) returns passes through unchanged.

## upsert

Adds `element`, replacing an equivalent one if the set holds it.

```cpp
status_t upsert(value_t element) noexcept;
```

```cpp
template <readable_iterator input_iterator_type_>
status_t upsert(
    input_iterator_type_ first,
    input_iterator_type_ last) noexcept;
```

Writes every element of [ `first`, `last` ), replacing any equivalent element.

All-or-nothing over this set from the first element on; an element already here is overwritten by the merge, which moves rather than copies once its buffer is secured.

Statuses: - Any status an element's [`copy`](#copy) returns passes through unchanged.

## insert_if_missing

Adds every element of [ `first`, `last` ) this set lacks, leaving incumbents alone.

```cpp
template <readable_iterator input_iterator_type_>
status_t insert_if_missing(
    input_iterator_type_ first,
    input_iterator_type_ last) noexcept;
```

All-or-nothing over this set from the first element on: the staging set holds every element before the merge begins, and the merge makes its one allocation before it moves anything.

Statuses: - Any status an element's [`copy`](#copy) returns passes through unchanged.

## erase

Removes the element equivalent to `wanted`.

```cpp
template <typename comparable_type_>
status_t erase(comparable_type_ const & wanted) noexcept;
```

Statuses: - [`key_not_found_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#key_not_found_k) No element is equivalent to `wanted`.

## erase_range

Erases the half-open range [lower, upper), handing each removed element to `callback` first.

```cpp
template <typename lower_type_, typename upper_type_, typename callback_type_ = no_op_t>
void erase_range(
    lower_type_ const & lower,
    upper_type_ const & upper,
    callback_type_ && callback = {}) noexcept;
```

## erase_if

Removes every element `predicate` admits, handing each to `callback` first, and answers how many went.

```cpp
template <typename predicate_type_, typename callback_type_ = no_op_t>
requires std::predicate<predicate_type_ &, value_t &>
std::size_t erase_if(
    predicate_type_ && predicate,
    callback_type_ && callback = {}) noexcept;
```

## make

An empty set with room for [`capacity`](#capacity) elements.

```cpp
expected<basic_flat_set> make(
    std::size_t capacity,
    comparator_t comparator = {},
    allocator_t allocator = {}) noexcept;
```

## basic_growing_pool

Records of `value_type_`, taken and vacated by index, growing chunk by chunk up to a limit without moving a record, and readable by index or handle from other threads while the one owner grows it.

```cpp
template <typename value_type_,
          std::unsigned_integral index_type_ = std::uint32_t,
          allocator_of<std::byte> allocator_type_ = default_allocator_t>
class basic_growing_pool
```

## absent_k

What [`take`](#take) answers when every record is taken and no more may be added.

```cpp
index_t absent_k;
```

## capacity_max_k

The most records a pool holds, every index but [`absent_k`](#absent_k).

```cpp
std::size_t capacity_max_k;
```

## basic_growing_pool

```cpp
basic_growing_pool() noexcept=default;
```

```cpp
basic_growing_pool(allocator_t allocator) noexcept;
```

```cpp
basic_growing_pool(basic_growing_pool && other) noexcept;
```

```cpp
basic_growing_pool(basic_growing_pool const &)=delete;
```

## operator=

```cpp
basic_growing_pool & operator=(basic_growing_pool && other) noexcept;
```

```cpp
basic_growing_pool & operator=(basic_growing_pool const &)=delete;
```

## capacity

Records the pool holds now, taken or free, bookkeeping of whoever serializes [`take`](#take).

```cpp
std::size_t capacity() const noexcept;
```

## capacity_limit

Records the pool may grow to.

```cpp
std::size_t capacity_limit() const noexcept;
```

## full

Whether every record is taken and none may be added.

```cpp
bool full() const noexcept;
```

## records

Every record, taken or free, in index order.

```cpp
records_range<basic_growing_pool, value_t> records() noexcept;
```

```cpp
records_range<basic_growing_pool const, value_t const> records() const noexcept;
```

## operator[]

The record at `index`, taken or not, whose chunk must be published.

```cpp
value_t & operator[](index_t index) noexcept;
```

```cpp
value_t const & operator[](index_t index) const noexcept;
```

## index_of

The index of `record`, which must be one of [`records`](#records), found among published chunks.

```cpp
index_t index_of(value_t const & record) const noexcept;
```

## take

Takes a free record, as its last holder left it, growing the pool when none is free and it may, or answers [`absent_k`](#absent_k) when it may not or the allocator refuses.

```cpp
index_t take() noexcept;
```

## at

The record `handle` names, or null once that record was vacated.

```cpp
requires generation_tagged<value_t, index_t>
value_t * at(handle_t handle) noexcept;
```

```cpp
requires generation_tagged<value_t, index_t>
value_t const * at(handle_t handle) const noexcept;
```

## make

A pool of at least [`capacity`](#capacity) free records, rounded up to a power of two and clipped to [`capacity_limit`](#capacity_limit), which a [`take`](#take) finding none free grows chunk by chunk up to that limit.

```cpp
expected<basic_growing_pool> make(
    std::size_t capacity,
    std::size_t capacity_limit,
    allocator_t allocator = {}) noexcept;
```

Statuses: - [`invalid_argument_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#invalid_argument_k) A limit past [`capacity_max_k`](#capacity_max_k), below [`capacity`](#capacity), or too large to count in bytes.
- [`out_of_memory_heap_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#out_of_memory_heap_k) The allocator refused the first chunk.

## handle_t

A record's index and the generation it was taken at, for a tagged record only.

```cpp
struct handle_t
```

- `index` `index_t`
- `generation` `index_t`

## records_walk

A forward walk over every record, taken or free, in index order.

```cpp
template <typename pool_type_,
          typename record_type_>
class records_walk
```

## records_range

Every record of a pool, taken or free, in index order, which a range-for walks.

```cpp
template <typename pool_type_,
          typename record_type_>
class records_range
```

## basic_hash_index

Maps fixed-width keys to record positions, at most [`capacity`](#capacity) of them, with linear probing in windows and backward-shift erasure.

```cpp
template <window_key key_type_,
          std::unsigned_integral index_type_ = std::uint32_t,
          typename hasher_type_ = default_hash_t,
          allocator_of<std::byte> allocator_type_ = default_allocator_t,
          row_kit row_kit_type_ = native_row_kit_t>
class basic_hash_index
```

## absent_k

The position [`find`](https://www.unum.cloud/docs/smashtable/cpp/isolation.md#find) answers when no key matches, which no record may occupy.

```cpp
index_t absent_k;
```

## basic_hash_index

```cpp
basic_hash_index() noexcept=default;
```

```cpp
basic_hash_index(basic_hash_index && other) noexcept;
```

```cpp
basic_hash_index(basic_hash_index const &)=delete;
```

## operator=

```cpp
basic_hash_index & operator=(basic_hash_index && other) noexcept;
```

```cpp
basic_hash_index & operator=(basic_hash_index const &)=delete;
```

## find

The position stored under `key`, the first in probe order when several are, or [`absent_k`](#absent_k).

```cpp
index_t find(key_t key) const noexcept;
```

```cpp
template <typename confirm_type_>
index_t find(key_t key, confirm_type_ && confirm) const noexcept;
```

The first position under `key` that `confirm` accepts, for keys that hash something longer.

## insert

Stores `index` under `key`, beside any position already stored under it.

```cpp
status_t insert(key_t key, index_t index, assume_unique_t) noexcept;
```

Statuses: - [`capacity_exhausted_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#capacity_exhausted_k) The index already holds [`capacity`](#capacity) keys.

## erase

Removes the entry pairing `key` with `index`, shifting the rest of its run back.

```cpp
status_t erase(key_t key, index_t index) noexcept;
```

Each later key in the run moves into the hole when the hole lies between its home and its slot, so every key stays reachable from its home without a tombstone.

Statuses: - [`key_not_found_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#key_not_found_k) No entry pairs `key` with `index`.

## clear

Forgets every entry and keeps the allocation, zeroing the headers alone.

```cpp
void clear() noexcept;
```

## make

An empty index accepting up to [`capacity`](#capacity) keys, over twice as many slots.

```cpp
expected<basic_hash_index> make(
    std::size_t capacity,
    hasher_t hasher = {},
    allocator_t allocator = {}) noexcept;
```

Statuses: - [`invalid_argument_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#invalid_argument_k) A capacity whose slots no power of two covers.
- [`out_of_memory_heap_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#out_of_memory_heap_k) The allocator refused the buffer.

## basic_hash_table

Growable hash table with linear probing and Structure-of-Arrays layout.

```cpp
template <typename value_type_,
          typename hasher_type_ = default_hash_t,
          typename equals_type_ = equal_to_t,
          allocator_of<std::byte> allocator_type_ = default_allocator_t,
          row_kit row_kit_type_ = native_row_kit_t>
class basic_hash_table
```

Compatible with `std::unordered_set` interface. See file header for detailed design rationale.

See also: [https://en.cppreference.com/w/cpp/container/unordered_set](https://en.cppreference.com/w/cpp/container/unordered_set)

See also: [https://en.cppreference.com/w/cpp/container/unordered_map](https://en.cppreference.com/w/cpp/container/unordered_map)

## upsert_result_t

What a probe that may store an element managed to do.

```cpp
enum upsert_result_t
```

- `inserted_k`: A free or tombstoned slot took the new element.
- `updated_k`: An equal key was already there, and the callback saw it.
- `no_slot_k`: Every slot along the probe sequence was taken by a different key.
- `no_memory_k`: A new key needed a larger table, and the allocator refused to supply one.

## reserve_result_t

What a growth attempt did to the table.

```cpp
enum reserve_result_t
```

- `unchanged_k`: The capacity already covered the request, so every iterator stays valid.
- `reallocated_k`: A larger buffer replaced the old one, invalidating every iterator.
- `failed_k`: The allocator refused, leaving the table exactly as it was.

## emplace_report_t

What an insertion hands back: nothing at all, or where the element landed and how.

```cpp
enum emplace_report_t
```

- `no_result_k`
- `insert_result_k`

## value_t

The whole stored element: the key for a set, a [`mapping`](https://www.unum.cloud/docs/smashtable/cpp/stored-types.md#mapping) view of both halves for a map.

```cpp
using value_t = typename layout_t::value_t;
```

## key_t

The key half, which is the whole element for a set.

```cpp
using key_t = typename layout_t::key_t;
```

## mapped_t

The mapped half, `void` for a set.

```cpp
using mapped_t = typename layout_t::mapped_t;
```

## owned_value_type

The element as an owned pair, which `value_type` cannot be: it views two regions.

```cpp
using owned_value_type = typename layout_t::value_copy_t;
```

## is_associative

Traits the transactional adapters dispatch on.

```cpp
using is_associative = std::bool_constant<has_values_k>;
```

## rebind

Restates this table over a different element type, hasher and equality.

```cpp
template <typename other_element_type_, typename other_hasher_type_, typename other_equals_type_ = equals_t>
using rebind = basic_hash_table<other_element_type_, other_hasher_type_, other_equals_type_, allocator_t, row_kit_type_>;
```

A store that decorates its elements - wrapping them in version metadata, say - needs the equality restated alongside the hasher, since both must address the decorated shape.

## basic_hash_table

Default constructor, avoiding memory allocations, accepting a pre-constructed hasher functor, an equality operator, and the allocator state.

```cpp
basic_hash_table(
    hasher_t hasher = {},
    equals_t equals = {},
    allocator_t allocator = {}) noexcept;
```

```cpp
basic_hash_table(basic_hash_table && other) noexcept;
```

```cpp
basic_hash_table(basic_hash_table const &) noexcept=delete;
```

```cpp
basic_hash_table(
    offset_t,
    hasher_t = {},
    equals_t = {},
    allocator_t = {}) noexcept=delete;
```

See also: [https://en.cppreference.com/w/cpp/container/unordered_map/unordered_map](https://en.cppreference.com/w/cpp/container/unordered_map/unordered_map)

## operator=

```cpp
basic_hash_table & operator=(basic_hash_table && other) noexcept;
```

```cpp
basic_hash_table & operator=(basic_hash_table const &) noexcept=delete;
```

## deleted_count

Tombstones left behind by erasures, which only a rehash reclaims.

```cpp
offset_t deleted_count() const noexcept;
```

## bucket_count

STL-compatibility function.

```cpp
offset_t bucket_count() const noexcept;
```

See also: [https://en.cppreference.com/w/cpp/container/unordered_map/bucket_count](https://en.cppreference.com/w/cpp/container/unordered_map/bucket_count)

## max_bucket_count

STL-compatibility function.

```cpp
offset_t max_bucket_count() const noexcept;
```

See also: [https://en.cppreference.com/w/cpp/container/unordered_map/max_bucket_count](https://en.cppreference.com/w/cpp/container/unordered_map/max_bucket_count)

## hash_function

STL-compatibility function.

```cpp
hasher_t hash_function() const noexcept;
```

See also: [https://en.cppreference.com/w/cpp/container/unordered_map/hash_function](https://en.cppreference.com/w/cpp/container/unordered_map/hash_function)

## key_eq

STL-compatibility function.

```cpp
equals_t key_eq() const noexcept;
```

See also: [https://en.cppreference.com/w/cpp/container/unordered_map/key_eq](https://en.cppreference.com/w/cpp/container/unordered_map/key_eq)

## get_allocator

STL-compatibility function.

```cpp
allocator_t get_allocator() const noexcept;
```

See also: [https://en.cppreference.com/w/cpp/container/unordered_map/get_allocator](https://en.cppreference.com/w/cpp/container/unordered_map/get_allocator)

## probe_to_find

Probe optimized for `find:` checks if a value is present.

```cpp
template <typename comparable_key_type_, typename callback_type_, typename... tags_types_>
requires (promises_something<tags_types_> && ...)
void probe_to_find(
    comparable_key_type_ && wanted,
    callback_type_ && call,
    tags_types_...) const noexcept;
```

```cpp
template <typename comparable_key_type_, typename callback_type_, typename... tags_types_>
requires (promises_something<tags_types_> && ...)
void probe_to_find(
    comparable_key_type_ && wanted,
    callback_type_ && call,
    tags_types_...) noexcept;
```

Unlike [`probe_to_insert`](#probe_to_insert) or [`probe_to_upsert`](#probe_to_upsert), doesn't track "deleted" slots.

- `wanted` (in): Hashable and comparable with key object.
- `call` (in): A callback receiving a `const_slot_ref_t` to the matching slot's object.

## probe_to_visit

Visits __every__ populated slot matching `wanted`, not just the first.

```cpp
template <typename comparable_key_type_, typename callback_type_, typename... tags_types_>
requires (promises_something<tags_types_> && ...)
void probe_to_visit(
    comparable_key_type_ && wanted,
    callback_type_ && call,
    tags_types_...) const noexcept;
```

A table whose equality separates versions of one key files them all in one probe run, because the hasher still peels to the bare key. Finding one of them is not finding the newest one.

- `wanted` (in): Hashable and comparable with key object.
- `call` (in): Receives each `const_slot_ref_t` and returns `[walk_control_t](https://www.unum.cloud/docs/smashtable/cpp/transactions.md#walk_control_t)`. Must be `noexcept`.

## probe_to_insert

Probe optimized for [`insert`](https://www.unum.cloud/docs/smashtable/cpp/isolation.md#insert) of a unique key.

```cpp
template <typename comparable_key_type_, typename callback_type_, typename... tags_types_>
requires (promises_something<tags_types_> && ...)
upsert_result_t probe_to_insert(
    comparable_key_type_ && wanted,
    callback_type_ && call,
    tags_types_...) noexcept;
```

Unlike [`probe_to_upsert`](#probe_to_upsert) avoids potentially expensive equality comparisons, knowing that the incoming key is different from all present members.

- `wanted` (in): Hashable and comparable with key object.
- `call` (in): A callback receiving a `slot_ref_t` to UN-initialized memory, where an element should be built.

## probe_to_upsert

Probe optimized for potential `upserts`.

```cpp
template <typename comparable_key_type_, typename callback_unused_type_, typename callback_equal_type_, typename... tags_types_>
requires (promises_something<tags_types_> && ...)
upsert_result_t probe_to_upsert(
    comparable_key_type_ && wanted,
    callback_unused_type_ && call_unused,
    callback_equal_type_ && call_equal,
    tags_types_...) noexcept;
```

More expensive than [`probe_to_find`](#probe_to_find) and [`probe_to_insert`](#probe_to_insert), so pick this method wisely.

- `wanted` (in): Hashable and comparable with key object.
- `call_unused` (in): A callback receiving a `slot_ref_t` to UN-initialized memory, where an element should be built.
- `call_equal` (in): A callback receiving a `slot_ref_t` to the matching slot's object.

Statuses: - [`no_slot_k`](#no_slot_k) Every slot holds a different key.

## unsafe_retarget

Retargets an element reference to a specific slot using direct array indexing.

```cpp
template <typename element_ref_type_>
void unsafe_retarget(
    element_ref_type_ & slot,
    offset_t slot_index) const noexcept;
```

- `slot` (out): Slot reference to retarget with new region pointers and a new index.
- `slot_index` (in): Absolute slot index in [0, slots_count).

## slots_remaining_after

Number of slots between the reference's position and the end of the table.

```cpp
template <typename address_or_iterator_type_>
offset_t slots_remaining_after(
    address_or_iterator_type_ && slot) const noexcept;
```

## contains

Reports whether a key equivalent to `wanted` is present.

```cpp
template <typename comparable_key_type_, typename... tags_types_>
requires (promises_something<tags_types_> && ...)
expected<bool> contains(
    comparable_key_type_ && wanted,
    tags_types_... tags) const noexcept;
```

- `wanted` (in): Key to probe for.
- `tags` (in): Dispatch tags the probe understands.

## find

Similar to STL, searches for the element with the given key.

```cpp
template <typename comparable_key_type_ = key_t const &>
const_iterator_t find(comparable_key_type_ && wanted) const noexcept;
```

```cpp
template <typename comparable_key_type_ = key_t const &>
iterator_t find(comparable_key_type_ && wanted) noexcept;
```

## at

Returns a reference to the mapped value of the element with the given key.

```cpp
template <typename comparable_key_type_ = key_t const &>
mapped_storage_t & at(comparable_key_type_ && key) noexcept;
```

```cpp
template <typename comparable_key_type_ = key_t const &>
mapped_storage_t const & at(comparable_key_type_ && key) const noexcept;
```

Returns a const reference to the mapped value of the element with the given key.

See also: [https://en.cppreference.com/w/cpp/container/unordered_map/at](https://en.cppreference.com/w/cpp/container/unordered_map/at)

Warnings: A missing key has no value to name and this library does not throw, so the call aborts rather than hand back a reference one past the values region.

## operator[]

A temporarily banned function, that is replaced by __`at()`.__

```cpp
template <typename comparable_key_type_ = key_t const &>
void operator[](comparable_key_type_ &&)=delete;
```

See also: [https://en.cppreference.com/w/cpp/container/unordered_map/operator_at](https://en.cppreference.com/w/cpp/container/unordered_map/operator_at)

## count

Number of elements matching the key, either 1 or 0 as duplicates aren't allowed.

```cpp
template <typename comparable_key_type_ = key_t const &>
expected<std::size_t> count(comparable_key_type_ && key) const noexcept;
```

See also: [https://en.cppreference.com/w/cpp/container/unordered_map/count](https://en.cppreference.com/w/cpp/container/unordered_map/count)

## for_each

Invokes the callback for every populated slot, bucket by bucket, until it halts the walk.

```cpp
template <typename callback_type_ = no_op<slot_ref_t>>
status_t for_each(callback_type_ && callback) noexcept;
```

```cpp
template <typename callback_type_ = no_op<const_slot_ref_t>>
status_t for_each(callback_type_ && callback) const noexcept;
```

## emplace_hint

Deleted: hint-based emplace is not supported.

```cpp
template <typename... args_types_>
iterator_t emplace_hint(
    const_iterator_t,
    args_types_ && ...) noexcept=delete;
```

A hint names a position, and an open-addressed table decides position by hashing the key, so there is nothing a caller could usefully hint at. Declaring it deleted rather than omitting it turns a port from `std::unordered_map` into a signposted error instead of an unexplained missing member. Use [`emplace`](#emplace), or [`probe_to_upsert`](#probe_to_upsert) for finer control.

See also: [https://en.cppreference.com/w/cpp/container/unordered_map/emplace_hint](https://en.cppreference.com/w/cpp/container/unordered_map/emplace_hint)

## emplace

Main insertion method for maps, finding the optimal location and overwriting it.

```cpp
template <emplace_report_t report_ = emplace_report_t::no_result_k, typename convertible_key_type_, typename convertible_mapped_type_, typename... tags_types_, typename std::enable_if<can_use_map_emplace<convertible_key_type_, convertible_mapped_type_>(), int>::type = 0>
requires (promises_something<tags_types_> && ...)
std::conditional_t<report_==emplace_report_t::insert_result_k, insert_result_t, void> emplace(
    convertible_key_type_ && key,
    convertible_mapped_type_ && value,
    tags_types_... tags) noexcept;
```

```cpp
template <emplace_report_t report_ = emplace_report_t::no_result_k, typename convertible_key_type_, typename... tags_types_, typename std::enable_if<can_use_set_emplace<convertible_key_type_>(), int>::type = 0>
requires (promises_something<tags_types_> && ...)
std::conditional_t<report_==emplace_report_t::insert_result_k, insert_result_t, void> emplace(
    convertible_key_type_ && key,
    tags_types_... tags) noexcept;
```

Main insertion method for sets, finding the optimal location and overwriting it.

More performant than [`insert`](https://www.unum.cloud/docs/smashtable/cpp/isolation.md#insert), as it avoids temporary object construction.

- `key` (in): The key to insert.
- `value` (in): The mapped value to store under `key`.
- `tags` (in): Markers for special acceleration: `[assume_reserved_t](#assume_reserved_t)` avoids reserving more memory, `[assume_unique_t](#assume_unique_t)` skips equality comparisons.

See also: [https://en.cppreference.com/w/cpp/container/unordered_map/emplace](https://en.cppreference.com/w/cpp/container/unordered_map/emplace)

See also: [https://en.cppreference.com/w/cpp/container/unordered_set/emplace](https://en.cppreference.com/w/cpp/container/unordered_set/emplace)

## insert

Main insertion and upsertion method, compatible with STL code.

```cpp
template <emplace_report_t report_ = emplace_report_t::no_result_k, typename temporary_pack_type_, typename... tags_types_>
requires (!readable_iterator<std::remove_cvref_t<temporary_pack_type_>> && (promises_something<tags_types_> && ...))
std::conditional_t<report_==emplace_report_t::insert_result_k, insert_result_t, void> insert(
    temporary_pack_type_ && pack,
    tags_types_... tags) noexcept;
```

```cpp
template <multipass_iterator begin_iterator_type_, iterator_sentinel<begin_iterator_type_> end_iterator_type_, typename... tags_types_>
requires (promises_about_the_room<tags_types_> && ...)
status_t insert(
    begin_iterator_type_ begin,
    end_iterator_type_ end,
    tags_types_... tags) noexcept;
```

Inserts every element of [ [`begin`](#begin), [`end`](#end) ), refusing the batch when a key is already present here.

All-or-nothing over this table from the first element on, a taken key included: every key is checked against the table before the first of them is written.

See also: [https://en.cppreference.com/w/cpp/container/unordered_map/insert](https://en.cppreference.com/w/cpp/container/unordered_map/insert)

Notes: With maps this expects a [`mapping`](https://www.unum.cloud/docs/smashtable/cpp/stored-types.md#mapping), exposing `key` and `mapped` members.

Statuses: - [`key_already_exists_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#key_already_exists_k) A key is already here or repeats inside the range.
- [`capacity_exhausted_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#capacity_exhausted_k) No slot was free, which only a false `[assume_reserved_t](#assume_reserved_t)` promise provokes.
- Any status an element's [`copy`](#copy) returns passes through unchanged.

## upsert

Writes every element of [ [`begin`](#begin), [`end`](#end) ), replacing the keys already here.

```cpp
template <multipass_iterator begin_iterator_type_, iterator_sentinel<begin_iterator_type_> end_iterator_type_, typename... tags_types_>
requires (promises_about_the_room<tags_types_> && ...)
status_t upsert(
    begin_iterator_type_ begin,
    end_iterator_type_ end,
    tags_types_... tags) noexcept;
```

```cpp
template <typename convertible_element_type_>
status_t upsert(convertible_element_type_ && element) noexcept;
```

Files an element under its own key, replacing whatever key compared equal to it.

All-or-nothing over this table from the first element on. Growth is secured before any slot is written, and after it a bounded probe cannot run out: [`reserve_more`](#reserve_more) leaves at least a quarter of the slots free, and both probes walk every slot before giving up. An element that can refuse its own copy is duplicated in full before the first of them lands, because a slot once written cannot be un-written without leaving a tombstone that moves later probes.

- `element` (in): Element to file, moved into the table.

Statuses: - [`capacity_exhausted_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#capacity_exhausted_k) No slot was free, which only a false `[assume_reserved_t](#assume_reserved_t)` promise provokes.
- Any status an element's [`copy`](#copy) returns passes through unchanged.

Statuses: - [`capacity_exhausted_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#capacity_exhausted_k) The bounded probe found no slot, and only a rehash can make one.

## insert_if_missing

Inserts every element of [ [`begin`](#begin), [`end`](#end) ) whose key is free, leaving each incumbent key alone.

```cpp
template <multipass_iterator begin_iterator_type_, iterator_sentinel<begin_iterator_type_> end_iterator_type_, typename... tags_types_>
requires (promises_about_the_room<tags_types_> && ...)
status_t insert_if_missing(
    begin_iterator_type_ begin,
    end_iterator_type_ end,
    tags_types_... tags) noexcept;
```

All-or-nothing over this table from the first element on, on the same terms as [`upsert`](https://www.unum.cloud/docs/smashtable/cpp/isolation.md#upsert).

Statuses: - [`capacity_exhausted_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#capacity_exhausted_k) No slot was free, which only a false `[assume_reserved_t](#assume_reserved_t)` promise provokes.
- Any status an element's [`copy`](#copy) returns passes through unchanged.

## merge

An interface similar to [`std::unordered_map::merge`](#merge), banned in favor of a manual `insert(begin, end)`.

```cpp
template <typename other_type_>
void merge(other_type_ &&)=delete;
```

See also: [https://en.cppreference.com/w/cpp/container/unordered_map/merge](https://en.cppreference.com/w/cpp/container/unordered_map/merge)

## erase

Removes the element the reference points to, leaving a tombstone behind.

```cpp
void erase(slot_ref_t slot) noexcept;
```

```cpp
void erase(iterator_t slot) noexcept;
```

```cpp
void erase(const_iterator_t)=delete;
```

```cpp
template <typename comparable_key_type_, typename... tags_types_>
requires (promises_something<tags_types_> && ...)
bool erase(comparable_key_type_ && key, tags_types_... tags) noexcept;
```

Removes a value by key in the most efficient fashion.

If you already have the iterator, use the faster overload that avoids the search entirely.

- `key` (in): The key to remove.
- `tags` (in): Markers for special acceleration: `[assume_reserved_t](#assume_reserved_t)` assumes non-empty.

See also: [https://en.cppreference.com/w/cpp/container/unordered_map/erase](https://en.cppreference.com/w/cpp/container/unordered_map/erase)

Warnings: The reference must point at a populated slot.

Notes: Erasures never deallocate; memory stays cluttered until the next `force_resize()`.

## reserve

Grows the table to fit that many elements, if the current capacity is short.

```cpp
reserve_result_t reserve(offset_t planned_elements) noexcept;
```

See also: [https://en.cppreference.com/w/cpp/container/unordered_map/reserve](https://en.cppreference.com/w/cpp/container/unordered_map/reserve)

Statuses: - [`failed_k`](#failed_k) The larger buffer could not be allocated, leaving this table untouched.

## reserve_more

The recommended entry point for bulk insertions, sized for what is present already.

```cpp
reserve_result_t reserve_more(offset_t new_elements) noexcept;
```

Statuses: - [`failed_k`](#failed_k) The larger buffer could not be allocated, leaving this table untouched.

## force_resize

Exports the data into a fresh table of the requested size and swaps the contents.

```cpp
reserve_result_t force_resize(hash_slots_count_t slots_count) noexcept;
```

Also used to clean the tombstones left behind by deletions.

Statuses: - [`failed_k`](#failed_k) The request cannot hold what is stored, or the new buffer could not be allocated, leaving this table untouched either way.

## swap

A cheap copy-less swap mechanism used in move-constructors.

```cpp
void swap(basic_hash_table & other) noexcept;
```

See also: [https://en.cppreference.com/w/cpp/container/unordered_map/swap](https://en.cppreference.com/w/cpp/container/unordered_map/swap)

## clear

Erases all elements, keeping the memory.

```cpp
void clear() noexcept;
```

For deallocation call `shrink_to_fit()`.

See also: [https://en.cppreference.com/w/cpp/container/unordered_map/clear](https://en.cppreference.com/w/cpp/container/unordered_map/clear)

## shrink_to_fit

Brings the memory consumption of the container to the minimum.

```cpp
void shrink_to_fit() noexcept;
```

See also: [https://en.cppreference.com/w/cpp/container/vector/shrink_to_fit](https://en.cppreference.com/w/cpp/container/vector/shrink_to_fit)

Notes: Best-effort, matching the `void` shape of the standard containers: a refused allocation leaves the table exactly as it was, with every element still reachable. Call [`force_resize`](#force_resize) when the outcome has to be known.

## deallocate

Deallocates all the memory used by the container.

```cpp
void deallocate() noexcept;
```

Warnings: Call `clear()` first to destruct all the non-trivial elements.

## rehash

Sets the number of buckets to the desired value, rehashing in the process.

```cpp
reserve_result_t rehash(offset_t count_buckets) noexcept;
```

See also: [https://en.cppreference.com/w/cpp/container/unordered_map/rehash](https://en.cppreference.com/w/cpp/container/unordered_map/rehash)

Notes: A request too small for what is stored is raised to what the current size needs, so `rehash(0)` compacts rather than emptying the table into a layout with no slots at all.

Statuses: - [`failed_k`](#failed_k) The new buffer could not be allocated, leaving this table untouched.

## move_to_new

Creates a new buffer of the requested capacity and rehashes the present data into it.

```cpp
basic_hash_table move_to_new(hash_slots_count_t slots_count) noexcept;
```

Move-constructors are used, avoiding copies, and this table is left deallocated.

## copy_to_new

Duplicates the table, reusing the exact bucket layout when the elements are trivial.

```cpp
basic_hash_table copy_to_new() const noexcept;
```

```cpp
basic_hash_table copy_to_new(
    hash_slots_count_t slots_count) const noexcept;
```

Duplicates the table into a differently sized one, rehashing every element.

## make

Most commonly used __constructor-like__ interface, sized by the planned element count.

```cpp
expected<basic_hash_table> make(
    offset_t planned_elements,
    hasher_t hasher = {},
    equals_t equals = {},
    allocator_t allocator = {}) noexcept;
```

```cpp
expected<basic_hash_table> make(
    hash_slots_count_t slots,
    hasher_t hasher = {},
    equals_t equals = {},
    allocator_t allocator = {}) noexcept;
```

Most commonly used __constructor-like__ interface, sized by the exact slot count.

```cpp
template <multipass_iterator begin_iterator_type_, iterator_sentinel<begin_iterator_type_> end_iterator_type_>
expected<basic_hash_table> make(
    begin_iterator_type_ begin,
    end_iterator_type_ end,
    hasher_t hasher = {},
    equals_t equals = {},
    allocator_t allocator = {}) noexcept;
```

Builds a table pre-sized for [ [`begin`](#begin), [`end`](#end) ) and fills it.

A refusal leaves nothing allocated: the table is new and empty, so there is no earlier state for a half-filled one to be told apart from.

Statuses: - [`capacity_exhausted_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#capacity_exhausted_k) The bounded probe found no slot for an element.

## memory_usage

Total memory needed for the three regions of a table this size.

```cpp
std::size_t memory_usage(hash_slots_count_t slots_count) noexcept;
```

- `slots_count` (in): Total number of slots, a power of two and a multiple of 32.

## insert_result_t

A return type for the insert function, similar to `insert_return_type` in STL.

```cpp
struct insert_result_t
```

`position` names the stored or the conflicting element, and the end when nothing was stored. `outcome` says which of the four happened, so a key already taken, a probe with no slot left and an allocation the table could not make are all distinguishable from one another, without comparing the iterator against `end()`.

- `position` `iterator_t`
- `outcome` `upsert_result_t`

## basic_ring

A first-in first-out ring of at most [`capacity`](#capacity) elements of `value_type_`, which a failed push reports.

```cpp
template <typename value_type_,
          allocator_of<value_type_> allocator_type_ = default_allocator<value_type_>>
class basic_ring
```

## capacity_limit_k

The largest capacity, so a size always fits the 32-bit counters.

```cpp
std::size_t capacity_limit_k;
```

## basic_ring

```cpp
basic_ring() noexcept=default;
```

```cpp
basic_ring(allocator_t allocator) noexcept;
```

```cpp
basic_ring(basic_ring && other) noexcept;
```

```cpp
basic_ring(basic_ring const &)=delete;
```

## ~basic_ring

```cpp
~basic_ring() noexcept;
```

## operator=

```cpp
basic_ring & operator=(basic_ring && other) noexcept;
```

```cpp
basic_ring & operator=(basic_ring const &)=delete;
```

## oldest

The element the next pop removes; the ring must not be empty.

```cpp
value_t & oldest() noexcept;
```

```cpp
value_t const & oldest() const noexcept;
```

## newest

The element the last push added; the ring must not be empty.

```cpp
value_t & newest() noexcept;
```

```cpp
value_t const & newest() const noexcept;
```

## operator[]

The element `index` places after the oldest, without bounds checking.

```cpp
value_t & operator[](std::size_t index) noexcept;
```

```cpp
value_t const & operator[](std::size_t index) const noexcept;
```

## at

The element `index` places after the oldest, or null past the newest.

```cpp
value_t * at(std::size_t index) noexcept;
```

```cpp
value_t const * at(std::size_t index) const noexcept;
```

## push

Appends `element` to a ring known not to be full.

```cpp
status_t push(assume_reserved_t, value_t && element) noexcept;
```

```cpp
status_t push(value_t && element) noexcept;
```

Appends `element`, or answers [`capacity_exhausted_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#capacity_exhausted_k) and leaves the ring alone.

## push_evicting

Appends `element`, first moving the oldest into `evicted` when the ring is full.

```cpp
ring_eviction_t push_evicting(
    value_t && element,
    value_t & evicted) noexcept;
```

Capacity must be nonzero.

## pop

Destroys the oldest element; the ring must not be empty.

```cpp
void pop() noexcept;
```

## pop_into

Moves the oldest element into `destination` and removes it, or answers [`operation_would_block_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#operation_would_block_k).

```cpp
status_t pop_into(value_t & destination) noexcept;
```

## push_many

Copies as many of `elements` as fit, oldest first, and returns how many.

```cpp
requires std::is_nothrow_copy_constructible_v<value_t>
std::size_t push_many(std::span<value_t const> elements) noexcept;
```

## pop_many

Moves as many elements as `destination` holds out of the ring, oldest first, and returns how many.

```cpp
std::size_t pop_many(std::span<value_t> destination) noexcept;
```

## clear

Destroys every element and keeps the slots.

```cpp
void clear() noexcept;
```

## make

An empty ring of [`capacity`](#capacity) slots, where zero allocates nothing and holds nothing.

```cpp
expected<basic_ring> make(
    std::size_t capacity,
    allocator_t allocator = {}) noexcept;
```

Statuses: - [`invalid_argument_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#invalid_argument_k) A capacity that is not a power of two up to [`capacity_limit_k`](#capacity_limit_k).

## basic_vector

Exception-free dynamic array that uses error codes instead of exceptions.

```cpp
template <typename value_type_,
          allocator_of<value_type_> allocator_type_ = default_allocator<value_type_>>
class basic_vector
```

Provides RAII memory management with explicit failure handling, unlike `std::vector`.

#### Template Requirements

- `value_type_` must be nothrow move-constructible, and nothrow default-constructible to be resized.
- For types with potentially throwing constructors, provide a static ``.make() method returning `expected<value_type_>` to enable exception-free construction via `emplace_back()`.

See also: [https://en.cppreference.com/w/cpp/container/vector](https://en.cppreference.com/w/cpp/container/vector)

## basic_vector

Default constructor creates an empty vector.

```cpp
basic_vector() noexcept=default;
```

```cpp
basic_vector(allocator_t allocator) noexcept;
```

Constructor with custom allocator.

```cpp
basic_vector(basic_vector && other) noexcept;
```

Move constructor transfers ownership.

```cpp
basic_vector(basic_vector const &)=delete;
```

Copy construction is deleted (use ``.copy() method for explicit copies).

- `allocator` (in): The allocator instance to use.

## ~basic_vector

Destructor deallocates memory and destroys all elements.

```cpp
~basic_vector() noexcept;
```

## operator=

Move assignment transfers ownership after destroying current elements.

```cpp
basic_vector & operator=(basic_vector && other) noexcept;
```

```cpp
basic_vector & operator=(basic_vector const &)=delete;
```

Copy assignment is deleted (use ``.copy() method for explicit copies).

## copy

Creates a deep copy of this vector.

```cpp
expected<basic_vector> copy() const noexcept;
```

## reserve

Reserves capacity for at least `new_capacity` elements.

```cpp
status_t reserve(std::size_t new_capacity) noexcept;
```

Grows by at least a doubling, so asking for one more slot at a time still amortizes to constant cost.

- `new_capacity` (in): The new capacity.

Statuses: - [`out_of_memory_heap_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#out_of_memory_heap_k) The byte count of `new_capacity` overflows the size type.

## push_back

Appends an element without capacity check (performance variant).

```cpp
status_t push_back(assume_reserved_t, value_t && value) noexcept;
```

```cpp
status_t push_back(value_t && value) noexcept;
```

Appends an element to the end of the vector.

Requires pre-reserved capacity. Use for hot paths after `reserve()`.

Tag indicating capacity was pre-reserved.

- `value` (in): Element to append (moved into the vector).

## pop_back

Removes the last element from the vector.

```cpp
void pop_back() noexcept;
```

Precondition: Vector must not be empty.

## insert

Inserts `value` at `position` into reserved room, shifting the tail up by one.

```cpp
status_t insert(
    assume_reserved_t,
    std::size_t position,
    value_t && value) noexcept;
```

```cpp
status_t insert(std::size_t position, value_t && value) noexcept;
```

Inserts `value` at `position`, shifting the elements at and after it up by one.

Linear in the elements after `position`, which is what a sorted run of a few hundred entries costs and why an ordered container built on this stays small.

- `position` (in): Index the new element takes, at most `size()`.
- `value` (in): Element to insert (moved into the vector).

## erase

Removes `position's` element, handing it to `callback`, then shifts the rest down.

```cpp
template <typename callback_type_ = no_op_t>
requires std::invocable<callback_type_ &, value_t &>
void erase(
    std::size_t position,
    callback_type_ && callback = {}) noexcept;
```

```cpp
template <typename callback_type_ = no_op_t>
requires std::invocable<callback_type_ &, value_t &>
void erase(
    std::size_t position,
    std::size_t count,
    callback_type_ && callback = {}) noexcept;
```

Removes [`count`](https://www.unum.cloud/docs/smashtable/cpp/isolation.md#count) elements from `position`, handing each to `callback` first and shifting the rest down.

- `position` (in): Index of the element to remove, below `size()`.
- `callback` (in): Receives the element before it is moved away. Must be `noexcept`.
- `count` (in): Elements to remove, which must not run past the end.

## erase_if

Removes every element `predicate` admits in one pass, keeping the order of the rest.

```cpp
template <typename predicate_type_, typename callback_type_ = no_op_t>
requires std::predicate<predicate_type_ &, value_t &> && std::invocable<callback_type_ &, value_t &>
std::size_t erase_if(
    predicate_type_ && predicate,
    callback_type_ && callback = {}) noexcept;
```

- `predicate` (in): Decides which elements go. Must be `noexcept`.
- `callback` (in): Receives each removed element before it moves away. Must be `noexcept`.

## emplace_back

Constructs element in-place without capacity check (performance variant).

```cpp
template <typename... args_types_>
status_t emplace_back(
    assume_reserved_t,
    args_types_ &&... args) noexcept;
```

```cpp
template <typename... args_types_>
status_t emplace_back(args_types_ &&... args) noexcept;
```

Constructs element in-place at the end of the vector.

Requires pre-reserved capacity. Use for hot paths after `reserve()`.

Tag indicating capacity was pre-reserved.

- `args` (in): Arguments to forward to element constructor.

Notes: For types with potentially throwing constructors, provide a static ``.make() method returning `expected<value_t>` to enable exception-free construction.

## resize

Resizes the vector to contain `new_size` elements.

```cpp
status_t resize(std::size_t new_size) noexcept;
```

```cpp
requires std::is_trivially_copyable_v<value_t>
status_t resize(assume_uninitialized_t, std::size_t new_size) noexcept;
```

Resizes the vector to `new_size` without constructing the new elements, so their first writer can be a kernel or a byte copy rather than the host.

```cpp
status_t resize(std::size_t new_size, value_t const & value) noexcept;
```

Resizes the vector and initializes new elements with `value`.

If `new_size` < `size()`, elements are destroyed. If `new_size` > `size()`, new elements are default-constructed.

- `new_size` (in): The new size.
- `value` (in): Value to copy into new elements.

## assign

Replaces the contents with a copy of [`values`](#values), all or nothing.

```cpp
status_t assign(std::span<value_t const> values) noexcept;
```

- `values` (in): Elements to copy, never ones of this vector's own.

## clear

Destroys all elements but keeps allocated capacity.

```cpp
void clear() noexcept;
```

## swap

Swaps contents with another vector.

```cpp
status_t swap(basic_vector & other) noexcept;
```

- `other` (inout): The vector to swap with.

Notes: If `propagate_on_container_swap` is false (e.g., [`std::allocator`](#allocator)), allocators must compare equal. Attempting to swap vectors with unequal non-propagating allocators returns [`invalid_argument_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#invalid_argument_k) and leaves both vectors unchanged.

Statuses: - [`invalid_argument_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#invalid_argument_k) Allocators are incompatible.

## operator[]

Accesses element at `index` without bounds checking.

```cpp
value_t & operator[](std::size_t index) noexcept;
```

```cpp
value_t const & operator[](std::size_t index) const noexcept;
```

Accesses element at `index` without bounds checking (const version).

- `index` (in): The element index.

## at

Accesses element at `index` with bounds checking.

```cpp
value_t * at(std::size_t index) noexcept;
```

```cpp
value_t const * at(std::size_t index) const noexcept;
```

Accesses element at `index` with bounds checking (const version).

- `index` (in): The element index.

## front

Accesses the first element.

```cpp
value_t & front() noexcept;
```

```cpp
value_t const & front() const noexcept;
```

Accesses the first element (const version).

## back

Accesses the last element.

```cpp
value_t & back() noexcept;
```

```cpp
value_t const & back() const noexcept;
```

Accesses the last element (const version).

## data

Returns pointer to underlying array.

```cpp
value_t * data() noexcept;
```

```cpp
value_t const * data() const noexcept;
```

Returns pointer to underlying array (const version).

## empty

Checks whether the vector is empty.

```cpp
bool empty() const noexcept;
```

## size

Returns the number of elements.

```cpp
std::size_t size() const noexcept;
```

## capacity

Returns the capacity.

```cpp
std::size_t capacity() const noexcept;
```

## get_allocator

A copy of this vector's allocator, for building a sibling that allocates the same way.

```cpp
allocator_t get_allocator() const noexcept;
```

## begin

Returns an iterator to the beginning.

```cpp
value_t * begin() noexcept;
```

```cpp
value_t const * begin() const noexcept;
```

Returns a const iterator to the beginning.

## end

Returns an iterator to the end.

```cpp
value_t * end() noexcept;
```

```cpp
value_t const * end() const noexcept;
```

Returns a const iterator to the end.

## make

Creates a new vector with specified capacity.

```cpp
expected<basic_vector> make(std::size_t initial_capacity) noexcept;
```

```cpp
expected<basic_vector> make(
    std::size_t initial_capacity,
    allocator_t allocator) noexcept;
```

Creates a new vector with specified capacity and allocator.

- `initial_capacity` (in): Initial capacity to allocate.
- `allocator` (in): The allocator instance to use.

## basic_wb_node

Node for weight-balanced binary search tree.

```cpp
template <typename value_type_,
          typename comparator_type_,
          typename augmentation_type_ = no_augmentation_t>
class basic_wb_node
```

Stores subtree size for O(log n) order statistics and O(1) amortized rebalancing.

#### Rebalancing Parameters

Δ = 3 is the rotation threshold: rebalance when weight(left) > 3 × weight(right) or vice versa, with weight = size + 1. Γ = 2 selects the rotation type: a single rotation when weight(heavy.inner) < 2 × weight(heavy.outer).

These are the __only__ valid integer parameters, proven in Coq by Hirai and Yamamoto in 2011, and are exposed as `delta_k` and `gamma_k`.

Layout: `payload` is the stored entry, `left` and `right` the links, and [`size`](https://www.unum.cloud/docs/smashtable/cpp/isolation.md#size) the number of nodes in the subtree rooted here - invariant [`size`](https://www.unum.cloud/docs/smashtable/cpp/isolation.md#size) `=` `1` `+` `size(left)` `+` `size(right)`, which is what makes [`select`](https://www.unum.cloud/docs/smashtable/cpp/isolation.md#select) and [`rank`](https://www.unum.cloud/docs/smashtable/cpp/isolation.md#rank) logarithmic.

#### Augmentation

An augmented tree keeps [`augmented_size`](#augmented_size) next to [`size`](https://www.unum.cloud/docs/smashtable/cpp/isolation.md#size), holding the number of entries in the subtree for which `augmentation_type_::augmented_count` returns 1. Because that count is read off the entry, every rotation, join, and split restores it from the moved node's own entry and its two children. An entry whose count flips while it sits in the tree is repaired by [`refresh_augmentation`](#refresh_augmentation), which rewalks only the root-to-entry path and may be called any number of times per write - one wrapper operation is free to retag several entries.

## node_placement_t

What a walk that may create a node did with the key it was handed.

```cpp
enum node_placement_t
```

- `refused_k`: No node was available to store the key, so nothing was stored.
- `matched_k`: An equal key was already there, and `match` names the node holding it.
- `made_k`: A fresh node took the key, and `match` names it.

## augmented_count_t

The augmented counter, degenerating to an empty type when no augmentation is asked for.

```cpp
using augmented_count_t = std::conditional_t<is_augmented_k, std::size_t, no_augmented_count_t>;
```

## is_augmented_k

True when a second count is maintained, which is what gates every augmented code path.

```cpp
bool is_augmented_k;
```

## get_augmented_size

Number of entries in the subtree rooted at `node` that the policy counts.

```cpp
size_t get_augmented_size(node_t *node) noexcept;
```

## get_own_augmented_count

The entry's own contribution to the augmented count, 0 or 1.

```cpp
size_t get_own_augmented_count(node_t *node) noexcept;
```

## find_min

Find minimum (leftmost) node in subtree.

```cpp
node_t * find_min(node_t *node) noexcept;
```

- `node` (in): Root of subtree.

## find_max

Find maximum (rightmost) node in subtree.

```cpp
node_t * find_max(node_t *node) noexcept;
```

- `node` (in): Root of subtree.

## find_successor

Finds the next node in in-order traversal (successor).

```cpp
node_t * find_successor(
    node_t *root,
    node_t *node,
    comparator_t const & comparator) noexcept;
```

- `root` (in): Root of the tree.
- `node` (in): Current node.
- `comparator` (in): Comparator for ordering.

## find_predecessor

Finds the previous node in in-order traversal (predecessor).

```cpp
node_t * find_predecessor(
    node_t *root,
    node_t *node,
    comparator_t const & comparator) noexcept;
```

- `root` (in): Root of the tree.
- `node` (in): Current node.
- `comparator` (in): Comparator for ordering.

## select

Select k-th smallest element (0-indexed).

```cpp
node_t * select(
    node_t *node,
    size_t k,
    comparator_t const & comparator) noexcept;
```

Runs in O(log n) expected time, where n = size(node).

Finding the median and the first quartile:

```
auto median = select(root, size/2, comp);  // Find median
auto q1 = select(root, size/4, comp);      // First quartile
```

- `node` (in): Root of subtree.
- `k` (in): Index of element to find (0 = minimum, size-1 = maximum).
- `comparator` (in): Comparator instance.

## rank

Find rank (position) of element in sorted order.

```cpp
template <typename comparable_type_>
size_t rank(
    node_t *node,
    comparable_type_ && comparable,
    comparator_t const & comparator) noexcept;
```

Runs in O(log n) expected time. Counting the elements ordered before `value:`

```
auto position = rank(root, value, comp);
// position elements are smaller than value
// If value exists, it's at index position
```

- `node` (in): Root of subtree.
- `comparable` (in): Key to find rank of.
- `comparator` (in): Comparator instance.

## select_augmented

Select the k-th smallest entry among those the augmentation policy counts.

```cpp
node_t * select_augmented(node_t *node, size_t k) noexcept;
```

Runs in O(log n) time: one root-to-node path, reading only the stored counts.

- `node` (in): Root of subtree.
- `k` (in): Index among counted entries, 0 for the smallest.

## rank_augmented

Number of counted entries ordered before `comparable`.

```cpp
template <typename comparable_type_>
size_t rank_augmented(
    node_t *node,
    comparable_type_ && comparable,
    comparator_t const & comparator) noexcept;
```

Runs in O(log n) time.

- `node` (in): Root of subtree.
- `comparable` (in): Key to find the augmented rank of.
- `comparator` (in): Comparator instance.

## refresh_augmentation

Repairs augmented counts on the path to `comparable` after its predicate flipped.

```cpp
template <typename comparable_type_>
bool refresh_augmentation(
    node_t *node,
    comparable_type_ && comparable,
    comparator_t const & comparator) noexcept;
```

Runs in O(log n) time, touching only the ancestors whose counts could have moved.

## for_each_left_right

In-order traversal (left-root-right) with callback.

```cpp
template <typename callback_type_>
walk_control_t for_each_left_right(
    node_t *node,
    callback_type_ && callback) noexcept;
```

Visits nodes in sorted order according to comparator.

- `node` (in): Root of subtree to traverse.
- `callback` (in): Callback to invoke for each node. Must be `noexcept`.

## range

Finds all nodes in the half-open range [low, high) and invokes callback for each.

```cpp
template <typename lower_type_, typename upper_type_, typename callback_type_>
walk_control_t range(
    node_t *node,
    lower_type_ && low,
    upper_type_ && high,
    comparator_t const & comparator,
    callback_type_ && callback) noexcept;
```

Recursively traverses the tree, visiting only nodes within the specified range.

- `node` (in): Root of subtree to search.
- `low` (in): Lower bound of range (inclusive).
- `high` (in): Upper bound of range (exclusive).
- `comparator` (in): Comparator for element comparison.
- `callback` (in): Callback to invoke for each node in range. Must be `noexcept`.

Warnings: Current recursive implementation is suboptimal.

## update_size

Update size field to match children.

```cpp
void update_size(node_t *node) noexcept;
```

Must be called after any operation that modifies children.

## update_augmented_size

Recomputes only the augmented count, for a node whose shape is already correct.

```cpp
void update_augmented_size(node_t *node) noexcept;
```

Used where an entry's own predicate changed but no link moved.

## reset_to_leaf

Restores a node whose links were just cleared, so both counts describe it alone.

```cpp
void reset_to_leaf(node_t *node) noexcept;
```

## build_from_sorted

Builds a balanced tree from sorted range [ `first`, `first` + [`count`](https://www.unum.cloud/docs/smashtable/cpp/isolation.md#count) ) in O(n).

```cpp
template <multipass_iterator iterator_type_, allocator_of<node_t> node_allocator_type_>
build_result_t build_from_sorted(
    iterator_type_ first,
    std::size_t count,
    node_allocator_type_ & allocator) noexcept;
```

- `first` (in): Beginning of the sorted range.
- `count` (in): Number of elements in the range.
- `allocator` (inout): Hands back a raw node, or `nullptr` when it cannot.

Warnings: An unsorted range builds a tree whose structure is undefined.

Notes: A range handing out rvalues, as a move iterator does, gives its elements up.

Statuses: - Any status an element's [`copy`](#copy) returns passes through unchanged.

## rotate_right

Single right rotation.

```cpp
node_t * rotate_right(node_t *y) noexcept;
```

```
*      y              x
*     / \            / \
*    x   C    =>    A   y
*   / \                / \
*  A   B              B   C
*
```

## rotate_left

Single left rotation.

```cpp
node_t * rotate_left(node_t *x) noexcept;
```

```
*    x                y
*   / \              / \
*  A   y      =>    x   C
*     / \          / \
*    B   C        A   B
*
```

## get_weight

Weight of a subtree, counting the empty tree as 1.

```cpp
size_t get_weight(node_t *node) noexcept;
```

Hirai and Yamamoto state the invariant over `size+1`; comparing raw sizes makes every node with an empty child look unbalanced and asks for rotations that cannot be performed, since the pivot's child is null.

## is_balanced

Check if node satisfies weight-balance invariant.

```cpp
bool is_balanced(node_t *node) noexcept;
```

## rebalance

Rebalances a node whose weight invariant is violated.

```cpp
node_t * rebalance(node_t *node) noexcept;
```

Uses Δ = 3 and Γ = 2, the only valid integer solution.

When the left side is too heavy, weight(left) > 3 × weight(right), a single right rotation fixes it if weight(left.right) < 2 × weight(left.left), and a double left-right rotation does otherwise. The right-heavy case mirrors this.

## extract

Pops the root replacing it with one of descendants, if present.

```cpp
extract_result_t extract(
    node_t *node,
    comparator_t const & comparator) noexcept;
```

```cpp
template <typename comparable_type_>
extract_result_t extract(
    node_t *node,
    comparable_type_ && comparable,
    comparator_t const & comparator) noexcept;
```

Searches for a matching ancestor and extracts it out.

- `node` (in): Node to extract.
- `comparator` (in): Comparator for element comparison.
- `comparable` (in): Any key comparable with stored entries.

## insert

Inserts an existing node into the tree.

```cpp
find_or_make_result_t insert(
    node_t *node,
    node_t *new_child,
    comparator_t const & comparator) noexcept;
```

Used by merge to insert extracted nodes.

- `node` (in): Root of subtree to insert into.
- `new_child` (in): Pre-allocated node to insert.
- `comparator` (in): Comparator for element comparison.

## upsert

Inserts or updates an element in the tree.

```cpp
template <allocator_of<node_t> node_allocator_type_>
find_or_make_result_t upsert(
    node_t *node,
    value_type_ && payload,
    comparator_t const & comparator,
    node_allocator_type_ & allocator) noexcept;
```

If key exists, overwrites the element. If not, creates new node.

- `node` (in): Root of subtree.
- `payload` (in): Entry to insert or assign (moved).
- `comparator` (in): Comparator for element comparison.
- `allocator` (inout): Hands back a raw node, or `nullptr` when it cannot.

## for_each_bottom_up

Visits every node bottom-up, so a caller may free each one as it goes.

```cpp
template <typename callback_type_>
void for_each_bottom_up(
    node_t *node,
    callback_type_ && callback) noexcept;
```

## erase_if

Drops every node satisfying `predicate`, returning the new root and surviving count.

```cpp
template <typename predicate_type_, typename node_deallocator_type_>
requires std::predicate<predicate_type_ &, value_t &>
erase_if_result_t erase_if(
    node_t *node,
    predicate_type_ && predicate,
    node_deallocator_type_ && node_deallocator,
    comparator_t const & comparator) noexcept;
```

Both halves may shed any number of nodes, so the two survivors are re-joined rather than stitched back in place - rotating once could not close a gap of many weight classes.

## sample_range

Uniformly samples one node whose key lies in [lower, upper), or nullptr when empty.

```cpp
template <typename lower_type_, typename upper_type_, typename generator_type_, typename predicate_type_ = no_op_t>
requires uniform_random_bits<std::remove_cvref_t<generator_type_>> && (std::same_as<std::remove_cvref_t<predicate_type_>, no_op_t> || std::predicate<predicate_type_ &, node_t *>)
node_t * sample_range(
    node_t *node,
    lower_type_ && lower,
    upper_type_ && upper,
    comparator_t const & comparator,
    generator_type_ && generator,
    predicate_type_ && predicate = {}) noexcept;
```

## join_with_root

Joins two trees with a root node between them.

```cpp
node_t * join_with_root(
    node_t *left,
    node_t *root,
    node_t *right) noexcept;
```

Precondition: [`root`](#root) is non-null and all(left) < root < all(right).

The two sides may sit many weight classes apart, so hanging [`root`](#root) between them and rotating once is not enough. Walking down the heavier side's inner spine until the two pieces are within Δ of each other, then rebalancing on the way back up, is what keeps the invariant - this is what makes [`split`](#split) and [`erase_range`](https://www.unum.cloud/docs/smashtable/cpp/isolation.md#erase_range) produce balanced trees. Runs in O(log n) expected time, where n is the size of the larger tree.

- `left` (in): Left subtree (all elements < root).
- `root` (in): Middle node to join with.
- `right` (in): Right subtree (all elements > root).

## join

Joins two trees where all(left) < all(right).

```cpp
node_t * join(
    node_t *left,
    node_t *right,
    comparator_t const & comparator) noexcept;
```

Recursively joins trees by extracting min from right subtree.

Runs in O(log n) expected time.

- `left` (in): Left subtree.
- `right` (in): Right subtree.
- `comparator` (in): Comparator for ordering elements.

## split

Splits tree at a given key.

```cpp
template <typename comparable_type_>
split_result_t split(
    node_t *node,
    comparable_type_ && comparable,
    comparator_t const & comparator) noexcept;
```

Returns two trees: left contains all elements < comparable, right contains all elements >= comparable.

Runs in O(log n) expected time. Splitting around 5:

```
auto [left, right] = split(root, 5, comp);
// left: all elements = 5
```

- `node` (in): Root of tree to split.
- `comparable` (in): Key to split at.
- `comparator` (in): Comparator for element comparison.

## build_result_t

What a bulk build produced, and why it stopped where it did.

```cpp
struct build_result_t
```

Not an [`expected`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#expected), which holds a value or a reason and never both: a refused build still owns every node it made, and whoever asked for it has to free them.

- `root` `node_t *`: Everything that was built, which the owner frees whether the build finished or not.
- `status` `status_t`: Why the build stopped: a refused node, a refused element copy, or [`success_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#success_k).
- `count` `std::size_t`: How many nodes hang off [`root`](#root); a partial build leaves this short of the range.

## split_result_t

Result of splitting a tree at a key.

```cpp
struct split_result_t
```

- `left` `node_t *`: Subtree with all elements ordered before the split key.
- `right` `node_t *`: Subtree with all elements not ordered before the split key.

## basic_wb_tree

Weight-balanced tree container with order statistics support.

```cpp
template <typename value_type_,
          typename comparator_type_ = less_t,
          typename node_allocator_type_ = std::allocator<basic_wb_node<value_type_, comparator_type_>>,
          typename augmentation_type_ = no_augmentation_t>
class basic_wb_tree
```

Provides ordered storage similar to `std::set` with additional O(log n) select/rank operations.

#### Order Statistics API

Beyond standard tree operations, provides:

- `select(k)`: Find k-th smallest element in O(log n)
- `rank(x)`: Find position of element x in O(log n)
Use cases: pagination, percentiles, quantiles, window functions.

## key_t

SFINAE to extract key_type for maps, or use value_type for sets.

```cpp
using key_t = typename mapping_key_type_or_itself<value_t>::type;
```

## mapped_t

SFINAE to extract mapped_type for maps, or void for sets.

```cpp
using mapped_t = typename mapped_value_type_or_void<value_t>::type;
```

## is_associative

Trait to indicate this container uses iterator-based reads, not callbacks.

```cpp
using is_associative = std::bool_constant<is_mapping<value_t>>;
```

## rebind

Rebind this tree type to different element and comparator types.

```cpp
template <typename other_value_type_, typename other_comparator_>
using rebind = basic_wb_tree<other_value_type_, other_comparator_, typename std::allocator_traits<node_allocator_type_>::template rebind_alloc<basic_wb_node<other_value_type_, other_comparator_, augmentation_type_>>, augmentation_type_>;
```

Follows STL allocator rebind pattern for type transformations.

## basic_wb_tree

Default constructor.

```cpp
basic_wb_tree() noexcept=default;
```

```cpp
basic_wb_tree(allocator_t allocator) noexcept;
```

```cpp
basic_wb_tree(comparator_t comparator, allocator_t allocator) noexcept;
```

Seeds both policies, which a stateful comparator needs to survive a rebind.

```cpp
basic_wb_tree(wb_tree_t && other) noexcept;
```

Move constructor.

```cpp
basic_wb_tree(wb_tree_t const &)=delete;
```

Creates empty tree.

## operator=

Move assignment operator.

```cpp
wb_tree_t & operator=(wb_tree_t && other) noexcept;
```

```cpp
wb_tree_t & operator=(wb_tree_t const &)=delete;
```

## ~basic_wb_tree

Destructor.

```cpp
~basic_wb_tree() noexcept;
```

Deallocates all nodes.

## empty

Checks whether the tree is empty.

```cpp
bool empty() const noexcept;
```

## insert

Inserts an element only when its key is absent, leaving any incumbent alone.

```cpp
upserted_node_t insert(value_t && payload) noexcept;
```

```cpp
template <readable_iterator input_iterator_type_, typename... tags_types_>
requires (promises_about_the_range<tags_types_> && ...)
status_t insert(
    input_iterator_type_ first,
    input_iterator_type_ last,
    tags_types_... tags) noexcept;
```

Inserts [ `first`, `last` ), refusing the batch on any key already here.

All-or-nothing over this tree from the first element on, a taken key included: the whole range is staged and checked before the merge absorbing it relinks a single node.

- `payload` (in): Entry to insert, moved into the tree only when a node is made for it.

Statuses: - [`refused_k`](#refused_k) The allocator refused the node, so nothing was stored.

Statuses: - [`key_already_exists_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#key_already_exists_k) A key repeats inside an unsorted range or is already in this tree.
- Any status an element's [`copy`](#copy) returns passes through unchanged.

## insert_or_assign

Atomically inserts or updates an element.

```cpp
template <typename comparable_type_>
upserted_node_t insert_or_assign(
    comparable_type_ && comparable) noexcept;
```

Overwrites the existing element if key exists. Matches `std::map::insert_or_assign()` semantics.

- `comparable` (in): Entry to insert or assign (moved into the tree).

Statuses: - [`refused_k`](#refused_k) The key is absent and the allocator refused its node, so nothing was stored.

## upsert

Alias for `insert_or_assign()`.

```cpp
template <typename comparable_type_>
upserted_node_t upsert(comparable_type_ && comparable) noexcept;
```

```cpp
template <readable_iterator input_iterator_type_, typename... tags_types_>
requires (promises_about_the_range<tags_types_> && ...)
status_t upsert(
    input_iterator_type_ first,
    input_iterator_type_ last,
    tags_types_... tags) noexcept;
```

Writes every element of [ `first`, `last` ), overwriting the keys already here.

Atomically inserts or updates an element.

- `comparable` (in): Entry to insert or assign (moved into the tree).

Statuses: - [`refused_k`](#refused_k) The key is absent and the allocator refused its node, so nothing was stored.

Statuses: - Any status an element's [`copy`](#copy) returns passes through unchanged.

## clear

Removes all elements from the tree.

```cpp
void clear() noexcept;
```

## contains

Existence check, heterogeneous when the comparator declares `is_transparent`.

```cpp
template <typename comparable_type_ = value_t>
expected<bool> contains(comparable_type_ && comparable) const noexcept;
```

- `comparable` (in): Object comparable to [`value_t`](#value_t).

## count

Number of elements matching `comparable`, which is 0 or 1 for unique keys.

```cpp
template <typename comparable_type_ = value_t>
expected<std::size_t> count(
    comparable_type_ && comparable) const noexcept;
```

- `comparable` (in): Object comparable to [`value_t`](#value_t).

## select

Select k-th smallest element (0-indexed).

```cpp
node_t * select(size_t k) noexcept;
```

```cpp
node_t const * select(size_t k) const noexcept;
```

Select k-th smallest element (const version).

Runs in O(log n) expected time. Printing the median:

```
auto median_node = tree.select(tree.size() / 2);
if (median_node) fmt::println("Median: {}", median_node->payload);
```

- `k` (in): Index of element to find (0 = minimum, size-1 = maximum).

## rank

Find rank (position) of element in sorted order.

```cpp
size_t rank(value_t const & payload) const noexcept;
```

Runs in O(log n) expected time. Counting the elements ordered before 42:

```
auto position = tree.rank(42);
// position elements are smaller than 42
```

- `payload` (in): Entry to find rank of.

## augmented_size

Number of entries the augmentation policy counts across the whole tree.

```cpp
size_t augmented_size() const noexcept;
```

Exact for the counts as they stand now. One scalar per node cannot encode a function of a parameter, so a reader whose predicate differs from the one currently materialized in the entries - an older snapshot, say - gets no answer from this count and none of the descents built on it.

## select_augmented

Select the k-th smallest entry among those the augmentation policy counts, O(log n).

```cpp
node_t * select_augmented(size_t k) noexcept;
```

```cpp
node_t const * select_augmented(size_t k) const noexcept;
```

Select over the augmented count, const version.

## rank_augmented

Number of counted entries ordered before `comparable`, in O(log n).

```cpp
template <typename comparable_type_>
size_t rank_augmented(comparable_type_ && comparable) const noexcept;
```

## refresh_augmentation

Tells the tree that the entry matching `comparable` changed its augmented count.

```cpp
template <typename comparable_type_>
bool refresh_augmentation(comparable_type_ && comparable) noexcept;
```

Repairs the root-to-entry path in O(log n) rather than rescanning.

A wrapper calls this once per retagged entry, which may be several per write when one publish supersedes another entry.

## for_each

Iterates over all entries in sorted order.

```cpp
template <typename callback_type_>
status_t for_each(callback_type_ && callback) noexcept;
```

- `callback` (in): Callback to invoke for each element. Must be `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.

## total_imbalance

Sum of absolute subtree-size differences, used by the tests to watch balance quality.

```cpp
std::size_t total_imbalance() const noexcept;
```

## erase_if

Drops every element satisfying `predicate` and reports how many went.

```cpp
template <typename predicate_type_>
requires std::predicate<predicate_type_ &, value_t &>
std::size_t erase_if(predicate_type_ && predicate) noexcept;
```

## erase_range

Erases the half-open range [lower, upper), invoking `callback` for each element.

```cpp
template <typename lower_type_, typename upper_type_, typename callback_type_ = no_op_t>
void erase_range(
    lower_type_ && lower,
    upper_type_ && upper,
    callback_type_ && callback = {}) noexcept;
```

Splitting twice and re-joining keeps this O(log N + K) rather than K separate erases.

## extract

Extracts a node from the tree.

```cpp
template <typename comparable_type_>
extract_result_t extract(comparable_type_ && comparable) noexcept;
```

The extracted node is removed from the tree and returned in an RAII wrapper.

Runs in O(log n) expected time. Moving the node for 42 into another tree:

```
auto extracted = tree.extract(42);
if (extracted) {
    other_tree.merge(std::move(extracted));
}
```

- `comparable` (in): Key to extract.

## merge

Merges an extracted node into this tree.

```cpp
void merge(extract_result_t other) noexcept;
```

```cpp
void merge(wb_tree_t & other) noexcept;
```

Merges another tree into this one, transferring all nodes.

```cpp
void merge(wb_tree_t & other, assume_unique_t) noexcept;
```

Merges another tree into this one, assuming all keys are unique.

Elements with keys that already exist in this tree are deallocated (not kept in source).

- `other` (in): Extracted node to merge.

Notes: Unlike `std::set::merge()`, a node with a duplicate key is deallocated rather than being returned. This ensures no memory leaks in a noexcept context.

Notes: Unlike `std::set::merge()`, nodes with duplicate keys are deallocated rather than remaining in the source container. This ensures no memory leaks in a noexcept context.

Notes: Complexity: O(m log n) where m = other.size(), n = this.size().

Preconditions: All keys in `other` must be different from keys in this tree.

Warnings: If precondition violated (duplicate keys exist), behavior is undefined.

## range

Visits every element in [lower, upper) in sorted order, or fewer if the callback halts.

```cpp
template <typename lower_type_ = value_t, typename upper_type_ = value_t, typename callback_type_ = no_op_t>
status_t range(
    lower_type_ && lower,
    upper_type_ && upper,
    callback_type_ && callback) const noexcept;
```

```cpp
template <typename lower_type_ = value_t, typename upper_type_ = value_t, typename callback_type_ = no_op_t>
status_t range(
    lower_type_ && lower,
    upper_type_ && upper,
    callback_type_ && callback) noexcept;
```

Same range walk, but the callback may modify each element in place.

## find_copy

Copies out the element equal to `comparable`.

```cpp
template <typename comparable_type_>
expected<value_t> find_copy(
    comparable_type_ && comparable) const noexcept;
```

Statuses: - [`key_not_found_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#key_not_found_k) No element is equal to `comparable`.
- Any status the element's [`copy`](#copy) returns passes through unchanged.

## lower_bound_copy

Copies out the first element not less than `comparable`.

```cpp
template <typename comparable_type_>
expected<value_t> lower_bound_copy(
    comparable_type_ && comparable) const noexcept;
```

Statuses: - [`key_not_found_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#key_not_found_k) Every element is less than `comparable`.
- Any status the element's [`copy`](#copy) returns passes through unchanged.

## upper_bound_copy

Copies out the first element greater than `comparable`.

```cpp
template <typename comparable_type_>
expected<value_t> upper_bound_copy(
    comparable_type_ && comparable) const noexcept;
```

Statuses: - [`key_not_found_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#key_not_found_k) No element is greater than `comparable`.
- Any status the element's [`copy`](#copy) returns passes through unchanged.

## insert_if_missing

Inserts one element only when its key is absent, leaving any existing element alone.

```cpp
template <typename comparable_type_>
inserted_iterator_t insert_if_missing(
    comparable_type_ && comparable) noexcept;
```

```cpp
template <readable_iterator input_iterator_type_, typename... tags_types_>
requires (promises_about_the_range<tags_types_> && ...)
status_t insert_if_missing(
    input_iterator_type_ first,
    input_iterator_type_ last,
    tags_types_... tags) noexcept;
```

Inserts [ `first`, `last` ) where the key is free, leaving incumbents alone.

All-or-nothing over this tree from the first element on: a node the allocator refuses and an element refusing its own copy are both met while the staging tree is built, and the merge absorbing it only relinks nodes.

Statuses: - Any status an element's [`copy`](#copy) returns passes through unchanged.

## begin

Returns iterator to first element (minimum).

```cpp
iterator begin() noexcept;
```

```cpp
const_iterator begin() const noexcept;
```

Returns const iterator to first element (minimum).

## cbegin

Returns const iterator to first element (minimum).

```cpp
const_iterator cbegin() const noexcept;
```

## end

Returns iterator to past-the-end element.

```cpp
iterator end() noexcept;
```

```cpp
const_iterator end() const noexcept;
```

Returns const iterator to past-the-end element.

## cend

Returns const iterator to past-the-end element.

```cpp
const_iterator cend() const noexcept;
```

## find

Finds an element equal to the given `comparable`.

```cpp
template <typename comparable_type_>
iterator find(comparable_type_ && comparable) noexcept;
```

```cpp
template <typename comparable_type_>
const_iterator find(comparable_type_ && comparable) const noexcept;
```

Finds an element equal to the given `comparable` (const version).

Heterogeneous lookup supported if comparator defines `is_transparent`.

- `comparable` (in): Object comparable to [`value_t`](#value_t).

## lower_bound

Finds the first element not less than the given `comparable` (lower bound).

```cpp
template <typename comparable_type_>
iterator lower_bound(comparable_type_ && comparable) noexcept;
```

```cpp
template <typename comparable_type_>
const_iterator lower_bound(
    comparable_type_ && comparable) const noexcept;
```

Finds the first element not less than the given `comparable` (const version).

- `comparable` (in): Object comparable to [`value_t`](#value_t).

## upper_bound

Finds the first element greater than the given `comparable` (upper bound).

```cpp
template <typename comparable_type_>
iterator upper_bound(comparable_type_ && comparable) noexcept;
```

```cpp
template <typename comparable_type_>
const_iterator upper_bound(
    comparable_type_ && comparable) const noexcept;
```

Finds the first element greater than the given `comparable` (const version).

- `comparable` (in): Object comparable to [`value_t`](#value_t).

## erase

Erases a single element matching the given `comparable`.

```cpp
template <typename comparable_type_>
bool erase(comparable_type_ && comparable) noexcept;
```

```cpp
erase_result_t erase(iterator position) noexcept;
```

Erases the element at the specified iterator position.

```cpp
erase_result_t erase(const_iterator position) noexcept;
```

Erases the element at the specified [const_iterator](#const_iterator) position.

```cpp
erase_result_t erase(iterator first, iterator last) noexcept;
```

Erases all elements in the range [first, last).

No callbacks.

- `comparable` (in): Object comparable to [`value_t`](#value_t) and convertible to search key.
- `position` (in): Iterator to element to erase. Must be valid and dereferenceable.
- `first` (in): Iterator to first element in range.
- `last` (in): Iterator to past-the-end of range.

Notes: If `position` is end(), returns {end(), success} without modifying the tree.

Notes: If first == last, no elements are erased and returns {last, success}.

## split

Splits this tree at a given key.

```cpp
template <typename comparable_type_>
split_result_t split(comparable_type_ && comparable) noexcept;
```

Returns both left (< key) and right (>= key) parts. This tree is left empty.

Runs in O(log n) expected time. Splitting around 5:

```
auto split = tree.split(5);
// split.left has elements = 5
```

- `comparable` (in): Key to split at.

## join

Joins another tree into this one.

```cpp
void join(wb_tree_t & other) noexcept;
```

Precondition: all elements in this tree < all elements in other tree.

Runs in O(log n) expected time. Splitting around 5 and joining back:

```
auto right = tree.split(5);  // tree: [0,5), right: [5,∞)
tree.join(right);            // tree: [0,∞)
```

- `other` (in): Tree to join (will be empty after join).

Warnings: This is a low-level operation. The caller must ensure all(this) < all(other). For general merging with duplicate handling, use merge() instead.

## key_comp

Returns the comparator object.

```cpp
comparator_t key_comp() const noexcept;
```

## root

Returns pointer to root node (for internal use).

```cpp
node_t * root() const noexcept;
```

## allocator

Returns reference to node allocator (for internal use).

```cpp
node_allocator_t & allocator() noexcept;
```

```cpp
node_allocator_t const & allocator() const noexcept;
```

Returns const reference to node allocator (for internal use).

## upserted_node_t

The node an upsert settled on, and how it got there.

```cpp
struct upserted_node_t
```

Assigning to the result overwrites that node's entry, which is what makes it usable as a handle rather than a report.

- `node` `node_t *`
- `placement` `node_t::node_placement_t`

## extract_result_t

RAII wrapper for extracted nodes.

```cpp
struct extract_result_t
```

Owns the extracted node and deallocates it when destroyed (unless released).

## inserted_iterator_t

Where an insertion settled, and how it got there.

```cpp
struct inserted_iterator_t
```

Names the same three outcomes as `[upserted_node_t](#upserted_node_t)`, one level up from the nodes.

- `position` `iterator`: The element's position, which is `end()` when nothing was stored.
- `placement` `node_t::node_placement_t`: Whether the entry was made, matched an incumbent, or refused for want of memory.

## erase_result_t

Result of an erase operation on an iterator.

```cpp
struct erase_result_t
```

Combines iterator to next element with operation status.

- `next` `iterator`: Iterator to the element following the erased one, or `end()`.
- `status` `status_t`: Status of the erase operation.

## iterator

Bidirectional iterator for WB tree.

```cpp
class iterator
```

Provides in-order traversal of tree elements.

## const_iterator

Const bidirectional iterator for WB tree.

```cpp
class const_iterator
```

Provides in-order traversal of tree elements (read-only).

## split_result_t

Result of splitting a tree at a key.

```cpp
struct split_result_t
```

Contains two trees: left (all < key) and right (all >= key).

- `left` `wb_tree_t`: Tree with all elements ordered before the split key.
- `right` `wb_tree_t`: Tree with all elements not ordered before the split key.

## hash_atomic_slot_ref

Thread-safe smart reference to a hash table slot with metadata accessors.

```cpp
template <typename value_type_,
          typename hasher_type_,
          waiting_policy<std::uint64_t const *, std::uint64_t> waiting_policy_type_ = bare_waiting_policy_t,
          template<typename> class atomic_reference_ = atomic_ref>
class hash_atomic_slot_ref
```

Ideally, we would want to avoid Compare-And-Swap ____(CAS) loops for locking individual slots. On the locking path, we can use a `fetch_or` atomic operation to set both bits (populated + deleted) simultaneously and transition to the locked state. If the previous value indicates the slot was already locked, we retry until we acquire the lock.

The intuition of using the `fetch_and` for the inverse operation, however, is wrong. When unlocking, we need to restore the previous state (populated/deleted) of the slot or transition to the new one, depending on the `mark_populated()/mark_deleted`()/mark_free() calls made while the slot was locked.

The bits outside the active ones in each 32-bit word shouldn't be changed. The active ones may have to be flipped. Assuming the value of the relevant bits couldn't have changed, we can use `fetch_xor` to control the result with one more atomic and no compare-and-swap loop. __XOR-is-all-you-need!__

Neither path is lock-free in the technical sense: `lock()` spins until it wins the slot, so a thread stopped between `lock()` and `unlock()` blocks every prober that reaches that slot. What the pair buys is that the whole table is never locked, and that no slot state needs a CAS retry. What a losing prober does with its core in the meantime is `waiting_policy_type_`, which is where a caller that owns the hardware spends a stall instead of an issue slot.

This doesn't resolve __false-sharing__ issues native to such a densely packed design, but still results in very low contention if the duration of atomic operations under the lock is comparable to CPU's memory latency.

## header_ref

The staged header, not the shared one, so reads under the lock stay private.

```cpp
hash_bucket_head_t & header_ref() const noexcept;
```

## is_free

Whether the staged state is [`free_k`](#free_k).

```cpp
bool is_free() const noexcept;
```

## is_deleted

Whether the staged state is [`deleted_k`](#deleted_k).

```cpp
bool is_deleted() const noexcept;
```

## is_populated

Whether the staged state is [`populated_k`](#populated_k).

```cpp
bool is_populated() const noexcept;
```

## is_locked

Whether the staged state is [`locked_k`](#locked_k).

```cpp
bool is_locked() const noexcept;
```

## mark_free

Stages [`free_k`](#free_k), which `unlock()` then publishes.

```cpp
void mark_free() const noexcept;
```

## mark_populated

Stages [`populated_k`](#populated_k), which `unlock()` then publishes.

```cpp
void mark_populated() const noexcept;
```

## mark_deleted

Stages [`deleted_k`](#deleted_k), which `unlock()` then publishes.

```cpp
void mark_deleted() const noexcept;
```

## lock

Spins on `fetch_or` until this thread is the one that observed a non-locked slot.

```cpp
void lock() const noexcept;
```

Warnings: On a device this spin only makes progress under independent thread scheduling, since 32 slots share one header and a warp probing one bucket serializes through here.

Notes: The reference is a temporary rather than a named variable because a `constexpr` function may not define a variable of non-literal type before C++23. It costs nothing - the reference only carries the address it was handed.

## unlock

Drives the two owned bits from [`locked_k`](#locked_k) to whatever was staged, with one posted xor.

```cpp
void unlock() const noexcept;
```

## immutable_b_tree

An immutable B-tree over `value_type_`, built once from a sorted span, whose nodes are rows of `keys_per_row_` keys searched by `row_kit_type_`.

```cpp
template <typename value_type_,
          std::size_t keys_per_row_ = keys_per_row<typename mapping_key_type_or_itself<value_type_>::type>(default_row_bytes_k),
          row_kit row_kit_type_ = native_row_kit_t,
          typename allocator_type_ = default_allocator<value_type_>>
class immutable_b_tree
```

A set holds one allocation of rows; a map holds a second one of mapped values, indexed by rank.

## value_t

The whole stored element: the key for a set, a [`mapping`](https://www.unum.cloud/docs/smashtable/cpp/stored-types.md#mapping) of both halves for a map.

```cpp
using value_t = value_type_;
```

## key_t

The key half the rows are searched on, which is the whole element for a set.

```cpp
using key_t = typename mapping_key_type_or_itself<value_t>::type;
```

## mapped_t

The mapped half, held in rank order beside the rows, and `void` for a set.

```cpp
using mapped_t = typename mapped_value_type_or_void<value_t>::type;
```

## mapped_slot_t

What one entry of the mapped array holds; an empty stand-in when the tree is a set.

```cpp
using mapped_slot_t = std::conditional_t<is_mapping<value_t>, mapped_t, placeholder_t>;
```

## immutable_b_tree

```cpp
immutable_b_tree() noexcept=default;
```

```cpp
immutable_b_tree(allocator_t allocator) noexcept;
```

```cpp
immutable_b_tree(immutable_b_tree && other) noexcept;
```

```cpp
immutable_b_tree(immutable_b_tree const &)=delete;
```

## operator=

```cpp
immutable_b_tree & operator=(immutable_b_tree && other) noexcept;
```

```cpp
immutable_b_tree & operator=(immutable_b_tree const &)=delete;
```

## size_bytes

The bytes this tree stores, rows and mapped values together.

```cpp
std::size_t size_bytes() const noexcept;
```

```cpp
std::size_t size_bytes(std::size_t keys_count) noexcept;
```

The bytes a tree over `keys_count` elements stores: whole rows of keys, and a value per key for a map.

## words

The stored words, node after node, for writing the tree out.

```cpp
std::span<word_t const> words() const noexcept;
```

## *

How many keys order below `wanted`, which is also the position of its lower bound.

```cpp
std::size_t rank(key_t wanted) const noexcept;
```

## *

The position of `wanted`, or [`key_not_found_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#key_not_found_k).

```cpp
expected<std::size_t> find(key_t wanted) const noexcept;
```

Where keys repeat, the first of them.

## *

The key at position `ordinal` in sorted order, which must be below [`size`](https://www.unum.cloud/docs/smashtable/cpp/isolation.md#size).

```cpp
key_t select(std::size_t ordinal) const noexcept;
```

## mapped_*_at

The value the key at position `ordinal` carries, which must be below [`size`](https://www.unum.cloud/docs/smashtable/cpp/isolation.md#size).

```cpp
requires is_mapping<value_t>
mapped_slot_t const & mapped__at(std::size_t ordinal) const noexcept;
```

## at_*_rank

A walk from position `ordinal`, or [`end`](#end) when there is no such position.

```cpp
iterator at__rank(std::size_t ordinal) const noexcept;
```

## lower_*_bound

A walk from the first key not below `wanted`.

```cpp
iterator lower__bound(key_t wanted) const noexcept;
```

## *

Builds the tree over `sorted`, which may repeat keys.

```cpp
expected<immutable_b_tree> make(
    std::span<value_t const> sorted,
    allocator_t allocator = {}) noexcept;
```

A map keeps the mapped values in the order they arrive, so a repeated key reads back the value that came first.

Statuses: - [`invalid_argument_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#invalid_argument_k) `sorted` is out of order.

## iterator

A forward walk over the keys in order, yielding each by value.

```cpp
class iterator
```

A map walks its keys too, and [`rank`](https://www.unum.cloud/docs/smashtable/cpp/isolation.md#rank) indexes [`mapped_at`](#mapped_at) for the value beside one.

## immutable_elias_fano

An immutable sequence of non-decreasing unsigned integers, built once from values pulled in order and read back by position - the offsets of variable-length rows, a few bits apiece.

```cpp
template <typename value_type_ = std::uint64_t,
          allocator_of<std::uint64_t> allocator_type_ = default_allocator<std::uint64_t>,
          row_kit row_kit_type_ = native_row_kit_t>
class immutable_elias_fano
```

`row_kit_type_` scans the high parts in [`select`](https://www.unum.cloud/docs/smashtable/cpp/isolation.md#select) where it has a scan of its own.

## select_stride_k

Set bits between consecutive samples of the select index.

```cpp
std::size_t select_stride_k;
```

## immutable_elias_fano

```cpp
immutable_elias_fano() noexcept=default;
```

```cpp
immutable_elias_fano(allocator_t allocator) noexcept;
```

```cpp
immutable_elias_fano(immutable_elias_fano && other) noexcept;
```

```cpp
immutable_elias_fano(immutable_elias_fano const &)=delete;
```

## operator=

```cpp
immutable_elias_fano & operator=(
    immutable_elias_fano && other) noexcept;
```

```cpp
immutable_elias_fano & operator=(immutable_elias_fano const &)=delete;
```

## size_bytes

The bytes this sequence stores: the low parts, the high parts and the select samples.

```cpp
std::size_t size_bytes() const noexcept;
```

## *

The value at `position`.

```cpp
value_t select(std::size_t position) const noexcept;
```

- `select`
- `operator[]`
- `operator[]`

## make

Builds the sequence of [`count`](https://www.unum.cloud/docs/smashtable/cpp/isolation.md#count) values, none above `universe`, pulled in order through `fill`, so no caller ever holds them all at once.

```cpp
template <typename fill_type_>
expected<immutable_elias_fano> make(
    std::size_t count,
    value_t universe,
    fill_type_ && fill,
    allocator_t allocator = {}) noexcept;
```

```cpp
expected<immutable_elias_fano> make(
    std::span<value_t const> sorted,
    allocator_t allocator = {}) noexcept;
```

Builds the sequence of `sorted`, held whole.

- `count` (in): Number of values in the sequence.
- `universe` (in): Largest value any of them may take.
- `fill` (in): Answers `expected<std::span<value_t const>>` for a position, holding the values from that position on - at least one while any remain, possibly all of them.
- `allocator` (in): The allocator instance to use.

Statuses: - The first failure `fill` reports.
- [`invalid_argument_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#invalid_argument_k) The values decrease, pass `universe` or fall short of [`count`](https://www.unum.cloud/docs/smashtable/cpp/isolation.md#count).

## immutable_packed_array

An immutable array of unsigned integers between a base and a maximum, built once from values pulled in order, each kept in the bit width of the maximum less the base.

```cpp
template <std::unsigned_integral value_type_ = std::uint64_t,
          allocator_of<std::uint64_t> allocator_type_ = default_allocator<std::uint64_t>>
class immutable_packed_array
```

## immutable_packed_array

```cpp
immutable_packed_array() noexcept=default;
```

```cpp
immutable_packed_array(allocator_t allocator) noexcept;
```

```cpp
immutable_packed_array(immutable_packed_array && other) noexcept;
```

```cpp
immutable_packed_array(immutable_packed_array const &)=delete;
```

## operator=

```cpp
immutable_packed_array & operator=(
    immutable_packed_array && other) noexcept;
```

```cpp
immutable_packed_array & operator=(
    immutable_packed_array const &)=delete;
```

## bits

How many bits each value takes: the bit width of the maximum less the base.

```cpp
unsigned bits() const noexcept;
```

## *

The distance every stored value is measured from, and the least value it may hold.

```cpp
value_t base() const noexcept;
```

## size_bytes

The bytes the packed words take, which a zero width keeps at zero.

```cpp
std::size_t size_bytes() const noexcept;
```

## saved_bytes

The bytes [`save`](#save) writes: the header and then the packed words.

```cpp
std::size_t saved_bytes() const noexcept;
```

## save

Writes the saved form into the front of `bytes`, for `[immutable_packed_array_view](#immutable_packed_array_view)` to read in place.

```cpp
status_t save(std::span<std::byte> bytes) const noexcept;
```

Statuses: - [`invalid_argument_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#invalid_argument_k) `bytes` is shorter than [`saved_bytes`](#saved_bytes), in which case nothing is written.

## make

Builds the array of [`count`](https://www.unum.cloud/docs/smashtable/cpp/isolation.md#count) values from [`base`](#base) to `maximum` inclusive, pulled in order through `fill`, so no caller ever holds them all at once.

```cpp
template <typename fill_type_>
expected<immutable_packed_array> make(
    std::size_t count,
    value_t base,
    value_t maximum,
    fill_type_ && fill,
    allocator_t allocator = {}) noexcept;
```

```cpp
expected<immutable_packed_array> make(
    std::size_t count,
    value_t value,
    allocator_t allocator = {}) noexcept;
```

Builds the array of [`count`](https://www.unum.cloud/docs/smashtable/cpp/isolation.md#count) copies of `value`, which takes no bits and no words.

```cpp
expected<immutable_packed_array> make(
    std::span<value_t const> values,
    allocator_t allocator = {}) noexcept;
```

Builds the array of [`values`](#values), held whole, based at the least of them and as wide as the greatest needs.

- `count` (in): Number of values in the array.
- `base` (in): Smallest value any of them may take.
- `maximum` (in): Largest value any of them may take.
- `fill` (in): Answers `expected<std::span<value_t const>>` for a position, holding the values from that position on - at least one while any remain, possibly all of them.
- `allocator` (in): The allocator instance to use.

Statuses: - The first failure `fill` reports.
- [`invalid_argument_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#invalid_argument_k) [`base`](#base) exceeds `maximum` or a value falls outside them or short of [`count`](https://www.unum.cloud/docs/smashtable/cpp/isolation.md#count).

## immutable_packed_array_view

An immutable packed array read in place from bytes it does not own, as saved.

```cpp
template <std::unsigned_integral value_type_ = std::uint64_t>
class immutable_packed_array_view
```

A pointer and three fields, so it copies freely and stays valid exactly as long as the bytes it was made over.

## immutable_packed_array_view

Default-constructs an empty `[immutable_packed_array_view](#immutable_packed_array_view)`.

```cpp
constexpr immutable_packed_array_view() noexcept=default;
```

## bits

How many bits each value takes.

```cpp
unsigned bits() const noexcept;
```

## saved_*_bytes

The bytes the saved form spans, so a reader can step past it to whatever follows.

```cpp
std::size_t saved__bytes() const noexcept;
```

## make

Reads the saved form at the front of `bytes`, which may sit at any alignment.

```cpp
expected<immutable_packed_array_view> make(
    std::span<std::byte const> bytes) noexcept;
```

Statuses: - [`invalid_argument_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#invalid_argument_k) `bytes` ends before the words its header names, or the header holds a base or a width that [`value_t`](#value_t) cannot.

## immutable_splus_tree

An immutable S+ tree over `value_type_`, built once from a sorted span, whose nodes are rows of `keys_per_row_` keys searched by `row_kit_type_`.

```cpp
template <typename value_type_,
          std::size_t keys_per_row_ = keys_per_row<typename mapping_key_type_or_itself<value_type_>::type>(default_row_bytes_k),
          row_kit row_kit_type_ = native_row_kit_t,
          typename allocator_type_ = default_allocator<value_type_>>
class immutable_splus_tree
```

A set holds one allocation of rows; a map holds a second one of mapped values, indexed by rank.

## view_t

The in-place view every lookup goes through, over this tree's storage or saved bytes.

```cpp
using view_t = immutable_splus_tree_view<value_type_, keys_per_row_, row_kit_type_>;
```

## value_t

Every stored element: the key itself for a set, a [`mapping`](https://www.unum.cloud/docs/smashtable/cpp/stored-types.md#mapping) of both halves for a map.

```cpp
using value_t = value_type_;
```

## key_t

The key half the rows are searched on, which is the whole element for a set.

```cpp
using key_t = typename view_t::key_t;
```

## mapped_t

The mapped half, held in rank order beside the rows, and `void` for a set.

```cpp
using mapped_t = typename view_t::mapped_t;
```

## mapped_slot_t

What one entry of the mapped array holds: an empty stand-in when the tree is a set.

```cpp
using mapped_slot_t = typename view_t::mapped_slot_t;
```

## iterator

A forward walk over the keys in order, as the view walks them.

```cpp
using iterator = typename view_t::iterator;
```

## immutable_splus_tree

```cpp
immutable_splus_tree() noexcept=default;
```

```cpp
immutable_splus_tree(allocator_t allocator) noexcept;
```

```cpp
immutable_splus_tree(immutable_splus_tree && other) noexcept;
```

```cpp
immutable_splus_tree(immutable_splus_tree const &)=delete;
```

## operator=

```cpp
immutable_splus_tree & operator=(
    immutable_splus_tree && other) noexcept;
```

```cpp
immutable_splus_tree & operator=(immutable_splus_tree const &)=delete;
```

## size_bytes

The bytes this tree stores, rows and mapped values together.

```cpp
std::size_t size_bytes() const noexcept;
```

```cpp
std::size_t size_bytes(std::size_t keys_count) noexcept;
```

The bytes a tree over `keys_count` elements stores: whole rows on every level, and a value per key for a map.

## words

The stored words, root level first, for writing the tree out.

```cpp
std::span<word_t const> words() const noexcept;
```

## view

This tree searched in place, valid while the tree lives and stays where it is.

```cpp
view_t const & view() const noexcept;
```

## saved_bytes

The bytes [`save`](#save) writes: the header, the rows, and the mapped values on their alignment.

```cpp
std::size_t saved_bytes() const noexcept;
```

## save

Writes the saved form into the front of `bytes`, for `[immutable_splus_tree_view](#immutable_splus_tree_view)` to search in place.

```cpp
requires std::is_trivially_copyable_v<mapped_slot_t>
status_t save(std::span<std::byte> bytes) const noexcept;
```

Statuses: - [`invalid_argument_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#invalid_argument_k) `bytes` is shorter than [`saved_bytes`](#saved_bytes), and nothing is written.

## immutable_splus_tree_view

An immutable S+ tree searched in place, over rows and mapped values it does not own: either a saved form in borrowed bytes, or the storage of the tree it was taken from.

```cpp
template <typename value_type_,
          std::size_t keys_per_row_ = keys_per_row<typename mapping_key_type_or_itself<value_type_>::type>(default_row_bytes_k),
          row_kit row_kit_type_ = native_row_kit_t>
class immutable_splus_tree_view
```

A few pointers and the level offsets, so it copies freely and stays valid exactly as long as the bytes it was made over.

## value_t

Every stored element: the key itself for a set, a [`mapping`](https://www.unum.cloud/docs/smashtable/cpp/stored-types.md#mapping) of both halves for a map.

```cpp
using value_t = value_type_;
```

## key_t

The key half the rows are searched on, which is the whole element for a set.

```cpp
using key_t = typename mapping_key_type_or_itself<value_t>::type;
```

## mapped_t

The mapped half, held in rank order beside the rows, and `void` for a set.

```cpp
using mapped_t = typename mapped_value_type_or_void<value_t>::type;
```

## mapped_slot_t

What one entry of the mapped array holds: an empty stand-in when the tree is a set.

```cpp
using mapped_slot_t = std::conditional_t<is_mapping<value_t>, mapped_t, placeholder_t>;
```

## levels_capacity_k

More levels than a fanout of three needs for 2^64 keys.

```cpp
std::size_t levels_capacity_k;
```

## saved_rows_offset_k

Where the rows start in the saved form, right after the header.

```cpp
std::size_t saved_rows_offset_k;
```

## saved_alignment_k

The boundary saved bytes start on, so the kits read whole words and mapped values align.

```cpp
std::size_t saved_alignment_k;
```

## immutable_splus_tree_view

Default-constructs an empty `[immutable_splus_tree_view](#immutable_splus_tree_view)`.

```cpp
constexpr immutable_splus_tree_view() noexcept=default;
```

## size_bytes

The bytes the rows and the mapped values take.

```cpp
std::size_t size_bytes() const noexcept;
```

```cpp
std::size_t size_bytes(std::size_t keys_count) noexcept;
```

The bytes a tree over `keys_count` elements stores: whole rows on every level, and a value per key for a map.

## make

Reads the saved form at the front of `bytes`, starting on [`saved_alignment_k`](#saved_alignment_k).

```cpp
expected<immutable_splus_tree_view> make(
    std::span<std::byte const> bytes) noexcept;
```

Statuses: - [`invalid_argument_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#invalid_argument_k) `bytes` is misaligned, ends before the rows and mapped values its header names, or was saved by a tree of another key, row width or mapped value.

## iterator

A forward walk over the keys in order, yielding each by value.

```cpp
class iterator
```

A map walks its keys too, and [`rank`](https://www.unum.cloud/docs/smashtable/cpp/isolation.md#rank) indexes [`mapped_at`](#mapped_at) for the value beside one.

## binary_node_search

The searches every binary node shares, over its `left`, `right` and `payload`, so the AVL and weight-balanced nodes answer bounds identically.

```cpp
template <typename node_type_,
          typename comparator_type_>
struct binary_node_search
```

## hash_storage

The one allocation a table is carved from, and the counters describing it.

```cpp
template <typename value_type_,
          typename hasher_type_,
          allocator_of<std::byte> allocator_type_>
struct hash_storage
```

Owns the buffer and the elements inside it, and frees both, so a table holding one needs no destructor of its own. This is also the only thing that passes between a growable table and a pinned one, which is what lets that hand-off be a move of a value rather than one type reaching into the other.

## has_values_k

Whether the element carries a mapped value, making the table a map rather than a set.

```cpp
bool has_values_k;
```

## bytes_in_bucket_k

Bytes one bucket occupies across all three regions, header included.

```cpp
std::size_t bytes_in_bucket_k;
```

## destruct_keys_k

Whether teardown must run a key destructor.

```cpp
bool destruct_keys_k;
```

## destruct_values_k

Whether teardown must run a value destructor.

```cpp
bool destruct_values_k;
```

## memory

Base of the single allocation the three regions are carved from.

```cpp
std::byte * memory;
```

## keys

Keys region, indexed by slot.

```cpp
key_t * keys;
```

## values

Values region, indexed by slot, null for sets.

```cpp
mapped_storage_t * values;
```

## headers

Headers region, indexed by bucket.

```cpp
hash_bucket_head_t * headers;
```

## slots_count

Total number of slots, always a power of two.

```cpp
offset_t slots_count;
```

## growth_threshold

Rehash trigger at the 75% load factor.

```cpp
offset_t growth_threshold;
```

## populated_count

Count of populated slots.

```cpp
offset_t populated_count;
```

## deleted_count

Count of deleted slots still holding tombstones.

```cpp
offset_t deleted_count;
```

## allocator

Supplies and reclaims the single byte buffer behind the three regions.

```cpp
allocator_t allocator;
```

## hash_storage

```cpp
hash_storage() noexcept=default;
```

```cpp
hash_storage(allocator_t allocator_state) noexcept;
```

```cpp
hash_storage(hash_storage && other) noexcept;
```

```cpp
hash_storage(hash_storage const &)=delete;
```

## operator=

```cpp
hash_storage & operator=(hash_storage && other) noexcept;
```

```cpp
hash_storage & operator=(hash_storage const &)=delete;
```

## ~hash_storage

```cpp
~hash_storage() noexcept;
```

## is_allocated

Whether a buffer is behind the three regions.

```cpp
bool is_allocated() const noexcept;
```

## retarget_regions

Recomputes the three region pointers from [`memory`](#memory) and [`slots_count`](#slots_count).

```cpp
void retarget_regions() noexcept;
```

## retarget_slot

Points `slot` at the three regions and at `slot_index` within them.

```cpp
template <typename slot_ref_type_>
void retarget_slot(
    slot_ref_type_ & slot,
    offset_t slot_index) const noexcept;
```

## destroy_elements

Runs the destructors of every live key and value, leaving the headers as they are.

```cpp
void destroy_elements() noexcept;
```

## clear

Destroys every element and zeroes the headers, keeping the buffer: a slot's state lives in its header alone, so the keys and values left behind are never taken for elements.

```cpp
void clear() noexcept;
```

## deallocate

Returns the buffer to the allocator and drops every pointer and counter.

```cpp
void deallocate() noexcept;
```

Warnings: Elements are not destroyed, so call [`clear`](https://www.unum.cloud/docs/smashtable/cpp/isolation.md#clear) or [`destroy_elements`](#destroy_elements) first.

## swap

A cheap copy-less exchange of the buffer, the counters and the allocator.

```cpp
void swap(hash_storage & other) noexcept;
```

## make

Allocates and zeroes the buffer for `slots`, keeping [`allocator`](#allocator) for its release.

```cpp
hash_storage make(
    hash_slots_count_t slots,
    allocator_t allocator_state) noexcept;
```

## memory_usage

Total memory needed for the three regions of a table this size.

```cpp
std::size_t memory_usage(hash_slots_count_t slots) noexcept;
```

## intrusive_list

The oldest and newest of a first-in first-out list of record indices.

```cpp
template <std::unsigned_integral index_type_ = std::uint32_t>
struct intrusive_list
```

## absent_k

Ends a list and names no record.

```cpp
index_t absent_k;
```

## oldest

The record [`pop`](#pop) answers next.

```cpp
index_t oldest;
```

## newest

The record [`push`](#push) linked last.

```cpp
index_t newest;
```

## push

Links the record at `index` after the newest.

```cpp
template <typename records_type_>
requires singly_linked_records<records_type_, index_t>
void push(records_type_ & records, index_t index) noexcept;
```

## pop

Unlinks the oldest record and answers its index, or [`absent_k`](#absent_k) when the list is empty.

```cpp
template <typename records_type_>
requires singly_linked_records<records_type_, index_t>
index_t pop(records_type_ & records) noexcept;
```

## erase

Unlinks the record at `index` from wherever it sits.

```cpp
template <typename records_type_>
requires singly_linked_records<records_type_, index_t>
status_t erase(records_type_ & records, index_t index) noexcept;
```

Statuses: - [`key_not_found_k`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#key_not_found_k) The record was never pushed, or was popped or erased since. A record of another list is not detected.

## no_entropy_t

A generator that yields nothing, so a concept can probe a sampling call without drawing.

```cpp
struct no_entropy_t
```

The counterpart of `no_op_t` on the other slot: a concept needs a value of some type to write the call it is asking about, and binding a callback there would leave a swapped generator and callback invisible. Nothing samples through this - [`draw_below`](#draw_below) wants [`min`](#min), [`max`](#max) and a call operator, and this is the least that satisfies all three.

## result_type

What a draw hands back, widest so a probe never narrows what a real generator would give.

```cpp
using result_type = std::uint64_t;
```

## min

The lowest value a draw can take, which [`draw_below`](#draw_below) subtracts to normalise.

```cpp
result_type min() noexcept;
```

## max

The highest value a draw can take, which [`draw_below`](#draw_below) spans to size its mask.

```cpp
result_type max() noexcept;
```

## operator()

Draws nothing, since no concept using this ever runs the body it probes.

```cpp
result_type operator()() noexcept;
```

## serial_row_kit_t

The reference kit every kit must agree with, the one each finishes a partial chunk with.

```cpp
struct serial_row_kit_t
```

## mask_equal_width_k

Keys one [`mask_equal`](#mask_equal) compares, its answer in the low bits of a 32-bit mask.

```cpp
std::size_t mask_equal_width_k;
```

## count_below

How many of [`keys`](#keys) order below `wanted`; for a sorted row, the lower bound.

```cpp
template <typename key_type_, std::size_t extent_>
requires row_searchable_key<key_type_>
std::size_t count_below(
    std::span<key_type_ const, extent_> keys,
    std::type_identity_t<key_type_> wanted) noexcept;
```

```cpp
template <std::size_t extent_>
std::size_t count_below(
    std::span<std::uint64_t const, extent_> high_words,
    std::span<std::uint64_t const, extent_> low_words,
    key128_t wanted) noexcept;
```

How many keys of a split row order below `wanted`, reading a low word only where its high word ties.

## mask_equal

Which of [`keys`](#keys) equal `wanted`, one bit per key, the lowest for the first: a hash table's window, where slots nobody filled compare too and the caller masks them off.

```cpp
template <typename word_type_>
requires std::same_as<word_type_, std::uint32_t> || std::same_as<word_type_, std::uint64_t> || std::same_as<word_type_, key128_t>
std::uint32_t mask_equal(
    std::span<word_type_ const, mask_equal_width_k> keys,
    word_type_ wanted) noexcept;
```

## select_set_bit

Where the `remaining` -th set bit after set bit `sampled` of [`words`](#words) sits, counting `sampled` as the zeroth: the scan an Elias-Fano select runs from its sample.

```cpp
std::uint64_t select_set_bit(
    std::span<std::uint64_t const> words,
    std::uint64_t sampled,
    std::size_t remaining) noexcept;
```

`remaining` must be positive. A bit [`words`](#words) does not hold, which only a corrupted sequence asks for, answers `words.size() * 64`, past every real bit, rather than reading past the span. Kits scanning several words per instruction finish the span's last few here.

## select_onward

Continues a select at `word`, what remains to count of the word at `word_index`, never reading past [`words`](#words).

```cpp
std::uint64_t select_onward(
    std::span<std::uint64_t const> words,
    std::size_t word_index,
    std::uint64_t word,
    std::size_t remaining) noexcept;
```

## select_in_word

The offset of the [`rank`](https://www.unum.cloud/docs/smashtable/cpp/isolation.md#rank) -th set bit of `word`, counted from zero, found by halving.

```cpp
unsigned select_in_word(std::uint64_t word, std::size_t rank) noexcept;
```

## first_of

The first of a pack, for a caller that needs one representative of several arguments.

```cpp
template <typename first_type_, typename... rest_types_>
first_type_ & first_of(first_type_ & first, rest_types_ & ...) noexcept;
```

## advance_iterator

Steps [`iterator`](#iterator) forward [`count`](https://www.unum.cloud/docs/smashtable/cpp/isolation.md#count) positions, in one jump where it supports `+=`.

```cpp
template <readable_iterator iterator_type_>
void advance_iterator(
    iterator_type_ & iterator,
    std::size_t count) noexcept;
```

## distance_between

How many steps separate two positions, in one subtraction where they support it.

```cpp
template <multipass_iterator iterator_type_, iterator_sentinel<iterator_type_> sentinel_type_>
std::size_t distance_between(
    iterator_type_ first,
    sentinel_type_ const & last) noexcept;
```

## upper_bound_or_end

The first position of `collection` past `upper`, or its end where `upper` is `unbounded`.

```cpp
template <typename collection_type_, typename upper_type_>
auto upper_bound_or_end(
    collection_type_ const & collection,
    upper_type_ const & upper) noexcept;
```

## above_until

Whether `key` orders above `until` under `less`, which every key does where `until` is `unbounded`, so a descending walk stops on the first key that does not.

```cpp
template <typename less_type_, typename key_type_, typename until_type_>
bool above_until(
    less_type_ const & less,
    key_type_ const & key,
    until_type_ const & until) noexcept;
```

## contains_type

Compile-time check if a type appears in parameter pack.

```cpp
template <typename needle_type_, typename... haystack_types_>
bool contains_type();
```

## atomic_add_fetch

Relaxed atomic increment of a plain counter, returning the post-increment value.

```cpp
template <std::integral integral_type_>
integral_type_ atomic_add_fetch(
    integral_type_ & counter,
    integral_type_ addend) noexcept;
```

Relaxed suffices for a counter read by value - a statistic, or a version stamp compared for identity and recency - because one location has a total modification order. It publishes nothing: a caller needing the data a counter describes to be visible must order that itself.

## atomic_load

Atomic read of a counter other threads may be incrementing, relaxed unless [`order`](https://www.unum.cloud/docs/smashtable/cpp/isolation.md#order) asks for more.

```cpp
template <std::integral integral_type_>
integral_type_ atomic_load(
    integral_type_ const & counter,
    memory_order_t order = memory_order_relaxed_k) noexcept;
```

Needed wherever a plain read would race an [`atomic_add_fetch`](#atomic_add_fetch) on the same field.

Warnings: The counter is read through a `const` path but must not be a `const` __object__ - an `atomic_ref` over one is undefined. Every caller reaches a mutable member of a mutable container through a `const` member function, which is what makes the cast below sound.

## atomic_store

Relaxed atomic write of a counter other threads may be reading.

```cpp
template <std::integral integral_type_>
void atomic_store(
    integral_type_ & counter,
    integral_type_ value) noexcept;
```

The mirror of [`atomic_load`](#atomic_load), and just as unordered: a caller needing the data a counter describes to be visible alongside it must order that itself.

## atomic_load_newest

Reads `word` through a read-modify-write, getting the newest value, never an older one.

```cpp
template <std::integral integral_type_>
integral_type_ atomic_load_newest(integral_type_ & word) noexcept;
```

A plain load may read a stale write; a read-modify-write reads the newest and joins its release sequence, so a store made before this call is visible to whoever reads the word afterwards. That is what an announce-then-re-read protocol needs and what a load cannot give it.

## atomic_sub_fetch

Relaxed atomic decrement of a plain counter, returning the post-decrement value.

```cpp
template <std::integral integral_type_>
integral_type_ atomic_sub_fetch(
    integral_type_ & counter,
    integral_type_ subtrahend) noexcept;
```

## atomic_wait

Parks until `counter` stops reading `observed`, so a waiter costs no core as it waits.

```cpp
template <std::integral integral_type_>
void atomic_wait(
    integral_type_ const & counter,
    integral_type_ observed) noexcept;
```

Warnings: Wakes only where writers call [`atomic_notify_all`](#atomic_notify_all); bare [`atomic_store`](#atomic_store) wakes nobody.

See also: The same `const-path` caveat as `[atomic_load](#atomic_load)` applies to the cast.

## atomic_notify_all

Wakes every waiter parked on `counter`.

```cpp
template <std::integral integral_type_>
void atomic_notify_all(integral_type_ & counter) noexcept;
```

The mirror of [`atomic_wait`](#atomic_wait).

## atomic_post_add

Posts `addend` onto `word` without reading what was there.

```cpp
template <template<typename> class atomic_reference_ = atomic_ref, std::integral integral_type_, typename order_type_>
void atomic_post_add(
    integral_type_ & word,
    integral_type_ addend,
    order_type_ order) noexcept;
```

## atomic_post_sub

Posts `subtrahend` off `word` without reading what was there.

```cpp
template <template<typename> class atomic_reference_ = atomic_ref, std::integral integral_type_, typename order_type_>
void atomic_post_sub(
    integral_type_ & word,
    integral_type_ subtrahend,
    order_type_ order) noexcept;
```

## atomic_post_set_bits

Posts [`bits`](#bits) set in `word` without reading what was there.

```cpp
template <template<typename> class atomic_reference_ = atomic_ref, std::integral integral_type_, typename order_type_>
void atomic_post_set_bits(
    integral_type_ & word,
    integral_type_ bits,
    order_type_ order) noexcept;
```

## atomic_post_clear_bits

Posts [`bits`](#bits) cleared in `word` without reading what was there.

```cpp
template <template<typename> class atomic_reference_ = atomic_ref, std::integral integral_type_, typename order_type_>
void atomic_post_clear_bits(
    integral_type_ & word,
    integral_type_ bits,
    order_type_ order) noexcept;
```

## atomic_max_fetch

Raises `word` to `floor` unless it stands higher, so a stale floor never lowers it.

```cpp
template <template<typename> class atomic_reference_ = atomic_ref, std::integral integral_type_>
void atomic_max_fetch(
    integral_type_ & word,
    integral_type_ floor) noexcept;
```

One instruction through a reference that spells `fetch_max`, and the compare-exchange loop it replaces otherwise. A word only ever raised this way is monotone whoever writes it.

## atomic_fetch_max

Raises `word` to `floor` unless it stands higher, answering what it held before.

```cpp
template <template<typename> class atomic_reference_ = atomic_ref, std::integral integral_type_, typename order_type_>
integral_type_ atomic_fetch_max(
    integral_type_ & word,
    integral_type_ floor,
    order_type_ order) noexcept;
```

One instruction through a reference that spells `fetch_max`, which `std::atomic_ref` does not before C++26, and the compare-exchange loop it replaces otherwise. A word only ever raised this way is monotone whoever writes it.

## atomic_post_max

Raises `word` to `floor` without reading what was there, which Arm spells `stumax`.

```cpp
template <template<typename> class atomic_reference_ = atomic_ref, std::integral integral_type_, typename order_type_>
void atomic_post_max(
    integral_type_ & word,
    integral_type_ floor,
    order_type_ order) noexcept;
```

## atomic_post_flip_bits

Posts [`bits`](#bits) flipped in `word` without reading what was there.

```cpp
template <template<typename> class atomic_reference_ = atomic_ref, std::integral integral_type_, typename order_type_>
void atomic_post_flip_bits(
    integral_type_ & word,
    integral_type_ bits,
    order_type_ order) noexcept;
```

## atomic_fetch_add_if_at_most

Adds `addend` to `word` only while the sum stays at or below `limit`.

```cpp
template <template<typename> class atomic_reference_ = atomic_ref, std::integral integral_type_, typename order_type_>
integral_type_ atomic_fetch_add_if_at_most(
    integral_type_ & word,
    integral_type_ addend,
    integral_type_ limit,
    order_type_ order) noexcept;
```

The bound is the whole point: a predicate a loop would re-check after every failed exchange becomes an argument the instruction decides on, so a refused caller writes nothing and leaves the line where it was. Without the extended form this is the compare-exchange loop it replaces.

## atomic_fetch_sub_if_at_least

Subtracts `subtrahend` from `word` only while the difference stays at or above `floor`.

```cpp
template <template<typename> class atomic_reference_ = atomic_ref, std::integral integral_type_, typename order_type_>
integral_type_ atomic_fetch_sub_if_at_least(
    integral_type_ & word,
    integral_type_ subtrahend,
    integral_type_ floor,
    order_type_ order) noexcept;
```

## atomic_fetch_test_and_set_bit

Sets bit `bit` of `word`, below its width, and answers whether it was set before: a claim exactly one of several racing callers wins.

```cpp
template <template<typename> class atomic_reference_ = atomic_ref, std::integral integral_type_, typename order_type_>
bool atomic_fetch_test_and_set_bit(
    integral_type_ & word,
    unsigned bit,
    order_type_ order) noexcept;
```

## atomic_fetch_test_and_reset_bit

Clears bit `bit` of `word`, below its width, and answers whether it was set before.

```cpp
template <template<typename> class atomic_reference_ = atomic_ref, std::integral integral_type_, typename order_type_>
bool atomic_fetch_test_and_reset_bit(
    integral_type_ & word,
    unsigned bit,
    order_type_ order) noexcept;
```

## atomic_claim_first_clear_bit

Claims a clear bit of [`words`](#words) with an acquiring set, scanning words in order and each word from its lowest clear bit.

```cpp
template <template<typename> class atomic_reference_ = atomic_ref, std::unsigned_integral word_type_>
std::size_t atomic_claim_first_clear_bit(
    std::span<word_type_> words) noexcept;
```

A lost race marks only the bit it lost and tries the next clear one of the same word, so a word costs one load and one claim per bit taken from under the caller. Bits released behind the scan are not seen. Release a claim with [`atomic_post_clear_bits`](#atomic_post_clear_bits) at release order.

## larger_of

The larger of two values, and the smaller.

```cpp
template <typename value_type_>
value_type_ const & larger_of(
    value_type_ const & first,
    value_type_ const & second) noexcept;
```

Spelled here rather than pulled from `<algorithm>`, which costs about ten thousand preprocessed lines for these two. It also sidesteps the Windows headers, which define [`min`](#min) and [`max`](#max) as function-like macros unless `NOMINMAX` is set, and would eat an unparenthesized [`std::max`](#max) call.

## bits_to_hold

The number of bits needed to represent `x`, so `0` for zero and `1` for one.

```cpp
std::size_t bits_to_hold(std::size_t x) noexcept;
```

## roundup_to_pow2

Rounds up an integer to the next power of two.

```cpp
std::size_t roundup_to_pow2(std::size_t x) noexcept;
```

Returns 0 for input 0, and 1 for input 1.

- `x` (in): Value to round up.

## draw_below

A uniform draw below `bound`, without the bias a modulo would introduce.

```cpp
template <typename generator_type_>
requires uniform_random_bits<std::remove_cvref_t<generator_type_>>
std::size_t draw_below(
    generator_type_ && generator,
    std::size_t bound) noexcept;
```

Masks to the next power of two and redraws when the value lands above the bound, which is unbiased because every value under the mask is equally likely and the surplus is simply discarded. At least half of the masked range is accepted, so fewer than two draws are expected.

- `generator` (in): Any uniform random bit generator, as `std::mt19937` and friends are.
- `bound` (in): One past the largest value that may be returned; zero and one draw nothing.

Notes: A generator narrower than the bound, like the 32-bit `std::mt19937`, is called repeatedly and the results concatenated, since masking a short draw could never reach the high bits.

## roundup_to_multiple

Rounds up a value to the next multiple of a compile-time constant.

```cpp
template <typename value_type_, value_type_ multiple_>
value_type_ roundup_to_multiple(value_type_ x) noexcept;
```

- `x` (in): Value to round up.

## algebra_keeps_first

Whether a member of the first side, at `membership`, is kept by `algebra_`.

```cpp
template <algebra_t algebra_>
bool algebra_keeps_first(membership_t membership) noexcept;
```

## algebra_walks_both

Whether `algebra_` needs the second side walked as well as the first.

```cpp
template <algebra_t algebra_>
bool algebra_walks_both() noexcept;
```

Only the two that can keep a member the first side never saw.

## algebra_keeps_second

Whether a member of the second side is kept, which needs no algebra to answer.

```cpp
bool algebra_keeps_second(membership_t membership) noexcept;
```

The second side is walked only to pick up what the first never had, so both algebras that reach it keep the same members - anything already shared was handed over by the first sweep.

## walk_algebra

Hands `callback` every member of `algebra_` over `first` and `second`.

```cpp
template <algebra_t algebra_, typename first_type_, typename second_type_, typename callback_type_ = no_op_t>
status_t walk_algebra(
    first_type_ & first,
    second_type_ & second,
    callback_type_ && callback) noexcept;
```

Each side is read through a read transaction opened here, which fixes what that side shows from [`snapshot_k`](https://www.unum.cloud/docs/smashtable/cpp/isolation.md#snapshot_k) up; pass transactions to choose the instants yourself, at the cost of the nested walk `compare_crossed_` falls back to.

Warnings: The two sides keep separate orders, so the pair is never one stamp, however read.

## is_subset

Whether every member of `first` is also in `second`.

```cpp
template <typename first_type_, typename second_type_>
expected<bool> is_subset(
    first_type_ & first,
    second_type_ & second) noexcept;
```

Settled at the first member `second` lacks, and the walk of `first` stops there.

A side with more members than the other cannot be contained in it, which is the whole answer without a walk. Both counts are read before either side is touched, so the pair is a decision about the sizes at one moment, not a size from one moment weighed against a walk from another.

## is_disjoint

Whether the two sides share no member, on the same terms as [`is_subset`](#is_subset).

```cpp
template <typename first_type_, typename second_type_>
expected<bool> is_disjoint(
    first_type_ & first,
    second_type_ & second) noexcept;
```

Sharing is symmetric, so the walk takes the smaller side and probes the larger.

## hash_slot_state_of

Reads the state of the slot selected by `mask` out of both header lanes.

```cpp
hash_slot_state_t hash_slot_state_of(
    hash_bucket_head_t const & head,
    hash_bucket_mask_t mask) noexcept;
```

## hash_mark_free

Drives the slot selected by `mask` into the [`free_k`](#free_k) state.

```cpp
void hash_mark_free(
    hash_bucket_head_t & head,
    hash_bucket_mask_t mask) noexcept;
```

## hash_mark_populated

Drives the slot selected by `mask` into the [`populated_k`](#populated_k) state.

```cpp
void hash_mark_populated(
    hash_bucket_head_t & head,
    hash_bucket_mask_t mask) noexcept;
```

## hash_mark_deleted

Drives the slot selected by `mask` into the [`deleted_k`](#deleted_k) state.

```cpp
void hash_mark_deleted(
    hash_bucket_head_t & head,
    hash_bucket_mask_t mask) noexcept;
```

## hash_window_slots

Reads the `width_` slots starting at slot `window` of the bucket `head` describes, for a probe entering them at slot `entry:` the live slots from `entry` up to the first free one.

```cpp
template <std::size_t width_>
requires (hash_bucket_capacity_k % width_ == 0)
hash_window_slots_t hash_window_slots(
    hash_bucket_head_t const & head,
    std::size_t window,
    std::size_t entry) noexcept;
```

## walk_hash_windows

Walks the probe run entered at slot `entry` a window at a time, handing `on_match` each populated slot whose key equals `wanted` until it halts, as [`hand_over`](https://www.unum.cloud/docs/smashtable/cpp/transactions.md#hand_over) reads its answer.

```cpp
template <typename row_kit_type_, typename key_type_, typename offset_type_, typename on_match_type_>
void walk_hash_windows(
    hash_bucket_head_t const *headers,
    key_type_ const *keys,
    offset_type_ slots_count,
    offset_type_ entry,
    std::type_identity_t<key_type_> const & wanted,
    on_match_type_ && on_match) noexcept;
```

Each window takes [`row_kit_type_::mask_equal_width_k`](#mask_equal_width_k) keys starting at a multiple of that width, compares them with one [`mask_equal`](#mask_equal), and masks the answer down to the live slots before the first free one. A deleted slot hides keys behind it, so only a free one ends the walk, and [`slots_count`](#slots_count) bounds it, so a full table ends it too.

- `headers` (in): The headers region, indexed by bucket.
- `keys` (in): The keys region, indexed by slot, every key a `window_key`.
- `slots_count` (in): The slot count, a power of two, at least one window.
- `entry` (in): The home slot of `wanted`, already masked to the table.
- `wanted` (in): The key to find.
- `on_match` (in): Receives the slot index of each match, in probe order.

## for_each_in_hash_bucket

Iterates over the populated slots of a bucket by scanning its population bitmap.

```cpp
template <typename value_type_, typename hasher_type_, typename callback_type_>
walk_control_t for_each_in_hash_bucket(
    hash_slot_ref<value_type_, hasher_type_> & slot,
    callback_type_ && callback) noexcept;
```

Skips empty and deleted slots outright through `countr_zero`, rather than walking every one.

- `slot` (inout): Reference to a slot in the bucket. Its `slot_` field is modified during iteration to point to each populated slot sequentially.
- `callback` (in): Functor invoked for each populated slot, receiving `[hash_slot_ref](#hash_slot_ref)`.

## move_to_array

Moves the objects `sequence_` names out of `from` into a fixed-size array.

```cpp
template <typename type_, std::size_t... sequence_>
std::array<type_, sizeof...(sequence_)> move_to_array(
    type_ *from,
    std::index_sequence<sequence_...>) noexcept;
```

## generate_array_safely

Builds a fixed-size array from `generator`, or nothing at all if any element refuses.

```cpp
template <typename type_, std::size_t count_, typename generator_type_>
expected<std::array<type_, count_>> generate_array_safely(
    generator_type_ && generator) noexcept;
```

The generator hands back an [`expected`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#expected) per element, and a single failure destroys the prefix already built, so no half-populated array is ever observable. The scratch buffer the elements are assembled in is raw storage this function owns, so every element it constructs it also destroys - a moved-from element still has a destructor to run.

## row_kit_compiled

Whether this build carries `kit`, whatever the processor running it.

```cpp
bool row_kit_compiled(row_kit_t kit) noexcept;
```

## row_kit_supported

Whether this build carries `kit` and the running processor and operating system can execute it.

```cpp
bool row_kit_supported(row_kit_t kit) noexcept;
```

Probes the processor on every call, so ask once at open or construction and keep the answer.

## detect_row_kit

The newest kit this build carries and the processor can run, falling back to [`serial_k`](#serial_k).

```cpp
row_kit_t detect_row_kit() noexcept;
```

## visit_row_kit

Calls `callback` with an instance of the kit `kit` names, or of the serial kit when this build lacks it.

```cpp
template <typename callback_type_>
decltype(auto) visit_row_kit(
    row_kit_t kit,
    callback_type_ && callback) noexcept;
```

The callback is instantiated once per compiled kit, so a structure it builds calls that kit with no dispatch.

Warnings: Visiting a kit the processor cannot run faults on its first search; pass a kit [`row_kit_supported`](#row_kit_supported) accepted, such as the one [`detect_row_kit`](#detect_row_kit) returns.

## successor_or_self

The key right after `key`, or `key` itself when nothing orders after it.

```cpp
template <typename key_type_>
requires row_searchable_key<key_type_>
key_type_ successor_or_self(key_type_ key) noexcept;
```

## count_not_above

How many of [`keys`](#keys) order at or below `wanted`; for a sorted row, the upper bound.

```cpp
template <row_kit row_kit_type_, typename key_type_, std::size_t extent_>
requires row_searchable_key<key_type_>
std::size_t count_not_above(
    std::span<key_type_ const, extent_> keys,
    std::type_identity_t<key_type_> wanted) noexcept;
```

```cpp
template <row_kit row_kit_type_, std::size_t extent_>
std::size_t count_not_above(
    std::span<std::uint64_t const, extent_> high_words,
    std::span<std::uint64_t const, extent_> low_words,
    key128_t wanted) noexcept;
```

How many keys of a split row order at or below `wanted`.

## count_below_sorted

The lower bound of `wanted` in `sorted` of any length.

```cpp
template <row_kit row_kit_type_, typename key_type_, std::size_t extent_>
requires row_searchable_key<key_type_>
std::size_t count_below_sorted(
    std::span<key_type_ const, extent_> sorted,
    std::type_identity_t<key_type_> wanted) noexcept;
```

```cpp
template <row_kit row_kit_type_, std::size_t extent_>
std::size_t count_below_sorted(
    std::span<std::uint64_t const, extent_> high_words,
    std::span<std::uint64_t const, extent_> low_words,
    key128_t wanted) noexcept;
```

The lower bound of `wanted` in a sorted split row of any length, by 256 bytes of high words.

A row of up to about 256 bytes of keys goes to the kit whole; a longer one is first narrowed to such a window by branchless halving. Exact only when `sorted` is sorted.

## count_below_in_row

The lower bound of `wanted` in the sorted row at `row`, laid out by `format_type_` and searched by `row_kit_type_`.

```cpp
template <typename format_type_, row_kit row_kit_type_>
std::size_t count_below_in_row(
    typename format_type_::word_t const *row,
    typename format_type_::key_t wanted) noexcept;
```

## atomic_alignment

The alignment `atomic_ref` demands of a counter updated through it.

```cpp
std::size_t atomic_alignment;
```

A 64-bit integer is only 4-byte aligned by default on a 32-bit target, while `atomic_ref` needs 8, so a counter that is perfectly well-behaved on x86-64 becomes undefined when built for i386. Every counter the helpers below touch carries this.

## size_bits_k

How many bits the size type holds here, which is not 64 everywhere.

```cpp
std::size_t size_bits_k;
```

## size_max_k

The largest `std::size_t`, which also serves as the "no such index" sentinel.

```cpp
std::size_t size_max_k;
```

## algebra_chunk_k

How many members a crossed walk carries out of one side before it puts that side down.

```cpp
std::size_t algebra_chunk_k;
```

The only memory such a walk holds, on its own stack; a larger chunk re-seeds the walk fewer times and costs that much more of it.

## hash_bucket_capacity_k

Number of slots sharing one bucket header, sized so the header fits a 64-bit atomic.

```cpp
std::size_t hash_bucket_capacity_k;
```

## every_row_kit_k

Every kit in enumerator order, for a benchmark or a log that walks them all.

```cpp
row_kit_t every_row_kit_k[];
```