Skip to main content

Crate artmap

Crate artmap 

Source
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 over ArtMap<K, ()>.
  • VersionedArtMap: a map with a chain of 64-bit MVCC versions per key.
  • ArenaArtMap and ArenaVersionedArtMap: the same, allocated from a bump Arena and 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::forget pins 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, use get_value or with_value, or copy out with EntryRef::to_owned or EntryRef::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). Drop of 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§

arena
Arena-backed adaptive radix trees
versioned
Multi-version adaptive radix tree (EBR)

Structs§

ArtMap
A concurrent ordered map backed by an adaptive radix tree.
ArtSet
A concurrent ordered set backed by an adaptive radix tree.
EntryRef
A consistent snapshot of one entry of an ArtMap.
Guard
An epoch guard for an ArtMap or VersionedArtMap.
GuardKeys
Keys borrowed through a caller’s Guard: bare &'a K, bounded by both the map borrow and the guard borrow.
GuardValues
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, with rev).
ValueRef
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.

Type Aliases§

Iter
An iterator over all entries of an ArtMap.