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.
A quick attempt at RingBuffer
implementation.
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")); | |
} | |
} |