#![allow(clippy::missing_errors_doc)]
use core::cell::UnsafeCell;
use core::mem::MaybeUninit;
use core::sync::atomic::{AtomicU64, Ordering};
use std::sync::Arc;
#[derive(Debug, PartialEq, Eq)]
pub enum SpscPushResult<T> {
Ok,
Full(T),
}
#[derive(Debug, PartialEq, Eq)]
pub enum SpscPopResult<T> {
Ok(T),
Empty,
}
#[repr(C, align(64))]
struct SpscHeader<T> {
tail: AtomicU64,
_pad_tail: [u8; 56],
head: AtomicU64,
_pad_head: [u8; 56],
capacity: u64,
capacity_mask: u64,
buffer: Box<[UnsafeCell<MaybeUninit<T>>]>,
}
unsafe impl<T: Send> Send for SpscHeader<T> {}
unsafe impl<T: Send> Sync for SpscHeader<T> {}
pub struct Producer<T> {
inner: Arc<SpscHeader<T>>,
}
pub struct Consumer<T> {
inner: Arc<SpscHeader<T>>,
}
unsafe impl<T: Send> Send for Producer<T> {}
unsafe impl<T: Send> Send for Consumer<T> {}
pub fn new_spsc<T: Send>(capacity: usize) -> (Producer<T>, Consumer<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(SpscHeader {
tail: AtomicU64::new(0),
_pad_tail: [0u8; 56],
head: AtomicU64::new(0),
_pad_head: [0u8; 56],
capacity: capacity as u64,
capacity_mask: (capacity as u64) - 1,
buffer: buf.into_boxed_slice(),
});
(
Producer {
inner: Arc::clone(&inner),
},
Consumer { inner },
)
}
impl<T: Send> Producer<T> {
#[inline(always)]
pub fn push(&self, item: T) -> SpscPushResult<T> {
let h = &*self.inner;
let tail = h.tail.load(Ordering::Relaxed);
let head = h.head.load(Ordering::Acquire);
if tail.wrapping_sub(head) >= h.capacity {
core::hint::cold_path();
return SpscPushResult::Full(item);
}
let idx = (tail & h.capacity_mask) as usize;
unsafe {
(*h.buffer.get_unchecked(idx).get()).write(item);
}
h.tail.store(tail + 1, Ordering::Release);
SpscPushResult::Ok
}
}
impl<T: Send> Consumer<T> {
#[inline(always)]
pub fn pop(&self) -> SpscPopResult<T> {
let h = &*self.inner;
let head = h.head.load(Ordering::Relaxed);
let tail = h.tail.load(Ordering::Acquire);
if head >= tail {
core::hint::cold_path();
return SpscPopResult::Empty;
}
let idx = (head & h.capacity_mask) as usize;
let item = unsafe { (*h.buffer.get_unchecked(idx).get()).assume_init_read() };
h.head.store(head + 1, Ordering::Release);
SpscPopResult::Ok(item)
}
}
impl<T> Drop for SpscHeader<T> {
fn drop(&mut self) {
let head = self.head.load(Ordering::Relaxed);
let tail = self.tail.load(Ordering::Relaxed);
let mut pos = head;
while pos < tail {
let idx = (pos & self.capacity_mask) as usize;
unsafe {
(*self.buffer[idx].get()).assume_init_drop();
}
pos += 1;
}
}
}
#[unsafe(no_mangle)]
pub static __flynnel_marker_ring_spsc_push: u8 = 0;
#[unsafe(no_mangle)]
pub static __flynnel_marker_ring_spsc_pop: u8 = 0;
#[cfg(test)]
mod tests {
use super::*;
use std::sync::Arc;
use std::sync::atomic::{AtomicUsize, Ordering as O};
use std::thread;
#[test]
fn push_pop_single_thread() {
let (p, c) = new_spsc::<u32>(8);
assert!(matches!(p.push(1), SpscPushResult::Ok));
assert!(matches!(p.push(2), SpscPushResult::Ok));
assert!(matches!(p.push(3), SpscPushResult::Ok));
assert!(matches!(c.pop(), SpscPopResult::Ok(1)));
assert!(matches!(c.pop(), SpscPopResult::Ok(2)));
assert!(matches!(c.pop(), SpscPopResult::Ok(3)));
assert!(matches!(c.pop(), SpscPopResult::Empty));
}
#[test]
fn full_returns_item_back() {
let (p, _c) = new_spsc::<u32>(2);
assert!(matches!(p.push(1), SpscPushResult::Ok));
assert!(matches!(p.push(2), SpscPushResult::Ok));
match p.push(3) {
SpscPushResult::Full(v) => assert_eq!(v, 3),
_ => panic!("expected Full"),
}
}
#[test]
fn drop_runs_destructors_for_unclaimed_slots() {
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 (p, _c) = new_spsc::<DropCount<'_>>(4);
assert!(matches!(p.push(DropCount(&count)), SpscPushResult::Ok));
assert!(matches!(p.push(DropCount(&count)), SpscPushResult::Ok));
assert!(matches!(p.push(DropCount(&count)), SpscPushResult::Ok));
}
assert_eq!(count.load(O::Relaxed), 3);
}
#[test]
fn concurrent_spsc_stress_no_item_loss() {
let (p, c) = new_spsc::<u32>(64);
let n = 50_000u32;
let consumed = Arc::new(AtomicUsize::new(0));
let sum = Arc::new(AtomicUsize::new(0));
let consumed_c = Arc::clone(&consumed);
let sum_c = Arc::clone(&sum);
let consumer = thread::spawn(move || {
while consumed_c.load(O::Relaxed) < n as usize {
match c.pop() {
SpscPopResult::Ok(v) => {
consumed_c.fetch_add(1, O::Relaxed);
sum_c.fetch_add(v as usize, O::Relaxed);
}
SpscPopResult::Empty => std::thread::yield_now(),
}
}
});
let producer = thread::spawn(move || {
for i in 0..n {
loop {
match p.push(i) {
SpscPushResult::Ok => break,
SpscPushResult::Full(_) => std::thread::yield_now(),
}
}
}
});
producer.join().expect("producer");
consumer.join().expect("consumer");
let expected: usize = (0..n as usize).sum();
assert_eq!(consumed.load(O::Relaxed), n as usize);
assert_eq!(sum.load(O::Relaxed), expected,
"sum invariant: each pushed item consumed exactly once");
}
#[test]
fn capacity_rounds_to_power_of_two() {
let (p, _c) = new_spsc::<u32>(5);
for i in 0..8 {
assert!(matches!(p.push(i), SpscPushResult::Ok),
"should fit 8 items (5 rounded to 8)");
}
match p.push(99) {
SpscPushResult::Full(_) => {}
_ => panic!("9th push should be Full"),
}
}
}