parkring 1.0.0

Bounded MPMC channels and queues (Vyukov and SCQ), a Chase-Lev work-stealing deque and a work-stealing thread pool, with futex-based parking. Checked with loom, Miri and fuzzing.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

//! Position arithmetic for the lock-free queue.
//!
//! Positions (`head`, the low bits of `tail`, and every slot sequence) live
//! in `[0, 2^(BITS-1))`. The top bit of `tail` is the closed flag, so every
//! increment masks it out and every comparison is a signed difference modulo
//! `2^(BITS-1)`. Because capacities are powers of two they divide the position
//! space, so `pos & mask` stays consistent when positions wrap.

/// Set in `tail` once the queue is closed. Never cleared.
pub(crate) const CLOSED_BIT: usize = 1 << (usize::BITS - 1);

/// Mask selecting the position bits of `tail`.
pub(crate) const POS_MASK: usize = !CLOSED_BIT;

/// Largest supported capacity. Keeps every in-flight difference far from the
/// sign boundary of [`pos_diff`].
pub(crate) const MAX_CAPACITY: usize = 1 << (usize::BITS - 3);

/// `pos + n` in position space.
#[inline]
pub(crate) const fn pos_add(pos: usize, n: usize) -> usize {
    pos.wrapping_add(n) & POS_MASK
}

/// Signed `a - b` in position space.
///
/// The difference is taken modulo `2^(BITS-1)` and bit `BITS-2` is sign
/// extended, so values that straddle the wrap still compare correctly.
#[inline]
pub(crate) const fn pos_diff(a: usize, b: usize) -> isize {
    (((a.wrapping_sub(b)) & POS_MASK) << 1) as isize >> 1
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn add_wraps_without_touching_closed_bit() {
        assert_eq!(pos_add(POS_MASK, 1), 0);
        assert_eq!(pos_add(POS_MASK - 1, 3), 1);
        assert_eq!(pos_add(5, 3) & CLOSED_BIT, 0);
    }

    #[test]
    fn diff_is_signed_across_the_wrap() {
        assert_eq!(pos_diff(5, 3), 2);
        assert_eq!(pos_diff(3, 5), -2);
        assert_eq!(pos_diff(1, POS_MASK), 2);
        assert_eq!(pos_diff(POS_MASK, 1), -2);
        assert_eq!(pos_diff(0, 0), 0);
    }

    #[test]
    fn diff_ignores_closed_bit_on_either_side() {
        assert_eq!(pos_diff(7 | CLOSED_BIT, 3), 4);
        assert_eq!(pos_diff(7, 3 | CLOSED_BIT), 4);
    }
}