#![deny(unsafe_op_in_unsafe_fn, clippy::undocumented_unsafe_blocks)]
use std::alloc::Layout as AllocLayout;
use std::ptr::NonNull;
use std::sync::Arc;
use crate::arena::Arena;
use crate::raw::heap::Invariant;
use crate::raw::node::{Node16, Node256, Node4, Node48, NodeHeader, NodeType};
use crate::raw::slot::TaggedOffset;
use crate::raw::{Layout, LeafNode, Storage};
use crate::sync::atomic::{AtomicU32, Ordering};
#[derive(Copy, Clone, Debug)]
pub(crate) struct Full;
pub(crate) unsafe trait ArenaLeaf {
const NEEDS_DROP: bool;
fn set_next_retired(&self, next: u32);
fn next_retired(&self) -> u32;
unsafe fn drop_in_arena(this: NonNull<Self>, arena: &Arena);
}
pub(crate) struct ArenaStorage<L: ArenaLeaf> {
pub(crate) arena: Arc<Arena>,
retired: AtomicU32,
_marker: Invariant<L>,
}
unsafe impl<L: ArenaLeaf + Send + Sync> Send for ArenaStorage<L> {}
unsafe impl<L: ArenaLeaf + Send + Sync> Sync for ArenaStorage<L> {}
impl<L: ArenaLeaf> ArenaStorage<L> {
pub(crate) fn new(arena: Arc<Arena>) -> Self {
const {
assert!(std::mem::align_of::<Node256<AtomicU32>>() <= crate::arena::ARENA_ALIGN);
}
Self {
arena,
retired: AtomicU32::new(0),
_marker: std::marker::PhantomData,
}
}
pub(crate) fn alloc_value<T>(&self, value: T) -> Result<NonNull<T>, (Full, T)> {
const {
assert!(std::mem::align_of::<T>() <= crate::arena::ARENA_ALIGN);
}
match self.arena.alloc(AllocLayout::new::<T>()) {
Some(off) => {
let p = unsafe { self.arena.ptr::<T>(off) };
unsafe { p.write(value) };
Ok(p)
}
None => Err((Full, value)),
}
}
}
fn place<N>(arena: &Arena, node: N) -> Result<NonNull<NodeHeader<AtomicU32>>, Full> {
let off = arena.alloc(AllocLayout::new::<N>()).ok_or(Full)?;
let p = unsafe { arena.ptr::<N>(off) };
unsafe { p.write(node) };
Ok(p.cast())
}
unsafe impl<L: ArenaLeaf> Layout for ArenaStorage<L> {
type Atomic = AtomicU32;
type Leaf = L;
type Full = Full;
#[inline(always)]
unsafe fn node(&self, raw: TaggedOffset) -> NonNull<NodeHeader<AtomicU32>> {
unsafe { self.arena.ptr(raw.offset()) }
}
#[inline(always)]
unsafe fn leaf(&self, raw: TaggedOffset) -> NonNull<L> {
unsafe { self.arena.ptr(raw.offset()) }
}
#[inline(always)]
fn node_raw(&self, n: NonNull<NodeHeader<AtomicU32>>) -> TaggedOffset {
TaggedOffset::from_inner(self.arena.offset_of(n))
}
#[inline(always)]
fn leaf_raw(&self, l: NonNull<L>) -> TaggedOffset {
TaggedOffset::from_leaf(self.arena.offset_of(l))
}
fn alloc_node(&self, ty: NodeType) -> Result<NonNull<NodeHeader<AtomicU32>>, Full> {
match ty {
NodeType::Node4 => place(&self.arena, Node4::<AtomicU32>::new()),
NodeType::Node16 => place(&self.arena, Node16::<AtomicU32>::new()),
NodeType::Node48 => place(&self.arena, Node48::<AtomicU32>::new()),
NodeType::Node256 => place(&self.arena, Node256::<AtomicU32>::new()),
}
}
unsafe fn free_node(&self, _n: NonNull<NodeHeader<AtomicU32>>) {}
unsafe fn free_leaf(&self, l: NonNull<L>) {
unsafe { L::drop_in_arena(l, &self.arena) }
}
}
unsafe impl<L: ArenaLeaf + LeafNode> Storage for ArenaStorage<L> {
type Guard = ();
unsafe fn retire_node(&self, _n: NonNull<NodeHeader<AtomicU32>>, _g: &()) {}
unsafe fn retire_leaf(&self, l: NonNull<L>, _g: &()) {
let off = self.arena.offset_of(l);
let leaf = unsafe { l.as_ref() };
let mut head = self.retired.load(Ordering::Relaxed);
loop {
leaf.set_next_retired(head);
match self.retired.compare_exchange_weak(
head,
off,
Ordering::Release,
Ordering::Relaxed,
) {
Ok(_) => return,
Err(h) => head = h,
}
}
}
}
impl<L: ArenaLeaf> Drop for ArenaStorage<L> {
fn drop(&mut self) {
if !L::NEEDS_DROP {
return;
}
let mut off = self.retired.load(Ordering::Relaxed);
while off != 0 {
let leaf = unsafe { self.arena.ptr::<L>(off) };
let next = unsafe { leaf.as_ref() }.next_retired();
unsafe { L::drop_in_arena(leaf, &self.arena) };
off = next;
}
}
}