#![deny(unsafe_op_in_unsafe_fn, clippy::undocumented_unsafe_blocks)]
use std::ops::Bound;
use std::ptr::NonNull;
use std::rc::Rc;
use crate::guard::{pin_tagged, GuardHandle};
use crate::key::AsBytes;
use crate::raw::cursor::{Cursor, KeyBuf};
use crate::versioned::entry::VersionedEntryRef;
use crate::versioned::tree::{Storage, VersionedTree};
pub struct Range<'a, K, V> {
tree: &'a VersionedTree<K, V>,
guard: GuardHandle<'a>,
cursor: Cursor<Storage<K, V>>,
}
impl<'a, K, V> Range<'a, K, V> {
pub(crate) fn owned(
tree: &'a VersionedTree<K, V>,
start: Bound<KeyBuf>,
end: Bound<KeyBuf>,
) -> Self {
let (g, id) = pin_tagged();
Self {
tree,
guard: GuardHandle::Shared(Rc::new(g), id),
cursor: Cursor::new(start, end),
}
}
pub(crate) fn borrowed(
tree: &'a VersionedTree<K, V>,
guard: &'a crossbeam_epoch::Guard,
start: Bound<KeyBuf>,
end: Bound<KeyBuf>,
) -> Self {
Self {
tree,
guard: GuardHandle::Borrowed(guard),
cursor: Cursor::new(start, end),
}
}
}
impl<'a, K: AsBytes + Send + 'static, V: Send + 'static> Iterator for Range<'a, K, V> {
type Item = VersionedEntryRef<'a, K, V>;
#[inline(always)]
fn next(&mut self) -> Option<Self::Item> {
loop {
let leaf = self.cursor.next(&self.tree.raw)?;
let head = unsafe { leaf.as_ref() }.head();
if !head.is_tombstone() {
return Some(VersionedEntryRef {
leaf,
node: NonNull::from(head),
tree: self.tree,
guard: self.guard.duplicate(),
});
}
}
}
}
impl<K: AsBytes + Send + 'static, V: Send + 'static> DoubleEndedIterator for Range<'_, K, V> {
#[inline(always)]
fn next_back(&mut self) -> Option<Self::Item> {
loop {
let leaf = self.cursor.next_back(&self.tree.raw)?;
let head = unsafe { leaf.as_ref() }.head();
if !head.is_tombstone() {
return Some(VersionedEntryRef {
leaf,
node: NonNull::from(head),
tree: self.tree,
guard: self.guard.duplicate(),
});
}
}
}
}
impl<K: AsBytes + Send + 'static, V: Send + 'static> std::iter::FusedIterator for Range<'_, K, V> {}