ringbuf 0.5.3

Lock-free SPSC FIFO ring buffer with direct access to inner data
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

use super::Observer;
use core::num::NonZeroUsize;

/// Trait that should be implemented by ring buffer wrappers.
///
/// Used for automatically delegating methods.
pub trait Based {
    /// Type the wrapper based on.
    type Base: ?Sized;
    /// Reference to base.
    fn base(&self) -> &Self::Base;
    /// Mutable reference to base.
    fn base_mut(&mut self) -> &mut Self::Base;
}

/// Modulus for pointers to item in ring buffer storage.
///
/// Equals to `2 * capacity`.
#[inline]
pub fn modulus<O: Observer + ?Sized>(this: &O) -> NonZeroUsize {
    this.capacity()
        .checked_mul(NonZeroUsize::new(2).unwrap())
        .expect("capacity exceeds usize::MAX / 2")
}

/// Add two values below `modulus` without overflowing the intermediate sum.
#[inline]
pub fn add_mod(left: usize, right: usize, modulus: NonZeroUsize) -> usize {
    debug_assert!(left < modulus.get() && right < modulus.get());
    if modulus.get().is_power_of_two() {
        // Preserve the bitmask fast path for power-of-two capacities.
        left.wrapping_add(right) & (modulus.get() - 1)
    } else {
        let until_wrap = modulus.get() - left;
        if right >= until_wrap { right - until_wrap } else { left + right }
    }
}

/// Subtract two values below `modulus` without underflowing.
#[inline]
pub fn sub_mod(left: usize, right: usize, modulus: NonZeroUsize) -> usize {
    debug_assert!(left < modulus.get() && right < modulus.get());
    if left >= right {
        left - right
    } else {
        modulus.get() - (right - left)
    }
}

#[cfg(test)]
mod tests {
    use super::{add_mod, sub_mod};
    use core::num::NonZeroUsize;

    fn check(left: usize, right: usize, modulus: usize) {
        let (a, b, m) = (left as u128, right as u128, modulus as u128);
        let modulus = NonZeroUsize::new(modulus).unwrap();
        assert_eq!(add_mod(left, right, modulus), ((a + b) % m) as usize);
        assert_eq!(sub_mod(left, right, modulus), ((m + a - b) % m) as usize);
    }

    #[test]
    fn modular_arithmetic() {
        for modulus in 1..=8 {
            for left in 0..modulus {
                for right in 0..modulus {
                    check(left, right, modulus);
                }
            }
        }
        for modulus in [usize::MAX / 2, usize::MAX / 2 + 1, usize::MAX - 1, usize::MAX] {
            for left in [0, 1, modulus / 2, modulus - 2, modulus - 1] {
                for right in [0, 1, modulus / 2, modulus - 2, modulus - 1] {
                    check(left, right, modulus);
                }
            }
        }
    }
}