#![deny(unsafe_op_in_unsafe_fn, clippy::undocumented_unsafe_blocks)]
pub(crate) mod cursor;
pub(crate) mod heap;
pub(crate) mod node;
pub(crate) mod read;
pub(crate) mod remove;
pub(crate) mod shrink;
pub(crate) mod slot;
pub(crate) mod walk;
pub(crate) mod write;
use std::cell::Cell;
use std::ptr::NonNull;
use crate::latch::{HybridLatch, WriteGuard};
use crate::sync::atomic::{AtomicIsize, Ordering};
use node::{Node16, Node256, Node4, Node48, NodeHeader, NodeType};
use slot::AtomicSlot;
#[cfg(loom)]
use slot::Slot;
pub(crate) type Raw<S> = <<S as Layout>::Atomic as AtomicSlot>::Raw;
pub(crate) type NodePtr<S> = NonNull<NodeHeader<<S as Layout>::Atomic>>;
pub(crate) trait LeafNode {
fn key_bytes(&self) -> &[u8];
fn mark_removed(&self);
fn is_removed(&self) -> bool;
}
pub(crate) unsafe trait Layout {
type Atomic: AtomicSlot;
type Leaf;
type Full;
unsafe fn node(&self, raw: Raw<Self>) -> NodePtr<Self>;
unsafe fn leaf(&self, raw: Raw<Self>) -> NonNull<Self::Leaf>;
fn node_raw(&self, n: NodePtr<Self>) -> Raw<Self>;
fn leaf_raw(&self, l: NonNull<Self::Leaf>) -> Raw<Self>;
fn alloc_node(&self, ty: NodeType) -> Result<NodePtr<Self>, Self::Full>;
unsafe fn free_node(&self, n: NodePtr<Self>);
unsafe fn free_leaf(&self, l: NonNull<Self::Leaf>);
}
pub(crate) unsafe trait Storage: Layout<Leaf: LeafNode> {
type Guard;
unsafe fn retire_node(&self, n: NodePtr<Self>, guard: &Self::Guard);
unsafe fn retire_leaf(&self, l: NonNull<Self::Leaf>, guard: &Self::Guard);
}
pub(crate) struct RawTree<S: Layout> {
root: S::Atomic,
root_latch: HybridLatch,
len: Counter,
pub(crate) storage: S,
}
const STRIPES: usize = 8;
#[repr(align(128))]
struct Stripe(AtomicIsize);
struct Counter {
stripes: [Stripe; STRIPES],
}
impl Counter {
#[cfg(not(loom))]
const fn new() -> Self {
Self {
stripes: [const { Stripe(AtomicIsize::new(0)) }; STRIPES],
}
}
#[cfg(loom)]
fn new() -> Self {
Self {
stripes: std::array::from_fn(|_| Stripe(AtomicIsize::new(0))),
}
}
#[inline]
fn add(&self, n: isize) {
self.stripes[stripe()].0.fetch_add(n, Ordering::Relaxed);
}
#[inline]
fn sum(&self) -> isize {
self.stripes.iter().fold(0isize, |acc, s| {
acc.wrapping_add(s.0.load(Ordering::Relaxed))
})
}
}
#[inline]
fn stripe() -> usize {
static NEXT: std::sync::atomic::AtomicUsize = std::sync::atomic::AtomicUsize::new(0);
std::thread_local! {
static STRIPE: usize = NEXT.fetch_add(1, std::sync::atomic::Ordering::Relaxed) % STRIPES;
}
STRIPE.try_with(|s| *s).unwrap_or(0)
}
impl<S: Layout> RawTree<S> {
#[cfg(not(loom))]
pub(crate) const fn new_in(storage: S) -> Self
where
S::Atomic: slot::ConstNull,
{
Self {
root: <S::Atomic as slot::ConstNull>::NULL,
root_latch: HybridLatch::new(),
len: Counter::new(),
storage,
}
}
#[cfg(loom)]
pub(crate) fn new_in(storage: S) -> Self {
Self {
root: S::Atomic::new(Raw::<S>::NULL),
root_latch: HybridLatch::new(),
len: Counter::new(),
storage,
}
}
#[inline]
pub(crate) fn len(&self) -> usize {
self.len.sum().max(0) as usize
}
#[cfg(test)]
pub(crate) fn raw_len(&self) -> isize {
self.len.sum()
}
#[inline]
pub(crate) fn root(&self) -> Raw<S> {
self.root.load(Ordering::Acquire)
}
#[inline]
fn set_root(&self, w: &WriteGuard<'_>, v: Raw<S>) {
debug_assert!(w.holds(&self.root_latch));
self.root.store(v, Ordering::Release);
}
#[inline]
pub(crate) fn len_add(&self, n: isize) {
if n != 0 {
self.len.add(n);
}
}
#[inline(always)]
pub(crate) unsafe fn node_ref(&self, raw: Raw<S>) -> &NodeHeader<S::Atomic> {
unsafe { self.storage.node(raw).as_ref() }
}
#[inline(always)]
pub(crate) unsafe fn leaf_ref(&self, raw: Raw<S>) -> &S::Leaf {
unsafe { self.storage.leaf(raw).as_ref() }
}
}
pub(crate) struct Unpublished<'s, S: Layout> {
leaf: Cell<Option<NonNull<S::Leaf>>>,
storage: &'s S,
}
impl<'s, S: Layout> Unpublished<'s, S> {
pub(crate) unsafe fn new(storage: &'s S, leaf: NonNull<S::Leaf>) -> Self {
Self {
leaf: Cell::new(Some(leaf)),
storage,
}
}
#[inline]
pub(crate) fn ptr(&self) -> NonNull<S::Leaf> {
self.leaf.get().expect("unpublished leaf is armed")
}
#[inline]
pub(crate) fn disarm(&self) {
self.leaf.set(None);
}
}
impl<S: Layout> Drop for Unpublished<'_, S> {
fn drop(&mut self) {
if let Some(l) = self.leaf.take() {
unsafe { self.storage.free_leaf(l) }
}
}
}
pub(crate) struct Prepared<S: Layout> {
inline: [Option<(NodePtr<S>, bool)>; 4],
spill: Vec<(NodePtr<S>, bool)>,
}
impl<S: Layout> Prepared<S> {
#[inline]
pub(crate) fn new() -> Self {
Self {
inline: [None; 4],
spill: Vec::new(),
}
}
fn entries(&mut self) -> impl Iterator<Item = &mut (NodePtr<S>, bool)> {
self.inline
.iter_mut()
.flatten()
.chain(self.spill.iter_mut())
}
pub(crate) fn node(&mut self, s: &S, ty: NodeType) -> Result<NodePtr<S>, S::Full> {
for (n, used) in self.entries() {
if !*used && unsafe { n.as_ref() }.node_type == ty {
*used = true;
unsafe { reinit::<S>(*n) };
return Ok(*n);
}
}
let n = s.alloc_node(ty)?;
let entry = Some((n, true));
if let Some(slot) = self.inline.iter_mut().find(|e| e.is_none()) {
*slot = entry;
} else {
self.spill.push((n, true));
}
Ok(n)
}
#[inline]
pub(crate) fn reset(&mut self) {
for (_, used) in self.entries() {
*used = false;
}
}
#[inline]
pub(crate) fn commit(&mut self) {
for e in self.inline.iter_mut() {
if matches!(e, Some((_, true))) {
*e = None;
}
}
self.spill.retain(|(_, used)| !*used);
}
pub(crate) fn release(&mut self, s: &S) {
for e in self.inline.iter_mut() {
if let Some((n, _)) = e.take() {
unsafe { s.free_node(n) };
}
}
for (n, _) in self.spill.drain(..) {
unsafe { s.free_node(n) };
}
}
}
unsafe fn reinit<S: Layout>(n: NodePtr<S>) {
unsafe {
match n.as_ref().node_type {
NodeType::Node4 => n.cast::<Node4<S::Atomic>>().write(Node4::new()),
NodeType::Node16 => n.cast::<Node16<S::Atomic>>().write(Node16::new()),
NodeType::Node48 => n.cast::<Node48<S::Atomic>>().write(Node48::new()),
NodeType::Node256 => n.cast::<Node256<S::Atomic>>().write(Node256::new()),
}
}
}
#[derive(Copy, Clone, PartialEq, Eq, Debug)]
pub(crate) enum Mode {
Replace,
InsertIfAbsent,
}
pub(crate) enum Outcome<L> {
Inserted(NonNull<L>),
Replaced(NonNull<L>),
Existing(NonNull<L>),
}
#[inline]
pub(crate) fn boxed<T>(v: T) -> NonNull<T> {
unsafe { NonNull::new_unchecked(Box::into_raw(Box::new(v))) }
}
#[inline]
pub(crate) fn common_prefix(a: &[u8], b: &[u8]) -> usize {
a.iter().zip(b).take_while(|(x, y)| x == y).count()
}
#[cfg(all(test, not(loom)))]
mod counter_tests {
use super::{Counter, STRIPES};
#[test]
fn striped_sum_is_exact_at_quiescence() {
let c = std::sync::Arc::new(Counter::new());
let threads = STRIPES * 2;
let per = if cfg!(miri) { 50 } else { 20_000 };
let hs: Vec<_> = (0..threads)
.map(|t| {
let c = std::sync::Arc::clone(&c);
std::thread::spawn(move || {
for _ in 0..per {
c.add(if t % 2 == 0 { 1 } else { -1 });
}
c.add(1);
})
})
.collect();
for h in hs {
h.join().unwrap();
}
assert_eq!(c.sum(), threads as isize);
}
}