#![deny(unsafe_op_in_unsafe_fn, clippy::undocumented_unsafe_blocks)]
use std::ptr::NonNull;
use crate::guard::{retire, Retired};
use crate::key::AsBytes;
use crate::latch::AbortOnUnwind;
use crate::raw::heap::HeapStorage;
use crate::raw::{Mode, Outcome, RawTree, Unpublished};
use crate::versioned::node::{VersionNode, VersionedLeaf};
pub(crate) type Storage<K, V> = HeapStorage<VersionedLeaf<K, V>>;
pub(crate) type RemovedHead<K, V> = (NonNull<VersionedLeaf<K, V>>, NonNull<VersionNode<V>>);
pub(crate) struct VersionedTree<K, V> {
pub(crate) raw: RawTree<Storage<K, V>>,
}
impl<K, V> VersionedTree<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 VersionedTree<K, V> {
fn drop(&mut self) {
unsafe { self.raw.destroy() }
}
}
#[inline]
pub(crate) fn find_le<V>(head: &VersionNode<V>, max: u64) -> Option<&VersionNode<V>> {
let mut cur: *const VersionNode<V> = head;
while !cur.is_null() {
let n = unsafe { &*cur };
if n.version <= max {
return Some(n);
}
cur = n.next();
}
None
}
fn find_le_ptr<V>(head: *mut VersionNode<V>, max: u64) -> Option<*mut VersionNode<V>> {
let mut cur = head;
while !cur.is_null() {
let n = unsafe { &*cur };
if n.version <= max {
return Some(cur);
}
cur = n.next();
}
None
}
pub(crate) fn chain<V>(head: &VersionNode<V>) -> impl Iterator<Item = &VersionNode<V>> {
let mut cur: *const VersionNode<V> = head;
std::iter::from_fn(move || {
if cur.is_null() {
return None;
}
let n = unsafe { &*cur };
cur = n.next();
Some(n)
})
}
impl<K: AsBytes + Send + 'static, V: Send + 'static> VersionedTree<K, V> {
pub(crate) fn insert(
&self,
key: K,
version: u64,
value: Option<V>,
guard: &crossbeam_epoch::Guard,
) -> isize {
if let Some(leaf) = self.raw.get(key.as_bytes()) {
drop(key);
return self.apply(leaf, version, value, guard);
}
let count = isize::from(value.is_some());
let leaf = VersionedLeaf::new_boxed(key, version, value);
let owner = unsafe { Unpublished::new(&self.raw.storage, leaf) };
let key_bytes = unsafe { leaf.as_ref() }.key.as_bytes();
let outcome = match self
.raw
.insert(&owner, key_bytes, Mode::InsertIfAbsent, count, guard)
{
Ok(o) => o,
Err(never) => match never {},
};
match outcome {
Outcome::Inserted(_) => count,
Outcome::Existing(existing) => {
let (version, value) = unsafe { VersionedLeaf::take_first(owner.ptr()) };
self.apply(existing, version, value, guard)
}
Outcome::Replaced(_) => unreachable!("InsertIfAbsent never replaces"),
}
}
fn apply(
&self,
leaf: NonNull<VersionedLeaf<K, V>>,
version: u64,
value: Option<V>,
guard: &crossbeam_epoch::Guard,
) -> isize {
let leaf = unsafe { leaf.as_ref() };
let value = value;
let w = leaf.chain_latch.lock();
let head = leaf.head_ptr();
let old_live = !unsafe { &*head }.is_tombstone();
let at = |p: *mut VersionNode<V>| -> Option<&VersionNode<V>> {
unsafe { p.as_ref() }
};
let mut prev: *mut VersionNode<V> = std::ptr::null_mut();
let mut cur = head;
while let Some(n) = at(cur).filter(|n| n.version > version) {
prev = cur;
cur = n.next();
}
let node = leaf.alloc_version(&w, version, value);
let replaced = at(cur).is_some_and(|n| n.version == version);
unsafe {
(*node).init_next(if replaced { (*cur).next() } else { cur });
}
let bomb = AbortOnUnwind;
if prev.is_null() {
leaf.set_head(&w, node);
} else {
unsafe { (*prev).set_next(&w, node) };
}
if replaced {
unsafe { (*cur).mark_superseded(&w) };
}
let new_head = leaf.head_ptr();
let new_live = !unsafe { &*new_head }.is_tombstone();
let delta = isize::from(new_live) - isize::from(old_live);
self.raw.len_add(delta);
bomb.defuse();
drop(w);
if replaced {
unsafe { retire_version(cur, guard) };
}
delta
}
pub(crate) fn remove_head(
&self,
key: &[u8],
guard: &crossbeam_epoch::Guard,
) -> Option<RemovedHead<K, V>> {
let leaf_ptr = self.raw.get(key)?;
let leaf = unsafe { leaf_ptr.as_ref() };
let w = leaf.chain_latch.lock();
let head = leaf.head_ptr();
let h = unsafe { &*head };
if h.is_tombstone() {
return None;
}
let tomb = leaf.alloc_version(&w, h.version, None);
unsafe { (*tomb).init_next(h.next()) };
let bomb = AbortOnUnwind;
leaf.set_head(&w, tomb);
h.mark_superseded(&w);
self.raw.len_add(-1);
bomb.defuse();
drop(w);
unsafe { retire_version(head, guard) };
Some((leaf_ptr, unsafe { NonNull::new_unchecked(head) }))
}
pub(crate) fn prune_leaf<F: Fn(&V) -> bool>(
&self,
leaf: NonNull<VersionedLeaf<K, V>>,
min_version: u64,
is_tombstone: &F,
guard: &crossbeam_epoch::Guard,
) -> usize {
let leaf = unsafe { leaf.as_ref() };
for _attempt in 0..64 {
let head = leaf.head_ptr();
let Some(t_ptr) = find_le_ptr(head, min_version) else {
return 0;
};
let t = unsafe { &*t_ptr };
let is_head = t_ptr == head;
let dead = is_head && t.value().is_none_or(is_tombstone);
let w = leaf.chain_latch.lock();
let head_now = leaf.head_ptr();
let t_now = find_le_ptr(head_now, min_version);
if t_now != Some(t_ptr) || t.is_superseded() {
drop(w);
continue;
}
let dead = dead && head_now == t_ptr;
let bomb = AbortOnUnwind;
let mut unlinked: Vec<*mut VersionNode<V>> = Vec::new();
let kept: &VersionNode<V> = if dead && !t.is_tombstone() {
let b = leaf.alloc_version(&w, t.version, None);
leaf.set_head(&w, b);
t.mark_superseded(&w);
self.raw.len_add(-1);
unlinked.push(t_ptr);
unsafe { &*b }
} else {
t
};
let mut cur = t.next();
if std::ptr::eq(kept, t) {
kept.set_next(&w, std::ptr::null_mut());
}
while !cur.is_null() {
let n = unsafe { &*cur };
n.mark_superseded(&w);
unlinked.push(cur);
cur = n.next();
}
bomb.defuse();
drop(w);
let count = unlinked.len();
for n in unlinked {
unsafe { retire_version(n, guard) };
}
return count;
}
0
}
}
unsafe fn retire_version<V: Send + 'static>(
n: *mut VersionNode<V>,
guard: &crossbeam_epoch::Guard,
) {
if unsafe { (*n).is_inline() } {
return;
}
retire(guard, unsafe {
Retired::from_non_null(NonNull::new_unchecked(n))
});
}
#[cfg(test)]
mod tests {
use super::*;
use std::sync::atomic::{AtomicBool, Ordering};
use std::sync::Arc;
#[test]
fn transient_len_never_negative() {
let t = Arc::new(VersionedTree::<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 n = if cfg!(miri) { 20 } else { 100_000 };
let mut v = 1u64;
while !stop.load(Ordering::Relaxed) && v < n {
let g = crate::guard::pin();
t.insert(vec![7], v, Some(v), &g);
t.insert(vec![7], v + 1, None, &g);
v += 2;
}
})
};
let polls = if cfg!(miri) { 50 } else { 200_000 };
for _ in 0..polls {
let len = t.raw.raw_len();
assert!((0..=1).contains(&len), "raw len {len} out of range");
}
stop.store(true, Ordering::Relaxed);
writer.join().unwrap();
assert_eq!(t.raw.raw_len(), 0);
}
}