#![deny(unsafe_op_in_unsafe_fn, clippy::undocumented_unsafe_blocks)]
use std::marker::PhantomData;
use std::mem::MaybeUninit;
use std::ptr::NonNull;
use crate::arena::storage::ArenaLeaf;
use crate::arena::Arena;
use crate::key::AsBytes;
use crate::latch::{ChainGuard, ChainLock};
use crate::raw::LeafNode;
use crate::sync::atomic::{AtomicBool, AtomicU32, Ordering};
#[repr(C, align(8))]
pub(crate) struct Leaf<K, V> {
pub(crate) removed: AtomicBool,
next_retired: AtomicU32,
pub(crate) key: K,
pub(crate) value: V,
}
impl<K, V> Leaf<K, V> {
pub(crate) fn new(key: K, value: V) -> Self {
Self {
removed: AtomicBool::new(false),
next_retired: AtomicU32::new(0),
key,
value,
}
}
#[inline]
pub(crate) fn is_removed(&self) -> bool {
self.removed.load(Ordering::Acquire)
}
}
impl<K: AsBytes, V> LeafNode for Leaf<K, V> {
#[inline(always)]
fn key_bytes(&self) -> &[u8] {
self.key.as_bytes()
}
#[inline]
fn mark_removed(&self) {
self.removed.store(true, Ordering::Release);
}
#[inline]
fn is_removed(&self) -> bool {
Leaf::is_removed(self)
}
}
unsafe impl<K, V> ArenaLeaf for Leaf<K, V> {
const NEEDS_DROP: bool = std::mem::needs_drop::<K>() || std::mem::needs_drop::<V>();
#[inline]
fn set_next_retired(&self, next: u32) {
self.next_retired.store(next, Ordering::Relaxed);
}
#[inline]
fn next_retired(&self) -> u32 {
self.next_retired.load(Ordering::Relaxed)
}
unsafe fn drop_in_arena(this: NonNull<Self>, _arena: &Arena) {
unsafe { this.drop_in_place() }
}
}
const SUPERSEDED: u32 = 0b01;
const TOMBSTONE: u32 = 0b10;
const FLAGS: u32 = SUPERSEDED | TOMBSTONE;
#[repr(C, align(8))]
pub(crate) struct VersionNode<V> {
pub(crate) version: u64,
next: AtomicU32,
pub(crate) next_retired: AtomicU32,
value: MaybeUninit<V>,
}
impl<V> VersionNode<V> {
pub(crate) fn new(version: u64, value: Option<V>) -> Self {
let (value, flags) = match value {
Some(v) => (MaybeUninit::new(v), 0),
None => (MaybeUninit::uninit(), TOMBSTONE),
};
Self {
version,
next: AtomicU32::new(flags),
next_retired: AtomicU32::new(0),
value,
}
}
#[inline]
pub(crate) fn is_tombstone(&self) -> bool {
self.next.load(Ordering::Relaxed) & TOMBSTONE != 0
}
#[inline]
pub(crate) fn value(&self) -> Option<&V> {
(!self.is_tombstone()).then(|| unsafe { self.value.assume_init_ref() })
}
pub(crate) fn into_value(self) -> Option<V> {
let this = std::mem::ManuallyDrop::new(self);
(!this.is_tombstone()).then(|| unsafe { std::ptr::read(this.value.as_ptr()) })
}
#[inline]
pub(crate) fn next(&self) -> u32 {
self.next.load(Ordering::Acquire) & !FLAGS
}
#[inline]
fn store_next(&self, next: u32, order: Ordering) {
debug_assert_eq!(next & FLAGS, 0, "version nodes are 8-aligned");
let flags = self.next.load(Ordering::Relaxed) & FLAGS;
self.next.store(next | flags, order);
}
#[inline]
pub(crate) fn init_next(&self, next: u32) {
self.store_next(next, Ordering::Relaxed);
}
#[inline]
pub(crate) fn set_next(&self, _w: &ChainGuard<'_>, next: u32) {
self.store_next(next, Ordering::Release);
}
#[inline]
pub(crate) fn is_superseded(&self) -> bool {
self.next.load(Ordering::Acquire) & SUPERSEDED != 0
}
#[inline]
pub(crate) fn mark_superseded(&self, _w: &ChainGuard<'_>) {
let cur = self.next.load(Ordering::Relaxed);
self.next.store(cur | SUPERSEDED, Ordering::Release);
}
}
impl<V> Drop for VersionNode<V> {
fn drop(&mut self) {
if !self.is_tombstone() {
unsafe { self.value.assume_init_drop() };
}
}
}
#[repr(C, align(8))]
pub(crate) struct VersionedLeaf<K, V> {
head: AtomicU32,
pub(crate) chain_latch: ChainLock,
pub(crate) key: K,
_values: PhantomData<V>,
}
impl<K, V> VersionedLeaf<K, V> {
pub(crate) fn new(key: K, head: u32) -> Self {
Self {
head: AtomicU32::new(head),
chain_latch: ChainLock::new(),
key,
_values: PhantomData,
}
}
#[inline]
pub(crate) fn head(&self) -> u32 {
self.head.load(Ordering::Acquire)
}
#[inline]
pub(crate) fn set_head(&self, w: &ChainGuard<'_>, head: u32) {
debug_assert!(w.holds(&self.chain_latch));
self.head.store(head, Ordering::Release);
}
#[inline]
pub(crate) unsafe fn detach_head_unpublished(&self) {
self.head.store(0, Ordering::Relaxed);
}
}
impl<K: AsBytes, V> LeafNode for VersionedLeaf<K, V> {
#[inline(always)]
fn key_bytes(&self) -> &[u8] {
self.key.as_bytes()
}
#[inline]
fn mark_removed(&self) {
debug_assert!(self.chain_latch.is_dead(), "unlinked with a live chain");
}
#[inline]
fn is_removed(&self) -> bool {
self.chain_latch.is_dead()
}
}
unsafe impl<K, V> ArenaLeaf for VersionedLeaf<K, V> {
const NEEDS_DROP: bool = std::mem::needs_drop::<K>() || std::mem::needs_drop::<V>();
#[inline]
fn set_next_retired(&self, next: u32) {
self.chain_latch.set_retired_link(next);
}
#[inline]
fn next_retired(&self) -> u32 {
self.chain_latch.retired_link()
}
unsafe fn drop_in_arena(this: NonNull<Self>, arena: &Arena) {
let mut off = unsafe { this.as_ref() }.head.load(Ordering::Relaxed);
while off != 0 {
let n = unsafe { arena.ptr::<VersionNode<V>>(off) };
let next = unsafe { n.as_ref() }.next();
unsafe { n.drop_in_place() };
off = next;
}
unsafe { std::ptr::addr_of_mut!((*this.as_ptr()).key).drop_in_place() };
}
}
#[cfg(all(test, not(loom)))]
mod tests {
use super::VersionNode;
#[test]
fn version_nodes_stay_compact() {
assert_eq!(std::mem::size_of::<VersionNode<u64>>(), 24);
assert_eq!(
std::mem::size_of::<super::VersionedLeaf<[u8; 8], u64>>(),
16
);
}
#[test]
fn into_value_moves_the_value_out_once() {
use std::rc::Rc;
let v = Rc::new(1);
let n = VersionNode::new(1, Some(Rc::clone(&v)));
assert_eq!(n.value().map(|v| **v), Some(1));
let out = n.into_value().unwrap();
assert_eq!(Rc::strong_count(&v), 2, "moved, not cloned or dropped");
drop(out);
assert_eq!(Rc::strong_count(&v), 1);
assert!(VersionNode::<Rc<u8>>::new(2, None).into_value().is_none());
}
}