use crossbeam_epoch::Guard;
use std::ops::Bound;
use crate::key::AsBytes;
use crate::node::{Leaf, TaggedPtr};
use crate::tree::Tree;
pub struct Range<'a, K: AsBytes + Send + 'static, V: Send + 'static> {
tree: &'a Tree<K, V>,
_guard: &'a 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>,
guard: &'a Guard,
start_bound: Bound<Vec<u8>>,
end_bound: Bound<Vec<u8>>,
) -> Self {
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 = (&'a K, &'a V);
fn next(&mut self) -> Option<Self::Item> {
if self.exhausted {
return None;
}
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;
Some((&leaf.key, &leaf.value))
}
}
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;
}
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;
Some((&leaf.key, &leaf.value))
}
}
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>, guard: &'a Guard) -> Self {
Self {
inner: Range::new(tree, guard, Bound::Unbounded, Bound::Unbounded),
}
}
}
impl<'a, K: AsBytes + Send + 'static, V: Send + 'static> Iterator for Iter<'a, K, V> {
type Item = (&'a K, &'a 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(|(k, _)| k)
}
}
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(|(_, v)| v)
}
}
pub(crate) unsafe fn first_leaf_in_subtree<K, V>(ptr: TaggedPtr) -> Option<*mut Leaf<K, V>> {
if ptr.is_leaf() {
return Some(ptr.as_leaf_ptr());
}
let header = &*ptr.as_inner_ptr();
let exact = header.exact_leaf.load(std::sync::atomic::Ordering::Acquire);
if !exact.is_null() {
return Some(exact as *mut Leaf<K, V>);
}
match header.node_type {
crate::node::NodeType::Node4 => {
let n = &*(ptr.as_inner_ptr() as *const crate::node::Node4);
if n.header.num_children > 0 {
let child =
TaggedPtr::from_raw(n.children[0].load(std::sync::atomic::Ordering::Acquire));
first_leaf_in_subtree(child)
} else {
None
}
}
crate::node::NodeType::Node16 => {
let n = &*(ptr.as_inner_ptr() as *const crate::node::Node16);
if n.header.num_children > 0 {
let child =
TaggedPtr::from_raw(n.children[0].load(std::sync::atomic::Ordering::Acquire));
first_leaf_in_subtree(child)
} else {
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 = TaggedPtr::from_raw(
n.children[slot as usize].load(std::sync::atomic::Ordering::Acquire),
);
return first_leaf_in_subtree(child);
}
}
None
}
crate::node::NodeType::Node256 => {
let n = &*(ptr.as_inner_ptr() as *const crate::node::Node256);
for byte in 0..=255u8 {
let child = TaggedPtr::from_raw(
n.children[byte as usize].load(std::sync::atomic::Ordering::Acquire),
);
if !child.is_null() {
return first_leaf_in_subtree(child);
}
}
None
}
}
}
pub(crate) unsafe fn last_leaf_in_subtree<K, V>(ptr: TaggedPtr) -> Option<*mut Leaf<K, V>> {
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);
let count = n.header.num_children as usize;
if count > 0 {
let child = TaggedPtr::from_raw(
n.children[count - 1].load(std::sync::atomic::Ordering::Acquire),
);
last_leaf_in_subtree(child)
} else {
let exact = header.exact_leaf.load(std::sync::atomic::Ordering::Acquire);
if !exact.is_null() {
Some(exact as *mut Leaf<K, V>)
} else {
None
}
}
}
crate::node::NodeType::Node16 => {
let n = &*(ptr.as_inner_ptr() as *const crate::node::Node16);
let count = n.header.num_children as usize;
if count > 0 {
let child = TaggedPtr::from_raw(
n.children[count - 1].load(std::sync::atomic::Ordering::Acquire),
);
last_leaf_in_subtree(child)
} else {
let exact = header.exact_leaf.load(std::sync::atomic::Ordering::Acquire);
if !exact.is_null() {
Some(exact as *mut Leaf<K, V>)
} else {
None
}
}
}
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 = TaggedPtr::from_raw(
n.children[slot as usize].load(std::sync::atomic::Ordering::Acquire),
);
return last_leaf_in_subtree(child);
}
}
let exact = header.exact_leaf.load(std::sync::atomic::Ordering::Acquire);
if !exact.is_null() {
Some(exact as *mut Leaf<K, V>)
} else {
None
}
}
crate::node::NodeType::Node256 => {
let n = &*(ptr.as_inner_ptr() as *const crate::node::Node256);
for byte in (0..=255u8).rev() {
let child = TaggedPtr::from_raw(
n.children[byte as usize].load(std::sync::atomic::Ordering::Acquire),
);
if !child.is_null() {
return last_leaf_in_subtree(child);
}
}
let exact = header.exact_leaf.load(std::sync::atomic::Ordering::Acquire);
if !exact.is_null() {
Some(exact as *mut Leaf<K, V>)
} else {
None
}
}
}
}