st3/
lib.rs

1//! # St³ — Stealing Static Stack
2//!
3//! Very fast lock-free, bounded, work-stealing queue with FIFO stealing and
4//! LIFO or FIFO semantic for the worker thread.
5//!
6//! The `Worker` handle enables push and pop operations from a single thread,
7//! while `Stealer` handles can be shared between threads to perform FIFO
8//! batch-stealing operations.
9//!
10//! `St³` is effectively a faster, fixed-size alternative to the Chase-Lev
11//! double-ended queue. It uses no atomic fences, much fewer atomic loads and
12//! stores, and fewer Read-Modify-Write operations: none for `push`, one for
13//! `pop` and one (LIFO) or two (FIFO) for `steal`.
14//!
15//! ## Example
16//!
17//! ```
18//! use std::thread;
19//! use st3::lifo::Worker;
20//!
21//! // Push 4 items into a queue of capacity 256.
22//! let worker = Worker::new(256);
23//! worker.push("a").unwrap();
24//! worker.push("b").unwrap();
25//! worker.push("c").unwrap();
26//! worker.push("d").unwrap();
27//!
28//! // Steal items concurrently.
29//! let stealer = worker.stealer();
30//! let th = thread::spawn(move || {
31//!     let other_worker = Worker::new(256);
32//!
33//!     // Try to steal half the items and return the actual count of stolen items.
34//!     match stealer.steal(&other_worker, |n| n/2) {
35//!         Ok(actual) => actual,
36//!         Err(_) => 0,
37//!     }
38//! });
39//!
40//! // Pop items concurrently.
41//! let mut pop_count = 0;
42//! while worker.pop().is_some() {
43//!     pop_count += 1;
44//! }
45//!
46//! // Does it add up?
47//! let steal_count = th.join().unwrap();
48//! assert_eq!(pop_count + steal_count, 4);
49//! ```
50#![warn(missing_docs, missing_debug_implementations, unreachable_pub)]
51#![no_std]
52
53extern crate alloc;
54
55use alloc::boxed::Box;
56use alloc::vec::Vec;
57
58use core::fmt;
59use core::mem::MaybeUninit;
60
61use config::{UnsignedLong, UnsignedShort};
62
63use crate::loom_exports::cell::UnsafeCell;
64
65mod config;
66pub mod fifo;
67pub mod lifo;
68mod loom_exports;
69
70/// Error returned when stealing is unsuccessful.
71#[derive(Debug, Clone, PartialEq, Eq)]
72pub enum StealError {
73    /// No item was stolen.
74    Empty,
75    /// Another concurrent stealing operation is ongoing.
76    Busy,
77}
78
79impl fmt::Display for StealError {
80    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
81        match self {
82            StealError::Empty => write!(f, "cannot steal from empty queue"),
83            StealError::Busy => write!(f, "a concurrent steal operation is ongoing"),
84        }
85    }
86}
87
88#[inline]
89/// Pack two short integers into a long one.
90fn pack(value1: UnsignedShort, value2: UnsignedShort) -> UnsignedLong {
91    ((value1 as UnsignedLong) << UnsignedShort::BITS) | value2 as UnsignedLong
92}
93#[inline]
94/// Unpack a long integer into 2 short ones.
95fn unpack(value: UnsignedLong) -> (UnsignedShort, UnsignedShort) {
96    (
97        (value >> UnsignedShort::BITS) as UnsignedShort,
98        value as UnsignedShort,
99    )
100}
101
102fn allocate_buffer<T>(len: usize) -> Box<[UnsafeCell<MaybeUninit<T>>]> {
103    let mut buffer = Vec::with_capacity(len);
104
105    // Note: resizing the vector would normally be an O(N) operation due to
106    // initialization, but initialization is optimized out in release mode since
107    // an `UnsafeCell<MaybeUninit>` does not actually need to be initialized as
108    // `UnsafeCell` is `repr(transparent)`.
109    buffer.resize_with(len, || UnsafeCell::new(MaybeUninit::uninit()));
110
111    buffer.into_boxed_slice()
112}
st3/lib.rs

st3/
lib.rs
