# Containers > SmashTable for Python `SortedMap` and `SortedSet` keep their keys in order, which is what iteration, `scan` and slice erase rest on. `HashMap` and `HashSet` are the same stores over an open-addressed core, and offer point access only: ```python cache = st.HashMap(key=str) cache['a'] = 1 cache['a'], len(cache), 'a' in cache # (1, 1, True) cache.scan() # AttributeError — no ordering to scan list(cache) # TypeError — not iterable ``` The absent methods are absent from the type rather than refused at the call, so reaching for one fails the way a typo fails. Everything else is shared — the same key layouts, the same isolation and sharing choices, the same transactions — so one `st.transaction()` may span ordered and unordered stores together. 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 ├─ basic_avl_tree ├─ basic_wb_tree # also `rank` and `select` ├─ basic_hash_table # grows, iterates, rehashes ├─ basic_flat_set # sorted, one allocation, searched a row at a time ├─ basic_ring # first-in first-out, capacity fixed at `make` ├─ basic_hash_index # keys to record positions, capacity fixed, no tombstones ├─ basic_fixed_pool # records taken and vacated by index, handles that go stale ├─ basic_growing_pool # the same in chunks that never move, read beside its growth └─ intrusive_list # first-in first-out through the records' own `next` Immutable, built once and never written ├─ immutable_b_tree # keys on every level ├─ immutable_splus_tree # every key in the leaves, separators above ├─ immutable_elias_fano # non-decreasing integers in a few bits apiece └─ immutable_packed_array # integers as distances from a base, one width each atomic_* → Pinned core. Fixed capacity, atomic per slot, callback reads. └─ atomic_hash_table # the one type that runs on a GPU ↑ ::adopt(std::move(growable).release()) ↓ ::adopt(std::move(pinned).release()) atomic_intrusive_stack → any thread pushes, one takes all, no capacity *_store → 2-phase commit, watch and CAS. ├─ monotonic_store # one visible version per key ├─ snapshot_store # every version a live reader can still name └─ reference_store # 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 # one lock spans a whole commit └─ partitioned_store # one lock per partition, one shared commit order transaction_group → 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` 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`, 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; // …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(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(stamps)); // base 1000, 3 bits apiece std::vector 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` 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 const reclaimed = store.vacuum(); // everything no reader can name expected const window = store.vacuum(lower, upper); // ordered cores, one slice at a time ``` ### Snapshot Isolation > `smashtable/snapshot_store.hpp` `snapshot_store` 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 // isolation_k == snapshot_k serializable_store // reads validated too strict_serializable_store // and a commit waits for its own publication serializable_avl_map // and `_avl_set`, `_wb_*`, `_hash_*` strict_serializable_avl_map // 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`: | | `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` and `hash_map` 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::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::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. `import smashtable` `from smashtable import SortedMap, SortedSet, HashMap, …` ## DuplicateKeyError A key was inserted where the caller asked for it to be absent. ```python class DuplicateKeyError(SmashTableError, KeyError) ``` ## SortedMap An ordered mapping whose writes can be grouped into transactions. ```python class SortedMap ``` Keys are homogeneous and their type is fixed at construction, which is what lets every comparison skip type dispatch. Floats and booleans may be values but never keys. Raises: - `TypeError`: If key is missing, or names float or bool. - `ValueError`: If key, value, isolation or sharing names an unknown choice. ## SortedMap ```python SortedMap( *, key: _KeySpec, value: _ValueSpec = 'scalar', isolation: Literal['monotonic_atomic_view', 'snapshot', 'serializable', 'strict_serializable'] = 'monotonic_atomic_view', sharing: Literal['locked', 'partitioned'] = 'locked', ) ``` ## * Value for a key, or default when the key is absent. ```python def get(key: _Key, default: Any = None, /) -> Any ``` Raises: - `TypeError`: If key is not of this store's key type. ## * Remove a key and return its value. ```python def pop(key: _Key, default: Any = ..., /) -> Any ``` Raises: - `KeyError`: If the key is absent and no default was given. ## popmin Remove and return the smallest (key, value) pair. ```python def popmin() -> tuple[_Key, Any] ``` Named for what it does rather than borrowing dict's popitem, which removes the most recently inserted pair. The store steps forward only, so the largest key would cost a full walk while the smallest costs one lookup. Raises: - `KeyError`: If the store is empty. ## * Value for a key, inserting default first when the key is absent. ```python def setdefault(key: _Key, default: Any = None, /) -> Any ``` The insertion is one strict operation rather than a lookup followed by a write, so two threads racing on the same key cannot both believe they won. Raises: - `TypeError`: If key is not of this store's key type, or default is not a value this store can hold. ## * Apply every pair of a mapping or an iterable of pairs. ```python def update( other: Mapping[_Key, Any] | Iterable[tuple[_Key, Any]], /, ) -> None ``` The batch lands as one unit: the store stages it and commits it once, so a failure part-way leaves nothing applied. This is stronger than dict, which applies pairs one at a time. Raises: - `TypeError`: If other is neither a mapping nor an iterable of pairs, or a key or value in it is not one this store can hold. - `ValueError`: If an element of other is not a pair. ## * Remove every entry. ```python def clear() -> None ``` The key type stays as it was. ## scan List of (key, value) pairs in key order, over the half-open window [start, stop). ```python def scan( start: _Key | None = None, stop: _Key | None = None, *, limit: int | None = None, ) -> list[tuple[_Key, Any]] ``` Bounds need not be present keys. Read in one span rather than lazily, so the list holds a single committed state unless isolation is 'read_committed'; iterate the container itself to walk it lazily. Raises: - `TypeError`: If a bound is not of this store's key type. - `ValueError`: If limit is negative. ## keys A lazy view over the keys, in order. ```python def keys() -> _KeysView ``` ## values A lazy view over the values, in key order. ```python def values() -> _ValuesView ``` ## items A lazy view over the (key, value) pairs, in key order. ```python def items() -> _ItemsView ``` ## * Open a transaction over this store alone. ```python def transaction() -> Transaction ``` ## key_type The key layout this store was built around: 'int', 'uint', 'str' or 'bytes'. ```python key_type: Literal['int', 'uint', 'str', 'bytes'] ``` ## value_mode 'scalar' when values must be scalars, 'object' when any object is stored. ```python value_mode: Literal['scalar', 'object'] ``` ## isolation What this store actually promises a reader, as Jepsen names it. ```python isolation: _DeliveredIsolationName ``` Four levels may be asked for, in ascending strength: 'monotonic_atomic_view', 'snapshot', 'serializable' and 'strict_serializable'. The last two both refuse a schedule no serial order explains; the stricter one additionally waits for every earlier commit to become visible, so a transaction opening after a commit returns cannot be ordered before it. The effective level rather than the one asked for. A stamped store keeps its level across partitions, since visibility there is a comparison against a stamp rather than a lock somebody holds. A monotonic one sharded across partitions reports 'read_committed', because a reader holding no stamp can catch a commit half-applied. ## sharing How this store is shared between threads: 'locked' or 'partitioned'. ```python sharing: Literal['locked', 'partitioned'] ``` What was asked for, unlike isolation, which reports what is delivered. ## __hash__ Mutable and compared by content, so it is deliberately unhashable. ```python __hash__: None ``` ## SortedSet An ordered set whose writes can be grouped into transactions. ```python class SortedSet ``` Members are homogeneous and their type is fixed at construction. Floats and booleans are not valid members, for the same reason they are not valid keys. ## SortedSet ```python SortedSet( *, key: _KeySpec, isolation: Literal['monotonic_atomic_view', 'snapshot', 'serializable', 'strict_serializable'] = 'monotonic_atomic_view', sharing: Literal['locked', 'partitioned'] = 'locked', ) ``` ## __delitem__ A set is subscripted only by a slice, which erases the window it names. ```python def __delitem__(window: slice, /) -> None ``` ## * Insert a member. ```python def add(member: _Key, /) -> None ``` Adding one that is already present does nothing. Raises: - `TypeError`: If member is not of this set's key type. ## * Remove a member if present, and say nothing if not. ```python def discard(member: _Key, /) -> None ``` ## * Remove a member. ```python def remove(member: _Key, /) -> None ``` Raises: - `KeyError`: If the member is absent. ## popmin Remove and return the smallest member. ```python def popmin() -> _Key ``` Unlike set, which pops an arbitrary member, this pops the smallest, which the ordered store reaches in one lookup. Raises: - `KeyError`: If the set is empty. ## * Add every member of an iterable. ```python def update(other: Iterable[_Key], /) -> None ``` The batch lands as one unit: the store stages it and commits it once, so a failure part-way leaves nothing applied. This is stronger than set, which adds members one at a time. Raises: - `TypeError`: If other is not iterable, or a member of it is not of this set's key type. ## scan List of members in order, over the half-open window [start, stop). ```python def scan( start: _Key | None = None, stop: _Key | None = None, *, limit: int | None = None, ) -> list[_Key] ``` Bounds need not be present members. Read in one span rather than lazily, so the list holds a single committed state unless isolation is 'read_committed'; iterate the set to walk it lazily. Raises: - `TypeError`: If a bound is not of this set's key type. - `ValueError`: If limit is negative. ## union Members of either side, as a new set. ```python def union(other: Iterable[_Key], /) -> SortedSet ``` ## intersection Members of both sides. ```python def intersection(other: Iterable[_Key], /) -> SortedSet ``` ## difference Members of this side only. ```python def difference(other: Iterable[_Key], /) -> SortedSet ``` ## symmetric_difference Members of exactly one side. ```python def symmetric_difference(other: Iterable[_Key], /) -> SortedSet ``` ## isdisjoint Whether the two sides share no member. ```python def isdisjoint(other: Iterable[_Key], /) -> bool ``` ## key_type The key layout this store was built around: 'int', 'uint', 'str' or 'bytes'. ```python key_type: Literal['int', 'uint', 'str', 'bytes'] ``` ## isolation What this store actually promises a reader, as Jepsen names it. ```python isolation: _DeliveredIsolationName ``` Four levels may be asked for, in ascending strength: 'monotonic_atomic_view', 'snapshot', 'serializable' and 'strict_serializable'. The last two both refuse a schedule no serial order explains; the stricter one additionally waits for every earlier commit to become visible, so a transaction opening after a commit returns cannot be ordered before it. The effective level rather than the one asked for. A stamped store keeps its level across partitions, since visibility there is a comparison against a stamp rather than a lock somebody holds. A monotonic one sharded across partitions reports 'read_committed', because a reader holding no stamp can catch a commit half-applied. ## sharing How this store is shared between threads: 'locked' or 'partitioned'. ```python sharing: Literal['locked', 'partitioned'] ``` What was asked for, unlike isolation, which reports what is delivered. ## __hash__ Mutable and compared by content, so it is deliberately unhashable. ```python __hash__: None ``` ## HashMap An unordered mapping whose writes can be grouped into transactions. ```python class HashMap ``` Point access only. The open-addressed core supplies no ordering, so this class has no iteration, no keys/values/items, no scan and no range erase - reaching for one is an AttributeError rather than an empty result. Use SortedMap when order or enumeration matters. ## HashMap ```python HashMap( *, key: _KeySpec, value: _ValueSpec = 'scalar', isolation: Literal['monotonic_atomic_view', 'snapshot', 'serializable', 'strict_serializable'] = 'monotonic_atomic_view', sharing: Literal['locked', 'partitioned'] = 'locked', ) ``` ## key_type The key layout this store was built around: 'int', 'uint', 'str' or 'bytes'. ```python key_type: Literal['int', 'uint', 'str', 'bytes'] ``` ## value_mode 'scalar' when values must be scalars, 'object' when any object is stored. ```python value_mode: Literal['scalar', 'object'] ``` ## isolation What this store actually promises a reader, as Jepsen names it. ```python isolation: _DeliveredIsolationName ``` Four levels may be asked for, in ascending strength: 'monotonic_atomic_view', 'snapshot', 'serializable' and 'strict_serializable'. The last two both refuse a schedule no serial order explains; the stricter one additionally waits for every earlier commit to become visible, so a transaction opening after a commit returns cannot be ordered before it. The effective level rather than the one asked for. A stamped store keeps its level across partitions, since visibility there is a comparison against a stamp rather than a lock somebody holds. A monotonic one sharded across partitions reports 'read_committed', because a reader holding no stamp can catch a commit half-applied. ## sharing How this store is shared between threads: 'locked' or 'partitioned'. ```python sharing: Literal['locked', 'partitioned'] ``` What was asked for, unlike isolation, which reports what is delivered. ## HashSet An unordered set whose writes can be grouped into transactions. ```python class HashSet ``` Membership and mutation only. The core supplies no ordering, so this class has no iteration, no scan, no pop and none of the set algebra, each of which would have to walk at least one side. Use SortedSet when any of those matter. ## HashSet ```python HashSet( *, key: _KeySpec, isolation: Literal['monotonic_atomic_view', 'snapshot', 'serializable', 'strict_serializable'] = 'monotonic_atomic_view', sharing: Literal['locked', 'partitioned'] = 'locked', ) ``` ## key_type The key layout this store was built around: 'int', 'uint', 'str' or 'bytes'. ```python key_type: Literal['int', 'uint', 'str', 'bytes'] ``` ## isolation What this store actually promises a reader, as Jepsen names it. ```python isolation: _DeliveredIsolationName ``` Four levels may be asked for, in ascending strength: 'monotonic_atomic_view', 'snapshot', 'serializable' and 'strict_serializable'. The last two both refuse a schedule no serial order explains; the stricter one additionally waits for every earlier commit to become visible, so a transaction opening after a commit returns cannot be ordered before it. The effective level rather than the one asked for. A stamped store keeps its level across partitions, since visibility there is a comparison against a stamp rather than a lock somebody holds. A monotonic one sharded across partitions reports 'read_committed', because a reader holding no stamp can catch a commit half-applied. ## sharing How this store is shared between threads: 'locked' or 'partitioned'. ```python sharing: Literal['locked', 'partitioned'] ``` What was asked for, unlike isolation, which reports what is delivered.