#![allow(clippy::missing_errors_doc)]
use core::cell::UnsafeCell;
use core::mem::MaybeUninit;
use core::sync::atomic::{AtomicI64, Ordering, fence};
use std::sync::Arc;
#[derive(Debug, PartialEq, Eq)]
pub enum Steal<T> {
Success(T),
Empty,
Retry,
}
#[repr(C, align(64))]
struct Header<T> {
top: AtomicI64,
_pad_top: [u8; 56],
bottom: AtomicI64,
_pad_bottom: [u8; 56],
capacity: usize,
capacity_mask: i64,
buffer: Box<[UnsafeCell<MaybeUninit<T>>]>,
}
unsafe impl<T: Send> Send for Header<T> {}
unsafe impl<T: Send> Sync for Header<T> {}
impl<T> Drop for Header<T> {
fn drop(&mut self) {
let t = self.top.load(Ordering::Relaxed);
let b = self.bottom.load(Ordering::Relaxed);
let mut i = t;
while i < b {
let idx = (i & self.capacity_mask) as usize;
unsafe {
(*self.buffer[idx].get()).assume_init_drop();
}
i += 1;
}
}
}
pub struct Worker<T> {
inner: Arc<Header<T>>,
}
pub struct Stealer<T> {
inner: Arc<Header<T>>,
}
impl<T> Clone for Stealer<T> {
fn clone(&self) -> Self {
Self {
inner: Arc::clone(&self.inner),
}
}
}
pub fn new_chase_lev<T>(capacity: usize) -> (Worker<T>, Stealer<T>) {
let capacity = capacity.max(2).next_power_of_two();
let mut buf = Vec::with_capacity(capacity);
for _ in 0..capacity {
buf.push(UnsafeCell::new(MaybeUninit::uninit()));
}
let inner = Arc::new(Header {
top: AtomicI64::new(0),
_pad_top: [0u8; 56],
bottom: AtomicI64::new(0),
_pad_bottom: [0u8; 56],
capacity,
capacity_mask: (capacity as i64) - 1,
buffer: buf.into_boxed_slice(),
});
let w = Worker {
inner: Arc::clone(&inner),
};
let s = Stealer { inner };
(w, s)
}
impl<T> Worker<T> {
#[inline(always)]
pub fn push(&self, item: T) -> Result<(), T> {
let h = &*self.inner;
let b = h.bottom.load(Ordering::Relaxed);
let t = h.top.load(Ordering::Acquire);
let size = b - t;
if size >= h.capacity as i64 {
return push_full_cold(item);
}
let idx = (b & h.capacity_mask) as usize;
unsafe {
(*h.buffer.get_unchecked(idx).get()).write(item);
}
h.bottom.store(b + 1, Ordering::Release);
Ok(())
}
#[inline]
pub fn pop(&self) -> Steal<T> {
let h = &*self.inner;
let b = h.bottom.load(Ordering::Relaxed) - 1;
h.bottom.store(b, Ordering::Relaxed);
fence(Ordering::SeqCst);
let t = h.top.load(Ordering::Relaxed);
if t > b {
h.bottom.store(b + 1, Ordering::Relaxed);
return Steal::Empty;
}
let idx = (b & h.capacity_mask) as usize;
let item = unsafe { (*h.buffer.get_unchecked(idx).get()).assume_init_read() };
if t < b {
return Steal::Success(item);
}
let won = h
.top
.compare_exchange(t, t + 1, Ordering::SeqCst, Ordering::Relaxed)
.is_ok();
h.bottom.store(b + 1, Ordering::Relaxed);
if won {
Steal::Success(item)
} else {
core::mem::forget(item);
Steal::Empty
}
}
pub fn stealer(&self) -> Stealer<T> {
Stealer {
inner: Arc::clone(&self.inner),
}
}
#[inline]
pub fn is_empty(&self) -> bool {
let h = &*self.inner;
let b = h.bottom.load(Ordering::Acquire);
let t = h.top.load(Ordering::Acquire);
b <= t
}
#[inline]
pub fn capacity(&self) -> usize {
self.inner.capacity
}
#[inline]
pub fn len(&self) -> usize {
let h = &*self.inner;
let b = h.bottom.load(Ordering::Acquire);
let t = h.top.load(Ordering::Acquire);
(b - t).max(0) as usize
}
#[inline(always)]
pub unsafe fn slot_ptr(&self, idx: i64) -> *const T {
let h = &*self.inner;
let slot_idx = (idx & h.capacity_mask) as usize;
unsafe { h.buffer.get_unchecked(slot_idx).get() as *const T }
}
}
#[cold]
#[inline(never)]
fn push_full_cold<T>(item: T) -> Result<(), T> {
Err(item)
}
impl<T> Stealer<T> {
#[inline]
pub fn steal(&self) -> Steal<T> {
let h = &*self.inner;
let t = h.top.load(Ordering::Acquire);
fence(Ordering::SeqCst);
let b = h.bottom.load(Ordering::Acquire);
if t >= b {
return Steal::Empty;
}
let idx = (t & h.capacity_mask) as usize;
let item = unsafe { (*h.buffer.get_unchecked(idx).get()).assume_init_read() };
let won = h
.top
.compare_exchange(t, t + 1, Ordering::SeqCst, Ordering::Relaxed)
.is_ok();
if won {
Steal::Success(item)
} else {
core::mem::forget(item);
Steal::Retry
}
}
#[inline]
pub fn prefetch_for_steal(&self) {
let h = &*self.inner;
let t = h.top.load(Ordering::Relaxed);
let idx = (t & h.capacity_mask) as usize;
let slot = h.buffer[idx].get() as *const u8;
#[cfg(target_arch = "x86_64")]
{
unsafe {
std::arch::x86_64::_mm_prefetch(
slot as *const i8,
std::arch::x86_64::_MM_HINT_T0,
);
}
}
#[cfg(not(target_arch = "x86_64"))]
{
std::hint::black_box(slot);
}
}
#[inline]
pub fn is_empty(&self) -> bool {
let h = &*self.inner;
let b = h.bottom.load(Ordering::Acquire);
let t = h.top.load(Ordering::Acquire);
b <= t
}
}
#[cfg(test)]
mod tests {
use super::*;
use std::sync::Arc;
use std::sync::atomic::{AtomicUsize, Ordering as O};
use std::thread;
#[test]
fn push_then_pop_is_lifo() {
let (w, _s) = new_chase_lev::<u32>(8);
w.push(1).unwrap();
w.push(2).unwrap();
w.push(3).unwrap();
assert_eq!(w.pop(), Steal::Success(3));
assert_eq!(w.pop(), Steal::Success(2));
assert_eq!(w.pop(), Steal::Success(1));
assert_eq!(w.pop(), Steal::Empty);
}
#[test]
fn steal_drains_fifo() {
let (w, s) = new_chase_lev::<u32>(8);
w.push(1).unwrap();
w.push(2).unwrap();
w.push(3).unwrap();
assert_eq!(s.steal(), Steal::Success(1));
assert_eq!(s.steal(), Steal::Success(2));
assert_eq!(s.steal(), Steal::Success(3));
assert_eq!(s.steal(), Steal::Empty);
}
#[test]
fn capacity_rounds_to_power_of_two() {
let (w, _s) = new_chase_lev::<u32>(5);
assert_eq!(w.capacity(), 8);
let (w2, _s2) = new_chase_lev::<u32>(0);
assert_eq!(w2.capacity(), 2);
}
#[test]
fn push_full_returns_err() {
let (w, _s) = new_chase_lev::<u32>(2);
w.push(1).unwrap();
w.push(2).unwrap();
let err = w.push(3).unwrap_err();
assert_eq!(err, 3, "push must return the rejected item back");
}
#[test]
fn empty_pop_returns_empty() {
let (w, _s) = new_chase_lev::<u32>(4);
assert_eq!(w.pop(), Steal::Empty);
}
#[test]
fn empty_steal_returns_empty() {
let (_w, s) = new_chase_lev::<u32>(4);
assert_eq!(s.steal(), Steal::Empty);
}
#[test]
fn prefetch_for_steal_is_safe_on_empty() {
let (_w, s) = new_chase_lev::<u32>(4);
s.prefetch_for_steal();
s.prefetch_for_steal();
}
#[test]
fn prefetch_does_not_disturb_state() {
let (w, s) = new_chase_lev::<u32>(8);
w.push(1).unwrap();
w.push(2).unwrap();
let was_empty_before = w.is_empty();
for _ in 0..16 {
s.prefetch_for_steal();
}
assert_eq!(was_empty_before, w.is_empty());
assert_eq!(s.steal(), Steal::Success(1));
assert_eq!(s.steal(), Steal::Success(2));
assert_eq!(s.steal(), Steal::Empty);
}
#[test]
fn stealer_clone_shares_state() {
let (w, s1) = new_chase_lev::<u32>(8);
let s2 = s1.clone();
w.push(10).unwrap();
w.push(20).unwrap();
assert_eq!(s1.steal(), Steal::Success(10));
assert_eq!(s2.steal(), Steal::Success(20));
assert_eq!(s1.steal(), Steal::Empty);
assert_eq!(s2.steal(), Steal::Empty);
}
#[test]
fn stealer_from_worker_is_same_deque() {
let (w, _s_orig) = new_chase_lev::<u32>(8);
let s = w.stealer();
w.push(42).unwrap();
assert_eq!(s.steal(), Steal::Success(42));
}
#[test]
fn drop_runs_destructors_for_unclaimed_slots() {
use std::sync::atomic::{AtomicUsize, Ordering as O};
#[derive(Debug)]
struct DropCount<'a>(&'a AtomicUsize);
impl Drop for DropCount<'_> {
fn drop(&mut self) {
self.0.fetch_add(1, O::Relaxed);
}
}
let count = AtomicUsize::new(0);
{
let (w, _s) = new_chase_lev::<DropCount<'_>>(4);
w.push(DropCount(&count)).unwrap();
w.push(DropCount(&count)).unwrap();
w.push(DropCount(&count)).unwrap();
}
assert_eq!(count.load(O::Relaxed), 3,
"unclaimed slots must run their destructors when the deque drops");
}
#[test]
fn drop_does_not_double_drop_after_pop() {
use std::sync::atomic::{AtomicUsize, Ordering as O};
#[derive(Debug)]
struct DropCount<'a>(&'a AtomicUsize);
impl Drop for DropCount<'_> {
fn drop(&mut self) {
self.0.fetch_add(1, O::Relaxed);
}
}
let count = AtomicUsize::new(0);
{
let (w, _s) = new_chase_lev::<DropCount<'_>>(4);
w.push(DropCount(&count)).unwrap();
w.push(DropCount(&count)).unwrap();
match w.pop() {
Steal::Success(d) => drop(d),
other => panic!("expected Success, got {other:?}"),
}
assert_eq!(count.load(O::Relaxed), 1, "pop's drop should run");
}
assert_eq!(count.load(O::Relaxed), 2,
"exactly one extra drop should run when deque is dropped with 1 unclaimed slot");
}
#[test]
fn concurrent_owner_push_and_thieves_no_double_take() {
let (w, s_proto) = new_chase_lev::<u32>(64);
let s_proto = Arc::new(s_proto);
let w = Arc::new(w);
let n = 5_000u32;
let consumed = Arc::new(AtomicUsize::new(0));
let sum = Arc::new(AtomicUsize::new(0));
let mut thieves = Vec::new();
for _ in 0..8 {
let s = (*s_proto).clone();
let consumed = Arc::clone(&consumed);
let sum = Arc::clone(&sum);
thieves.push(thread::spawn(move || {
while consumed.load(O::Relaxed) < n as usize {
match s.steal() {
Steal::Success(v) => {
consumed.fetch_add(1, O::Relaxed);
sum.fetch_add(v as usize, O::Relaxed);
}
Steal::Empty | Steal::Retry => std::thread::yield_now(),
}
}
}));
}
let w_owner = Arc::clone(&w);
let consumed_owner = Arc::clone(&consumed);
let sum_owner = Arc::clone(&sum);
let owner = thread::spawn(move || {
let mut i = 0u32;
while i < n {
match w_owner.push(i) {
Ok(()) => i += 1,
Err(_) => {
if let Steal::Success(v) = w_owner.pop() {
consumed_owner.fetch_add(1, O::Relaxed);
sum_owner.fetch_add(v as usize, O::Relaxed);
} else {
std::thread::yield_now();
}
}
}
}
while consumed_owner.load(O::Relaxed) < n as usize {
match w_owner.pop() {
Steal::Success(v) => {
consumed_owner.fetch_add(1, O::Relaxed);
sum_owner.fetch_add(v as usize, O::Relaxed);
}
Steal::Empty | Steal::Retry => std::thread::yield_now(),
}
}
});
owner.join().expect("owner joined");
for h in thieves {
h.join().expect("thief joined");
}
let expected: usize = (0..n as usize).sum();
assert_eq!(
sum.load(O::Relaxed),
expected,
"sum invariant violated: each slot should be consumed exactly once"
);
assert_eq!(consumed.load(O::Relaxed), n as usize);
}
#[test]
fn wraparound_across_capacity_boundary_preserves_ordering() {
let (w, s) = new_chase_lev::<u32>(4);
w.push(0).unwrap();
w.push(1).unwrap();
assert_eq!(w.pop(), Steal::Success(1));
assert_eq!(s.steal(), Steal::Success(0));
w.push(10).unwrap();
w.push(11).unwrap();
w.push(12).unwrap();
w.push(13).unwrap();
assert_eq!(s.steal(), Steal::Success(10));
assert_eq!(s.steal(), Steal::Success(11));
assert_eq!(w.pop(), Steal::Success(13));
assert_eq!(w.pop(), Steal::Success(12));
assert_eq!(w.pop(), Steal::Empty);
}
}