#![deny(unsafe_op_in_unsafe_fn, clippy::undocumented_unsafe_blocks)]
use crate::latch::AbortOnUnwind;
use crate::raw::node::{Taken, MAX_PREFIX_LEN};
use crate::raw::slot::{AtomicSlot, Slot};
use crate::raw::{Layout, LeafNode, Raw, RawTree, Storage};
impl<S: Layout> RawTree<S> {
pub(crate) unsafe fn destroy(&mut self) {
let root = self.root();
self.root
.store(Raw::<S>::NULL, crate::sync::atomic::Ordering::Relaxed);
let mut work = vec![root];
while let Some(raw) = work.pop() {
if raw.is_null() {
continue;
}
if raw.is_leaf() {
unsafe { self.storage.free_leaf(self.storage.leaf(raw)) };
continue;
}
let node = unsafe { self.node_ref(raw) };
work.push(node.exact_leaf());
node.for_each_child(|_, c| work.push(c));
unsafe { self.storage.free_node(self.storage.node(raw)) };
}
}
}
impl<S: Storage> RawTree<S> {
pub(crate) fn clear(&self, guard: &S::Guard) {
self.clear_counting(guard, |_| 1);
}
pub(crate) fn clear_counting(
&self,
guard: &S::Guard,
count: impl Fn(std::ptr::NonNull<S::Leaf>) -> isize,
) {
let old = {
let Some(w) = self.root_latch.lock() else {
unreachable!("root latch is never obsolete")
};
let old = self
.root
.swap(Raw::<S>::NULL, crate::sync::atomic::Ordering::AcqRel);
drop(w);
old
};
if old.is_null() {
return;
}
let bomb = AbortOnUnwind;
let mut total = 0isize;
let mut work = vec![old];
while let Some(raw) = work.pop() {
if raw.is_leaf() {
let leaf = unsafe { self.storage.leaf(raw) };
total += count(leaf);
unsafe { leaf.as_ref() }.mark_removed();
unsafe { self.storage.retire_leaf(leaf, guard) };
continue;
}
let node = unsafe { self.node_ref(raw) };
let Some(w) = node.latch.lock() else {
debug_assert!(false, "a detached node cannot be obsolete");
continue;
};
let mut leaves = Vec::new();
let exact = node.exact_leaf();
if !exact.is_null() {
leaves.push(exact);
}
node.for_each_child(|_, c| {
if c.is_leaf() {
leaves.push(c);
} else {
work.push(c);
}
});
for &l in &leaves {
total += count(unsafe { self.storage.leaf(l) });
unsafe { self.leaf_ref(l) }.mark_removed();
}
w.mark_obsolete();
for l in leaves {
unsafe { self.storage.retire_leaf(self.storage.leaf(l), guard) };
}
unsafe { self.storage.retire_node(self.storage.node(raw), guard) };
}
self.len_add(-total);
bomb.defuse();
}
pub(crate) fn validate(&mut self) -> usize {
self.validate_counting(|_| 1)
}
pub(crate) fn validate_counting(
&mut self,
live: impl Fn(std::ptr::NonNull<S::Leaf>) -> usize,
) -> usize {
let mut live_total = 0usize;
let root = self.root();
let mut count = 0usize;
let mut path: Vec<u8> = Vec::new();
let mut work: Vec<(Raw<S>, usize, Option<u8>)> = vec![(root, 0, None)];
while let Some((raw, depth, byte)) = work.pop() {
path.truncate(depth);
if let Some(b) = byte {
path.push(b);
}
if raw.is_null() {
continue;
}
if raw.is_leaf() {
let l = unsafe { self.leaf_ref(raw) };
assert!(!l.is_removed(), "a reachable leaf is marked removed");
let k = l.key_bytes();
assert!(
k.starts_with(&path),
"leaf key {k:?} does not start with its path {path:?}"
);
count += 1;
live_total += live(unsafe { self.storage.leaf(raw) });
continue;
}
let node = unsafe { self.node_ref(raw) };
assert!(!node.latch.is_obsolete(), "a linked node is obsolete");
assert!(
node.latch.read_version().is_some(),
"a node is locked at quiescence"
);
assert!(
node.raw_prefix_len() <= MAX_PREFIX_LEN,
"prefix_len exceeds MAX_PREFIX_LEN"
);
assert!(
!node.emptied_by(Taken::Nothing),
"an inner node is empty (an unlink missed it)"
);
let prefix = node.load_prefix();
path.extend_from_slice(prefix.as_slice());
let exact = node.exact_leaf();
if !exact.is_null() {
assert!(exact.is_leaf(), "exact_leaf holds an inner node");
let l = unsafe { self.leaf_ref(exact) };
assert!(!l.is_removed(), "a reachable leaf is marked removed");
let k = l.key_bytes();
assert_eq!(k, path.as_slice(), "exact leaf key must equal its path");
count += 1;
live_total += live(unsafe { self.storage.leaf(exact) });
}
let n = node.num_children();
let mut seen = 0usize;
let mut last: Option<u8> = None;
let here = path.len();
let mut children = Vec::new();
node.for_each_child(|b, c| {
assert!(last.is_none_or(|l| l < b), "children must be sorted");
last = Some(b);
seen += 1;
children.push((c, here, Some(b)));
});
assert_eq!(seen, n, "num_children must match the live children");
work.extend(children.into_iter().rev());
}
assert_eq!(
live_total,
self.len(),
"len must equal the reachable live count"
);
count
}
}