bufferring/masking/

mod.rs

//! A ring buffer for power-of-two capacities.

use core::fmt::{self, Debug, Display};
use core::num::Wrapping;

use crate::{storage::Slot, RingBuffer, Storage};

pub mod prop;

mod tests;

/// A ring buffer for power-of-two capacities.
///
/// When the capacity is a power of two, wrapping out-of-bound indices into the
/// valid range simply requires a binary AND operation (known as masking); it is
/// much faster than a general remainder computation.  This type requires that
/// the capacity be a power of two (which is a fairly common use case), and uses
/// masking liberally to simplify internal control logic.
pub struct MaskingBuffer<S: Storage + ?Sized> {
    /// The current offset.
    ///
    /// This points to the first initialized item in the data buffer (if any).
    /// It should be interpreted modulo the buffer capacity.
    cur: Wrapping<usize>,

    /// The number of initialized items.
    ///
    /// If this is equal to the buffer capacity, then the buffer is full; adding
    /// a new item will drop the oldest item to make space.
    ///
    /// This value, plus the current offset, indicates where the next-added item
    /// will be placed in the data buffer.
    len: usize,

    /// The underlying data buffer.
    ///
    /// This stores the actual items, and is a generic parameter so that they
    /// can be stored at an arbitrary location (e.g. on the stack or heap).
    data: S,
}

// TODO: Provide emplacement for non-Sized storages.

impl<S: Storage> MaskingBuffer<S> {
    /// Create a new [`MaskingBuffer`].
    ///
    /// If the given storage's capacity is not a power of two, [`Err`] will be
    /// returned.
    pub fn new(storage: S) -> Result<Self, Error> {
        if storage.cap().is_power_of_two() {
            // SAFETY: We have verified that the capacity is valid.
            Ok(unsafe { Self::new_unchecked(storage) })
        } else {
            Err(Error::NotPowerOfTwo)
        }
    }

    /// Create a new [`MaskingBuffer`], assuming that the given capacity is a
    /// power of two.
    ///
    /// If this is called with a capacity that is not a power of two, undefined
    /// behaviour will occur.
    pub unsafe fn new_unchecked(storage: S) -> Self {
        Self { cur: Wrapping(0), len: 0, data: storage }
    }
}

impl<S: Storage + ?Sized> MaskingBuffer<S> {
    /// Mask the given offset by the capacity.
    fn mask(&self, off: Wrapping<usize>) -> usize {
        off.0 & (self.cap() - 1)
    }
}

impl<S: Storage + ?Sized> RingBuffer for MaskingBuffer<S> {
    type Item = S::Item;

    fn cap(&self) -> usize {
        self.data.cap()
    }

    fn len(&self) -> usize {
        self.len
    }

    fn get(&self, off: usize) -> Option<&Self::Item> {
        if off >= self.len { return None; }
        // SAFETY:
        // - 'mask()' always returns a valid index into the buffer.
        // - 'off' is in range, so it refers to an initialized element.
        let off = self.mask(self.cur + Wrapping(off));
        Some(unsafe { self.data.get().get_unchecked(off).get_ref() })
    }

    fn get_mut(&mut self, off: usize) -> Option<&mut Self::Item> {
        if off >= self.len { return None; }
        // SAFETY:
        // - 'mask()' always returns a valid index into the buffer.
        // - 'off' is in range, so it refers to an initialized element.
        let off = self.mask(self.cur + Wrapping(off));
        Some(unsafe { self.data.get_mut().get_unchecked_mut(off).get_mut() })
    }

    unsafe fn get_disjoint_mut(&self, off: usize) -> &mut Self::Item {
        // SAFETY:
        // - 'mask()' always returns a valid index into the buffer.
        // - The caller guarantees that 'off' is in range.
        // - The caller guarantees that this item is not already in use.
        let off = self.mask(self.cur + Wrapping(off));
        unsafe { self.data.get().get_unchecked(off).get_int_mut() }
    }

    fn enqueue(&mut self, item: Self::Item) -> Option<Self::Item> {
        let is_full = self.is_full();
        // SAFETY:
        // - 'mask()' always returns a valid index into the buffer.
        let off = self.mask(self.cur + Wrapping(self.len));
        let ptr = unsafe { self.data.get_mut().get_unchecked_mut(off) };

        let res = is_full.then(|| {
            // SAFETY:
            // - The buffer is full, so the slot is initialized.
            self.len -= 1;
            self.cur += 1;
            unsafe { ptr.take() }
        });

        *ptr = Slot::new(item);

        self.len += 1;

        res
    }

    fn dequeue(&mut self) -> Option<Self::Item> {
        if self.is_empty() { return None; }

        // SAFETY:
        // - 'mask()' always returns a valid index into the buffer.
        // - The buffer is not empty, so this (first) slot must be initialized.
        let off = self.mask(self.cur);
        let item = unsafe { self.data.get_mut().get_unchecked_mut(off).take() };

        self.cur += 1;
        self.len -= 1;
        Some(item)
    }

    fn skip_one(&mut self) {
        if self.is_empty() { return; }

        // SAFETY:
        // - 'mask()' always returns a valid index into the buffer.
        // - The buffer is not empty, so this (first) slot must be initialized.
        let off = self.mask(self.cur + Wrapping(self.len));
        unsafe { self.data.get_mut().get_unchecked_mut(off).drop_in_place(); }

        self.cur += 1;
        self.len -= 1;
    }
}

impl<T: Clone, S: Storage<Item = T> + Clone> Clone for MaskingBuffer<S> {
    fn clone(&self) -> Self {
        // SAFETY: A `MaskingBuffer` with the same storage already exists.
        let mut res = unsafe { Self::new_unchecked(self.data.clone()) };
        for item in self.iter() {
            res.enqueue(item.clone());
        }
        res
    }
}

impl<S: Storage> Debug for MaskingBuffer<S>
where S: Debug, S::Item: Debug {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        struct Items<'a, S: Storage>(&'a MaskingBuffer<S>);

        impl<'a, S: Storage> Debug for Items<'a, S>
        where S::Item: Debug {
            fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
                f.debug_list().entries(self.0.iter()).finish()
            }
        }

        f.debug_struct("MaskingBuffer")
            .field("cur", &self.cur)
            .field("len", &self.len)
            .field("data", &self.data)
            .field("items", &Items(self))
            .finish()
    }
}

/// Errors for [`MaskingBuffer`].
#[derive(Clone, PartialEq, Eq, Debug)]
pub enum Error {
    /// An attempt was made to create a [`MaskingBuffer`] with a capacity that
    /// is not a power of two.
    NotPowerOfTwo,
}

impl Display for Error {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Self::NotPowerOfTwo => write!(f,
                "An attempt was made to create a `MaskingBuffer` with a \
                capacity that is not a power of two"),
        }
    }
}