Expand description
§artmap: concurrent adaptive radix trees
Concurrent, ordered, in-memory maps backed by an Adaptive Radix Tree (ART) with optimistic lock coupling (OLC):
ArtMap: a key-value map with epoch-based reclamation (EBR).ArtSet: an ordered set of keys, a thin wrapper overArtMap<K, ()>.VersionedArtMap: a map with a chain of 64-bit MVCC versions per key.ArenaArtMapandArenaVersionedArtMap: the same, allocated from a bumpArenaand reclaimed only when the map is dropped.
Lookups cost $O(k)$ in the key length. Readers never write to shared tree memory and never block; writers take fine-grained per-node latches, so writes to disjoint parts of the tree proceed in parallel.
§Epoch guards
The EBR maps protect memory with the process-wide default
crossbeam-epoch collector. Handles returned by the maps
(EntryRef, VersionedEntryRef, iterators) keep an epoch guard alive,
and Guards from map.pin() can be passed to the *_with_guard
methods to amortise pinning.
- Holding a guard stalls reclamation process-wide, for every user of the
default collector. That includes a handle, an iterator, or a
Guard. Do not hold one across I/O or long computations. - Leaking a handle with
mem::forgetpins the current thread for the rest of its life. This is memory-safe, but reclamation stops for every user of the default collector. - Async code. Handles are
!Send. Across an.await, useget_valueorwith_value, or copy out withEntryRef::to_ownedorEntryRef::value_cloned. - Deferred destructors of removed or replaced keys and values run on an
arbitrary thread, at an arbitrary later time, and may never run (for
example at process exit).
Dropof keys and values must not panic. - Dropping a map is synchronous: it frees every live entry immediately.
§Keys
Keys are ordered by the bytes returned by AsBytes. AsBytes is a safe
trait: implementations should be deterministic, agree with Borrow, and
not panic, but artmap never relies on that for memory safety. A
misbehaving implementation may cause wrong results or panics, never
undefined behaviour. as_bytes may be called more than once per
operation, concurrently, and on keys that were already removed.
§Consistency
Point operations are linearizable. Iterators guarantee that every key
present for the whole scan is yielded exactly once, in order; keys inserted
or removed during the scan may or may not appear. len() is exact when no
operation is in flight; while several threads write, it is approximate.
§Public surface
No safe API resolves an offset or pointer against an arena other than the map’s own, accepts a raw pointer or handle, or returns a reference that outlives the map borrow (or, for the EBR maps, its guard).
Re-exports§
pub use arena::Arena;pub use arena::ArenaArtMap;pub use arena::ArenaInserter;pub use arena::ArenaVersionedArtMap;pub use versioned::VersionedArtMap;pub use versioned::VersionedEntryRef;
Modules§
Structs§
- ArtMap
- A concurrent ordered map backed by an adaptive radix tree.
- ArtSet
- A concurrent ordered set backed by an adaptive radix tree.
- Entry
Ref - A consistent snapshot of one entry of an
ArtMap. - Guard
- An epoch guard for an
ArtMaporVersionedArtMap. - Guard
Keys - Keys borrowed through a caller’s
Guard: bare&'a K, bounded by both the map borrow and the guard borrow. - Guard
Values - Values borrowed through a caller’s
Guard: bare&'a V. - KeyRef
- A key yielded by
Keys: a handle that dereferences to the key. - Keys
- An iterator over the keys of an
ArtMap. - Range
- An iterator over a range of entries of an
ArtMap, in ascending key order (or descending, withrev). - Value
Ref - A value yielded by
Values: a handle that dereferences to the value. - Values
- An iterator over the values of an
ArtMap.
Traits§
- AsBytes
- A trait for types that can be borrowed as a byte slice for radix indexing.