#![deny(unsafe_op_in_unsafe_fn, clippy::undocumented_unsafe_blocks)]
use std::ops::{Bound, Deref};
use std::ptr::NonNull;
use crate::arena::node::{VersionNode, VersionedLeaf};
use crate::arena::versioned_tree::{chain, find_le, ArenaVersionedTree, Storage};
use crate::arena::Arena;
use crate::key::AsBytes;
use crate::raw::cursor::{Cursor, KeyBuf};
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct VersionRef<'a, V> {
pub version: u64,
pub value: Option<&'a V>,
}
pub struct ArenaVersionedEntryRef<'a, K, V> {
leaf: NonNull<VersionedLeaf<K, V>>,
node: NonNull<VersionNode<V>>,
arena: &'a Arena,
}
impl<K, V> Clone for ArenaVersionedEntryRef<'_, K, V> {
fn clone(&self) -> Self {
*self
}
}
impl<K, V> Copy for ArenaVersionedEntryRef<'_, K, V> {}
impl<'a, K: 'a, V: 'a> ArenaVersionedEntryRef<'a, K, V> {
pub(crate) unsafe fn new(
leaf: NonNull<VersionedLeaf<K, V>>,
node: u32,
arena: &'a Arena,
) -> Option<Self> {
let n = unsafe { arena.ptr::<VersionNode<V>>(node) };
if unsafe { n.as_ref() }.is_tombstone() {
return None;
}
Some(Self {
leaf,
node: n,
arena,
})
}
#[inline]
fn leaf(&self) -> &'a VersionedLeaf<K, V> {
unsafe { self.leaf.as_ref() }
}
#[inline]
fn node(&self) -> &'a VersionNode<V> {
unsafe { self.node.as_ref() }
}
#[inline]
pub fn key(&self) -> &'a K {
&self.leaf().key
}
#[inline]
pub fn value(&self) -> &'a V {
self.node()
.value()
.expect("an ArenaVersionedEntryRef never captures a tombstone")
}
#[inline]
pub fn version(&self) -> u64 {
self.node().version
}
#[inline]
pub fn is_removed(&self) -> bool {
false
}
#[inline]
pub fn is_superseded(&self) -> bool {
self.node().is_superseded() || self.leaf().chain_latch.is_dead()
}
pub fn versions(&self) -> impl Iterator<Item = VersionRef<'a, V>> + 'a
where
V: 'a,
{
let arena = self.arena;
chain::<V>(arena, arena.offset_of(self.node)).map(|n| VersionRef {
version: n.version,
value: n.value(),
})
}
pub fn get_version_le(&self, max_version: u64) -> Option<(u64, &'a V)> {
let n = find_le::<V>(self.arena, self.leaf().head(), max_version)?;
n.value().map(|v| (n.version, v))
}
pub fn latest(&self) -> Option<Self> {
unsafe { Self::new(self.leaf, self.leaf().head(), self.arena) }
}
}
impl<K, V> Deref for ArenaVersionedEntryRef<'_, K, V> {
type Target = V;
#[inline]
fn deref(&self) -> &V {
self.value()
}
}
impl<K: std::fmt::Debug, V: std::fmt::Debug> std::fmt::Debug for ArenaVersionedEntryRef<'_, K, V> {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.debug_struct("ArenaVersionedEntryRef")
.field("key", self.key())
.field("version", &self.version())
.field("value", self.value())
.finish()
}
}
impl<K: PartialEq, V: PartialEq> PartialEq for ArenaVersionedEntryRef<'_, K, V> {
fn eq(&self, other: &Self) -> bool {
self.key() == other.key()
&& self.version() == other.version()
&& self.value() == other.value()
}
}
impl<K: Eq, V: Eq> Eq for ArenaVersionedEntryRef<'_, K, V> {}
pub struct ArenaVersionedRange<'a, K, V> {
tree: &'a ArenaVersionedTree<K, V>,
cursor: Cursor<Storage<K, V>>,
}
impl<'a, K, V> ArenaVersionedRange<'a, K, V> {
pub(crate) fn new(
tree: &'a ArenaVersionedTree<K, V>,
start: Bound<KeyBuf>,
end: Bound<KeyBuf>,
) -> Self {
Self {
tree,
cursor: Cursor::new(start, end),
}
}
}
impl<'a, K: AsBytes, V> ArenaVersionedRange<'a, K, V> {
#[inline]
fn entry(
&self,
leaf: NonNull<VersionedLeaf<K, V>>,
) -> Option<ArenaVersionedEntryRef<'a, K, V>> {
let head = unsafe { leaf.as_ref() }.head();
unsafe { ArenaVersionedEntryRef::new(leaf, head, self.tree.arena()) }
}
}
impl<'a, K: AsBytes, V> Iterator for ArenaVersionedRange<'a, K, V> {
type Item = ArenaVersionedEntryRef<'a, K, V>;
#[inline(always)]
fn next(&mut self) -> Option<Self::Item> {
loop {
let leaf = self.cursor.next(&self.tree.raw)?;
if let Some(e) = self.entry(leaf) {
return Some(e);
}
}
}
}
impl<K: AsBytes, V> DoubleEndedIterator for ArenaVersionedRange<'_, K, V> {
#[inline(always)]
fn next_back(&mut self) -> Option<Self::Item> {
loop {
let leaf = self.cursor.next_back(&self.tree.raw)?;
if let Some(e) = self.entry(leaf) {
return Some(e);
}
}
}
}
impl<K: AsBytes, V> std::iter::FusedIterator for ArenaVersionedRange<'_, K, V> {}