#![deny(unsafe_op_in_unsafe_fn, clippy::undocumented_unsafe_blocks)]
use std::borrow::Borrow;
use std::marker::PhantomData;
use std::mem::{align_of, size_of};
use std::ops::{Bound, RangeBounds};
use std::sync::Arc;
use crate::arena::map::pad;
use crate::arena::node::{VersionNode, VersionedLeaf};
use crate::arena::tree::InserterCache;
use crate::arena::versioned_iter::{ArenaVersionedEntryRef, ArenaVersionedRange};
use crate::arena::versioned_tree::{chain, find_le, ArenaVersionedTree};
use crate::arena::{Arena, ArenaFull};
use crate::key::AsBytes;
use crate::raw::cursor::{owned_bound, KeyBuf};
use crate::raw::node::{Node16, Node256, Node4, Node48, MAX_PREFIX_LEN};
use crate::sync::atomic::AtomicU32;
pub struct ArenaVersionedArtMap<K, V> {
tree: ArenaVersionedTree<K, V>,
}
impl<K, V> ArenaVersionedArtMap<K, V> {
#[inline]
pub fn new(arena: Arc<Arena>) -> Self {
Self {
tree: ArenaVersionedTree::new(arena),
}
}
#[inline]
pub fn with_capacity(capacity: usize) -> Self {
Self::new(Arena::with_capacity(capacity))
}
#[inline]
pub fn arena(&self) -> &Arc<Arena> {
self.tree.arena()
}
#[inline]
pub fn len(&self) -> usize {
self.tree.len()
}
#[inline]
pub fn is_empty(&self) -> bool {
self.len() == 0
}
pub const fn max_insert_bytes(key_len: usize) -> usize {
let version = pad(size_of::<VersionNode<V>>(), align_of::<VersionNode<V>>());
let leaf = pad(
size_of::<VersionedLeaf<K, V>>(),
align_of::<VersionedLeaf<K, V>>(),
);
let node4s = key_len / (MAX_PREFIX_LEN + 1) + 2;
version
+ leaf
+ node4s * pad(size_of::<Node4<AtomicU32>>(), 8)
+ pad(size_of::<Node16<AtomicU32>>(), 8)
+ pad(size_of::<Node48<AtomicU32>>(), 8)
+ pad(size_of::<Node256<AtomicU32>>(), 8)
}
}
impl<K: AsBytes, V> ArenaVersionedArtMap<K, V> {
#[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_slice(&self, key: &[u8]) -> Option<V>
where
V: Clone,
{
let e = self.entry_for(key)?;
Some(e.value().clone())
}
#[inline]
pub fn get_by_slice(&self, key: &[u8]) -> Option<V>
where
V: Clone,
{
self.get_slice(key)
}
#[inline]
pub fn get_latest<Q>(&self, key: &Q) -> Option<(u64, V)>
where
K: Borrow<Q>,
Q: AsBytes + ?Sized,
V: Clone,
{
let e = self.entry_for(key.as_bytes())?;
Some((e.version(), e.value().clone()))
}
#[inline]
pub fn get_entry<Q>(&self, key: &Q) -> Option<ArenaVersionedEntryRef<'_, K, V>>
where
K: Borrow<Q>,
Q: AsBytes + ?Sized,
{
self.entry_for(key.as_bytes())
}
fn entry_for(&self, key: &[u8]) -> Option<ArenaVersionedEntryRef<'_, K, V>> {
let leaf = self.tree.raw.get(key)?;
unsafe { ArenaVersionedEntryRef::new(leaf, leaf.as_ref().head(), self.tree.arena()) }
}
#[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 leaf = self.tree.raw.get(key.as_bytes())?;
let head = unsafe { leaf.as_ref() }.head();
let n = find_le::<V>(self.tree.arena(), head, max_version)?;
n.value().cloned().map(|v| (n.version, v))
}
pub fn get_all_versions<Q>(&self, key: &Q) -> Vec<(u64, Option<V>)>
where
K: Borrow<Q>,
Q: AsBytes + ?Sized,
V: Clone,
{
let Some(leaf) = self.tree.raw.get(key.as_bytes()) else {
return Vec::new();
};
let head = unsafe { leaf.as_ref() }.head();
chain::<V>(self.tree.arena(), head)
.map(|n| (n.version, n.value().cloned()))
.collect()
}
pub fn version_count<Q>(&self, key: &Q) -> usize
where
K: Borrow<Q>,
Q: AsBytes + ?Sized,
{
let Some(leaf) = self.tree.raw.get(key.as_bytes()) else {
return 0;
};
let head = unsafe { leaf.as_ref() }.head();
chain::<V>(self.tree.arena(), head).count()
}
#[inline]
pub fn contains_key<Q>(&self, key: &Q) -> bool
where
K: Borrow<Q>,
Q: AsBytes + ?Sized,
{
self.entry_for(key.as_bytes()).is_some()
}
#[inline]
pub fn insert(&self, key: K, version: u64, value: V) -> bool {
match self.try_insert(key, version, value) {
Ok(()) => true,
Err(full) => panic!("{full}"),
}
}
#[inline]
pub fn insert_versioned(&self, key: K, version: u64, value: V) -> bool {
self.insert(key, version, value)
}
#[inline]
pub fn try_insert(&self, key: K, version: u64, value: V) -> Result<(), ArenaFull<K, V>> {
match self.tree.insert(key, version, Some(value), None) {
Ok(_) => Ok(()),
Err((key, value)) => Err(ArenaFull {
key,
value: value.expect("the value comes back"),
}),
}
}
pub fn delete(&self, key: K, version: u64) -> bool {
match self.tree.insert(key, version, None, None) {
Ok(delta) => delta < 0,
Err(_) => panic!("the arena is full"),
}
}
#[deprecated(note = "use `delete(key, version)`, which does not rewrite history")]
pub fn remove<Q>(&self, key: &Q) -> Option<ArenaVersionedEntryRef<'_, K, V>>
where
K: Borrow<Q>,
Q: AsBytes + ?Sized,
{
let (leaf, old) = self
.tree
.remove_head(key.as_bytes())
.unwrap_or_else(|()| panic!("the arena is full"))?;
unsafe { ArenaVersionedEntryRef::new(leaf, old, self.tree.arena()) }
}
#[inline]
pub fn inserter(&self) -> ArenaVersionedInserter<'_, K, V> {
ArenaVersionedInserter {
tree: &self.tree,
cache: InserterCache::new(),
_not_send: PhantomData,
}
}
pub fn range<R, Q>(&self, range: R) -> ArenaVersionedRange<'_, K, V>
where
R: RangeBounds<Q>,
Q: AsBytes + ?Sized,
{
ArenaVersionedRange::new(
&self.tree,
owned_bound(range.start_bound()),
owned_bound(range.end_bound()),
)
}
pub fn iter(&self) -> ArenaVersionedRange<'_, K, V> {
ArenaVersionedRange::new(&self.tree, Bound::Unbounded, Bound::Unbounded)
}
#[inline]
pub fn find_successor(
&self,
search_key: &[u8],
include_equal: bool,
) -> Option<ArenaVersionedEntryRef<'_, K, V>> {
let start = if include_equal {
Bound::Included(KeyBuf::new(search_key))
} else {
Bound::Excluded(KeyBuf::new(search_key))
};
ArenaVersionedRange::new(&self.tree, start, Bound::Unbounded).next()
}
#[inline]
pub fn find_predecessor(
&self,
search_key: &[u8],
include_equal: bool,
) -> Option<ArenaVersionedEntryRef<'_, K, V>> {
let end = if include_equal {
Bound::Included(KeyBuf::new(search_key))
} else {
Bound::Excluded(KeyBuf::new(search_key))
};
ArenaVersionedRange::new(&self.tree, Bound::Unbounded, end).next_back()
}
#[inline]
pub fn first_entry(&self) -> Option<ArenaVersionedEntryRef<'_, K, V>> {
self.iter().next()
}
#[inline]
pub fn last_entry(&self) -> Option<ArenaVersionedEntryRef<'_, K, V>> {
self.iter().next_back()
}
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,
{
for e in self.range(range) {
if !callback(e.key(), e.value(), e.version()) {
break;
}
}
}
pub fn validate_invariants(&mut self) {
self.tree.raw.validate();
}
}
impl<'a, K: AsBytes, V> IntoIterator for &'a ArenaVersionedArtMap<K, V> {
type Item = ArenaVersionedEntryRef<'a, K, V>;
type IntoIter = ArenaVersionedRange<'a, K, V>;
#[inline]
fn into_iter(self) -> Self::IntoIter {
self.iter()
}
}
pub struct ArenaVersionedInserter<'m, K, V> {
tree: &'m ArenaVersionedTree<K, V>,
cache: InserterCache,
_not_send: PhantomData<*const ()>,
}
impl<K: AsBytes, V> ArenaVersionedInserter<'_, K, V> {
#[inline]
pub fn insert(&mut self, key: K, version: u64, value: V) -> bool {
match self.try_insert(key, version, value) {
Ok(()) => true,
Err(full) => panic!("{full}"),
}
}
#[inline]
pub fn try_insert(&mut self, key: K, version: u64, value: V) -> Result<(), ArenaFull<K, V>> {
match self
.tree
.insert(key, version, Some(value), Some(&mut self.cache))
{
Ok(_) => Ok(()),
Err((key, value)) => Err(ArenaFull {
key,
value: value.expect("the value comes back"),
}),
}
}
}