Skip to main content

concurrent_sharded_stack/
lib.rs

1//! A value-owning sharded stack backed by `concurrent-intrusive-collections`.
2//!
3//! Values are LIFO within each shard; empty scans and close are not global atomic
4//! operations. The underlying intrusive nodes are private implementation details.
5//! Payloads require `Send + 'static`, but do not need `Sync` or `Clone`.
6//!
7//! ```
8//! use concurrent_sharded_stack::{ConcurrentShardedStack, PopError};
9//! let stack = ConcurrentShardedStack::with_concurrency(4);
10//! stack.push(1).unwrap();
11//! stack.push(2).unwrap();
12//! assert_eq!(stack.pop(), Ok(2));
13//! assert_eq!(stack.pop(), Ok(1));
14//! assert_eq!(stack.pop(), Err(PopError::Empty));
15//! ```
16
17#![forbid(unsafe_op_in_unsafe_fn)]
18#![deny(missing_docs)]
19
20use concurrent_intrusive_collections::{
21    AtomicLink as Atomic, ConcurrentShardedStack as IntrusiveStack, SinglyLinked,
22};
23use std::cell::UnsafeCell;
24use std::fmt;
25
26pub use concurrent_intrusive_collections::PopError;
27
28/// A rejected push, retaining ownership of the original value.
29#[derive(Debug, PartialEq, Eq)]
30pub enum PushError<T> {
31    /// The target shard was closed.
32    Closed(T),
33}
34
35impl<T> PushError<T> {
36    /// Recovers the value that was not inserted.
37    pub fn into_inner(self) -> T {
38        match self {
39            Self::Closed(value) => value,
40        }
41    }
42}
43
44impl<T> fmt::Display for PushError<T> {
45    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
46        f.write_str("stack is closed")
47    }
48}
49impl<T: fmt::Debug> std::error::Error for PushError<T> {}
50
51struct Node<T> {
52    next: Atomic<Self>,
53    value: UnsafeCell<Option<T>>,
54}
55
56// SAFETY: the link is a fixed private field, never exposed to users or changed
57// by this wrapper after publication. Drop does not follow the non-owning link.
58unsafe impl<T> SinglyLinked for Node<T> {
59    unsafe fn next(&self) -> &Atomic<Self> {
60        &self.next
61    }
62}
63
64// SAFETY: concurrent stack readers access only next. Exactly one successful pop
65// callback takes value, while its epoch guard prevents Node from being dropped.
66// Rejection accesses an unpublished Owned<Node>; destruction has exclusive
67// access after the grace period. No payload references escape through this type.
68// A value can move between threads, so T: Send is required; T: Sync is not.
69unsafe impl<T: Send> Sync for Node<T> {}
70
71impl<T> Node<T> {
72    fn new(value: T) -> Self {
73        Self {
74            next: Atomic::null(),
75            value: UnsafeCell::new(Some(value)),
76        }
77    }
78
79    // Caller must be the unique successful pop callback for this node. This
80    // does not mutate links or form an exclusive reference to the complete node.
81    unsafe fn take(&self) -> T {
82        unsafe { &mut *self.value.get() }
83            .take()
84            .expect("node consumed twice")
85    }
86}
87
88/// A value-owning concurrent stack with LIFO ordering within each shard.
89///
90/// Delegates linking, XOR probing, closing and epoch reclamation to
91/// `concurrent-intrusive-collections`. A private node allocation stores each
92/// value. A successful pop moves out the value immediately; only the empty node
93/// allocation waits for the epoch grace period. No intrusive API is exposed.
94///
95/// `Empty` describes a scan, not a global snapshot. Close takes effect per shard.
96/// Values may be sent to another thread, but need not be shareable by reference:
97///
98/// ```
99/// use std::cell::Cell;
100/// use concurrent_sharded_stack::ConcurrentShardedStack;
101/// let stack = ConcurrentShardedStack::new();
102/// stack.push(Cell::new(7)).unwrap();
103/// assert_eq!(stack.pop().unwrap().get(), 7);
104/// ```
105pub struct ConcurrentShardedStack<T: Send + 'static> {
106    inner: IntrusiveStack<Node<T>>,
107}
108
109impl<T: Send + 'static> Default for ConcurrentShardedStack<T> {
110    fn default() -> Self {
111        Self::new()
112    }
113}
114
115impl<T: Send + 'static> ConcurrentShardedStack<T> {
116    /// Uses available parallelism rounded up to a power of two (fallback: four).
117    pub fn new() -> Self {
118        Self {
119            inner: IntrusiveStack::new(),
120        }
121    }
122
123    /// Uses exactly `shard_count` shards.
124    ///
125    /// # Panics
126    /// Panics unless the count is a nonzero power of two.
127    pub fn with_concurrency(shard_count: usize) -> Self {
128        Self {
129            inner: IntrusiveStack::with_concurrency(shard_count),
130        }
131    }
132
133    /// Pushes a value to this thread's shard, or returns it if that shard is closed.
134    pub fn push(&self, value: T) -> Result<(), PushError<T>> {
135        self.inner
136            .push(Box::new(Node::new(value)))
137            .map_err(|error| {
138                let mut node = error.into_inner();
139                PushError::Closed(
140                    node.value
141                        .get_mut()
142                        .take()
143                        .expect("unpublished node is occupied"),
144                )
145            })
146    }
147
148    /// Removes and returns one owned value, scanning local then XOR-ordered shards.
149    ///
150    /// A successful pop takes the payload exactly once while the node is pinned.
151    /// With active producers, retry `Empty`; it is not a completion signal.
152    pub fn pop(&self) -> Result<T, PopError> {
153        // SAFETY: the underlying stack invokes this callback only for its unique
154        // head-CAS winner, with the removed node protected by an epoch guard.
155        self.inner.pop_with(|node| unsafe { node.take() })
156    }
157
158    /// Closes every shard, preserving queued values for draining.
159    ///
160    /// Returns whether this call closed at least one shard. Concurrent callers
161    /// may both return true. After return all subsequent pushes are rejected.
162    pub fn close(&self) -> bool {
163        self.inner.close()
164    }
165
166    /// Returns whether every shard was observed closed.
167    pub fn is_closed(&self) -> bool {
168        self.inner.is_closed()
169    }
170
171    /// Returns whether every shard was observed empty during a scan.
172    pub fn is_empty(&self) -> bool {
173        self.inner.is_empty()
174    }
175
176    /// Returns the number of shards.
177    pub fn shard_count(&self) -> usize {
178        self.inner.shard_count()
179    }
180}
181
182impl<T: Send + 'static> Drop for ConcurrentShardedStack<T> {
183    fn drop(&mut self) {
184        // Preserve synchronous payload destruction, including draining the rest
185        // after one destructor panics. A second panic during unwind aborts as usual.
186        let cleanup = scopeguard::guard(&self.inner, |inner| {
187            while let Ok(value) = inner.pop_with(|node| unsafe { node.take() }) {
188                drop(value);
189            }
190        });
191        while let Ok(value) = cleanup.pop_with(|node| unsafe { node.take() }) {
192            drop(value);
193        }
194        // All take calls above are unique successful pops. Deferred nodes are
195        // now empty; their later destruction cannot access a popped payload.
196    }
197}
198
199#[cfg(test)]
200#[path = "tests/value.rs"]
201mod tests;