Skip to main content

artmap/
lib.rs

1// Copyright (c) 2026 SurrealDB Ltd
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15//! # artmap: concurrent adaptive radix trees
16//!
17//! Concurrent, ordered, in-memory maps backed by an **Adaptive Radix Tree**
18//! (ART) with **optimistic lock coupling** (OLC):
19//!
20//! - [`ArtMap`]: a key-value map with epoch-based reclamation (EBR).
21//! - [`ArtSet`]: an ordered set of keys, a thin wrapper over `ArtMap<K, ()>`.
22//! - [`VersionedArtMap`]: a map with a chain of 64-bit MVCC versions per key.
23//! - [`ArenaArtMap`] and [`ArenaVersionedArtMap`]: the same, allocated from a
24//!   bump [`Arena`] and reclaimed only when the map is dropped.
25//!
26//! Lookups cost $O(k)$ in the key length. Readers never write to shared tree
27//! memory and never block; writers take fine-grained per-node latches, so
28//! writes to disjoint parts of the tree proceed in parallel.
29//!
30//! ## Epoch guards
31//!
32//! The EBR maps protect memory with the process-wide default
33//! `crossbeam-epoch` collector. Handles returned by the maps
34//! ([`EntryRef`], [`VersionedEntryRef`], iterators) keep an epoch guard alive,
35//! and [`Guard`]s from `map.pin()` can be passed to the `*_with_guard`
36//! methods to amortise pinning.
37//!
38//! - **Holding a guard stalls reclamation process-wide**, for every user of the
39//!   default collector. That includes a handle, an iterator, or a [`Guard`]. Do
40//!   not hold one across I/O or long computations.
41//! - **Leaking a handle** with `mem::forget` pins the current thread for the
42//!   rest of its life. This is memory-safe, but reclamation stops for every
43//!   user of the default collector.
44//! - **Async code.** Handles are `!Send`. Across an `.await`, use `get_value`
45//!   or `with_value`, or copy out with [`EntryRef::to_owned`] or
46//!   [`EntryRef::value_cloned`].
47//! - **Deferred destructors** of removed or replaced keys and values run on an
48//!   arbitrary thread, at an arbitrary later time, and may never run (for
49//!   example at process exit). `Drop` of keys and values must not panic.
50//! - Dropping a map is synchronous: it frees every live entry immediately.
51//!
52//! ## Keys
53//!
54//! Keys are ordered by the bytes returned by [`AsBytes`]. `AsBytes` is a safe
55//! trait: implementations should be deterministic, agree with `Borrow`, and
56//! not panic, but artmap never relies on that for memory safety. A
57//! misbehaving implementation may cause wrong results or panics, never
58//! undefined behaviour. `as_bytes` may be called more than once per
59//! operation, concurrently, and on keys that were already removed.
60//!
61//! ## Consistency
62//!
63//! Point operations are linearizable. Iterators guarantee that every key
64//! present for the whole scan is yielded exactly once, in order; keys inserted
65//! or removed during the scan may or may not appear. `len()` is exact when no
66//! operation is in flight; while several threads write, it is approximate.
67//!
68//! ## Public surface
69//!
70//! No safe API resolves an offset or pointer against an arena other than the
71//! map's own, accepts a raw pointer or handle, or returns a reference that
72//! outlives the map borrow (or, for the EBR maps, its guard).
73
74#![cfg_attr(artmap_provenance_lints, feature(strict_provenance_lints))]
75// Renamed to `implicit_provenance_casts` on newer nightlies; the old names forward.
76#![cfg_attr(artmap_provenance_lints, allow(renamed_and_removed_lints))]
77#![cfg_attr(
78    artmap_provenance_lints,
79    deny(fuzzy_provenance_casts, lossy_provenance_casts)
80)]
81#![deny(let_underscore_drop, clippy::let_underscore_must_use)]
82
83pub mod arena;
84#[cfg(doctest)]
85pub mod compile_fail_tests;
86/// The README's examples, run as doctests.
87#[cfg(doctest)]
88#[doc = include_str!("../README.md")]
89pub struct ReadmeDoctests;
90mod entry;
91mod guard;
92#[cfg(artmap_hooks)]
93#[doc(hidden)]
94pub mod hooks;
95#[cfg(not(artmap_hooks))]
96mod hooks;
97mod iter;
98mod key;
99mod latch;
100#[cfg(all(test, loom))]
101mod loom_tests;
102mod node;
103mod raw;
104mod set;
105mod simd;
106mod sync;
107mod tree;
108pub mod versioned;
109
110use std::borrow::Borrow;
111use std::ops::{Bound, RangeBounds};
112
113pub use arena::{Arena, ArenaArtMap, ArenaInserter, ArenaVersionedArtMap};
114pub use entry::EntryRef;
115pub use guard::Guard;
116pub use iter::{GuardKeys, GuardValues, Iter, KeyRef, Keys, Range, ValueRef, Values};
117pub use key::AsBytes;
118pub use set::ArtSet;
119pub use versioned::{VersionedArtMap, VersionedEntryRef};
120
121use guard::{pin, GuardHandle};
122use raw::cursor::owned_bound;
123use raw::{Mode, Outcome};
124use tree::Tree;
125
126/// Positive `Send`/`Sync` assertions (ยง8.9).
127const _: () = {
128    const fn assert_send_sync<T: Send + Sync>() {}
129    assert_send_sync::<ArtMap<String, u64>>();
130    assert_send_sync::<ArtSet<String>>();
131    assert_send_sync::<VersionedArtMap<String, u64>>();
132    assert_send_sync::<ArenaArtMap<String, u64>>();
133    assert_send_sync::<ArenaVersionedArtMap<String, u64>>();
134    assert_send_sync::<Arena>();
135};
136
137/// A concurrent ordered map backed by an adaptive radix tree.
138///
139/// Reads take no latches (they validate optimistically and retry) and are
140/// linearizable; writes take per-node latches. Values are never mutated in
141/// place: an overwrite publishes a new entry and returns the displaced one,
142/// which stays readable through its handle.
143pub struct ArtMap<K, V> {
144    tree: Tree<K, V>,
145}
146
147impl<K, V> Default for ArtMap<K, V> {
148    #[inline]
149    fn default() -> Self {
150        Self::new()
151    }
152}
153
154impl<K, V> ArtMap<K, V> {
155    sync::const_fn_unless_loom! {
156        /// Creates an empty map.
157        #[inline]
158        pub fn new() -> Self {
159            Self { tree: Tree::new() }
160        }
161    }
162
163    /// Creates an empty map. The capacity is a hint and currently unused.
164    #[inline]
165    pub fn with_capacity(_capacity: usize) -> Self {
166        Self::new()
167    }
168
169    /// The number of entries. Exact when no operation is in flight. While
170    /// writes on several threads (or a `clear()`) are in flight it is
171    /// approximate: the count is striped by thread so that writers do not
172    /// contend on one cache line.
173    #[inline]
174    pub fn len(&self) -> usize {
175        self.tree.len()
176    }
177
178    /// `true` if the map has no entries.
179    #[inline]
180    pub fn is_empty(&self) -> bool {
181        self.len() == 0
182    }
183}
184
185impl<K: AsBytes + Send + 'static, V: Send + 'static> ArtMap<K, V> {
186    /// Pins the epoch, for the `*_with_guard` methods. See the crate docs for
187    /// what holding a guard implies.
188    ///
189    /// ```
190    /// let map = artmap::ArtMap::<[u8; 8], u64>::new();
191    /// map.insert(7u64.to_be_bytes(), 49);
192    /// let guard = map.pin();
193    /// assert_eq!(map.get_with_guard(&7u64.to_be_bytes(), &guard).as_deref(), Some(&49));
194    /// ```
195    #[inline]
196    pub fn pin(&self) -> Guard<'_> {
197        Guard::new()
198    }
199
200    /// A handle on the entry for `key`.
201    ///
202    /// ```
203    /// let map = artmap::ArtMap::<String, u32>::new();
204    /// map.insert("a".to_string(), 1);
205    /// let e = map.get("a").unwrap();
206    /// assert_eq!((e.key().as_str(), *e.value()), ("a", 1));
207    /// assert!(map.get("b").is_none());
208    /// ```
209    #[inline]
210    pub fn get<Q>(&self, key: &Q) -> Option<EntryRef<'_, K, V>>
211    where
212        K: Borrow<Q>,
213        Q: AsBytes + ?Sized,
214    {
215        self.get_by_slice(key.as_bytes())
216    }
217
218    /// A handle on the entry for a raw byte key.
219    #[inline]
220    pub fn get_by_slice(&self, key: &[u8]) -> Option<EntryRef<'_, K, V>> {
221        let guard = GuardHandle::owned();
222        let leaf = self.tree.raw.get(key)?;
223        Some(EntryRef::new(leaf, &self.tree, guard))
224    }
225
226    /// A handle on the entry for `key`, borrowing the caller's guard instead of
227    /// pinning.
228    #[inline]
229    pub fn get_with_guard<'a, Q>(
230        &'a self,
231        key: &Q,
232        guard: &'a Guard<'_>,
233    ) -> Option<EntryRef<'a, K, V>>
234    where
235        K: Borrow<Q>,
236        Q: AsBytes + ?Sized,
237    {
238        let leaf = self.tree.raw.get(key.as_bytes())?;
239        Some(EntryRef::new(
240            leaf,
241            &self.tree,
242            GuardHandle::Borrowed(&guard.inner),
243        ))
244    }
245
246    /// A clone of the value for `key`.
247    #[inline]
248    pub fn get_value<Q>(&self, key: &Q) -> Option<V>
249    where
250        K: Borrow<Q>,
251        Q: AsBytes + ?Sized,
252        V: Clone,
253    {
254        self.with_value(key, V::clone)
255    }
256
257    /// Calls `f` with the value for `key`, without cloning.
258    #[inline]
259    pub fn with_value<Q, R, F>(&self, key: &Q, f: F) -> Option<R>
260    where
261        K: Borrow<Q>,
262        Q: AsBytes + ?Sized,
263        F: FnOnce(&V) -> R,
264    {
265        let _g = pin();
266        let leaf = self.tree.raw.get(key.as_bytes())?;
267        // SAFETY: protected by `_g` for the duration of `f`; `R` cannot borrow
268        // from `&V` (it is chosen by the caller before the borrow exists).
269        Some(f(&unsafe { leaf.as_ref() }.value))
270    }
271
272    /// `true` if the map has an entry for `key`.
273    #[inline]
274    pub fn contains_key<Q>(&self, key: &Q) -> bool
275    where
276        K: Borrow<Q>,
277        Q: AsBytes + ?Sized,
278    {
279        self.contains_key_slice(key.as_bytes())
280    }
281
282    /// `true` if the map has an entry for a raw byte key.
283    #[inline]
284    pub fn contains_key_slice(&self, key: &[u8]) -> bool {
285        let _g = pin();
286        self.tree.raw.get(key).is_some()
287    }
288
289    /// Inserts or replaces. Returns the displaced entry (already unlinked and
290    /// marked removed), or `None` if the key was absent.
291    ///
292    /// Dropping the returned handle immediately costs one unpin.
293    ///
294    /// ```
295    /// let map = artmap::ArtMap::<String, u32>::new();
296    /// assert!(map.insert("a".to_string(), 1).is_none());
297    /// let old = map.insert("a".to_string(), 2).unwrap();
298    /// assert_eq!(*old, 1);
299    /// assert!(old.is_removed());
300    /// assert_eq!(map.get_value("a"), Some(2));
301    /// ```
302    #[inline]
303    pub fn insert(&self, key: K, value: V) -> Option<EntryRef<'_, K, V>> {
304        let guard = GuardHandle::owned();
305        self.insert_in(key, value, guard)
306    }
307
308    /// As [`insert`](Self::insert), borrowing the caller's guard.
309    #[inline]
310    pub fn insert_with_guard<'a>(
311        &'a self,
312        key: K,
313        value: V,
314        guard: &'a Guard<'_>,
315    ) -> Option<EntryRef<'a, K, V>> {
316        self.insert_in(key, value, GuardHandle::Borrowed(&guard.inner))
317    }
318
319    /// As [`insert`](Self::insert), returning a clone of the displaced value
320    /// (cloned after every latch is released).
321    #[inline]
322    pub fn insert_cloned(&self, key: K, value: V) -> Option<V>
323    where
324        V: Clone,
325    {
326        self.insert(key, value).map(|old| old.value().clone())
327    }
328
329    #[inline]
330    fn insert_in<'a>(
331        &'a self,
332        key: K,
333        value: V,
334        guard: GuardHandle<'a>,
335    ) -> Option<EntryRef<'a, K, V>> {
336        match self.tree.insert(key, value, Mode::Replace, guard.guard()) {
337            Outcome::Inserted(_) => None,
338            Outcome::Replaced(old) => Some(EntryRef::new(old, &self.tree, guard)),
339            Outcome::Existing(_) => unreachable!("Mode::Replace always publishes"),
340        }
341    }
342
343    /// Returns the entry for `key`, inserting `f()` first if it is absent.
344    ///
345    /// `f` runs without any latch held, and only if the key looked absent.
346    ///
347    /// ```
348    /// let map = artmap::ArtMap::<String, u32>::new();
349    /// assert_eq!(*map.get_or_insert_with("a".to_string(), || 1), 1);
350    /// assert_eq!(*map.get_or_insert_with("a".to_string(), || 2), 1);
351    /// ```
352    pub fn get_or_insert_with<F>(&self, key: K, f: F) -> EntryRef<'_, K, V>
353    where
354        F: FnOnce() -> V,
355    {
356        let guard = GuardHandle::owned();
357        // A hint only (Inv 10): the install below decides.
358        if let Some(leaf) = self.tree.raw.get(key.as_bytes()) {
359            return EntryRef::new(leaf, &self.tree, guard);
360        }
361        let value = f();
362        match self
363            .tree
364            .insert(key, value, Mode::InsertIfAbsent, guard.guard())
365        {
366            Outcome::Inserted(leaf) => EntryRef::new(leaf, &self.tree, guard),
367            Outcome::Existing(existing) => EntryRef::new(existing, &self.tree, guard),
368            Outcome::Replaced(_) => unreachable!("InsertIfAbsent never replaces"),
369        }
370    }
371
372    /// Inserts `(key, value)` only if `key` is absent, and reports whether it
373    /// did. An existing entry is left untouched and nothing is retired.
374    ///
375    /// Like [`get_or_insert_with`](Self::get_or_insert_with), it checks for the
376    /// key first, so a present key costs a lookup and no allocation.
377    pub(crate) fn insert_if_absent(&self, key: K, value: V) -> bool {
378        let guard = pin();
379        // A hint only (Inv 10): the install below decides.
380        if self.tree.raw.get(key.as_bytes()).is_some() {
381            return false;
382        }
383        match self.tree.insert(key, value, Mode::InsertIfAbsent, &guard) {
384            Outcome::Inserted(_) => true,
385            Outcome::Existing(_) => false,
386            Outcome::Replaced(_) => unreachable!("InsertIfAbsent never replaces"),
387        }
388    }
389
390    /// Removes the entry for `key`. Returns the removed entry (unlinked and
391    /// marked removed).
392    ///
393    /// ```
394    /// let map = artmap::ArtMap::<String, u32>::new();
395    /// map.insert("a".to_string(), 1);
396    /// assert_eq!(map.remove("a").as_deref(), Some(&1));
397    /// assert!(map.remove("a").is_none());
398    /// assert!(map.is_empty());
399    /// ```
400    #[inline]
401    pub fn remove<Q>(&self, key: &Q) -> Option<EntryRef<'_, K, V>>
402    where
403        K: Borrow<Q>,
404        Q: AsBytes + ?Sized,
405    {
406        self.remove_by_slice(key.as_bytes())
407    }
408
409    /// Removes the entry for a raw byte key.
410    #[inline]
411    pub fn remove_by_slice(&self, key: &[u8]) -> Option<EntryRef<'_, K, V>> {
412        let guard = GuardHandle::owned();
413        let leaf = self.tree.remove(key, guard.guard())?;
414        Some(EntryRef::new(leaf, &self.tree, guard))
415    }
416
417    /// An iterator over the entries in `range`, in key order.
418    ///
419    /// ```
420    /// let map = artmap::ArtMap::<String, u32>::new();
421    /// for (i, k) in ["a", "b", "c", "d"].into_iter().enumerate() {
422    ///     map.insert(k.to_string(), i as u32);
423    /// }
424    /// let keys: Vec<String> = map.range("b".."d").map(|e| e.key().clone()).collect();
425    /// assert_eq!(keys, ["b", "c"]);
426    /// let back: Vec<u32> = map.range("b"..).rev().map(|e| *e).collect();
427    /// assert_eq!(back, [3, 2, 1]);
428    /// ```
429    pub fn range<R, Q>(&self, range: R) -> Range<'_, K, V>
430    where
431        R: RangeBounds<Q>,
432        Q: AsBytes + ?Sized,
433    {
434        Range::owned(
435            &self.tree,
436            owned_bound(range.start_bound()),
437            owned_bound(range.end_bound()),
438        )
439    }
440
441    /// As [`range`](Self::range), borrowing the caller's guard.
442    pub fn range_with_guard<'a, R, Q>(&'a self, range: R, guard: &'a Guard<'_>) -> Range<'a, K, V>
443    where
444        R: RangeBounds<Q>,
445        Q: AsBytes + ?Sized,
446    {
447        Range::borrowed(
448            &self.tree,
449            &guard.inner,
450            owned_bound(range.start_bound()),
451            owned_bound(range.end_bound()),
452        )
453    }
454
455    /// Calls `callback(key, value)` for each entry in `range`, in key order,
456    /// until it returns `false`.
457    ///
458    /// One pin covers the whole scan, and no per-entry handle is created, so
459    /// this is the cheapest way to visit a range.
460    ///
461    /// ```
462    /// let map = artmap::ArtMap::<String, u32>::new();
463    /// for (i, k) in ["a", "b", "c", "d"].into_iter().enumerate() {
464    ///     map.insert(k.to_string(), i as u32);
465    /// }
466    /// let mut seen = Vec::new();
467    /// map.scan("b".."d", |k, v| {
468    ///     seen.push((k.clone(), *v));
469    ///     true
470    /// });
471    /// assert_eq!(seen, [("b".to_string(), 1), ("c".to_string(), 2)]);
472    /// ```
473    pub fn scan<R, Q, F>(&self, range: R, mut callback: F)
474    where
475        R: RangeBounds<Q>,
476        Q: AsBytes + ?Sized,
477        F: FnMut(&K, &V) -> bool,
478    {
479        let guard = self.pin();
480        for e in self.range_with_guard(range, &guard) {
481            if !callback(e.key(), e.value()) {
482                break;
483            }
484        }
485    }
486
487    /// An iterator over every entry, in key order.
488    pub fn iter(&self) -> Iter<'_, K, V> {
489        Range::owned(&self.tree, Bound::Unbounded, Bound::Unbounded)
490    }
491
492    /// As [`iter`](Self::iter), borrowing the caller's guard.
493    pub fn iter_with_guard<'a>(&'a self, guard: &'a Guard<'_>) -> Iter<'a, K, V> {
494        Range::borrowed(&self.tree, &guard.inner, Bound::Unbounded, Bound::Unbounded)
495    }
496
497    /// An iterator over every key, in order.
498    pub fn keys(&self) -> Keys<'_, K, V> {
499        Keys(self.iter())
500    }
501
502    /// An iterator over every value, in key order.
503    pub fn values(&self) -> Values<'_, K, V> {
504        Values(self.iter())
505    }
506
507    /// Keys as bare references, bounded by the map and the caller's guard.
508    pub fn keys_with_guard<'a>(&'a self, guard: &'a Guard<'_>) -> GuardKeys<'a, K, V> {
509        GuardKeys(self.iter_with_guard(guard))
510    }
511
512    /// Values as bare references, bounded by the map and the caller's guard.
513    pub fn values_with_guard<'a>(&'a self, guard: &'a Guard<'_>) -> GuardValues<'a, K, V> {
514        GuardValues(self.iter_with_guard(guard))
515    }
516
517    /// Removes every entry. Linearizable with respect to point operations:
518    /// the linearization point is the swap of the root. Runs in O(n) on the
519    /// calling thread, holding at most one node latch at a time.
520    pub fn clear(&self) {
521        let g = pin();
522        self.tree.raw.clear(&g);
523    }
524
525    /// Checks the tree's structural invariants and that `len()` equals the
526    /// number of reachable entries. Panics on a violation. Requires exclusive
527    /// access, so it never races with writers.
528    pub fn validate_invariants(&mut self) {
529        self.tree.raw.validate();
530    }
531}
532
533impl<'a, K: AsBytes + Send + 'static, V: Send + 'static> IntoIterator for &'a ArtMap<K, V> {
534    type Item = EntryRef<'a, K, V>;
535    type IntoIter = Iter<'a, K, V>;
536
537    #[inline]
538    fn into_iter(self) -> Self::IntoIter {
539        self.iter()
540    }
541}
542
543#[cfg(all(test, not(loom)))]
544mod tests {
545    use super::*;
546
547    #[test]
548    fn basic_flow() {
549        let mut map = ArtMap::<String, i32>::new();
550        assert!(map.is_empty());
551        assert!(map.insert("users:100".into(), 1).is_none());
552        assert!(map.insert("users:200".into(), 2).is_none());
553        assert!(map.insert("users:300".into(), 3).is_none());
554        assert_eq!(map.len(), 3);
555        assert_eq!(map.get("users:100").as_deref(), Some(&1));
556        assert_eq!(map.get_by_slice(b"users:200").as_deref(), Some(&2));
557        assert!(map.contains_key("users:300"));
558        assert!(!map.contains_key("users:400"));
559        assert_eq!(map.with_value("users:100", |v| *v * 2), Some(2));
560        let old = map.insert("users:100".into(), 10).expect("replaced");
561        assert_eq!(*old, 1);
562        assert!(old.is_removed());
563        drop(old);
564        assert_eq!(map.get("users:100").as_deref(), Some(&10));
565        assert_eq!(map.remove("users:200").as_deref(), Some(&2));
566        assert!(map.get("users:200").is_none());
567        assert_eq!(map.len(), 2);
568        map.validate_invariants();
569    }
570
571    #[test]
572    fn range_scan() {
573        let map = ArtMap::<String, i32>::new();
574        for i in 1..=5 {
575            map.insert(format!("k:{i}"), i);
576        }
577        let items: Vec<_> = map.range("k:2".."k:5").map(|e| *e.value()).collect();
578        assert_eq!(items, vec![2, 3, 4]);
579        let rev: Vec<_> = map.range("k:2".."k:5").rev().map(|e| *e.value()).collect();
580        assert_eq!(rev, vec![4, 3, 2]);
581    }
582
583    #[test]
584    fn get_or_insert_with() {
585        let map = ArtMap::<String, i32>::new();
586        {
587            let e = map.get_or_insert_with("key".into(), || 42);
588            assert_eq!(*e, 42);
589            assert_eq!(e.key(), "key");
590            assert!(!e.is_removed());
591            assert!(e.remove());
592            assert!(e.is_removed());
593            assert!(!e.remove());
594        }
595        assert!(map.get("key").is_none());
596        let e = map.get_or_insert_with("k2".into(), || 1);
597        let e2 = map.get_or_insert_with("k2".into(), || panic!("must not run"));
598        assert_eq!(*e, 1);
599        assert_eq!(*e2, 1);
600    }
601
602    #[test]
603    fn clear_is_exact() {
604        let mut map = ArtMap::<[u8; 8], u64>::new();
605        for i in 0..1000u64 {
606            map.insert(i.to_be_bytes(), i);
607        }
608        map.clear();
609        assert_eq!(map.len(), 0);
610        assert!(map.iter().next().is_none());
611        map.insert(1u64.to_be_bytes(), 1);
612        assert_eq!(map.len(), 1);
613        map.validate_invariants();
614    }
615}