#![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::iter::{ArenaEntryRef, Range};
use crate::arena::node::Leaf;
use crate::arena::tree::{ArenaTree, InserterCache};
use crate::arena::{Arena, ArenaFull};
use crate::key::AsBytes;
use crate::raw::cursor::owned_bound;
use crate::raw::node::{Node16, Node256, Node4, Node48, MAX_PREFIX_LEN};
use crate::sync::atomic::AtomicU32;
pub struct ArenaArtMap<K, V> {
tree: ArenaTree<K, V>,
}
impl<K, V> ArenaArtMap<K, V> {
#[inline]
pub fn new(arena: Arc<Arena>) -> Self {
Self {
tree: ArenaTree::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 leaf = pad(size_of::<Leaf<K, V>>(), align_of::<Leaf<K, V>>());
let node4s = key_len / (MAX_PREFIX_LEN + 1) + 2;
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)
}
}
pub(crate) const fn pad(size: usize, align: usize) -> usize {
size + align - 1
}
impl<K: AsBytes, V> ArenaArtMap<K, V> {
#[inline]
pub fn get<Q>(&self, key: &Q) -> Option<V>
where
K: Borrow<Q>,
Q: AsBytes + ?Sized,
V: Clone,
{
self.get_entry(key).map(|e| e.value().clone())
}
#[inline]
pub fn get_slice(&self, key: &[u8]) -> Option<V>
where
V: Clone,
{
let leaf = self.tree.raw.get(key)?;
Some(unsafe { ArenaEntryRef::new(leaf) }.value().clone())
}
#[inline]
pub fn get_entry<Q>(&self, key: &Q) -> Option<ArenaEntryRef<'_, K, V>>
where
K: Borrow<Q>,
Q: AsBytes + ?Sized,
{
let leaf = self.tree.raw.get(key.as_bytes())?;
Some(unsafe { ArenaEntryRef::new(leaf) })
}
#[inline]
pub fn contains_key<Q>(&self, key: &Q) -> bool
where
K: Borrow<Q>,
Q: AsBytes + ?Sized,
{
self.tree.raw.get(key.as_bytes()).is_some()
}
#[inline]
pub fn insert(&self, key: K, value: V) -> Option<ArenaEntryRef<'_, K, V>> {
match self.try_insert(key, value) {
Ok(old) => old,
Err(full) => panic!("{full}"),
}
}
#[inline]
pub fn try_insert(
&self,
key: K,
value: V,
) -> Result<Option<ArenaEntryRef<'_, K, V>>, ArenaFull<K, V>> {
let old = self.tree.insert(key, value, None)?;
Ok(old.map(|l| unsafe { ArenaEntryRef::new(l) }))
}
#[inline]
pub fn remove<Q>(&self, key: &Q) -> Option<ArenaEntryRef<'_, K, V>>
where
K: Borrow<Q>,
Q: AsBytes + ?Sized,
{
let leaf = self.tree.remove(key.as_bytes())?;
Some(unsafe { ArenaEntryRef::new(leaf) })
}
#[inline]
pub fn inserter(&self) -> ArenaInserter<'_, K, V> {
ArenaInserter {
tree: &self.tree,
cache: InserterCache::new(),
_not_send: PhantomData,
}
}
pub fn range<R, Q>(&self, range: R) -> Range<'_, K, V>
where
R: RangeBounds<Q>,
Q: AsBytes + ?Sized,
{
Range::new(
&self.tree,
owned_bound(range.start_bound()),
owned_bound(range.end_bound()),
)
}
pub fn iter(&self) -> Range<'_, K, V> {
Range::new(&self.tree, 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) -> bool,
{
for e in self.range(range) {
if !callback(e.key(), e.value()) {
break;
}
}
}
pub fn validate_invariants(&mut self) {
self.tree.raw.validate();
}
}
impl<'a, K: AsBytes, V> IntoIterator for &'a ArenaArtMap<K, V> {
type Item = ArenaEntryRef<'a, K, V>;
type IntoIter = Range<'a, K, V>;
#[inline]
fn into_iter(self) -> Self::IntoIter {
self.iter()
}
}
pub struct ArenaInserter<'m, K, V> {
tree: &'m ArenaTree<K, V>,
cache: InserterCache,
_not_send: PhantomData<*const ()>,
}
impl<'m, K: AsBytes, V> ArenaInserter<'m, K, V> {
#[inline]
pub fn insert(&mut self, key: K, value: V) -> Option<ArenaEntryRef<'m, K, V>> {
match self.try_insert(key, value) {
Ok(old) => old,
Err(full) => panic!("{full}"),
}
}
#[inline]
pub fn try_insert(
&mut self,
key: K,
value: V,
) -> Result<Option<ArenaEntryRef<'m, K, V>>, ArenaFull<K, V>> {
let old = self.tree.insert(key, value, Some(&mut self.cache))?;
Ok(old.map(|l| unsafe { ArenaEntryRef::new(l) }))
}
}