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}