pub mod entry;
pub mod iter;
pub mod key;
pub mod latch;
pub mod node;
pub mod simd;
pub mod tree;
use crossbeam_epoch::Guard;
use std::borrow::Borrow;
use std::ops::{Bound, RangeBounds};
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<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 get_by_slice(&self, key: &[u8]) -> Option<V>
where
V: Clone,
{
let guard = &crossbeam_epoch::pin();
self.tree.get(key, 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 guard_ref: &'static Guard = unsafe { std::mem::transmute(&guard) };
let (key_ptr, val_ptr) = self.tree.get_or_insert_with(key, f, guard_ref);
EntryRef {
key_ptr,
val_ptr,
tree: &self.tree,
guard: guard_ref,
is_removed: false,
}
}
#[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<'a, R, Q>(&'a self, range: R) -> Range<'a, 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,
};
let guard = crossbeam_epoch::pin();
let guard_ref: &'a Guard = unsafe { std::mem::transmute(&guard) };
Range::new(&self.tree, guard_ref, start, end)
}
pub fn iter(&self) -> Iter<'_, K, V> {
let guard = crossbeam_epoch::pin();
let guard_ref = unsafe {
std::mem::transmute::<&crossbeam_epoch::Guard, &crossbeam_epoch::Guard>(&guard)
};
Iter::new(&self.tree, guard_ref)
}
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 = (&'a K, &'a 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"), Some(1));
assert_eq!(map.get_by_slice(b"users:200"), 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"), Some(10));
assert_eq!(map.remove("users:200"), Some(2));
assert_eq!(map.get("users:200"), 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(|(k, v)| (k.as_str(), *v))
.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(|(k, v)| (k.as_str(), *v))
.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 mut 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_eq!(map.get("key"), None);
}
}