#![deny(unsafe_op_in_unsafe_fn, clippy::undocumented_unsafe_blocks)]
use std::ptr::NonNull;
use std::sync::Arc;
use crate::arena::node::Leaf;
use crate::arena::storage::{ArenaLeaf, ArenaStorage};
use crate::arena::{Arena, ArenaFull};
use crate::key::AsBytes;
use crate::raw::slot::TaggedOffset;
use crate::raw::write::Hint;
use crate::raw::{Mode, Outcome, RawTree, Unpublished};
pub(crate) type Storage<K, V> = ArenaStorage<Leaf<K, V>>;
pub(crate) type InsertResult<K, V> = Result<Option<NonNull<Leaf<K, V>>>, ArenaFull<K, V>>;
#[derive(Clone)]
pub(crate) struct InserterCache {
hint: Option<Hint<TaggedOffset>>,
path: [u8; 32],
}
impl InserterCache {
pub(crate) const fn new() -> Self {
Self {
hint: None,
path: [0; 32],
}
}
#[inline]
fn matching(&self, key: &[u8]) -> Option<Hint<TaggedOffset>> {
let h = self.hint?;
(h.depth <= self.path.len()
&& key.len() > h.depth
&& key[..h.depth] == self.path[..h.depth])
.then_some(h)
}
#[inline]
pub(crate) fn remember(&mut self, hint: Option<Hint<TaggedOffset>>, key: &[u8]) {
match hint {
Some(h) if h.depth <= self.path.len() && key.len() >= h.depth => {
self.path[..h.depth].copy_from_slice(&key[..h.depth]);
self.hint = Some(h);
}
_ => self.hint = None,
}
}
pub(crate) fn try_fast<L: ArenaLeaf + crate::raw::LeafNode>(
&mut self,
raw: &RawTree<ArenaStorage<L>>,
owner: &Unpublished<'_, ArenaStorage<L>>,
key: &[u8],
count: isize,
) -> Option<Outcome<L>> {
let mut h = self.matching(key)?;
let r = unsafe { raw.insert_at_hint(&mut h, owner, key, count) };
#[cfg(test)]
FAST_PATH_HITS.with(|n| n.set(n.get() + usize::from(r.is_some())));
self.hint = Some(h);
r
}
}
#[cfg(test)]
std::thread_local! {
pub(crate) static FAST_PATH_HITS: std::cell::Cell<usize> = const { std::cell::Cell::new(0) };
}
pub(crate) struct ArenaTree<K, V> {
pub(crate) raw: RawTree<Storage<K, V>>,
}
impl<K, V> ArenaTree<K, V> {
pub(crate) fn new(arena: Arc<Arena>) -> Self {
Self {
raw: RawTree::new_in(ArenaStorage::new(arena)),
}
}
#[inline]
pub(crate) fn arena(&self) -> &Arc<Arena> {
&self.raw.storage.arena
}
#[inline]
pub(crate) fn len(&self) -> usize {
self.raw.len()
}
}
impl<K, V> Drop for ArenaTree<K, V> {
fn drop(&mut self) {
if Leaf::<K, V>::NEEDS_DROP {
unsafe { self.raw.destroy() }
}
}
}
impl<K: AsBytes, V> ArenaTree<K, V> {
pub(crate) fn insert(
&self,
key: K,
value: V,
cache: Option<&mut InserterCache>,
) -> InsertResult<K, V> {
let leaf = match self.raw.storage.alloc_value(Leaf::new(key, value)) {
Ok(l) => l,
Err((_, l)) => {
return Err(ArenaFull {
key: l.key,
value: l.value,
})
}
};
let owner = unsafe { Unpublished::new(&self.raw.storage, leaf) };
let key_bytes = unsafe { leaf.as_ref() }.key.as_bytes();
let mut cache = cache;
if let Some(c) = cache.as_deref_mut() {
if c.try_fast(&self.raw, &owner, key_bytes, 1).is_some() {
return Ok(None);
}
}
let mut hint = None;
match self
.raw
.insert_hinted(&owner, key_bytes, Mode::Replace, 1, &(), &mut hint)
{
Ok(Outcome::Inserted(_)) => {
if let Some(c) = cache {
c.remember(hint, key_bytes);
}
Ok(None)
}
Ok(Outcome::Replaced(old)) => Ok(Some(old)),
Ok(Outcome::Existing(_)) => unreachable!("Mode::Replace always publishes"),
Err(_) => {
owner.disarm();
let l = unsafe { leaf.read() };
Err(ArenaFull {
key: l.key,
value: l.value,
})
}
}
}
pub(crate) fn remove(&self, key: &[u8]) -> Option<NonNull<Leaf<K, V>>> {
self.raw.remove(
key,
|l| unsafe { l.as_ref() }.key.as_bytes() == key,
&(),
)
}
}
#[cfg(all(test, not(loom)))]
mod tests {
use super::*;
fn hits() -> usize {
FAST_PATH_HITS.with(|n| n.get())
}
#[test]
fn inserter_fast_path_hits_for_sequential_keys() {
let t = ArenaTree::<Vec<u8>, u64>::new(Arena::with_capacity(8 << 20));
let mut cache = InserterCache::new();
let before = hits();
for i in 0..200u8 {
t.insert(vec![b'k', i], i as u64, Some(&mut cache))
.ok()
.unwrap();
}
let hit = hits() - before;
assert!(
hit >= 190,
"only {hit} of 200 sequential inserts used the fast path"
);
for i in 0..200u8 {
assert!(t.raw.get(&[b'k', i]).is_some());
}
}
#[test]
fn inserter_fast_path_hits_for_interleaved_runs() {
let t = ArenaTree::<Vec<u8>, u64>::new(Arena::with_capacity(8 << 20));
let mut cache = InserterCache::new();
for p in *b"ab" {
for i in 0..=255u8 {
t.insert(vec![p, i, 0], 0, None).ok().unwrap();
}
}
let before = hits();
for run in 0..16u8 {
let p = if run % 2 == 0 { b'a' } else { b'b' };
for i in 0..16u8 {
t.insert(vec![p, run, 1 + i], 1, Some(&mut cache))
.ok()
.unwrap();
}
}
let hit = hits() - before;
assert!(
hit >= 16 * 12,
"only {hit} of 256 run inserts used the fast path"
);
}
#[test]
fn stale_cache_fails_safely() {
let t = ArenaTree::<Vec<u8>, u64>::new(Arena::with_capacity(8 << 20));
let mut cache = InserterCache::new();
t.insert(b"ka".to_vec(), 1, Some(&mut cache)).ok().unwrap();
t.insert(b"kb".to_vec(), 2, Some(&mut cache)).ok().unwrap();
t.insert(b"kc".to_vec(), 3, None).ok().unwrap();
t.insert(b"x".to_vec(), 4, None).ok().unwrap();
t.insert(b"kd".to_vec(), 5, Some(&mut cache)).ok().unwrap();
for k in [&b"ka"[..], b"kb", b"kc", b"kd", b"x"] {
assert!(t.raw.get(k).is_some(), "{k:?} lost");
}
assert_eq!(t.len(), 5);
}
}