st3 0.3.0

A very fast lock-free, bounded, work-stealing LIFO queue.
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

//! Internal queue buffers of various sizes.

use std::fmt::Debug;
use std::mem::MaybeUninit;

use crate::config::UnsignedShort;
use crate::loom_types::cell::UnsafeCell;

/// Marker trait for fixed-size buffers.
pub trait Buffer<T>: private::Sealed {
    /// Buffer size.
    const CAPACITY: UnsignedShort;

    #[doc(hidden)]
    /// Buffer index bit mask.
    const MASK: UnsignedShort;

    #[doc(hidden)]
    /// Buffer data type.
    type Data: AsRef<[UnsafeCell<MaybeUninit<T>>]> + Debug;

    #[doc(hidden)]
    /// Returns an uninitialized buffer.
    fn allocate() -> Box<Self::Data>;
}

macro_rules! make_buffer {
    ($b:ident, $cap:expr) => {
        #[doc = concat!("Marker type for buffers of capacity ", $cap, ".")]
        #[derive(Copy, Clone, Debug)]
        pub struct $b {}

        impl private::Sealed for $b {}

        impl<T> Buffer<T> for $b {
            const CAPACITY: UnsignedShort = $cap;

            #[doc(hidden)]
            const MASK: UnsignedShort = $cap - 1;

            #[doc(hidden)]
            type Data = [UnsafeCell<MaybeUninit<T>>; $cap];

            #[doc(hidden)]
            #[cfg(not(st3_loom))]
            fn allocate() -> Box<Self::Data> {
                // Safety: initializing an array of `MaybeUninit` items with
                // `assume_init()` is valid, as per the `MaybeUninit` documentation.
                // Admittedly the situation is slightly different here: the buffer is
                // made of `MaybeUninit` elements wrapped in `UnsafeCell`s; however, the
                // latter is a `repr(transparent)` type with a trivial constructor, so
                // this should not make any difference.
                Box::new(unsafe { MaybeUninit::uninit().assume_init() })
            }
            #[doc(hidden)]
            #[cfg(st3_loom)]
            fn allocate() -> Box<Self::Data> {
                // Loom's `UnsafeCell` is not `repr(transparent)` and does not
                // have a trivial constructor so initialization must be done
                // element-wise.
                fn make_fixed_size<T>(buffer: Box<[T]>) -> Box<[T; $cap]> {
                    assert_eq!(buffer.len(), $cap);

                    // Safety: The length was checked.
                    unsafe { Box::from_raw(Box::into_raw(buffer).cast()) }
                }

                let mut buffer = Vec::with_capacity($cap);
                for _ in 0..$cap {
                    buffer.push(UnsafeCell::new(MaybeUninit::uninit()));
                }

                make_fixed_size(buffer.into_boxed_slice())
            }
        }
    };
}

// Define buffer capacities up to 2^15, which is the maximum that can be
// supported when the `long_counter` feature is disabled since buffer positions
// are then 16-bit wide (note that 1 bit is required for disambiguation between
// full and empty buffer). We could possibly define capacities up to 2^31 when
// `long_counter` is enabled, but this is probably enough in practice.
make_buffer!(B2, 2);
make_buffer!(B4, 4);
make_buffer!(B8, 8);
make_buffer!(B16, 16);
make_buffer!(B32, 32);
make_buffer!(B64, 64);
make_buffer!(B128, 128);
make_buffer!(B256, 256);
make_buffer!(B512, 512);
make_buffer!(B1024, 1024);
make_buffer!(B2048, 2048);
make_buffer!(B4096, 4096);
make_buffer!(B8192, 8192);
make_buffer!(B16384, 12384);
make_buffer!(B32768, 32768);

/// Prevent public implementation of Buffer.
mod private {
    pub trait Sealed {}
}