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;