Skip to main content

concurrent_intrusive_collections/
lib.rs

1//! Intrusive concurrent collections backed by Crossbeam's epoch collector.
2//!
3//! Nodes implement [`SinglyLinked`] and, optionally, [`DoublyLinked`]. Links
4//! point directly to complete nodes, so there are no adapters or link-to-node
5//! conversions. The default `std` feature enables the sharded stack, sharded
6//! `ConcurrentShardedQueue`.
7//! Disabling it leaves the link traits and the `alloc`-enabled [`epoch`] API.
8//!
9//! # Choosing a collection
10//!
11//! - `ConcurrentShardedQueue`: per-shard FIFO with local enqueue and XOR probing.
12//! - `ConcurrentShardedStack`: per-shard LIFO with local push and XOR probing.
13//!
14//! Collections take ownership through `Box<T>` and return results from
15//! shared-borrow callbacks. They do not return removed nodes for immediate reuse.
16//! Queue shards retain their last consumed node as a dummy until the next pop
17//! or destruction. See each collection for ordering and reclamation semantics.
18//!
19//! Rust 1.85 or newer and pointer-width atomic operations are required.
20
21#![cfg_attr(not(feature = "std"), no_std)]
22#![forbid(unsafe_op_in_unsafe_fn)]
23#![deny(missing_docs)]
24
25#[cfg(not(target_has_atomic = "ptr"))]
26compile_error!("concurrent-intrusive-collections requires pointer-width atomics");
27
28pub use crossbeam_epoch as epoch;
29
30/// An atomic forward/backward link stored privately in an intrusive node.
31///
32/// This is Crossbeam's atomic pointer type, reexported for implementing the link
33/// traits. Link access must follow the owning collection's safety protocol.
34pub use crossbeam_epoch::Atomic as AtomicLink;
35
36#[cfg(feature = "std")]
37mod error;
38#[cfg(feature = "std")]
39mod fifo_queue;
40#[cfg(feature = "std")]
41mod helper;
42#[cfg(feature = "std")]
43mod queue;
44#[cfg(feature = "std")]
45mod stack;
46#[cfg(feature = "std")]
47pub use error::{PopError, PushError};
48#[cfg(feature = "std")]
49pub use queue::ConcurrentShardedQueue;
50#[cfg(feature = "std")]
51pub use stack::ConcurrentShardedStack;
52
53/// A node containing an atomic forward link to another complete node.
54///
55/// Implement this trait on the node itself. Keep the link field private;
56/// collections obtain access through the unsafe accessor below.
57///
58/// # Safety
59///
60/// - `next` must always return the same initialized atomic field embedded in
61///   `self`. Distinct live nodes must have distinct link fields.
62/// - The accessor must not panic, modify the link, or invalidate the node.
63/// - Safe APIs must not allow the link to be changed independently while a
64///   collection owns the node, including its retirement period. In particular,
65///   do not expose the atomic through a public field or another safe accessor.
66/// - The link is non-owning. The node's destructor must not follow, dereference,
67///   or reclaim its successor: by destruction time the successor may be gone.
68///
69/// Collections must keep published nodes at stable addresses and synchronize
70/// access and reclamation. Implementing this trait alone does not do so.
71pub unsafe trait SinglyLinked: Sized {
72    /// Returns the node's forward link.
73    ///
74    /// # Safety
75    ///
76    /// All uses of the returned atomic must follow the owning collection's
77    /// synchronization, ownership, and reclamation protocol. Loading a pointer
78    /// does not by itself make that pointer valid to dereference.
79    unsafe fn next(&self) -> &AtomicLink<Self>;
80}
81
82/// A node that also contains an atomic backward link.
83///
84/// This only describes storage; updating two atomic links is not one atomic
85/// operation. A doubly linked collection must supply its own update protocol.
86///
87/// # Safety
88///
89/// `prev` has the same requirements as [`SinglyLinked::next`], and must return
90/// a different atomic field from `next` in the same node. Neither link owns
91/// the node to which it points.
92pub unsafe trait DoublyLinked: SinglyLinked {
93    /// Returns the node's backward link.
94    ///
95    /// # Safety
96    ///
97    /// All uses of the returned atomic must follow the owning collection's
98    /// synchronization, ownership, and reclamation protocol.
99    unsafe fn prev(&self) -> &AtomicLink<Self>;
100}