ubq 7.0.0

Lock-free unbounded MPMC queue with no_std + alloc support.
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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131

use crate::{block::MpmcBlock as Block, page::page_size};
use core::ptr;

#[derive(Clone, Copy, Debug)]
pub(crate) struct HeadCodec {
    block_length: usize,
    pointer_mask: usize,
    index_mask: usize,
    has_next_mask: usize,
}

impl HeadCodec {
    pub(crate) fn new<T>() -> Self {
        let page_size = page_size();
        let block_length = Block::<T>::capacity();
        let page_bits = page_size.trailing_zeros();
        let index_bits = usize::BITS - block_length.leading_zeros();

        assert!(
            index_bits <= page_bits,
            "the block index does not fit in the page-aligned pointer tag"
        );

        let index_mask = usize::MAX >> (usize::BITS - index_bits);
        let has_next_mask = if index_bits < page_bits {
            1usize << index_bits
        } else {
            // A maximal one-byte slot layout can consume every page-alignment
            // bit. `has_next` is only a cache hint, so dropping it is correct.
            0
        };

        Self {
            block_length,
            pointer_mask: !(page_size - 1),
            index_mask,
            has_next_mask,
        }
    }

    #[inline]
    pub(crate) const fn block_length(self) -> usize {
        self.block_length
    }

    #[cfg(test)]
    const fn has_next_enabled(self) -> bool {
        self.has_next_mask != 0
    }
}

pub(crate) struct Head<T> {
    pub(crate) block: *mut Block<T>,
    pub(crate) index: usize,
    pub(crate) has_next: bool,
}

impl<T> Head<T> {
    pub(crate) const ZERO: Self = Self {
        block: ptr::null_mut(),
        index: 0,
        has_next: false,
    };

    pub(crate) const fn from_ptr(block: *mut Block<T>) -> Self {
        Self {
            block,
            ..Self::ZERO
        }
    }

    #[inline]
    pub(crate) fn from_usize(value: usize, codec: HeadCodec) -> Self {
        Self {
            block: ptr::with_exposed_provenance_mut(value & codec.pointer_mask),
            index: value & codec.index_mask,
            has_next: codec.has_next_mask != 0 && value & codec.has_next_mask != 0,
        }
    }

    #[inline]
    pub(crate) fn to_usize(self, codec: HeadCodec) -> usize {
        debug_assert_eq!(self.block.addr() & !codec.pointer_mask, 0);
        debug_assert!(self.index <= codec.block_length);

        self.block.expose_provenance()
            | (self.index & codec.index_mask)
            | (if self.has_next {
                codec.has_next_mask
            } else {
                0
            })
    }

    pub(crate) const fn is_zero(&self) -> bool {
        self.block.is_null() && self.index == 0 && !self.has_next
    }
}

impl<T> Copy for Head<T> {}

impl<T> Clone for Head<T> {
    fn clone(&self) -> Self {
        *self
    }
}

#[cfg(test)]
mod tests {
    use super::{Head, HeadCodec};
    use crate::block::MpmcBlock as Block;

    #[test]
    fn codec_round_trips_the_page_aligned_block_and_index() {
        let codec = HeadCodec::new::<u64>();
        let length = codec.block_length();
        assert!(codec.has_next_enabled());

        let block = Block::<u64>::new();
        let head = Head {
            block,
            index: length,
            has_next: true,
        };
        let decoded = Head::from_usize(head.to_usize(codec), codec);
        assert_eq!(decoded.block, block);
        assert_eq!(decoded.index, length);
        assert!(decoded.has_next);
        Block::free(block);
    }
}