#![deny(unsafe_op_in_unsafe_fn, clippy::undocumented_unsafe_blocks)]
use std::ptr::NonNull;
use crate::key::AsBytes;
use crate::node::Leaf;
use crate::raw::heap::HeapStorage;
use crate::raw::{Mode, Outcome, RawTree, Unpublished};
pub(crate) type Storage<K, V> = HeapStorage<Leaf<K, V>>;
pub(crate) struct Tree<K, V> {
pub(crate) raw: RawTree<Storage<K, V>>,
}
impl<K, V> Tree<K, V> {
crate::sync::const_fn_unless_loom! {
pub(crate) fn new() -> Self {
Self {
raw: RawTree::new_in(HeapStorage::new()),
}
}
}
#[inline]
pub(crate) fn len(&self) -> usize {
self.raw.len()
}
}
impl<K, V> Drop for Tree<K, V> {
fn drop(&mut self) {
unsafe { self.raw.destroy() }
}
}
impl<K: AsBytes + Send + 'static, V: Send + 'static> Tree<K, V> {
pub(crate) fn insert(
&self,
key: K,
value: V,
mode: Mode,
guard: &crossbeam_epoch::Guard,
) -> Outcome<Leaf<K, V>> {
let leaf = crate::raw::boxed(Leaf::new(key, value));
let owner = unsafe { Unpublished::new(&self.raw.storage, leaf) };
let key_bytes = unsafe { leaf.as_ref() }.key.as_bytes();
match self.raw.insert(&owner, key_bytes, mode, 1, guard) {
Ok(o) => o,
Err(never) => match never {},
}
}
#[inline]
pub(crate) fn remove(
&self,
key: &[u8],
guard: &crossbeam_epoch::Guard,
) -> Option<NonNull<Leaf<K, V>>> {
self.raw.remove(
key,
|l| unsafe { l.as_ref() }.key.as_bytes() == key,
guard,
)
}
pub(crate) fn remove_leaf(
&self,
leaf: NonNull<Leaf<K, V>>,
guard: &crossbeam_epoch::Guard,
) -> bool {
let l = unsafe { leaf.as_ref() };
if l.is_removed() {
return false;
}
let key = l.key.as_bytes();
self.raw.remove(key, |c| c == leaf, guard).is_some()
}
}
#[cfg(all(test, not(loom)))]
mod tests {
use super::*;
use crate::raw::LeafNode;
fn get<'g>(t: &Tree<String, i32>, k: &str, _g: &'g crossbeam_epoch::Guard) -> Option<&'g i32> {
t.raw
.get(k.as_bytes())
.map(|l| unsafe { &(*l.as_ptr()).value })
}
#[test]
fn basic_crud() {
let mut t = Tree::<String, i32>::new();
let g = &crate::guard::pin();
for (k, v) in [("apple", 1), ("banana", 2), ("cherry", 3)] {
assert!(matches!(
t.insert(k.into(), v, Mode::Replace, g),
Outcome::Inserted(_)
));
}
assert_eq!(t.len(), 3);
assert_eq!(get(&t, "apple", g), Some(&1));
assert_eq!(get(&t, "durian", g), None);
let Outcome::Replaced(old) = t.insert("apple".into(), 400, Mode::Replace, g) else {
panic!("expected a replace")
};
let old = unsafe { old.as_ref() };
assert_eq!(old.value, 1);
assert!(old.is_removed());
assert_eq!(get(&t, "apple", g), Some(&400));
let removed = t.remove(b"banana", g).expect("present");
assert_eq!(unsafe { removed.as_ref() }.key_bytes(), b"banana");
assert_eq!(get(&t, "banana", g), None);
assert_eq!(t.len(), 2);
t.raw.validate();
}
#[test]
fn growth_and_prefixes() {
let mut t = Tree::<String, usize>::new();
let g = &crate::guard::pin();
for i in 0..300 {
t.insert(format!("prefix:{i:03}"), i, Mode::Replace, g);
}
for i in 0..300 {
let k = format!("prefix:{i:03}");
let v = t.raw.get(k.as_bytes()).map(|l| unsafe { l.as_ref() }.value);
assert_eq!(v, Some(i));
}
assert_eq!(t.len(), 300);
t.raw.validate();
}
#[test]
fn transient_len_never_negative() {
use std::sync::atomic::{AtomicBool, Ordering};
use std::sync::Arc;
let t = Arc::new(Tree::<Vec<u8>, u64>::new());
let stop = Arc::new(AtomicBool::new(false));
let writer = {
let (t, stop) = (Arc::clone(&t), Arc::clone(&stop));
std::thread::spawn(move || {
let mut i = 0u64;
while !stop.load(Ordering::Relaxed) && i < if cfg!(miri) { 20 } else { 200_000 } {
let g = crate::guard::pin();
t.insert(vec![7], i, Mode::Replace, &g);
t.remove(&[7], &g);
i += 1;
}
})
};
let polls = if cfg!(miri) { 50 } else { 200_000 };
for _ in 0..polls {
assert!(t.raw.raw_len() >= 0, "len went negative");
assert!(t.raw.raw_len() <= 1);
}
stop.store(true, Ordering::Relaxed);
writer.join().unwrap();
assert_eq!(t.raw.raw_len(), 0);
}
#[test]
fn transient_len_keeps_permanent_keys() {
use std::sync::atomic::{AtomicBool, Ordering};
use std::sync::Arc;
let t = Arc::new(Tree::<Vec<u8>, u64>::new());
{
let g = crate::guard::pin();
t.insert(vec![0, 1], 1, Mode::Replace, &g);
t.insert(vec![0, 3], 3, Mode::Replace, &g);
}
let stop = Arc::new(AtomicBool::new(false));
let writer = {
let (t, stop) = (Arc::clone(&t), Arc::clone(&stop));
std::thread::spawn(move || {
let mut i = 0u64;
while !stop.load(Ordering::Relaxed) && i < if cfg!(miri) { 20 } else { 200_000 } {
let g = crate::guard::pin();
t.insert(vec![0, 2], i, Mode::Replace, &g);
t.remove(&[0, 2], &g);
i += 1;
}
})
};
for _ in 0..if cfg!(miri) { 50 } else { 200_000 } {
let n = t.raw.raw_len();
assert!((2..=3).contains(&n), "len {n} outside [2, 3]");
}
stop.store(true, Ordering::Relaxed);
writer.join().unwrap();
}
#[test]
fn each_grown_node_is_retired_exactly_once() {
use crate::raw::heap::RETIRED_NODES;
let t = Tree::<Vec<u8>, u64>::new();
let g = &crate::guard::pin();
t.insert(vec![0, 0], 0, Mode::Replace, g);
t.insert(vec![0, 1], 1, Mode::Replace, g);
let before = RETIRED_NODES.with(|c| c.get());
for b in 2..=255u8 {
t.insert(vec![0, b], b as u64, Mode::Replace, g);
}
assert_eq!(RETIRED_NODES.with(|c| c.get()) - before, 3);
}
#[test]
fn long_shared_prefixes_build_chains() {
let mut t = Tree::<Vec<u8>, usize>::new();
let g = &crate::guard::pin();
let mk = |i: usize| {
let mut k = vec![7u8; 100];
k.extend_from_slice(&i.to_be_bytes());
k
};
for i in 0..50 {
t.insert(mk(i), i, Mode::Replace, g);
}
t.insert(vec![7u8; 100], 1000, Mode::Replace, g);
t.insert(vec![7u8; 40], 1001, Mode::Replace, g);
t.insert(vec![], 1002, Mode::Replace, g);
for i in 0..50 {
assert!(t.raw.get(&mk(i)).is_some());
}
assert!(t.raw.get(&[7u8; 100]).is_some());
assert!(t.raw.get(&[7u8; 40]).is_some());
assert!(t.raw.get(&[]).is_some());
assert!(t.raw.get(&[7u8; 41]).is_none());
assert_eq!(t.len(), 53);
t.raw.validate();
}
}