Tim McNamara's video on Ring Buffer

README.md

A quick attempt at RingBuffer implementation.

• From Tim McNamara's video on YouTube.
• More informations: Circular buffer on Wikipedia.
• Try it in the Rust playground.

lib.rs

use std::marker::PhantomData;

/// index which wraps around buffer length,
/// and might be initialized or not
#[derive(Debug, Clone, Copy)]
pub struct Idx<const N: usize>(Option<usize>);

impl<const N: usize> Idx<N> {
    /// return the next index, wrapped around buffer length,
    /// or `0`
    pub fn next(&self) -> usize {
        match self.0 {
            Some(x) if x + 1 != N => x + 1,
            _ => 0,
        }
    }
    pub fn is_none(&self) -> bool {
        self.0.is_none()
    }
    pub fn is_some(&self) -> bool {
        self.0.is_some()
    }
    pub fn as_usize(&self) -> usize {
        self.0.unwrap_or(0)
    }
}

/// a bounded buffer (which cannot be overwritten)
#[derive(Debug)]
pub struct Bounded;
#[derive(Debug)]
/// an unbounded buffer (which can be overwritten)
pub struct Unbounded;
mod sealed {
    use crate::{Bounded, Unbounded};

    pub trait Sealed {}
    impl Sealed for Bounded {}
    impl Sealed for Unbounded {}
}

#[derive(Debug, Clone)]
pub struct RingBuffer<T: Clone, S: sealed::Sealed, const N: usize> {
    sectors: Box<[Option<T>; N]>,
    took: Idx<N>,
    put: Idx<N>,
    _ghost: PhantomData<S>,
}

#[derive(Debug, PartialEq)]
pub enum RingBufferError {
    Full,
}

impl<T: Clone, S: sealed::Sealed, const N: usize> RingBuffer<T, S, N> {
    pub fn new() -> Self {
        let vec = vec![None; N];
        let boxed_slice: Box<[Option<T>]> = vec.into_boxed_slice();

        // SAFETY: nobody has a chance to touch it in-between
        let ptr = ::std::boxed::Box::into_raw(boxed_slice) as *mut [Option<T>; N];
        let sectors = unsafe { Box::from_raw(ptr) };

        Self {
            sectors,
            took: Idx(None),
            put: Idx(None),
            _ghost: PhantomData::<S>,
        }
    }
    /// if next slot is occupied,
    /// then buffer is full
    pub fn full(&self) -> bool {
        self.occupied(self.put.next())
    }
    /// if we took and put equally,
    /// or haven't written anything yet,
    /// then buffer is empty.
    pub fn empty(&self) -> bool {
        self.put.as_usize() == self.took.as_usize()
    }
    /// pull a value from the buffer,
    /// leaving slot empty
    pub fn pull(&mut self) -> Option<T> {
        let next = self.took.next();
        // SAFETY: we are in bounds, pull is sequential
        // and reader does not get incremented when there's no value
        let value = unsafe { self.sectors.get_unchecked_mut(next) }.take();
        if value.is_some() {
            self.took = Idx(Some(next));
        }
        value
    }
    /// if slot is occupied at index
    pub fn occupied(&self, at: usize) -> bool {
        self.sectors.get(at).map(|x| x.is_some()).unwrap_or(false)
    }
    /// if slot is vacant at index
    pub fn vacant(&self, at: usize) -> bool {
        self.sectors.get(at).map(|x| x.is_none()).unwrap_or(false)
    }
}
impl<T: Clone, const N: usize> RingBuffer<T, Bounded, N> {
    /// same implementation as `Unbounded`,
    /// but do not overwrite.
    pub fn push(&mut self, value: T) -> Result<usize, RingBufferError> {
        if self.full() {
            return Err(RingBufferError::Full);
        }
        let next = self.put.next();
        if let Some(sector) = self.sectors.get_mut(next) {
            *sector = Some(value);
            self.put = Idx(Some(next));
        }
        // SAFETY: we are in bounds, push is sequential
        // and reader only increment when overwriting past it
        if self.took.is_some() && next == self.took.next() {
            self.took = Idx(Some(self.took.next()));
        }
        Ok(next)
    }
}
/// same implementation as `Bounded`,
/// but overwrites.
impl<T: Clone, const N: usize> RingBuffer<T, Unbounded, N> {
    pub fn push(&mut self, value: T) -> usize {
        let next = self.put.next();
        if let Some(sector) = self.sectors.get_mut(next) {
            *sector = Some(value);
            self.put = Idx(Some(next));
        }
        // SAFETY: we are in bounds, push is sequential
        // and reader only increment when overwriting past it
        if self.took.is_some() && next == self.took.next() {
            self.took = Idx(Some(self.took.next()));
        }
        next
    }
}

#[cfg(test)]
mod tests {
    use crate::{Bounded, RingBufferError, Unbounded};

    use super::RingBuffer;

    #[doc = "from Wikipedia's example"]
    #[test]
    fn unbounded() {
        let mut ring: RingBuffer<&'static str, Unbounded, 7> = RingBuffer::new();
        assert_eq!(ring.pull(), None);

        ring.push("1");
        ring.push("2");
        ring.push("3");

        let first = ring.pull();
        let second = ring.pull();
        assert_eq!(first, Some("1"));
        assert_eq!(second, Some("2"));

        ring.push("4");
        ring.push("5");
        ring.push("6");
        ring.push("7");
        ring.push("8");
        ring.push("9");
        ring.push("A");
        ring.push("B");

        let third = ring.pull();
        let fourth = ring.pull();
        assert_eq!(third, Some("5"));
        assert_eq!(fourth, Some("6"));
    }

    #[doc = "from Wikipedia's example"]
    #[test]
    fn bounded() {
        let mut ring: RingBuffer<&'static str, Bounded, 7> = RingBuffer::new();
        assert_eq!(ring.pull(), None);

        let _ = ring.push("1");
        let _ = ring.push("2");
        let _ = ring.push("3");

        let first = ring.pull();
        let second = ring.pull();
        assert_eq!(first, Some("1"));
        assert_eq!(second, Some("2"));

        let _ = ring.push("4");
        let _ = ring.push("5");
        let _ = ring.push("6");
        let _ = ring.push("7");
        let _ = ring.push("8");
        let _ = ring.push("9");

        let first = ring.push("A");
        let second = ring.push("B");
        assert_eq!(first, Err(RingBufferError::Full));
        assert_eq!(second, Err(RingBufferError::Full));

        let third = ring.pull();
        let fourth = ring.pull();
        assert_eq!(third, Some("3"));
        assert_eq!(fourth, Some("4"));
    }
}