Circular buffer of a constant size

README.md

NRingBuffer

A simple and efficient constant-size non-allocating ring buffer.

n_ring.rs

use std::mem;
use std::mem::MaybeUninit;

/// Circular buffer of a constant size.
pub struct NRingBuffer<T, const N: usize> {
    buffer: [MaybeUninit<T>; N],
    len: usize,
    start: usize,
}

/// Iterator over [`NRingBuffer`].
pub struct NRingBufferIterator<'a, T, const N: usize> {
    ring: &'a NRingBuffer<T, N>,
    cursor: usize,
}

impl<T, const N: usize> NRingBuffer<T, N> {
    /// Creates a new [`NRingBuffer`].
    pub fn new() -> NRingBuffer<T, N> {
        NRingBuffer {
            buffer: unsafe { MaybeUninit::<[MaybeUninit<T>; N]>::uninit().assume_init() },
            len: 0,
            start: 0,
        }
    }

    /// Returns `true` if buffer is full.
    #[inline(always)]
    pub fn is_full(&self) -> bool {
        self.len == N
    }

    /// Returns `true` if buffer is empty.
    #[inline(always)]
    pub fn is_empty(&self) -> bool {
        self.len == 0
    }

    /// Returns number of elements in a buffer.
    #[inline(always)]
    pub fn len(&self) -> usize {
        self.len
    }

    /// Pushes new element to a buffer.
    ///
    /// Returns optional element that was pushed out from the buffer.
    ///
    /// If buffer has zero capacity, then the same element will be returned.
    pub fn push(&mut self, value: T) -> Option<T> {
        if N == 0 {
            return Some(value);
        }

        let pos = (self.start + self.len) % N;

        let mut value = MaybeUninit::new(value);
        mem::swap(&mut value, &mut self.buffer[pos]);

        let pushed_out = if self.is_full() {
            Some(unsafe { value.assume_init() })
        } else {
            None
        };

        if self.is_full() {
            if self.start == N - 1 {
                self.start = 0;
            } else {
                self.start += 1;
            }
        } else {
            self.len += 1;
        }

        pushed_out
    }

    /// Pulls back the first element of a buffer.
    pub fn pull_back(&mut self) -> Option<T> {
        if self.is_empty() {
            return None;
        }

        let mut value = MaybeUninit::<T>::uninit();
        mem::swap(&mut value, &mut self.buffer[self.start]);

        if self.start == N - 1 {
            self.start = 0;
        } else {
            self.start += 1;
        }

        self.len -= 1;

        Some(unsafe { value.assume_init() })
    }

    /// Returns an iterator over a buffer.
    #[inline]
    pub fn iter(&self) -> impl Iterator<Item = &T> {
        NRingBufferIterator::new(self)
    }
}

impl<T, const N: usize> Default for NRingBuffer<T, N> {
    /// Creates an empty buffer.
    fn default() -> Self {
        Self::new()
    }
}

impl<T, const N: usize> Drop for NRingBuffer<T, N> {
    fn drop(&mut self) {
        while let Some(_) = self.pull_back() {}
    }
}

impl<'a, T, const N: usize> NRingBufferIterator<'a, T, N> {
    /// Creates a new iterator over a [`NRingBuffer`].
    pub fn new(ring: &'a NRingBuffer<T, N>) -> Self {
        Self { ring, cursor: 0 }
    }
}

impl<'a, T, const N: usize> Iterator for NRingBufferIterator<'a, T, N> {
    type Item = &'a T;

    /// Returns next element of a [`NRingBuffer`] or [`None`].
    fn next(&mut self) -> Option<&'a T> {
        if self.cursor == self.ring.len {
            return None;
        }

        let pos = (self.ring.start + self.cursor) % N;
        self.cursor += 1;

        let element = &self.ring.buffer[pos];
        Some(unsafe { element.assume_init_ref() })
    }
}

///////////////////////////////////////////////////////////////////////////////
//                                  Tests                                    //
///////////////////////////////////////////////////////////////////////////////

#[cfg(test)]
mod tests {
    use super::*;
    use std::sync::atomic;
    use std::sync::atomic::AtomicBool;

    #[test]
    fn n_ring_basics() {
        let mut ring = NRingBuffer::<_, 2>::new();

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

        assert_eq!(ring.pull_back().unwrap(), 2);
        assert_eq!(ring.pull_back().unwrap(), 3);
        assert!(ring.pull_back().is_none());
    }

    #[test]
    fn n_ring_zero_elements() {
        let mut ring = NRingBuffer::<_, 0>::new();

        assert!(matches!(ring.push(1), Some(1)));
        assert!(matches!(ring.push(2), Some(2)));
        assert!(matches!(ring.push(3), Some(3)));

        assert!(ring.pull_back().is_none());
    }

    #[test]
    fn n_ring_iterator() {
        let mut ring = NRingBuffer::<_, 2>::new();

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

        let mut iter = ring.iter();
        assert!(matches!(iter.next(), Some(1)));
        assert!(matches!(iter.next(), Some(2)));

        let mut items = 0;
        for _ in ring.iter() {
            items += 1;
        }
        assert_eq!(items, 2);
    }

    #[test]
    fn n_ring_correct_drop() {
        let mut ring = NRingBuffer::<_, 2>::new();

        let is_dropped_1 = AtomicBool::new(false);
        let is_dropped_2 = AtomicBool::new(false);
        let is_dropped_3 = AtomicBool::new(false);

        let dropped_1 = Dropped(&is_dropped_1, 1);
        let dropped_2 = Dropped(&is_dropped_2, 2);
        let dropped_3 = Dropped(&is_dropped_3, 3);

        let pushed_out = ring.push(dropped_1);
        assert!(pushed_out.is_none());
        let pushed_out = ring.push(dropped_2);
        assert!(pushed_out.is_none());

        let pushed_out = ring.push(dropped_3);
        assert!(matches!(pushed_out, Some(Dropped(_, 1))));
        drop(pushed_out);
        assert!(is_dropped_1.load(atomic::Ordering::Acquire));

        let value = ring.pull_back();
        assert!(matches!(value, Some(Dropped(_, 2))));
        drop(value);
        assert!(is_dropped_2.load(atomic::Ordering::Acquire));

        let value = ring.pull_back();
        assert!(
            matches!(value, Some(Dropped(_, 3))),
            "incorrect: {:?}",
            value
        );
        drop(value);
        assert!(is_dropped_3.load(atomic::Ordering::Acquire));

        drop(ring);
    }

    #[test]
    fn n_ring_correct_drop_all() {
        let is_dropped_1 = AtomicBool::new(false);
        let is_dropped_2 = AtomicBool::new(false);
        let is_dropped_3 = AtomicBool::new(false);

        let dropped_1 = Dropped(&is_dropped_1, 1);
        let dropped_2 = Dropped(&is_dropped_2, 2);
        let dropped_3 = Dropped(&is_dropped_3, 3);

        {
            let mut ring = NRingBuffer::<_, 2>::new();

            ring.push(dropped_1);
            ring.push(dropped_2);
            ring.push(dropped_3);
        }

        assert!(is_dropped_1.load(atomic::Ordering::Acquire));
        assert!(is_dropped_2.load(atomic::Ordering::Acquire));
        assert!(is_dropped_3.load(atomic::Ordering::Acquire));
    }

    #[derive(Debug)]
    struct Dropped<'a>(&'a AtomicBool, usize);

    impl<'a> Drop for Dropped<'a> {
        fn drop(&mut self) {
            self.0.store(true, atomic::Ordering::Release);
        }
    }
}