#![deny(unsafe_op_in_unsafe_fn, clippy::undocumented_unsafe_blocks)]
use std::ops::{Bound, Deref};
use std::rc::Rc;
use crate::entry::EntryRef;
use crate::guard::{pin_tagged, GuardHandle};
use crate::key::AsBytes;
use crate::raw::cursor::{Cursor, KeyBuf};
use crate::tree::{Storage, Tree};
pub struct Range<'a, K, V> {
tree: &'a Tree<K, V>,
guard: GuardHandle<'a>,
cursor: Cursor<Storage<K, V>>,
}
impl<'a, K, V> Range<'a, K, V> {
pub(crate) fn owned(tree: &'a Tree<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 Tree<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 = EntryRef<'a, K, V>;
#[inline(always)]
fn next(&mut self) -> Option<Self::Item> {
let leaf = self.cursor.next(&self.tree.raw)?;
Some(EntryRef::new(leaf, self.tree, 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> {
let leaf = self.cursor.next_back(&self.tree.raw)?;
Some(EntryRef::new(leaf, self.tree, self.guard.duplicate()))
}
}
impl<K: AsBytes + Send + 'static, V: Send + 'static> std::iter::FusedIterator for Range<'_, K, V> {}
pub type Iter<'a, K, V> = Range<'a, K, V>;
pub struct KeyRef<'a, K, V>(EntryRef<'a, K, V>);
impl<'a, K, V> KeyRef<'a, K, V> {
#[inline]
pub fn entry(&self) -> &EntryRef<'a, K, V> {
&self.0
}
}
impl<K, V> Deref for KeyRef<'_, K, V> {
type Target = K;
#[inline]
fn deref(&self) -> &K {
self.0.key()
}
}
impl<K: std::fmt::Debug, V> std::fmt::Debug for KeyRef<'_, K, V> {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
self.0.key().fmt(f)
}
}
pub struct ValueRef<'a, K, V>(EntryRef<'a, K, V>);
impl<'a, K, V> ValueRef<'a, K, V> {
#[inline]
pub fn entry(&self) -> &EntryRef<'a, K, V> {
&self.0
}
}
impl<K, V> Deref for ValueRef<'_, K, V> {
type Target = V;
#[inline]
fn deref(&self) -> &V {
self.0.value()
}
}
impl<K, V: std::fmt::Debug> std::fmt::Debug for ValueRef<'_, K, V> {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
self.0.value().fmt(f)
}
}
pub struct Keys<'a, K, V>(pub(crate) Range<'a, K, V>);
impl<'a, K: AsBytes + Send + 'static, V: Send + 'static> Iterator for Keys<'a, K, V> {
type Item = KeyRef<'a, K, V>;
#[inline]
fn next(&mut self) -> Option<Self::Item> {
self.0.next().map(KeyRef)
}
}
impl<K: AsBytes + Send + 'static, V: Send + 'static> DoubleEndedIterator for Keys<'_, K, V> {
#[inline]
fn next_back(&mut self) -> Option<Self::Item> {
self.0.next_back().map(KeyRef)
}
}
pub struct Values<'a, K, V>(pub(crate) Range<'a, K, V>);
impl<'a, K: AsBytes + Send + 'static, V: Send + 'static> Iterator for Values<'a, K, V> {
type Item = ValueRef<'a, K, V>;
#[inline]
fn next(&mut self) -> Option<Self::Item> {
self.0.next().map(ValueRef)
}
}
impl<K: AsBytes + Send + 'static, V: Send + 'static> DoubleEndedIterator for Values<'_, K, V> {
#[inline]
fn next_back(&mut self) -> Option<Self::Item> {
self.0.next_back().map(ValueRef)
}
}
pub struct GuardKeys<'a, K, V>(pub(crate) Range<'a, K, V>);
impl<'a, K: AsBytes + Send + 'static, V: Send + 'static> Iterator for GuardKeys<'a, K, V> {
type Item = &'a K;
#[inline]
fn next(&mut self) -> Option<&'a K> {
let leaf = self.0.cursor.next(&self.0.tree.raw)?;
Some(unsafe { &(*leaf.as_ptr()).key })
}
}
pub struct GuardValues<'a, K, V>(pub(crate) Range<'a, K, V>);
impl<'a, K: AsBytes + Send + 'static, V: Send + 'static> Iterator for GuardValues<'a, K, V> {
type Item = &'a V;
#[inline]
fn next(&mut self) -> Option<&'a V> {
let leaf = self.0.cursor.next(&self.0.tree.raw)?;
Some(unsafe { &(*leaf.as_ptr()).value })
}
}