#![deny(unsafe_op_in_unsafe_fn, clippy::undocumented_unsafe_blocks)]
use std::ptr::NonNull;
use crate::latch::{AbortOnUnwind, SpinBackoff, WriteGuard};
use crate::raw::node::{NodeHeader, NodeType, MAX_PREFIX_LEN};
use crate::raw::slot::Slot;
use crate::raw::{
common_prefix, LeafNode, Mode, NodePtr, Outcome, Prepared, Raw, RawTree, Storage, Unpublished,
};
#[derive(Copy, Clone, Debug)]
pub(crate) struct Hint<R> {
pub(crate) node: R,
pub(crate) version: u64,
pub(crate) depth: usize,
}
#[derive(Copy, Clone)]
enum Parent<R> {
Root,
Node { raw: R, version: u64, byte: u8 },
}
enum ParentGuard<'t, A> {
Root(WriteGuard<'t>),
Node(&'t NodeHeader<A>, WriteGuard<'t>, u8),
}
impl<S: Storage> RawTree<S> {
fn lock_parent(
&self,
parent: Parent<Raw<S>>,
child: Raw<S>,
) -> Option<ParentGuard<'_, S::Atomic>> {
match parent {
Parent::Root => {
let w = self.root_latch.lock()?;
(self.root() == child).then_some(ParentGuard::Root(w))
}
Parent::Node { raw, byte, .. } => {
let p = unsafe { self.node_ref(raw) };
let w = p.latch.lock()?;
(p.find_child(byte) == Some(child)).then_some(ParentGuard::Node(p, w, byte))
}
}
}
fn publish_in_parent(&self, pg: &ParentGuard<'_, S::Atomic>, new: Raw<S>) {
match pg {
ParentGuard::Root(w) => self.set_root(w, new),
ParentGuard::Node(p, w, byte) => p.replace_child(w, *byte, new),
}
}
pub(crate) fn insert(
&self,
owner: &Unpublished<'_, S>,
key: &[u8],
mode: Mode,
count: isize,
guard: &S::Guard,
) -> Result<Outcome<S::Leaf>, S::Full> {
self.insert_hinted(owner, key, mode, count, guard, &mut None)
}
pub(crate) fn insert_hinted(
&self,
owner: &Unpublished<'_, S>,
key: &[u8],
mode: Mode,
count: isize,
guard: &S::Guard,
hint: &mut Option<Hint<Raw<S>>>,
) -> Result<Outcome<S::Leaf>, S::Full> {
let mut prep = Prepared::<S>::new();
let r = self.insert_with(owner, key, mode, count, guard, &mut prep, hint);
prep.release(&self.storage);
r
}
pub(crate) unsafe fn insert_at_hint(
&self,
hint: &mut Hint<Raw<S>>,
owner: &Unpublished<'_, S>,
key: &[u8],
count: isize,
) -> Option<Outcome<S::Leaf>> {
let byte = *key.get(hint.depth)?;
let node = unsafe { self.node_ref(hint.node) };
let w = node.latch.try_upgrade(hint.version)?;
if node.find_child(byte).is_some() || node.is_full() {
hint.version = w.unlock();
return None;
}
let new_ptr = owner.ptr();
let bomb = AbortOnUnwind;
self.len_add(count);
owner.disarm();
node.insert_child(&w, byte, self.storage.leaf_raw(new_ptr));
bomb.defuse();
hint.version = w.unlock();
Some(Outcome::Inserted(new_ptr))
}
#[allow(clippy::too_many_arguments)]
fn insert_with(
&self,
owner: &Unpublished<'_, S>,
key: &[u8],
mode: Mode,
count: isize,
guard: &S::Guard,
prep: &mut Prepared<S>,
hint: &mut Option<Hint<Raw<S>>>,
) -> Result<Outcome<S::Leaf>, S::Full> {
let new_ptr = owner.ptr();
let new_leaf = self.storage.leaf_raw(new_ptr);
let mut backoff = SpinBackoff::new();
'retry: loop {
prep.reset();
let root = self.root();
if root.is_null() {
let Some(w) = self.root_latch.lock() else {
unreachable!("root latch is never obsolete")
};
if !self.root().is_null() {
drop(w);
continue 'retry;
}
let bomb = AbortOnUnwind;
self.len_add(count);
owner.disarm();
self.set_root(&w, new_leaf);
bomb.defuse();
drop(w);
return Ok(Outcome::Inserted(new_ptr));
}
if root.is_leaf() {
let existing = unsafe { self.leaf_ref(root) };
let ekey = existing.key_bytes();
if ekey == key {
let old = self.storage_leaf(root);
if mode == Mode::InsertIfAbsent {
return Ok(Outcome::Existing(old));
}
let Some(w) = self.root_latch.lock() else {
unreachable!("root latch is never obsolete")
};
if self.root() != root {
drop(w);
continue 'retry;
}
let bomb = AbortOnUnwind;
owner.disarm();
self.set_root(&w, new_leaf);
existing.mark_removed();
bomb.defuse();
drop(w);
unsafe { self.storage.retire_leaf(old, guard) };
return Ok(Outcome::Replaced(old));
}
let common = common_prefix(ekey, key);
let (chain, _) =
self.build_chain(prep, &key[..common], (ekey, root), (key, new_leaf), common)?;
let Some(w) = self.root_latch.lock() else {
unreachable!("root latch is never obsolete")
};
if self.root() != root {
drop(w);
backoff.spin();
continue 'retry;
}
let bomb = AbortOnUnwind;
self.len_add(count);
owner.disarm();
self.set_root(&w, chain);
bomb.defuse();
drop(w);
prep.commit();
return Ok(Outcome::Inserted(new_ptr));
}
let mut parent = Parent::Root;
let mut node_raw = root;
let mut depth = 0usize;
loop {
let node = unsafe { self.node_ref(node_raw) };
let Some(v) = node.latch.read_version() else {
backoff.spin();
continue 'retry;
};
crate::hooks::pause(crate::hooks::Point::WriterAfterVersion);
if !self.still_parent(parent, node_raw) {
continue 'retry;
}
let prefix = node.load_prefix();
let rest = key.get(depth..).unwrap_or(&[]);
let matched = if prefix.is_prefix_of(rest) {
prefix.len
} else {
common_prefix(prefix.as_slice(), rest)
};
if matched < prefix.len {
if !node.latch.validate(v) {
continue 'retry;
}
let split_raw = {
let split = prep.node(&self.storage, NodeType::Node4)?;
let s = unsafe { &mut *split.as_ptr() };
s.init_prefix(&prefix.as_slice()[..matched]);
s.push_child_unpublished(prefix.bytes[matched], node_raw);
if depth + matched == key.len() {
s.init_exact_leaf(new_leaf);
} else {
s.push_child_unpublished(key[depth + matched], new_leaf);
}
self.storage.node_raw(split)
};
crate::hooks::pause(crate::hooks::Point::WriterBeforeUpgrade);
let Some(pg) = self.lock_parent(parent, node_raw) else {
backoff.spin();
continue 'retry;
};
let Some(nw) = node.latch.try_upgrade(v) else {
drop(pg);
backoff.spin();
continue 'retry;
};
let bomb = AbortOnUnwind;
node.store_prefix(&nw, &prefix.as_slice()[matched + 1..]);
self.len_add(count);
owner.disarm();
self.publish_in_parent(&pg, split_raw);
bomb.defuse();
drop(nw);
drop(pg);
prep.commit();
*hint = Some(Hint {
node: split_raw,
version: 0,
depth: depth + matched,
});
return Ok(Outcome::Inserted(new_ptr));
}
let node_depth = depth + prefix.len;
if node_depth == key.len() {
let exact = node.exact_leaf();
if !node.latch.validate(v) {
continue 'retry;
}
if !exact.is_null() {
let old = self.storage_leaf(exact);
if mode == Mode::InsertIfAbsent {
return Ok(Outcome::Existing(old));
}
let Some(nw) = node.latch.try_upgrade(v) else {
backoff.spin();
continue 'retry;
};
let bomb = AbortOnUnwind;
owner.disarm();
node.set_exact_leaf(&nw, new_leaf);
unsafe { self.leaf_ref(exact) }.mark_removed();
bomb.defuse();
drop(nw);
unsafe { self.storage.retire_leaf(old, guard) };
return Ok(Outcome::Replaced(old));
}
let Some(nw) = node.latch.try_upgrade(v) else {
backoff.spin();
continue 'retry;
};
let bomb = AbortOnUnwind;
self.len_add(count);
owner.disarm();
node.set_exact_leaf(&nw, new_leaf);
bomb.defuse();
drop(nw);
return Ok(Outcome::Inserted(new_ptr));
}
let byte = key[node_depth];
let child = node.find_child(byte);
if let Some(c) = child.filter(|c| !c.is_leaf()) {
parent = Parent::Node {
raw: node_raw,
version: v,
byte,
};
node_raw = c;
depth = node_depth + 1;
continue;
}
let full = node.is_full();
if !node.latch.validate(v) {
continue 'retry;
}
match child {
None if full => {
let grown_ty = node
.node_type
.grown()
.expect("a full node is never a Node256");
let grown = prep.node(&self.storage, grown_ty)?;
let Some(pg) = self.lock_parent(parent, node_raw) else {
backoff.spin();
continue 'retry;
};
let Some(nw) = node.latch.try_upgrade(v) else {
drop(pg);
backoff.spin();
continue 'retry;
};
let g = unsafe { &mut *grown.as_ptr() };
node.copy_into(g);
g.push_child_unpublished(byte, new_leaf);
let grown_raw = self.storage.node_raw(grown);
let bomb = AbortOnUnwind;
self.len_add(count);
owner.disarm();
self.publish_in_parent(&pg, grown_raw);
nw.mark_obsolete();
bomb.defuse();
drop(pg);
prep.commit();
*hint = Some(Hint {
node: grown_raw,
version: 0,
depth: node_depth,
});
let old = self.node_ptr(node_raw);
unsafe { self.storage.retire_node(old, guard) };
return Ok(Outcome::Inserted(new_ptr));
}
None => {
crate::hooks::pause(crate::hooks::Point::WriterBeforeUpgrade);
let Some(nw) = node.latch.try_upgrade(v) else {
backoff.spin();
continue 'retry;
};
let bomb = AbortOnUnwind;
self.len_add(count);
owner.disarm();
node.insert_child(&nw, byte, new_leaf);
bomb.defuse();
*hint = Some(Hint {
node: node_raw,
version: nw.unlock(),
depth: node_depth,
});
return Ok(Outcome::Inserted(new_ptr));
}
Some(c) if c.is_leaf() => {
let existing = unsafe { self.leaf_ref(c) };
let ekey = existing.key_bytes();
if ekey == key {
let old = self.storage_leaf(c);
if mode == Mode::InsertIfAbsent {
return Ok(Outcome::Existing(old));
}
let Some(nw) = node.latch.try_upgrade(v) else {
backoff.spin();
continue 'retry;
};
let bomb = AbortOnUnwind;
owner.disarm();
node.replace_child(&nw, byte, new_leaf);
existing.mark_removed();
bomb.defuse();
drop(nw);
unsafe { self.storage.retire_leaf(old, guard) };
return Ok(Outcome::Replaced(old));
}
let from = node_depth + 1;
let es = ekey.get(from..).unwrap_or(&[]);
let ns = &key[from..];
let common = common_prefix(es, ns);
let (chain, bottom) =
self.build_chain(prep, &ns[..common], (es, c), (ns, new_leaf), common)?;
let Some(nw) = node.latch.try_upgrade(v) else {
backoff.spin();
continue 'retry;
};
let bomb = AbortOnUnwind;
self.len_add(count);
owner.disarm();
node.replace_child(&nw, byte, chain);
bomb.defuse();
drop(nw);
prep.commit();
*hint = Some(Hint {
node: bottom,
version: 0,
depth: from + common,
});
return Ok(Outcome::Inserted(new_ptr));
}
Some(_) => unreachable!("inner children are descended above"),
}
}
}
}
#[inline]
fn still_parent(&self, parent: Parent<Raw<S>>, child: Raw<S>) -> bool {
match parent {
Parent::Root => self.root() == child,
Parent::Node { raw, version, .. } => {
unsafe { self.node_ref(raw) }.latch.validate(version)
}
}
}
#[inline]
fn storage_leaf(&self, raw: Raw<S>) -> NonNull<S::Leaf> {
unsafe { self.storage.leaf(raw) }
}
#[inline]
fn node_ptr(&self, raw: Raw<S>) -> NodePtr<S> {
unsafe { self.storage.node(raw) }
}
fn build_chain(
&self,
prep: &mut Prepared<S>,
prefix: &[u8],
a: (&[u8], Raw<S>),
b: (&[u8], Raw<S>),
common: usize,
) -> Result<(Raw<S>, Raw<S>), S::Full> {
debug_assert_eq!(prefix.len(), common);
let mut segments = Vec::new();
let mut rest = prefix;
while rest.len() > MAX_PREFIX_LEN {
segments.push((&rest[..MAX_PREFIX_LEN], rest[MAX_PREFIX_LEN]));
rest = &rest[MAX_PREFIX_LEN + 1..];
}
let bottom = prep.node(&self.storage, NodeType::Node4)?;
{
let n = unsafe { &mut *bottom.as_ptr() };
n.init_prefix(rest);
for (suffix, leaf) in [a, b] {
match suffix.get(common) {
None => n.init_exact_leaf(leaf),
Some(&byte) => n.push_child_unpublished(byte, leaf),
}
}
}
let bottom = self.storage.node_raw(bottom);
let mut below = bottom;
for (seg_prefix, byte) in segments.into_iter().rev() {
let n = prep.node(&self.storage, NodeType::Node4)?;
let r = unsafe { &mut *n.as_ptr() };
r.init_prefix(seg_prefix);
r.push_child_unpublished(byte, below);
below = self.storage.node_raw(n);
}
Ok((below, bottom))
}
pub(crate) fn remove(
&self,
key: &[u8],
matches: impl Fn(NonNull<S::Leaf>) -> bool,
guard: &S::Guard,
) -> Option<NonNull<S::Leaf>> {
let mut backoff = SpinBackoff::new();
'retry: loop {
let root = self.root();
if root.is_null() {
return None;
}
if root.is_leaf() {
let leaf = self.storage_leaf(root);
if !matches(leaf) {
return None;
}
let Some(w) = self.root_latch.lock() else {
unreachable!("root latch is never obsolete")
};
if self.root() != root {
drop(w);
continue 'retry;
}
let bomb = AbortOnUnwind;
self.set_root(&w, Raw::<S>::NULL);
unsafe { leaf.as_ref() }.mark_removed();
self.len_add(-1);
bomb.defuse();
drop(w);
unsafe { self.storage.retire_leaf(leaf, guard) };
return Some(leaf);
}
let mut parent = Parent::Root;
let mut node_raw = root;
let mut depth = 0usize;
loop {
let node = unsafe { self.node_ref(node_raw) };
let Some(v) = node.latch.read_version() else {
backoff.spin();
continue 'retry;
};
if !self.still_parent(parent, node_raw) {
continue 'retry;
}
let prefix = node.load_prefix();
let rest = key.get(depth..).unwrap_or(&[]);
if !prefix.is_prefix_of(rest) {
if !node.latch.validate(v) {
continue 'retry;
}
return None;
}
let node_depth = depth + prefix.len;
if node_depth == key.len() {
let exact = node.exact_leaf();
if !node.latch.validate(v) {
continue 'retry;
}
if exact.is_null() {
return None;
}
let leaf = self.storage_leaf(exact);
if !matches(leaf) {
return None;
}
let Some(nw) = node.latch.try_upgrade(v) else {
backoff.spin();
continue 'retry;
};
let bomb = AbortOnUnwind;
node.set_exact_leaf(&nw, Raw::<S>::NULL);
unsafe { leaf.as_ref() }.mark_removed();
self.len_add(-1);
bomb.defuse();
drop(nw);
unsafe { self.storage.retire_leaf(leaf, guard) };
return Some(leaf);
}
let byte = key[node_depth];
let child = node.find_child(byte);
if let Some(c) = child.filter(|c| !c.is_leaf()) {
parent = Parent::Node {
raw: node_raw,
version: v,
byte,
};
node_raw = c;
depth = node_depth + 1;
continue;
}
if !node.latch.validate(v) {
continue 'retry;
}
let leaf = self.storage_leaf(child?);
if !matches(leaf) {
return None;
}
let Some(nw) = node.latch.try_upgrade(v) else {
backoff.spin();
continue 'retry;
};
let bomb = AbortOnUnwind;
node.remove_child(&nw, byte);
unsafe { leaf.as_ref() }.mark_removed();
self.len_add(-1);
bomb.defuse();
drop(nw);
unsafe { self.storage.retire_leaf(leaf, guard) };
return Some(leaf);
}
}
}
}