#![deny(unsafe_op_in_unsafe_fn, clippy::undocumented_unsafe_blocks)]
use std::ptr::NonNull;
use crate::latch::SpinBackoff;
use crate::raw::slot::Slot;
use crate::raw::{LeafNode, RawTree, Storage};
impl<S: Storage> RawTree<S> {
pub(crate) fn get(&self, key: &[u8]) -> Option<NonNull<S::Leaf>> {
let mut backoff = SpinBackoff::new();
'retry: loop {
let mut cur = self.root();
crate::hooks::pause(crate::hooks::Point::ReaderAfterRoot);
if cur.is_null() {
return None;
}
if cur.is_leaf() {
let leaf = unsafe { self.storage.leaf(cur) };
let k = unsafe { leaf.as_ref() }.key_bytes();
return (k == key).then_some(leaf);
}
let mut parent: Option<(&crate::raw::node::NodeHeader<S::Atomic>, u64)> = None;
let mut depth = 0usize;
loop {
let node = unsafe { self.node_ref(cur) };
let Some(v) = node.latch.read_version() else {
backoff.spin();
continue 'retry;
};
crate::hooks::pause(crate::hooks::Point::ReaderAfterChildVersion);
#[cfg(loom)]
let coupled =
parent.filter(|_| !crate::latch::mutants::SKIP_R4_COUPLING.with(|m| m.get()));
#[cfg(not(loom))]
let coupled = parent;
let still_linked = match coupled {
Some((p, pv)) => p.latch.validate(pv),
None if parent.is_none() => self.root() == cur,
None => true,
};
if !still_linked {
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;
let child = if node_depth == key.len() {
node.exact_leaf()
} else {
node.find_child(key[node_depth])
.unwrap_or(crate::raw::Raw::<S>::NULL)
};
if child.is_null() || child.is_leaf() {
if !node.latch.validate(v) {
continue 'retry;
}
if child.is_null() {
return None;
}
let leaf = unsafe { self.storage.leaf(child) };
let k = unsafe { leaf.as_ref() }.key_bytes();
return (k == key).then_some(leaf);
}
parent = Some((node, v));
cur = child;
depth = node_depth + 1;
}
}
}
}