pub mod entry;
pub mod iter;
pub mod key;
pub mod latch;
pub mod node;
pub mod simd;
pub mod tree;
use std::borrow::Borrow;
use std::ops::{Bound, RangeBounds};
use std::sync::atomic::Ordering;
pub use entry::EntryRef;
pub use iter::{Iter, Keys, Range, Values};
pub use key::AsBytes;
pub use tree::Tree;
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> {
#[inline]
pub const fn new() -> Self {
Self { tree: Tree::new() }
}
#[inline]
pub fn len(&self) -> usize {
self.tree.len()
}
#[inline]
pub fn is_empty(&self) -> bool {
self.tree.is_empty()
}
}
impl<K: AsBytes + Send + 'static, V: Send + 'static> ArtMap<K, V> {
#[inline]
pub fn get<Q>(&self, key: &Q) -> Option<EntryRef<'_, K, V>>
where
K: Borrow<Q>,
Q: AsBytes + ?Sized,
{
let guard = &crossbeam_epoch::pin();
let leaf_ptr = self.tree.get_leaf(key.as_bytes(), guard)?;
let leaf = unsafe { &*leaf_ptr };
if leaf.removed.load(Ordering::Acquire) {
return None;
}
Some(EntryRef {
leaf_ptr,
tree: &self.tree,
})
}
#[inline]
pub fn get_by_slice(&self, key: &[u8]) -> Option<EntryRef<'_, K, V>> {
let guard = &crossbeam_epoch::pin();
let leaf_ptr = self.tree.get_leaf(key, guard)?;
let leaf = unsafe { &*leaf_ptr };
if leaf.removed.load(Ordering::Acquire) {
return None;
}
Some(EntryRef {
leaf_ptr,
tree: &self.tree,
})
}
#[inline]
pub fn get_value<Q>(&self, key: &Q) -> Option<V>
where
K: Borrow<Q>,
Q: AsBytes + ?Sized,
V: Clone,
{
let guard = &crossbeam_epoch::pin();
self.tree.get(key.as_bytes(), guard).cloned()
}
#[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 guard = &crossbeam_epoch::pin();
self.tree.get(key.as_bytes(), guard).map(f)
}
#[inline]
pub fn contains_key<Q>(&self, key: &Q) -> bool
where
K: Borrow<Q>,
Q: AsBytes + ?Sized,
{
let guard = &crossbeam_epoch::pin();
self.tree.get(key.as_bytes(), guard).is_some()
}
#[inline]
pub fn contains_key_slice(&self, key: &[u8]) -> bool {
let guard = &crossbeam_epoch::pin();
self.tree.get(key, guard).is_some()
}
#[inline]
pub fn insert(&self, key: K, value: V) -> Option<V> {
let guard = &crossbeam_epoch::pin();
self.tree.insert(key, value, guard)
}
#[inline]
pub fn get_or_insert_with<F>(&self, key: K, f: F) -> EntryRef<'_, K, V>
where
F: FnOnce() -> V,
{
let guard = crossbeam_epoch::pin();
let leaf_ptr = self.tree.get_or_insert_with(key, f, &guard);
EntryRef {
leaf_ptr,
tree: &self.tree,
}
}
#[inline]
pub fn remove<Q>(&self, key: &Q) -> Option<V>
where
K: Borrow<Q>,
Q: AsBytes + ?Sized,
{
let guard = &crossbeam_epoch::pin();
self.tree.remove(key.as_bytes(), guard)
}
#[inline]
pub fn remove_by_slice(&self, key: &[u8]) -> Option<V> {
let guard = &crossbeam_epoch::pin();
self.tree.remove(key, guard)
}
pub fn range<R, Q>(&self, range: R) -> Range<'_, K, V>
where
R: RangeBounds<Q>,
Q: AsBytes + ?Sized,
{
let start = match range.start_bound() {
Bound::Included(b) => Bound::Included(b.as_bytes().to_vec()),
Bound::Excluded(b) => Bound::Excluded(b.as_bytes().to_vec()),
Bound::Unbounded => Bound::Unbounded,
};
let end = match range.end_bound() {
Bound::Included(b) => Bound::Included(b.as_bytes().to_vec()),
Bound::Excluded(b) => Bound::Excluded(b.as_bytes().to_vec()),
Bound::Unbounded => Bound::Unbounded,
};
Range::new(&self.tree, start, end)
}
pub fn iter(&self) -> Iter<'_, K, V> {
Iter::new(&self.tree)
}
pub fn keys(&self) -> Keys<'_, K, V> {
Keys::new(self.iter())
}
pub fn values(&self) -> Values<'_, K, V> {
Values::new(self.iter())
}
#[inline]
pub fn clear(&self) {
self.tree.clear();
}
#[inline]
pub fn validate_invariants(&self) {
self.tree.validate_invariants();
}
}
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(test)]
mod tests {
use super::*;
#[test]
fn test_artmap_basic_flow() {
let map = ArtMap::<String, i32>::new();
assert!(map.is_empty());
assert_eq!(map.insert("users:100".to_string(), 1), None);
assert_eq!(map.insert("users:200".to_string(), 2), None);
assert_eq!(map.insert("users:300".to_string(), 3), 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_slice(b"users:100"));
assert!(!map.contains_key("users:400"));
let doubled = map.with_value("users:100", |v| *v * 2);
assert_eq!(doubled, Some(2));
assert_eq!(map.insert("users:100".to_string(), 10), Some(1));
assert_eq!(map.get("users:100").as_deref(), Some(&10));
assert_eq!(map.remove("users:200"), Some(2));
assert!(map.get("users:200").is_none());
assert_eq!(map.len(), 2);
map.validate_invariants();
}
#[test]
fn test_artmap_range_scan() {
let map = ArtMap::<String, i32>::new();
map.insert("k:1".to_string(), 1);
map.insert("k:2".to_string(), 2);
map.insert("k:3".to_string(), 3);
map.insert("k:4".to_string(), 4);
map.insert("k:5".to_string(), 5);
let items: Vec<_> = map
.range("k:2".."k:5")
.map(|e| (e.key().as_str(), *e.value()))
.collect();
assert_eq!(items, vec![("k:2", 2), ("k:3", 3), ("k:4", 4)]);
let rev_items: Vec<_> = map
.range("k:2".."k:5")
.rev()
.map(|e| (e.key().as_str(), *e.value()))
.collect();
assert_eq!(rev_items, vec![("k:4", 4), ("k:3", 3), ("k:2", 2)]);
}
#[test]
fn test_artmap_get_or_insert_with() {
let map = ArtMap::<String, i32>::new();
{
let entry = map.get_or_insert_with("key".to_string(), || 42);
assert_eq!(*entry, 42);
assert_eq!(entry.key(), "key");
assert_eq!(entry.value(), &42);
assert!(!entry.is_removed());
assert!(entry.remove());
assert!(entry.is_removed());
}
assert!(map.get("key").is_none());
}
}