use crossbeam_epoch::Guard;
use std::ops::Bound;
use crate::entry::EntryRef;
use crate::key::AsBytes;
use crate::tree::Tree;
pub struct Range<'a, K: AsBytes + Send + 'static, V: Send + 'static> {
tree: &'a Tree<K, V>,
_guard: Guard,
start_bound: Bound<Vec<u8>>,
end_bound: Bound<Vec<u8>>,
cursor_front: Vec<u8>,
cursor_back: Vec<u8>,
has_front: bool,
has_back: bool,
exhausted: bool,
}
impl<'a, K: AsBytes + Send + 'static, V: Send + 'static> Range<'a, K, V> {
pub(crate) fn new(
tree: &'a Tree<K, V>,
start_bound: Bound<Vec<u8>>,
end_bound: Bound<Vec<u8>>,
) -> Self {
let guard = crossbeam_epoch::pin();
Self {
tree,
_guard: guard,
start_bound,
end_bound,
cursor_front: Vec::with_capacity(32),
cursor_back: Vec::with_capacity(32),
has_front: false,
has_back: false,
exhausted: false,
}
}
}
impl<'a, K: AsBytes + Send + 'static, V: Send + 'static> Iterator for Range<'a, K, V> {
type Item = EntryRef<'a, K, V>;
fn next(&mut self) -> Option<Self::Item> {
if self.exhausted {
return None;
}
loop {
let (search_key, include_equal) = if self.has_front {
(self.cursor_front.as_slice(), false)
} else {
match &self.start_bound {
Bound::Included(k) => (k.as_slice(), true),
Bound::Excluded(k) => (k.as_slice(), false),
Bound::Unbounded => (&[][..], true),
}
};
let leaf_ptr = self.tree.find_successor(search_key, include_equal)?;
let leaf = unsafe { &*leaf_ptr };
let k_bytes = leaf.key.as_bytes();
match &self.end_bound {
Bound::Included(end) if k_bytes > end.as_slice() => {
self.exhausted = true;
return None;
}
Bound::Excluded(end) if k_bytes >= end.as_slice() => {
self.exhausted = true;
return None;
}
_ => {}
}
if self.has_back && k_bytes > self.cursor_back.as_slice() {
self.exhausted = true;
return None;
}
self.cursor_front.clear();
self.cursor_front.extend_from_slice(k_bytes);
self.has_front = true;
let entry = EntryRef {
leaf_ptr,
tree: self.tree,
};
if !entry.is_removed() {
return Some(entry);
}
}
}
}
impl<'a, K: AsBytes + Send + 'static, V: Send + 'static> DoubleEndedIterator for Range<'a, K, V> {
fn next_back(&mut self) -> Option<Self::Item> {
if self.exhausted {
return None;
}
loop {
let (search_key, include_equal) = if self.has_back {
(self.cursor_back.as_slice(), false)
} else {
match &self.end_bound {
Bound::Included(k) => (k.as_slice(), true),
Bound::Excluded(k) => (k.as_slice(), false),
Bound::Unbounded => (&[0xFF; 64][..], true),
}
};
let leaf_ptr = self.tree.find_predecessor(search_key, include_equal)?;
let leaf = unsafe { &*leaf_ptr };
let k_bytes = leaf.key.as_bytes();
match &self.start_bound {
Bound::Included(start) if k_bytes < start.as_slice() => {
self.exhausted = true;
return None;
}
Bound::Excluded(start) if k_bytes <= start.as_slice() => {
self.exhausted = true;
return None;
}
_ => {}
}
if self.has_front && k_bytes < self.cursor_front.as_slice() {
self.exhausted = true;
return None;
}
self.cursor_back.clear();
self.cursor_back.extend_from_slice(k_bytes);
self.has_back = true;
let entry = EntryRef {
leaf_ptr,
tree: self.tree,
};
if !entry.is_removed() {
return Some(entry);
}
}
}
}
pub struct Iter<'a, K: AsBytes + Send + 'static, V: Send + 'static> {
inner: Range<'a, K, V>,
}
impl<'a, K: AsBytes + Send + 'static, V: Send + 'static> Iter<'a, K, V> {
pub(crate) fn new(tree: &'a Tree<K, V>) -> Self {
Self {
inner: Range::new(tree, Bound::Unbounded, Bound::Unbounded),
}
}
}
impl<'a, K: AsBytes + Send + 'static, V: Send + 'static> Iterator for Iter<'a, K, V> {
type Item = EntryRef<'a, K, V>;
#[inline]
fn next(&mut self) -> Option<Self::Item> {
self.inner.next()
}
}
impl<'a, K: AsBytes + Send + 'static, V: Send + 'static> DoubleEndedIterator for Iter<'a, K, V> {
#[inline]
fn next_back(&mut self) -> Option<Self::Item> {
self.inner.next_back()
}
}
pub struct Keys<'a, K: AsBytes + Send + 'static, V: Send + 'static> {
inner: Iter<'a, K, V>,
}
impl<'a, K: AsBytes + Send + 'static, V: Send + 'static> Keys<'a, K, V> {
pub(crate) fn new(inner: Iter<'a, K, V>) -> Self {
Self { inner }
}
}
impl<'a, K: AsBytes + Send + 'static, V: Send + 'static> Iterator for Keys<'a, K, V> {
type Item = &'a K;
#[inline]
fn next(&mut self) -> Option<Self::Item> {
self.inner.next().map(|e| e.key())
}
}
pub struct Values<'a, K: AsBytes + Send + 'static, V: Send + 'static> {
inner: Iter<'a, K, V>,
}
impl<'a, K: AsBytes + Send + 'static, V: Send + 'static> Values<'a, K, V> {
pub(crate) fn new(inner: Iter<'a, K, V>) -> Self {
Self { inner }
}
}
impl<'a, K: AsBytes + Send + 'static, V: Send + 'static> Iterator for Values<'a, K, V> {
type Item = &'a V;
#[inline]
fn next(&mut self) -> Option<Self::Item> {
self.inner.next().map(|e| e.value())
}
}
pub(crate) unsafe fn first_leaf_in_subtree<K, V>(
ptr: crate::node::TaggedPtr,
) -> Option<*mut crate::node::Leaf<K, V>> {
if ptr.is_null() {
return None;
}
if ptr.is_leaf() {
return Some(ptr.as_leaf_ptr());
}
let header = &*ptr.as_inner_ptr();
if let Some(leaf) = header.load_exact_leaf::<K, V>(std::sync::atomic::Ordering::Acquire) {
return Some(leaf);
}
match header.node_type {
crate::node::NodeType::Node4 => {
let n = &*(ptr.as_inner_ptr() as *const crate::node::Node4);
for i in 0..n.header.num_children as usize {
let child = crate::node::TaggedPtr::from_raw(
n.children[i].load(std::sync::atomic::Ordering::Acquire),
);
if !child.is_null() {
if let Some(leaf) = first_leaf_in_subtree(child) {
return Some(leaf);
}
}
}
None
}
crate::node::NodeType::Node16 => {
let n = &*(ptr.as_inner_ptr() as *const crate::node::Node16);
for i in 0..n.header.num_children as usize {
let child = crate::node::TaggedPtr::from_raw(
n.children[i].load(std::sync::atomic::Ordering::Acquire),
);
if !child.is_null() {
if let Some(leaf) = first_leaf_in_subtree(child) {
return Some(leaf);
}
}
}
None
}
crate::node::NodeType::Node48 => {
let n = &*(ptr.as_inner_ptr() as *const crate::node::Node48);
for byte in 0..=255u8 {
let slot = n.child_indices[byte as usize];
if slot != crate::node::NODE48_EMPTY {
let child = crate::node::TaggedPtr::from_raw(
n.children[slot as usize].load(std::sync::atomic::Ordering::Acquire),
);
if !child.is_null() {
if let Some(leaf) = first_leaf_in_subtree(child) {
return Some(leaf);
}
}
}
}
None
}
crate::node::NodeType::Node256 => {
let n = &*(ptr.as_inner_ptr() as *const crate::node::Node256);
for byte in 0..=255u8 {
let child = crate::node::TaggedPtr::from_raw(
n.children[byte as usize].load(std::sync::atomic::Ordering::Acquire),
);
if !child.is_null() {
if let Some(leaf) = first_leaf_in_subtree(child) {
return Some(leaf);
}
}
}
None
}
}
}
pub(crate) unsafe fn last_leaf_in_subtree<K, V>(
ptr: crate::node::TaggedPtr,
) -> Option<*mut crate::node::Leaf<K, V>> {
if ptr.is_null() {
return None;
}
if ptr.is_leaf() {
return Some(ptr.as_leaf_ptr());
}
let header = &*ptr.as_inner_ptr();
match header.node_type {
crate::node::NodeType::Node4 => {
let n = &*(ptr.as_inner_ptr() as *const crate::node::Node4);
for i in (0..n.header.num_children as usize).rev() {
let child = crate::node::TaggedPtr::from_raw(
n.children[i].load(std::sync::atomic::Ordering::Acquire),
);
if !child.is_null() {
if let Some(leaf) = last_leaf_in_subtree(child) {
return Some(leaf);
}
}
}
header.load_exact_leaf::<K, V>(std::sync::atomic::Ordering::Acquire)
}
crate::node::NodeType::Node16 => {
let n = &*(ptr.as_inner_ptr() as *const crate::node::Node16);
for i in (0..n.header.num_children as usize).rev() {
let child = crate::node::TaggedPtr::from_raw(
n.children[i].load(std::sync::atomic::Ordering::Acquire),
);
if !child.is_null() {
if let Some(leaf) = last_leaf_in_subtree(child) {
return Some(leaf);
}
}
}
header.load_exact_leaf::<K, V>(std::sync::atomic::Ordering::Acquire)
}
crate::node::NodeType::Node48 => {
let n = &*(ptr.as_inner_ptr() as *const crate::node::Node48);
for byte in (0..=255u8).rev() {
let slot = n.child_indices[byte as usize];
if slot != crate::node::NODE48_EMPTY {
let child = crate::node::TaggedPtr::from_raw(
n.children[slot as usize].load(std::sync::atomic::Ordering::Acquire),
);
if !child.is_null() {
if let Some(leaf) = last_leaf_in_subtree(child) {
return Some(leaf);
}
}
}
}
header.load_exact_leaf::<K, V>(std::sync::atomic::Ordering::Acquire)
}
crate::node::NodeType::Node256 => {
let n = &*(ptr.as_inner_ptr() as *const crate::node::Node256);
for byte in (0..=255u8).rev() {
let child = crate::node::TaggedPtr::from_raw(
n.children[byte as usize].load(std::sync::atomic::Ordering::Acquire),
);
if !child.is_null() {
if let Some(leaf) = last_leaf_in_subtree(child) {
return Some(leaf);
}
}
}
header.load_exact_leaf::<K, V>(std::sync::atomic::Ordering::Acquire)
}
}
}