#![deny(unsafe_op_in_unsafe_fn, clippy::undocumented_unsafe_blocks)]
use crate::latch::{AbortOnUnwind, SpinBackoff, WriteGuard};
use crate::raw::node::{NodeHeader, NodeType, PrefixSnapshot, Rest, Taken, MAX_PREFIX_LEN};
use crate::raw::slot::Slot;
use crate::raw::write::Parent;
use crate::raw::{Prepared, Raw, RawTree, Storage};
const ATTEMPTS: usize = 8;
fn merged_prefix(
n: &PrefixSnapshot,
byte: u8,
c: &PrefixSnapshot,
) -> Option<([u8; MAX_PREFIX_LEN], usize)> {
let len = n.len + 1 + c.len;
if len > MAX_PREFIX_LEN {
return None;
}
let mut bytes = [0u8; MAX_PREFIX_LEN];
bytes[..n.len].copy_from_slice(n.as_slice());
bytes[n.len] = byte;
bytes[n.len + 1..len].copy_from_slice(c.as_slice());
Some((bytes, len))
}
#[derive(Copy, Clone)]
struct Frame<R> {
parent: Parent<R>,
node: R,
expanded: bool,
}
#[derive(Copy, Clone)]
enum Plan<R> {
Unlink,
Leaf(R),
Merge { byte: u8, child: R, ty: NodeType },
Shrink(NodeType),
}
impl<S: Storage> RawTree<S> {
pub(crate) fn shrink_to_fit(&self, guard: &S::Guard) {
let root = self.root();
if root.is_null() || root.is_leaf() {
return;
}
let mut prep = Prepared::<S>::new();
let mut stack = vec![Frame {
parent: Parent::Root,
node: root,
expanded: false,
}];
while let Some(f) = stack.pop() {
if f.expanded {
if self.fit(f.parent, f.node, &mut prep, guard).is_err() {
break;
}
continue;
}
let node = unsafe { self.node_ref(f.node) };
let Some((v, children)) = inner_children(node) else {
continue;
};
stack.push(Frame {
expanded: true,
..f
});
for (byte, c) in children.into_iter().rev() {
stack.push(Frame {
parent: Parent::Node {
raw: f.node,
version: v,
byte,
},
node: c,
expanded: false,
});
}
}
prep.release(&self.storage);
}
fn fit(
&self,
parent: Parent<Raw<S>>,
n_raw: Raw<S>,
prep: &mut Prepared<S>,
guard: &S::Guard,
) -> Result<(), S::Full> {
let node = unsafe { self.node_ref(n_raw) };
let mut backoff = SpinBackoff::new();
for _ in 0..ATTEMPTS {
prep.reset();
let Some(v) = node.latch.read_version() else {
if node.latch.is_obsolete() {
return Ok(());
}
backoff.spin();
continue;
};
let plan = match node.rest(Taken::Nothing) {
Rest::Empty => Some(Plan::Unlink),
Rest::Leaf(l) => Some(Plan::Leaf(l)),
Rest::Inner(byte, child) => {
let c = unsafe { self.node_ref(child) };
if node.prefix_len() + 1 + c.prefix_len() <= MAX_PREFIX_LEN {
Some(Plan::Merge {
byte,
child,
ty: NodeType::fitting(c.num_children()),
})
} else {
(node.node_type > NodeType::Node4).then_some(Plan::Shrink(NodeType::Node4))
}
}
Rest::Many => {
let ty = NodeType::fitting(node.num_children());
(ty < node.node_type).then_some(Plan::Shrink(ty))
}
};
if !node.latch.validate(v) {
backoff.spin();
continue;
}
let Some(plan) = plan else {
return Ok(());
};
let fresh = match plan {
Plan::Merge { ty, .. } | Plan::Shrink(ty) => Some(prep.node(&self.storage, ty)?),
Plan::Unlink | Plan::Leaf(_) => None,
};
crate::hooks::pause(crate::hooks::Point::WriterBeforeUpgrade);
let Some(pg) = self.lock_parent(parent, n_raw) else {
return Ok(());
};
#[cfg(loom)]
let unlatched = matches!(plan, Plan::Shrink(_))
&& crate::latch::mutants::FIT_WITHOUT_NODE_LATCH.with(|m| m.get());
#[cfg(not(loom))]
let unlatched = false;
let nw = if unlatched {
None
} else {
match node.latch.try_upgrade(v) {
Some(w) => Some(w),
None => {
drop(pg);
backoff.spin();
continue;
}
}
};
let mut cw: Option<WriteGuard<'_>> = None;
let replacement = match plan {
Plan::Unlink => None,
Plan::Leaf(l) => Some(l),
Plan::Shrink(_) => {
let f = fresh.expect("allocated above");
node.copy_into(unsafe { &mut *f.as_ptr() });
Some(self.storage.node_raw(f))
}
Plan::Merge { byte, child, ty } => {
let c = unsafe { self.node_ref(child) };
#[cfg(loom)]
let unlatched_child =
crate::latch::mutants::MERGE_WITHOUT_CHILD_LATCH.with(|m| m.get());
#[cfg(not(loom))]
let unlatched_child = false;
if !unlatched_child {
match c
.latch
.read_version()
.and_then(|cv| c.latch.try_upgrade(cv))
{
Some(w) => cw = Some(w),
None => {
drop(nw);
drop(pg);
backoff.spin();
continue;
}
}
}
let merged = merged_prefix(&node.load_prefix(), byte, &c.load_prefix());
let (Some((bytes, len)), true) = (merged, c.num_children() <= ty.capacity())
else {
drop(cw);
drop(nw);
drop(pg);
backoff.spin();
continue;
};
let f = fresh.expect("allocated above");
let dst = unsafe { &mut *f.as_ptr() };
c.copy_into(dst);
dst.init_prefix(&bytes[..len]);
Some(self.storage.node_raw(f))
}
};
let bomb = AbortOnUnwind;
match replacement {
None => self.unlink_in_parent(&pg),
Some(r) => self.publish_in_parent(&pg, r),
}
if let Some(cw) = cw {
cw.mark_obsolete();
}
if let Some(nw) = nw {
nw.mark_obsolete();
}
bomb.defuse();
drop(pg);
prep.commit();
if let Plan::Merge { child, .. } = plan {
unsafe { self.storage.retire_node(self.node_ptr(child), guard) };
}
unsafe { self.storage.retire_node(self.node_ptr(n_raw), guard) };
return Ok(());
}
Ok(())
}
}
type Children<R> = Vec<(u8, R)>;
fn inner_children<A: crate::raw::slot::AtomicSlot>(
node: &NodeHeader<A>,
) -> Option<(u64, Children<A::Raw>)> {
let mut backoff = SpinBackoff::new();
for _ in 0..ATTEMPTS {
let Some(v) = node.latch.read_version() else {
if node.latch.is_obsolete() {
return None;
}
backoff.spin();
continue;
};
let mut children = Vec::new();
node.for_each_child(|b, c| {
if !c.is_leaf() {
children.push((b, c));
}
});
if node.latch.validate(v) {
return Some((v, children));
}
backoff.spin();
}
None
}
#[cfg(all(test, not(loom)))]
mod tests {
use crate::raw::heap::NODE_COUNTS;
use crate::raw::node::{NodeType, Rest, Taken, MAX_PREFIX_LEN};
use crate::raw::remove::tests::{
chain_len, get, long_key, remove, retired, root_node, tree, Header, T,
};
use crate::raw::slot::Slot;
use crate::raw::Mode;
fn shrink(t: &T) {
t.raw.shrink_to_fit(&crate::guard::pin());
}
fn assert_fitted(t: &T) {
let mut work = vec![t.raw.root()];
while let Some(raw) = work.pop() {
if raw.is_null() || raw.is_leaf() {
continue;
}
let n: &Header = unsafe { t.raw.node_ref(raw) };
match n.rest(Taken::Nothing) {
Rest::Empty | Rest::Leaf(_) => panic!("a node with one leaf or none"),
Rest::Inner(_, c) => {
let c = unsafe { t.raw.node_ref(c) };
assert!(
n.prefix_len() + 1 + c.prefix_len() > MAX_PREFIX_LEN,
"a mergeable single child"
);
assert_eq!(n.node_type, NodeType::Node4);
}
Rest::Many => assert_eq!(n.node_type, NodeType::fitting(n.num_children())),
}
n.for_each_child(|_, c| work.push(c));
}
}
#[test]
fn every_layout_shrinks_to_fit() {
let mut t = T::new();
let g = &crate::guard::pin();
for i in 0..=255u8 {
t.insert(vec![0, i], i as u64, Mode::Replace, g);
}
assert_eq!(root_node(&t).node_type, NodeType::Node256);
let mut left = 256usize;
for (keep, ty) in [
(40, NodeType::Node48),
(10, NodeType::Node16),
(3, NodeType::Node4),
] {
for i in keep..left {
assert!(t.remove(&[0, i as u8], g).is_some());
}
left = keep;
let before = retired();
shrink(&t);
assert_eq!(retired() - before, 1, "the old node is retired");
assert_eq!(root_node(&t).node_type, ty, "{keep} children");
for i in 0..keep {
assert!(get(&t, &[0, i as u8]));
}
assert_eq!(t.raw.validate(), keep);
assert_fitted(&t);
}
let before = retired();
shrink(&t);
assert_eq!(retired(), before);
assert!(t.remove(&[0, 1], g).is_some() && t.remove(&[0, 2], g).is_some());
shrink(&t);
assert!(t.raw.root().is_leaf());
assert!(get(&t, &[0, 0]));
assert_eq!(t.raw.validate(), 1);
}
#[test]
fn a_node_with_one_leaf_gives_way_to_it() {
let mut t = tree(&[b"a1", b"a2", b"b"]);
assert!(remove(&t, b"a2"));
shrink(&t);
assert!(root_node(&t).find_child(b'a').unwrap().is_leaf());
assert!(get(&t, b"a1") && get(&t, b"b"));
let mut t2 = tree(&[b"k", b"ka", b"x"]);
assert!(remove(&t2, b"ka"));
shrink(&t2);
assert!(root_node(&t2).find_child(b'k').unwrap().is_leaf());
assert!(get(&t2, b"k"));
assert_eq!(t.raw.validate() + t2.raw.validate(), 4);
assert_fitted(&t);
assert_fitted(&t2);
}
#[test]
fn a_node_with_one_child_node_merges_into_it() {
let mut t = tree(&[b"ax", b"abc1", b"abc2"]);
assert!(remove(&t, b"ax"));
assert_eq!(root_node(&t).load_prefix().as_slice(), b"a");
let before = retired();
shrink(&t);
assert_eq!(retired() - before, 2, "the root and C are retired");
assert_eq!(root_node(&t).load_prefix().as_slice(), b"abc");
assert!(get(&t, b"abc1") && get(&t, b"abc2") && !get(&t, b"ax"));
assert_fitted(&t);
let g = &crate::guard::pin();
for k in [&b"ab"[..], b"az", b"abc3"] {
t.insert(k.to_vec(), 1, Mode::Replace, g);
}
assert!(get(&t, b"ab") && get(&t, b"az") && get(&t, b"abc3") && get(&t, b"abc1"));
assert_eq!(t.raw.validate(), 5);
}
#[test]
fn single_entries_collapse_in_one_pass() {
let mut t = tree(&[b"xa1", b"xa2", b"xb", b"y"]);
assert!(remove(&t, b"xa2") && remove(&t, b"xb"));
let before = retired();
shrink(&t);
assert_eq!(retired() - before, 2);
assert!(root_node(&t).find_child(b'x').unwrap().is_leaf());
assert!(get(&t, b"xa1") && get(&t, b"y"));
assert_eq!(t.raw.validate(), 2);
assert_fitted(&t);
}
#[test]
fn chain_links_that_cannot_merge_stay() {
let t = tree(&[&long_key(1), &long_key(2), &long_key(3)]);
let chain = chain_len(&t);
let before = retired();
shrink(&t);
assert_eq!(retired(), before, "nothing to fit");
assert_eq!(chain_len(&t), chain);
assert_fitted(&t);
assert!(remove(&t, &long_key(1)) && remove(&t, &long_key(2)));
shrink(&t);
assert!(t.raw.root().is_leaf());
assert_eq!(retired() - before, chain);
}
#[test]
fn an_empty_or_single_leaf_tree_is_left_alone() {
let t = T::new();
shrink(&t);
assert!(t.raw.root().is_null());
let t = tree(&[b"k"]);
shrink(&t);
assert!(t.raw.root().is_leaf());
}
#[test]
fn a_thinned_tree_returns_its_nodes() {
use rand::{Rng, SeedableRng};
let live_nodes =
|| NODE_COUNTS.with(|c| c.allocated.get() - c.freed.get() - c.retired.get());
let mut rng = rand::rngs::StdRng::seed_from_u64(11);
let n = if cfg!(miri) { 400 } else { 50_000 };
let base = live_nodes();
let mut t = T::new();
let g = &crate::guard::pin();
let keys: Vec<Vec<u8>> = (0..n).map(|_| rng.gen::<[u8; 8]>().to_vec()).collect();
for k in &keys {
t.insert(k.clone(), 0, Mode::Replace, g);
}
for k in keys.iter().filter(|_| !rng.gen_ratio(1, 100)) {
t.remove(k, g);
}
let thinned = live_nodes() - base;
shrink(&t);
let fitted = live_nodes() - base;
assert!(
fitted < thinned,
"{fitted} nodes after fitting, {thinned} before"
);
assert_fitted(&t);
let live = t.raw.validate();
assert!(fitted < live, "{fitted} nodes for {live} keys");
}
}