#![deny(unsafe_op_in_unsafe_fn, clippy::undocumented_unsafe_blocks)]
use std::ops::Bound;
use std::ptr::NonNull;
use crate::latch::SpinBackoff;
use crate::raw::slot::Slot;
use crate::raw::{common_prefix, Layout, LeafNode, Raw, RawTree, Storage};
#[derive(Clone)]
pub(crate) enum KeyBuf {
Inline([u8; 32], u8),
Heap(Box<[u8]>),
}
impl KeyBuf {
#[inline]
pub(crate) fn new(bytes: &[u8]) -> Self {
if bytes.len() <= 32 {
let mut b = [0u8; 32];
b[..bytes.len()].copy_from_slice(bytes);
KeyBuf::Inline(b, bytes.len() as u8)
} else {
KeyBuf::Heap(bytes.into())
}
}
#[inline]
pub(crate) fn as_slice(&self) -> &[u8] {
match self {
KeyBuf::Inline(b, len) => &b[..*len as usize],
KeyBuf::Heap(b) => b,
}
}
}
pub(crate) fn owned_bound<Q: crate::AsBytes + ?Sized>(b: Bound<&Q>) -> Bound<KeyBuf> {
match b {
Bound::Included(k) => Bound::Included(KeyBuf::new(k.as_bytes())),
Bound::Excluded(k) => Bound::Excluded(KeyBuf::new(k.as_bytes())),
Bound::Unbounded => Bound::Unbounded,
}
}
#[derive(Copy, Clone)]
struct Frame<R> {
node: R,
version: u64,
next: i16,
exact: bool,
}
const INLINE_FRAMES: usize = 12;
struct Stack<R: Copy> {
inline: [Option<Frame<R>>; INLINE_FRAMES],
len: usize,
spill: Vec<Frame<R>>,
}
impl<R: Copy> Stack<R> {
fn new() -> Self {
Self {
inline: [None; INLINE_FRAMES],
len: 0,
spill: Vec::new(),
}
}
#[inline]
fn clear(&mut self) {
self.len = 0;
self.spill.clear();
}
#[inline]
fn push(&mut self, f: Frame<R>) {
if self.len < INLINE_FRAMES {
self.inline[self.len] = Some(f);
} else {
self.spill.push(f);
}
self.len += 1;
}
#[inline]
fn pop(&mut self) {
if self.len > INLINE_FRAMES {
self.spill.pop();
}
self.len -= 1;
}
#[inline]
fn top(&mut self) -> Option<&mut Frame<R>> {
match self.len {
0 => None,
n if n <= INLINE_FRAMES => self.inline[n - 1].as_mut(),
_ => self.spill.last_mut(),
}
}
}
enum Step<R> {
Leaf(R),
Batch(R),
End,
Invalid,
}
const BATCH: usize = 16;
struct Side<R: Slot> {
stack: Stack<R>,
pending: Option<R>,
batch: [R; BATCH],
batch_len: u8,
batch_pos: u8,
batch_in_range: bool,
last: Option<Resume<R>>,
positioned: bool,
}
enum Resume<R> {
Leaf(R),
Key(KeyBuf),
}
impl<R: Slot> Resume<R> {
#[inline]
fn key<'t, S: Storage<Atomic: crate::raw::slot::AtomicSlot<Raw = R>>>(
&'t self,
tree: &'t RawTree<S>,
) -> &'t [u8] {
match self {
Resume::Leaf(l) => unsafe { tree.leaf_ref(*l) }.key_bytes(),
Resume::Key(k) => k.as_slice(),
}
}
}
impl<R: Slot> Side<R> {
fn new() -> Self {
Self {
stack: Stack::new(),
pending: None,
batch: [R::NULL; BATCH],
batch_len: 0,
batch_pos: 0,
batch_in_range: false,
last: None,
positioned: false,
}
}
#[inline]
fn reset(&mut self) {
self.stack.clear();
self.pending = None;
self.batch_len = 0;
self.batch_pos = 0;
self.batch_in_range = false;
}
#[inline]
fn remember(&mut self, leaf: R) {
self.last = Some(Resume::Leaf(leaf));
}
}
pub(crate) struct Cursor<S: Layout> {
start: Bound<KeyBuf>,
end: Bound<KeyBuf>,
front: Side<Raw<S>>,
back: Side<Raw<S>>,
done: bool,
}
#[derive(Copy, Clone, PartialEq, Eq)]
enum Dir {
Forward,
Backward,
}
#[inline(always)]
pub(crate) fn cmp_keys(a: &[u8], b: &[u8]) -> std::cmp::Ordering {
let n = a.len().min(b.len());
if n > 64 {
return a.cmp(b);
}
let mut i = 0;
while i + 8 <= n {
let (Some(x), Some(y)) = (a[i..].first_chunk::<8>(), b[i..].first_chunk::<8>()) else {
break;
};
let (x, y) = (u64::from_be_bytes(*x), u64::from_be_bytes(*y));
if x != y {
return x.cmp(&y);
}
i += 8;
}
while i < n {
if a[i] != b[i] {
return a[i].cmp(&b[i]);
}
i += 1;
}
a.len().cmp(&b.len())
}
#[inline(always)]
fn above_start(k: &[u8], start: &Bound<KeyBuf>) -> bool {
match start {
Bound::Included(s) => cmp_keys(k, s.as_slice()).is_ge(),
Bound::Excluded(s) => cmp_keys(k, s.as_slice()).is_gt(),
Bound::Unbounded => true,
}
}
#[inline(always)]
fn below_end(k: &[u8], end: &Bound<KeyBuf>) -> bool {
match end {
Bound::Included(e) => cmp_keys(k, e.as_slice()).is_le(),
Bound::Excluded(e) => cmp_keys(k, e.as_slice()).is_lt(),
Bound::Unbounded => true,
}
}
impl<S: Layout> Cursor<S> {
pub(crate) fn new(start: Bound<KeyBuf>, end: Bound<KeyBuf>) -> Self {
Self {
start,
end,
front: Side::new(),
back: Side::new(),
done: false,
}
}
}
impl<S: Storage> Cursor<S> {
pub(crate) fn invalidate(&mut self, tree: &RawTree<S>) {
for side in [&mut self.front, &mut self.back] {
side.positioned = false;
side.reset();
if let Some(r) = &side.last {
let owned = KeyBuf::new(r.key(tree));
side.last = Some(Resume::Key(owned));
}
}
}
}
impl<S: Storage> Cursor<S> {
#[inline(always)]
pub(crate) fn next(&mut self, tree: &RawTree<S>) -> Option<NonNull<S::Leaf>> {
self.advance(tree, Dir::Forward)
}
#[inline(always)]
pub(crate) fn next_back(&mut self, tree: &RawTree<S>) -> Option<NonNull<S::Leaf>> {
self.advance(tree, Dir::Backward)
}
#[inline(always)]
fn advance(&mut self, tree: &RawTree<S>, dir: Dir) -> Option<NonNull<S::Leaf>> {
let (side, other) = match dir {
Dir::Forward => (&mut self.front, &self.back),
Dir::Backward => (&mut self.back, &self.front),
};
if side.batch_in_range
&& side.batch_pos < side.batch_len
&& other.last.is_none()
&& side.pending.is_none()
&& side.positioned
&& !self.done
{
let leaf_raw = side.batch[side.batch_pos as usize];
side.batch_pos += 1;
side.remember(leaf_raw);
return Some(unsafe { tree.storage.leaf(leaf_raw) });
}
self.advance_slow(tree, dir)
}
#[inline(never)]
fn advance_slow(&mut self, tree: &RawTree<S>, dir: Dir) -> Option<NonNull<S::Leaf>> {
loop {
if self.done {
return None;
}
let side = match dir {
Dir::Forward => &mut self.front,
Dir::Backward => &mut self.back,
};
if !side.positioned {
let bound = match (&side.last, dir) {
(Some(r), _) => Bound::Excluded(KeyBuf::new(r.key(tree))),
(None, Dir::Forward) => self.start.clone(),
(None, Dir::Backward) => self.end.clone(),
};
seek(tree, side, &bound, dir);
side.positioned = true;
}
let leaf_raw = match side.pending.take() {
Some(l) => l,
None => match step(tree, side, dir) {
Step::Leaf(l) => l,
Step::Batch(l) => {
let last = side.batch[side.batch_len as usize - 1];
let k = unsafe { tree.leaf_ref(last) }.key_bytes();
side.batch_in_range = match dir {
Dir::Forward => below_end(k, &self.end),
Dir::Backward => above_start(k, &self.start),
};
l
}
Step::End => {
self.done = true;
return None;
}
Step::Invalid => {
side.positioned = false;
continue;
}
},
};
return self.accept(tree, dir, leaf_raw);
}
}
#[inline]
fn accept(
&mut self,
tree: &RawTree<S>,
dir: Dir,
leaf_raw: Raw<S>,
) -> Option<NonNull<S::Leaf>> {
let (side, other) = match dir {
Dir::Forward => (&mut self.front, &self.back),
Dir::Backward => (&mut self.back, &self.front),
};
let leaf = unsafe { tree.storage.leaf(leaf_raw) };
let k = unsafe { leaf.as_ref() }.key_bytes();
let (in_range, crossed) = match dir {
Dir::Forward => (
below_end(k, &self.end),
other
.last
.as_ref()
.is_some_and(|b| cmp_keys(k, b.key(tree)).is_ge()),
),
Dir::Backward => (
above_start(k, &self.start),
other
.last
.as_ref()
.is_some_and(|f| cmp_keys(k, f.key(tree)).is_le()),
),
};
if !in_range || crossed {
self.done = true;
return None;
}
side.remember(leaf_raw);
Some(leaf)
}
}
fn seek<S: Storage>(tree: &RawTree<S>, side: &mut Side<Raw<S>>, bound: &Bound<KeyBuf>, dir: Dir) {
let mut backoff = SpinBackoff::new();
'retry: loop {
side.reset();
let root = tree.root();
if root.is_null() {
return;
}
if root.is_leaf() {
let k = unsafe { tree.leaf_ref(root) }.key_bytes();
let take = match (bound, dir) {
(Bound::Unbounded, _) => true,
(Bound::Included(b), Dir::Forward) => cmp_keys(k, b.as_slice()).is_ge(),
(Bound::Excluded(b), Dir::Forward) => cmp_keys(k, b.as_slice()).is_gt(),
(Bound::Included(b), Dir::Backward) => cmp_keys(k, b.as_slice()).is_le(),
(Bound::Excluded(b), Dir::Backward) => cmp_keys(k, b.as_slice()).is_lt(),
};
if take {
side.pending = Some(root);
}
return;
}
let (key, inclusive) = match bound {
Bound::Unbounded => {
let node = unsafe { tree.node_ref(root) };
let Some(v) = node.latch.read_version() else {
backoff.spin();
continue 'retry;
};
if tree.root() != root {
continue 'retry;
}
side.stack.push(edge_frame(root, v, dir));
return;
}
Bound::Included(k) => (k.as_slice(), true),
Bound::Excluded(k) => (k.as_slice(), false),
};
let mut node_raw = root;
let mut depth = 0usize;
loop {
let node = unsafe { tree.node_ref(node_raw) };
let Some(v) = node.latch.read_version() else {
backoff.spin();
continue 'retry;
};
crate::hooks::pause(crate::hooks::Point::CursorSeek);
let coupled = match side.stack.top() {
Some(p) => {
let pv = p.version;
unsafe { tree.node_ref(p.node) }.latch.validate(pv)
}
None => tree.root() == node_raw,
};
if !coupled {
continue 'retry;
}
let prefix = node.load_prefix();
let rest = key.get(depth..).unwrap_or(&[]);
let m = common_prefix(prefix.as_slice(), rest);
if m < prefix.len {
let subtree_after_key = m == rest.len() || rest[m] < prefix.bytes[m];
if !node.latch.validate(v) {
continue 'retry;
}
if subtree_after_key == (dir == Dir::Forward) {
side.stack.push(edge_frame(node_raw, v, dir));
}
return;
}
let node_depth = depth + prefix.len;
if node_depth == key.len() {
if !node.latch.validate(v) {
continue 'retry;
}
side.stack.push(match dir {
Dir::Forward => Frame {
node: node_raw,
version: v,
next: 0,
exact: inclusive,
},
Dir::Backward => Frame {
node: node_raw,
version: v,
next: -1,
exact: inclusive,
},
});
return;
}
let byte = key[node_depth];
let child = node.find_child(byte);
if !node.latch.validate(v) {
continue 'retry;
}
side.stack.push(match dir {
Dir::Forward => Frame {
node: node_raw,
version: v,
next: byte as i16 + 1,
exact: false,
},
Dir::Backward => Frame {
node: node_raw,
version: v,
next: byte as i16 - 1,
exact: true,
},
});
match child {
None => return,
Some(c) if c.is_leaf() => {
let k = unsafe { tree.leaf_ref(c) }.key_bytes();
let take = match dir {
Dir::Forward => k > key || (inclusive && k == key),
Dir::Backward => k < key || (inclusive && k == key),
};
if take {
if let Some(top) = side.stack.top() {
top.next = byte as i16;
}
}
return;
}
Some(c) => {
node_raw = c;
depth = node_depth + 1;
}
}
}
}
}
fn edge_frame<R>(node: R, version: u64, dir: Dir) -> Frame<R> {
Frame {
node,
version,
next: match dir {
Dir::Forward => 0,
Dir::Backward => 255,
},
exact: true,
}
}
fn step<S: Storage>(tree: &RawTree<S>, side: &mut Side<Raw<S>>, dir: Dir) -> Step<Raw<S>> {
if side.batch_pos < side.batch_len {
let l = side.batch[side.batch_pos as usize];
side.batch_pos += 1;
return Step::Leaf(l);
}
let (stack, batch) = (&mut side.stack, &mut side.batch);
loop {
let Some(top) = stack.top() else {
return Step::End;
};
let node = unsafe { tree.node_ref(top.node) };
let exact_now = match dir {
Dir::Forward => top.exact,
Dir::Backward => top.exact && top.next < 0,
};
if exact_now {
top.exact = false;
let ex = node.exact_leaf();
if !node.latch.validate(top.version) {
return Step::Invalid;
}
if !ex.is_null() {
return Step::Leaf(ex);
}
continue;
}
let mut n = 0usize;
let mut inner = None;
let mut next = top.next;
loop {
let found = match dir {
Dir::Forward if next <= 255 => node.next_child(next as u16),
Dir::Backward if next >= 0 => node.prev_child(next as u8),
_ => None,
};
let Some((byte, child)) = found else {
break;
};
let after = match dir {
Dir::Forward => byte as i16 + 1,
Dir::Backward => byte as i16 - 1,
};
if child.is_leaf() {
batch[n] = child;
n += 1;
next = after;
if n == BATCH {
break;
}
} else {
if n == 0 {
inner = Some(child);
next = after;
}
break;
}
}
if let Some(child) = inner {
let parent_version = top.version;
top.next = next;
let cn = unsafe { tree.node_ref(child) };
let Some(cv) = cn.latch.read_version() else {
return Step::Invalid;
};
if !node.latch.validate(parent_version) {
return Step::Invalid;
}
stack.push(edge_frame(child, cv, dir));
continue;
}
if !node.latch.validate(top.version) {
return Step::Invalid;
}
top.next = next;
if n > 0 {
side.batch_len = n as u8;
side.batch_pos = 1;
side.batch_in_range = false;
return Step::Batch(side.batch[0]);
}
match dir {
Dir::Forward => stack.pop(),
Dir::Backward if top.exact => top.next = -1,
Dir::Backward => stack.pop(),
}
}
}