#![deny(unsafe_op_in_unsafe_fn, clippy::undocumented_unsafe_blocks)]
use crate::latch::AbortOnUnwind;
use crate::raw::node::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) {
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 count = 0isize;
let mut work = vec![old];
while let Some(raw) = work.pop() {
if raw.is_leaf() {
let leaf = unsafe { self.storage.leaf(raw) };
unsafe { leaf.as_ref() }.mark_removed();
count += 1;
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 {
unsafe { self.leaf_ref(l) }.mark_removed();
}
w.mark_obsolete();
count += leaves.len() as isize;
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(-count);
bomb.defuse();
}
pub(crate) fn validate(&mut self) -> usize {
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 k = unsafe { self.leaf_ref(raw) }.key_bytes();
assert!(
k.starts_with(&path),
"leaf key {k:?} does not start with its path {path:?}"
);
count += 1;
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"
);
let prefix = node.load_prefix();
assert!(prefix.len <= MAX_PREFIX_LEN);
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 k = unsafe { self.leaf_ref(exact) }.key_bytes();
assert_eq!(k, path.as_slice(), "exact leaf key must equal its path");
count += 1;
}
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!(count, self.len(), "len must equal the reachable leaf count");
count
}
}