use std::{
alloc::{self, Layout},
marker::PhantomData,
mem,
ptr::{self, NonNull},
slice,
sync::atomic::{
AtomicUsize,
Ordering::{Acquire, Relaxed, Release},
fence,
},
};
#[repr(C)]
struct Head<H> {
rc: AtomicUsize,
count: u32,
cap: u32,
h: H,
}
pub(crate) struct Raw<H, T> {
ptr: NonNull<Head<H>>,
own: PhantomData<(H, T)>,
}
unsafe impl<H: Send + Sync, T: Send + Sync> Send for Raw<H, T> {}
unsafe impl<H: Send + Sync, T: Send + Sync> Sync for Raw<H, T> {}
impl<H, T> Raw<H, T> {
fn layout(cap: usize) -> (Layout, usize) {
let items = Layout::array::<T>(cap).expect("node size");
let (l, off) = Layout::new::<Head<H>>().extend(items).expect("node size");
(l.pad_to_align(), off)
}
fn head(&self) -> &Head<H> {
unsafe { self.ptr.as_ref() }
}
fn base(&self) -> *mut T {
unsafe { self.ptr.as_ptr().cast::<u8>().add(Self::layout(0).1).cast() }
}
fn count(&self) -> usize {
self.head().count as usize
}
fn cap(&self) -> usize {
self.head().cap as usize
}
fn alloc(h: H, cap: usize) -> Self {
let cap32 = u32::try_from(cap).expect("a node holds fewer than 2^32 items");
let layout = Self::layout(cap).0;
let raw = unsafe { alloc::alloc(layout) }.cast::<Head<H>>();
let Some(ptr) = NonNull::new(raw) else { alloc::handle_alloc_error(layout) };
let head = Head { rc: AtomicUsize::new(1), count: 0, cap: cap32, h };
unsafe { ptr.write(head) };
Self { ptr, own: PhantomData }
}
pub(crate) fn new(h: H, cap: usize, items: impl IntoIterator<Item = T>) -> Self {
let mut node = Self::alloc(h, cap);
struct Written<T>(*mut T, usize);
impl<T> Drop for Written<T> {
fn drop(&mut self) {
unsafe {
ptr::drop_in_place(ptr::slice_from_raw_parts_mut(self.0, self.1))
}
}
}
let mut written = Written(node.base(), 0);
for item in items.into_iter().take(cap) {
unsafe { written.0.add(written.1).write(item) };
written.1 += 1;
}
let count = written.1 as u32;
mem::forget(written);
unsafe { node.ptr.as_mut().count = count };
node
}
pub(crate) fn header(&self) -> &H {
&self.head().h
}
pub(crate) fn items(&self) -> &[T] {
unsafe { slice::from_raw_parts(self.base(), self.count()) }
}
pub(crate) fn addr(&self) -> usize {
self.ptr.as_ptr() as usize
}
pub(crate) fn ptr_eq(&self, other: &Self) -> bool {
self.ptr == other.ptr
}
fn is_unique(&self) -> bool {
self.head().rc.load(Acquire) == 1
}
pub(crate) fn release(self, grave: &mut Vec<Self>) {
let this = mem::ManuallyDrop::new(self);
if this.head().rc.fetch_sub(1, Release) != 1 {
return;
}
fence(Acquire);
this.head().rc.store(1, Relaxed);
let this = mem::ManuallyDrop::into_inner(this);
if this.count() == 0 { drop(this) } else { grave.push(this) }
}
#[inline]
pub(crate) fn make_mut(&mut self, grave: &mut Vec<Self>) -> RawMut<'_, H, T>
where
H: Clone,
T: Clone,
{
if !self.is_unique() {
self.copy(grave)
}
RawMut(self)
}
fn copy(&mut self, grave: &mut Vec<Self>)
where
H: Clone,
T: Clone,
{
let copy =
Self::new(self.header().clone(), self.count(), self.items().iter().cloned());
mem::replace(self, copy).release(grave);
}
#[inline]
pub(crate) fn push(&mut self, item: T, grave: &mut Vec<Self>)
where
H: Clone,
T: Clone,
{
if self.is_unique() {
RawMut(self).push(item)
} else {
self.copy_with(item, grave)
}
}
fn copy_with(&mut self, item: T, grave: &mut Vec<Self>)
where
H: Clone,
T: Clone,
{
let items = self.items().iter().cloned().chain([item]);
let copy = Self::new(self.header().clone(), self.count() + 1, items);
mem::replace(self, copy).release(grave);
}
pub(crate) fn swap_remove(&mut self, i: usize, grave: &mut Vec<Self>) -> T
where
H: Clone,
T: Clone,
{
if self.is_unique() {
return RawMut(self).swap_remove(i);
}
let s = self.items();
let (last, init) = s.split_last().expect("an item to remove");
let removed = s[i].clone();
let items = init.iter().enumerate().map(|(j, x)| if j == i { last } else { x });
let copy = Self::new(self.header().clone(), s.len() - 1, items.cloned());
mem::replace(self, copy).release(grave);
removed
}
pub(crate) fn take_items(&mut self) -> Vec<T>
where
T: Clone,
{
if !self.is_unique() {
return self.items().to_vec();
}
let n = self.count();
let mut v = Vec::with_capacity(n);
unsafe {
ptr::copy_nonoverlapping(self.base(), v.as_mut_ptr(), n);
self.ptr.as_mut().count = 0;
v.set_len(n);
}
v
}
}
impl<H, T> Clone for Raw<H, T> {
fn clone(&self) -> Self {
if self.head().rc.fetch_add(1, Relaxed) > isize::MAX as usize {
std::process::abort()
}
Self { ptr: self.ptr, own: PhantomData }
}
}
impl<H, T> Drop for Raw<H, T> {
fn drop(&mut self) {
if self.head().rc.fetch_sub(1, Release) != 1 {
return;
}
fence(Acquire);
struct Free<H>(NonNull<Head<H>>, Layout);
impl<H> Drop for Free<H> {
fn drop(&mut self) {
unsafe {
ptr::drop_in_place(&mut (*self.0.as_ptr()).h);
alloc::dealloc(self.0.as_ptr().cast(), self.1);
}
}
}
let _free = Free(self.ptr, Self::layout(self.cap()).0);
unsafe {
ptr::drop_in_place(ptr::slice_from_raw_parts_mut(self.base(), self.count()))
}
}
}
pub(crate) struct RawMut<'a, H, T>(&'a mut Raw<H, T>);
impl<'a, H, T> RawMut<'a, H, T> {
pub(crate) fn header(&mut self) -> &mut H {
unsafe { &mut self.0.ptr.as_mut().h }
}
pub(crate) fn parts(&mut self) -> (&mut H, &mut [T]) {
unsafe {
let items = slice::from_raw_parts_mut(self.0.base(), self.0.count());
(&mut self.0.ptr.as_mut().h, items)
}
}
pub(crate) fn into_items(self) -> &'a mut [T] {
unsafe { slice::from_raw_parts_mut(self.0.base(), self.0.count()) }
}
fn grow(&mut self) {
let count = self.0.count();
let cap = (count + 1).next_power_of_two();
unsafe {
let h = ptr::read(&self.0.ptr.as_ref().h);
let mut new = Raw::<H, T>::alloc(h, cap);
ptr::copy_nonoverlapping(self.0.base(), new.base(), count);
new.ptr.as_mut().count = count as u32;
let old = mem::replace(self.0, new);
alloc::dealloc(old.ptr.as_ptr().cast(), Raw::<H, T>::layout(old.cap()).0);
mem::forget(old);
}
}
#[inline]
pub(crate) fn push(&mut self, item: T) {
let count = self.0.count();
if count == self.0.cap() {
self.grow()
}
unsafe {
self.0.base().add(count).write(item);
self.0.ptr.as_mut().count += 1;
}
}
pub(crate) fn swap_remove(&mut self, i: usize) -> T {
let count = self.0.count();
assert!(i < count);
unsafe {
let base = self.0.base();
let item = base.add(i).read();
if i != count - 1 {
ptr::copy_nonoverlapping(base.add(count - 1), base.add(i), 1);
}
self.0.ptr.as_mut().count -= 1;
item
}
}
}