#![cfg_attr(artmap_provenance_lints, feature(strict_provenance_lints))]
#![cfg_attr(artmap_provenance_lints, allow(renamed_and_removed_lints))]
#![cfg_attr(
artmap_provenance_lints,
deny(fuzzy_provenance_casts, lossy_provenance_casts)
)]
#![deny(let_underscore_drop, clippy::let_underscore_must_use)]
pub mod arena;
#[cfg(doctest)]
pub mod compile_fail_tests;
#[cfg(doctest)]
#[doc = include_str!("../README.md")]
pub struct ReadmeDoctests;
mod entry;
mod guard;
#[cfg(artmap_hooks)]
#[doc(hidden)]
pub mod hooks;
#[cfg(not(artmap_hooks))]
mod hooks;
mod iter;
mod key;
mod latch;
#[cfg(all(test, loom))]
mod loom_tests;
mod node;
mod raw;
mod set;
mod simd;
mod sync;
mod tree;
pub mod versioned;
use std::borrow::Borrow;
use std::ops::{Bound, RangeBounds};
pub use arena::{Arena, ArenaArtMap, ArenaInserter, ArenaVersionedArtMap};
pub use entry::EntryRef;
pub use guard::Guard;
pub use iter::{GuardKeys, GuardValues, Iter, KeyRef, Keys, Range, ValueRef, Values};
pub use key::AsBytes;
pub use set::ArtSet;
pub use versioned::{VersionedArtMap, VersionedEntryRef};
use guard::{pin, GuardHandle};
use raw::cursor::owned_bound;
use raw::{Mode, Outcome};
use tree::Tree;
const _: () = {
const fn assert_send_sync<T: Send + Sync>() {}
assert_send_sync::<ArtMap<String, u64>>();
assert_send_sync::<ArtSet<String>>();
assert_send_sync::<VersionedArtMap<String, u64>>();
assert_send_sync::<ArenaArtMap<String, u64>>();
assert_send_sync::<ArenaVersionedArtMap<String, u64>>();
assert_send_sync::<Arena>();
};
pub struct ArtMap<K, V> {
tree: Tree<K, V>,
}
impl<K, V> Default for ArtMap<K, V> {
#[inline]
fn default() -> Self {
Self::new()
}
}
impl<K, V> ArtMap<K, V> {
sync::const_fn_unless_loom! {
#[inline]
pub fn new() -> Self {
Self { tree: Tree::new() }
}
}
#[inline]
pub fn with_capacity(_capacity: usize) -> Self {
Self::new()
}
#[inline]
pub fn len(&self) -> usize {
self.tree.len()
}
#[inline]
pub fn is_empty(&self) -> bool {
self.len() == 0
}
}
impl<K: AsBytes + Send + 'static, V: Send + 'static> ArtMap<K, V> {
#[inline]
pub fn pin(&self) -> Guard<'_> {
Guard::new()
}
#[inline]
pub fn get<Q>(&self, key: &Q) -> Option<EntryRef<'_, K, V>>
where
K: Borrow<Q>,
Q: AsBytes + ?Sized,
{
self.get_by_slice(key.as_bytes())
}
#[inline]
pub fn get_by_slice(&self, key: &[u8]) -> Option<EntryRef<'_, K, V>> {
let guard = GuardHandle::owned();
let leaf = self.tree.raw.get(key)?;
Some(EntryRef::new(leaf, &self.tree, guard))
}
#[inline]
pub fn get_with_guard<'a, Q>(
&'a self,
key: &Q,
guard: &'a Guard<'_>,
) -> Option<EntryRef<'a, K, V>>
where
K: Borrow<Q>,
Q: AsBytes + ?Sized,
{
let leaf = self.tree.raw.get(key.as_bytes())?;
Some(EntryRef::new(
leaf,
&self.tree,
GuardHandle::Borrowed(&guard.inner),
))
}
#[inline]
pub fn get_value<Q>(&self, key: &Q) -> Option<V>
where
K: Borrow<Q>,
Q: AsBytes + ?Sized,
V: Clone,
{
self.with_value(key, V::clone)
}
#[inline]
pub fn with_value<Q, R, F>(&self, key: &Q, f: F) -> Option<R>
where
K: Borrow<Q>,
Q: AsBytes + ?Sized,
F: FnOnce(&V) -> R,
{
let _g = pin();
let leaf = self.tree.raw.get(key.as_bytes())?;
Some(f(&unsafe { leaf.as_ref() }.value))
}
#[inline]
pub fn contains_key<Q>(&self, key: &Q) -> bool
where
K: Borrow<Q>,
Q: AsBytes + ?Sized,
{
self.contains_key_slice(key.as_bytes())
}
#[inline]
pub fn contains_key_slice(&self, key: &[u8]) -> bool {
let _g = pin();
self.tree.raw.get(key).is_some()
}
#[inline]
pub fn insert(&self, key: K, value: V) -> Option<EntryRef<'_, K, V>> {
let guard = GuardHandle::owned();
self.insert_in(key, value, guard)
}
#[inline]
pub fn insert_with_guard<'a>(
&'a self,
key: K,
value: V,
guard: &'a Guard<'_>,
) -> Option<EntryRef<'a, K, V>> {
self.insert_in(key, value, GuardHandle::Borrowed(&guard.inner))
}
#[inline]
pub fn insert_cloned(&self, key: K, value: V) -> Option<V>
where
V: Clone,
{
self.insert(key, value).map(|old| old.value().clone())
}
#[inline]
fn insert_in<'a>(
&'a self,
key: K,
value: V,
guard: GuardHandle<'a>,
) -> Option<EntryRef<'a, K, V>> {
match self.tree.insert(key, value, Mode::Replace, guard.guard()) {
Outcome::Inserted(_) => None,
Outcome::Replaced(old) => Some(EntryRef::new(old, &self.tree, guard)),
Outcome::Existing(_) => unreachable!("Mode::Replace always publishes"),
}
}
pub fn get_or_insert_with<F>(&self, key: K, f: F) -> EntryRef<'_, K, V>
where
F: FnOnce() -> V,
{
let guard = GuardHandle::owned();
if let Some(leaf) = self.tree.raw.get(key.as_bytes()) {
return EntryRef::new(leaf, &self.tree, guard);
}
let value = f();
match self
.tree
.insert(key, value, Mode::InsertIfAbsent, guard.guard())
{
Outcome::Inserted(leaf) => EntryRef::new(leaf, &self.tree, guard),
Outcome::Existing(existing) => EntryRef::new(existing, &self.tree, guard),
Outcome::Replaced(_) => unreachable!("InsertIfAbsent never replaces"),
}
}
pub(crate) fn insert_if_absent(&self, key: K, value: V) -> bool {
let guard = pin();
if self.tree.raw.get(key.as_bytes()).is_some() {
return false;
}
match self.tree.insert(key, value, Mode::InsertIfAbsent, &guard) {
Outcome::Inserted(_) => true,
Outcome::Existing(_) => false,
Outcome::Replaced(_) => unreachable!("InsertIfAbsent never replaces"),
}
}
#[inline]
pub fn remove<Q>(&self, key: &Q) -> Option<EntryRef<'_, K, V>>
where
K: Borrow<Q>,
Q: AsBytes + ?Sized,
{
self.remove_by_slice(key.as_bytes())
}
#[inline]
pub fn remove_by_slice(&self, key: &[u8]) -> Option<EntryRef<'_, K, V>> {
let guard = GuardHandle::owned();
let leaf = self.tree.remove(key, guard.guard())?;
Some(EntryRef::new(leaf, &self.tree, guard))
}
pub fn range<R, Q>(&self, range: R) -> Range<'_, K, V>
where
R: RangeBounds<Q>,
Q: AsBytes + ?Sized,
{
Range::owned(
&self.tree,
owned_bound(range.start_bound()),
owned_bound(range.end_bound()),
)
}
pub fn range_with_guard<'a, R, Q>(&'a self, range: R, guard: &'a Guard<'_>) -> Range<'a, K, V>
where
R: RangeBounds<Q>,
Q: AsBytes + ?Sized,
{
Range::borrowed(
&self.tree,
&guard.inner,
owned_bound(range.start_bound()),
owned_bound(range.end_bound()),
)
}
pub fn scan<R, Q, F>(&self, range: R, mut callback: F)
where
R: RangeBounds<Q>,
Q: AsBytes + ?Sized,
F: FnMut(&K, &V) -> bool,
{
let guard = self.pin();
for e in self.range_with_guard(range, &guard) {
if !callback(e.key(), e.value()) {
break;
}
}
}
pub fn iter(&self) -> Iter<'_, K, V> {
Range::owned(&self.tree, Bound::Unbounded, Bound::Unbounded)
}
pub fn iter_with_guard<'a>(&'a self, guard: &'a Guard<'_>) -> Iter<'a, K, V> {
Range::borrowed(&self.tree, &guard.inner, Bound::Unbounded, Bound::Unbounded)
}
pub fn keys(&self) -> Keys<'_, K, V> {
Keys(self.iter())
}
pub fn values(&self) -> Values<'_, K, V> {
Values(self.iter())
}
pub fn keys_with_guard<'a>(&'a self, guard: &'a Guard<'_>) -> GuardKeys<'a, K, V> {
GuardKeys(self.iter_with_guard(guard))
}
pub fn values_with_guard<'a>(&'a self, guard: &'a Guard<'_>) -> GuardValues<'a, K, V> {
GuardValues(self.iter_with_guard(guard))
}
pub fn clear(&self) {
let g = pin();
self.tree.raw.clear(&g);
}
pub fn shrink_to_fit(&self) {
let g = pin();
self.tree.raw.shrink_to_fit(&g);
}
pub fn validate_invariants(&mut self) {
self.tree.raw.validate();
}
}
impl<'a, K: AsBytes + Send + 'static, V: Send + 'static> IntoIterator for &'a ArtMap<K, V> {
type Item = EntryRef<'a, K, V>;
type IntoIter = Iter<'a, K, V>;
#[inline]
fn into_iter(self) -> Self::IntoIter {
self.iter()
}
}
#[cfg(all(test, not(loom)))]
mod tests {
use super::*;
#[test]
fn basic_flow() {
let mut map = ArtMap::<String, i32>::new();
assert!(map.is_empty());
assert!(map.insert("users:100".into(), 1).is_none());
assert!(map.insert("users:200".into(), 2).is_none());
assert!(map.insert("users:300".into(), 3).is_none());
assert_eq!(map.len(), 3);
assert_eq!(map.get("users:100").as_deref(), Some(&1));
assert_eq!(map.get_by_slice(b"users:200").as_deref(), Some(&2));
assert!(map.contains_key("users:300"));
assert!(!map.contains_key("users:400"));
assert_eq!(map.with_value("users:100", |v| *v * 2), Some(2));
let old = map.insert("users:100".into(), 10).expect("replaced");
assert_eq!(*old, 1);
assert!(old.is_removed());
drop(old);
assert_eq!(map.get("users:100").as_deref(), Some(&10));
assert_eq!(map.remove("users:200").as_deref(), Some(&2));
assert!(map.get("users:200").is_none());
assert_eq!(map.len(), 2);
map.validate_invariants();
}
#[test]
fn range_scan() {
let map = ArtMap::<String, i32>::new();
for i in 1..=5 {
map.insert(format!("k:{i}"), i);
}
let items: Vec<_> = map.range("k:2".."k:5").map(|e| *e.value()).collect();
assert_eq!(items, vec![2, 3, 4]);
let rev: Vec<_> = map.range("k:2".."k:5").rev().map(|e| *e.value()).collect();
assert_eq!(rev, vec![4, 3, 2]);
}
#[test]
fn get_or_insert_with() {
let map = ArtMap::<String, i32>::new();
{
let e = map.get_or_insert_with("key".into(), || 42);
assert_eq!(*e, 42);
assert_eq!(e.key(), "key");
assert!(!e.is_removed());
assert!(e.remove());
assert!(e.is_removed());
assert!(!e.remove());
}
assert!(map.get("key").is_none());
let e = map.get_or_insert_with("k2".into(), || 1);
let e2 = map.get_or_insert_with("k2".into(), || panic!("must not run"));
assert_eq!(*e, 1);
assert_eq!(*e2, 1);
}
#[test]
fn clear_is_exact() {
let mut map = ArtMap::<[u8; 8], u64>::new();
for i in 0..1000u64 {
map.insert(i.to_be_bytes(), i);
}
map.clear();
assert_eq!(map.len(), 0);
assert!(map.iter().next().is_none());
map.insert(1u64.to_be_bytes(), 1);
assert_eq!(map.len(), 1);
map.validate_invariants();
}
}