ringbuf/traits/
utils.rs

1use super::Observer;
2use core::num::NonZeroUsize;
3
4/// Trait that should be implemented by ring buffer wrappers.
5///
6/// Used for automatically delegating methods.
7pub trait Based {
8    /// Type the wrapper based on.
9    type Base: ?Sized;
10    /// Reference to base.
11    fn base(&self) -> &Self::Base;
12    /// Mutable reference to base.
13    fn base_mut(&mut self) -> &mut Self::Base;
14}
15
16/// Modulus for pointers to item in ring buffer storage.
17///
18/// Equals to `2 * capacity`.
19#[inline]
20pub fn modulus<O: Observer + ?Sized>(this: &O) -> NonZeroUsize {
21    this.capacity()
22        .checked_mul(NonZeroUsize::new(2).unwrap())
23        .expect("capacity exceeds usize::MAX / 2")
24}
25
26/// Add two values below `modulus` without overflowing the intermediate sum.
27#[inline]
28pub fn add_mod(left: usize, right: usize, modulus: NonZeroUsize) -> usize {
29    debug_assert!(left < modulus.get() && right < modulus.get());
30    if modulus.get().is_power_of_two() {
31        // Preserve the bitmask fast path for power-of-two capacities.
32        left.wrapping_add(right) & (modulus.get() - 1)
33    } else {
34        let until_wrap = modulus.get() - left;
35        if right >= until_wrap { right - until_wrap } else { left + right }
36    }
37}
38
39/// Subtract two values below `modulus` without underflowing.
40#[inline]
41pub fn sub_mod(left: usize, right: usize, modulus: NonZeroUsize) -> usize {
42    debug_assert!(left < modulus.get() && right < modulus.get());
43    if left >= right {
44        left - right
45    } else {
46        modulus.get() - (right - left)
47    }
48}
49
50#[cfg(test)]
51mod tests {
52    use super::{add_mod, sub_mod};
53    use core::num::NonZeroUsize;
54
55    fn check(left: usize, right: usize, modulus: usize) {
56        let (a, b, m) = (left as u128, right as u128, modulus as u128);
57        let modulus = NonZeroUsize::new(modulus).unwrap();
58        assert_eq!(add_mod(left, right, modulus), ((a + b) % m) as usize);
59        assert_eq!(sub_mod(left, right, modulus), ((m + a - b) % m) as usize);
60    }
61
62    #[test]
63    fn modular_arithmetic() {
64        for modulus in 1..=8 {
65            for left in 0..modulus {
66                for right in 0..modulus {
67                    check(left, right, modulus);
68                }
69            }
70        }
71        for modulus in [usize::MAX / 2, usize::MAX / 2 + 1, usize::MAX - 1, usize::MAX] {
72            for left in [0, 1, modulus / 2, modulus - 2, modulus - 1] {
73                for right in [0, 1, modulus / 2, modulus - 2, modulus - 1] {
74                    check(left, right, modulus);
75                }
76            }
77        }
78    }
79}
ringbuf/traits/utils.rs

ringbuf/traits/
utils.rs
