#![deny(unsafe_op_in_unsafe_fn, clippy::undocumented_unsafe_blocks)]
use std::borrow::Borrow;
use std::ops::{Bound, RangeBounds};
use crate::guard::{pin, Guard, GuardHandle};
use crate::key::AsBytes;
use crate::raw::cursor::{owned_bound, Cursor};
use crate::versioned::entry::VersionedEntryRef;
use crate::versioned::iter::Range;
use crate::versioned::tree::{chain, find_le, VersionedTree};
pub struct VersionedArtMap<K, V> {
tree: VersionedTree<K, V>,
}
impl<K, V> Default for VersionedArtMap<K, V> {
fn default() -> Self {
Self::new()
}
}
impl<K, V> VersionedArtMap<K, V> {
crate::sync::const_fn_unless_loom! {
pub fn new() -> Self {
Self {
tree: VersionedTree::new(),
}
}
}
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> VersionedArtMap<K, V> {
#[inline]
pub fn pin(&self) -> Guard<'_> {
Guard::new()
}
#[inline]
pub fn get<Q>(&self, key: &Q) -> Option<V>
where
K: Borrow<Q>,
Q: AsBytes + ?Sized,
V: Clone,
{
self.get_latest(key).map(|(_, v)| v)
}
#[inline]
pub fn get_by_slice(&self, key: &[u8]) -> Option<V>
where
V: Clone,
{
self.get_slice(key)
}
#[inline]
pub fn get_slice(&self, key: &[u8]) -> Option<V>
where
V: Clone,
{
let _g = pin();
let leaf = self.tree.raw.get(key)?;
let head = unsafe { leaf.as_ref() }.head();
head.value().cloned()
}
#[inline]
pub fn get_latest<Q>(&self, key: &Q) -> Option<(u64, V)>
where
K: Borrow<Q>,
Q: AsBytes + ?Sized,
V: Clone,
{
let _g = pin();
let leaf = self.tree.raw.get(key.as_bytes())?;
let head = unsafe { leaf.as_ref() }.head();
head.value().cloned().map(|v| (head.version, v))
}
pub fn get_entry<Q>(&self, key: &Q) -> Option<VersionedEntryRef<'_, K, V>>
where
K: Borrow<Q>,
Q: AsBytes + ?Sized,
{
let guard = GuardHandle::owned();
let leaf = self.tree.raw.get(key.as_bytes())?;
let head = unsafe { leaf.as_ref() }.head();
VersionedEntryRef::new(leaf, head, &self.tree, guard)
}
#[inline]
pub fn get_version_le<Q>(&self, key: &Q, max_version: u64) -> Option<(u64, V)>
where
K: Borrow<Q>,
Q: AsBytes + ?Sized,
V: Clone,
{
let g = &pin();
self.version_le(key.as_bytes(), max_version, g)
}
#[inline]
pub fn get_version_le_with_guard<Q>(
&self,
key: &Q,
max_version: u64,
guard: &Guard<'_>,
) -> Option<(u64, V)>
where
K: Borrow<Q>,
Q: AsBytes + ?Sized,
V: Clone,
{
self.version_le(key.as_bytes(), max_version, &guard.inner)
}
fn version_le(&self, key: &[u8], max: u64, _g: &crossbeam_epoch::Guard) -> Option<(u64, V)>
where
V: Clone,
{
let leaf = self.tree.raw.get(key)?;
let n = find_le(unsafe { leaf.as_ref() }.head(), max)?;
n.value().cloned().map(|v| (n.version, v))
}
#[inline]
pub fn contains_key<Q>(&self, key: &Q) -> bool
where
K: Borrow<Q>,
Q: AsBytes + ?Sized,
{
let _g = pin();
self.tree
.raw
.get(key.as_bytes())
.is_some_and(|l| !unsafe { l.as_ref() }.head().is_tombstone())
}
#[inline]
pub fn insert(&self, key: K, version: u64, value: V) -> bool {
let g = &pin();
self.tree.insert(key, version, Some(value), g);
true
}
#[inline]
pub fn insert_with_guard(&self, key: K, version: u64, value: V, guard: &Guard<'_>) -> bool {
self.tree.insert(key, version, Some(value), &guard.inner);
true
}
#[inline]
pub fn insert_versioned(&self, key: K, version: u64, value: V) -> bool {
self.insert(key, version, value)
}
pub fn delete(&self, key: K, version: u64) -> bool {
let g = &pin();
self.tree.insert(key, version, None, g) < 0
}
#[deprecated(note = "use `delete(key, version)`, which does not rewrite history")]
pub fn remove<Q>(&self, key: &Q) -> Option<VersionedEntryRef<'_, K, V>>
where
K: Borrow<Q>,
Q: AsBytes + ?Sized,
{
let guard = GuardHandle::owned();
let (leaf, old) = self.tree.remove_head(key.as_bytes(), guard.guard())?;
VersionedEntryRef::new(leaf, unsafe { old.as_ref() }, &self.tree, guard)
}
pub fn remove_key<Q>(&self, key: &Q) -> bool
where
K: Borrow<Q>,
Q: AsBytes + ?Sized,
{
let g = &pin();
self.tree.remove_key(key.as_bytes(), g)
}
pub fn remove_version<Q>(&self, key: &Q, version: u64) -> bool
where
K: Borrow<Q>,
Q: AsBytes + ?Sized,
{
let g = &pin();
self.tree.remove_version(key.as_bytes(), version, g)
}
pub fn clear(&self) {
let g = &pin();
self.tree.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.validate();
}
pub fn version_count<Q>(&self, key: &Q) -> usize
where
K: Borrow<Q>,
Q: AsBytes + ?Sized,
{
let _g = pin();
match self.tree.raw.get(key.as_bytes()) {
Some(l) => chain(unsafe { l.as_ref() }.head()).count(),
None => 0,
}
}
pub fn get_all_versions<Q>(&self, key: &Q) -> Vec<(u64, Option<V>)>
where
K: Borrow<Q>,
Q: AsBytes + ?Sized,
V: Clone,
{
let _g = pin();
match self.tree.raw.get(key.as_bytes()) {
Some(l) => chain(unsafe { l.as_ref() }.head())
.map(|n| (n.version, n.value().cloned()))
.collect(),
None => Vec::new(),
}
}
pub fn prune_key<Q, F>(&self, key: &Q, min_version: u64, is_tombstone: F) -> usize
where
K: Borrow<Q>,
Q: AsBytes + ?Sized,
F: Fn(&V) -> bool,
{
let g = &pin();
match self.tree.raw.get(key.as_bytes()) {
Some(leaf) => self.tree.prune_leaf(leaf, min_version, &is_tombstone, g),
None => 0,
}
}
pub fn prune_all<F>(&self, min_version: u64, is_tombstone: F) -> usize
where
F: Fn(&V) -> bool,
{
let mut g = pin();
let mut cursor = Cursor::new(Bound::Unbounded, Bound::Unbounded);
let mut total = 0;
let mut n = 0usize;
while let Some(leaf) = cursor.next(&self.tree.raw) {
total += self.tree.prune_leaf(leaf, min_version, &is_tombstone, &g);
n += 1;
if n % 1024 == 0 {
cursor.invalidate(&self.tree.raw);
g.repin();
}
}
total
}
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 iter(&self) -> Range<'_, K, V> {
Range::owned(&self.tree, Bound::Unbounded, Bound::Unbounded)
}
pub fn iter_with_guard<'a>(&'a self, guard: &'a Guard<'_>) -> Range<'a, K, V> {
Range::borrowed(&self.tree, &guard.inner, Bound::Unbounded, Bound::Unbounded)
}
pub fn scan<R, Q, F>(&self, range: R, mut callback: F)
where
R: RangeBounds<Q>,
Q: AsBytes + ?Sized,
F: FnMut(&K, &V, u64) -> bool,
{
let guard = self.pin();
for e in self.range_with_guard(range, &guard) {
if !callback(e.key(), e.value(), e.version()) {
break;
}
}
}
}
impl<'a, K: AsBytes + Send + 'static, V: Send + 'static> IntoIterator
for &'a VersionedArtMap<K, V>
{
type Item = VersionedEntryRef<'a, K, V>;
type IntoIter = Range<'a, K, V>;
#[inline]
fn into_iter(self) -> Self::IntoIter {
self.iter()
}
}