371 Intermediate

371: Circular Buffer (Ring Buffer)

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "371: Circular Buffer (Ring Buffer)" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. Audio processing, network packet buffering, logging with bounded history, and real-time telemetry all need fixed-size FIFO queues where old data is overwritten when the buffer is full. Key difference from OCaml: | Aspect | Rust `CircularBuffer<T>` | OCaml `'a cbuf` |

Tutorial

The Problem

Audio processing, network packet buffering, logging with bounded history, and real-time telemetry all need fixed-size FIFO queues where old data is overwritten when the buffer is full. A circular buffer (ring buffer) achieves this with a fixed Vec<Option<T>> and two indices (head, tail) that wrap around modulo capacity. Operations are always O(1) with no allocation after construction. This is more efficient than VecDeque when the capacity is fixed at creation time — the modular arithmetic avoids the reallocation and copying that VecDeque might perform when growing.

🎯 Learning Outcomes

• Implement a circular buffer with head, tail, size, and capacity fields

• Use modular arithmetic (tail + 1) % capacity for index wrapping

• Track fullness with a separate size counter (avoids the "full vs empty" ambiguity)

• Implement push returning Err when full and pop returning None when empty

• Add push_overwrite that drops the oldest element when full

• Understand why circular buffers are used in audio and network I/O

Code Example

#![allow(clippy::all)]
//! Circular Buffer (Ring Buffer)
//!
//! Fixed-size FIFO queue with O(1) operations.

/// A circular buffer with fixed capacity
pub struct CircularBuffer<T> {
    data: Vec<Option<T>>,
    head: usize,
    tail: usize,
    size: usize,
    capacity: usize,
}

impl<T> CircularBuffer<T> {
    /// Create a new circular buffer with given capacity
    pub fn new(capacity: usize) -> Self {
        assert!(capacity > 0, "capacity must be > 0");
        let mut data = Vec::with_capacity(capacity);
        for _ in 0..capacity {
            data.push(None);
        }
        Self {
            data,
            head: 0,
            tail: 0,
            size: 0,
            capacity,
        }
    }

    /// Push an element to the back (returns error if full)
    pub fn push(&mut self, val: T) -> Result<(), &'static str> {
        if self.is_full() {
            return Err("buffer full");
        }
        self.data[self.tail] = Some(val);
        self.tail = (self.tail + 1) % self.capacity;
        self.size += 1;
        Ok(())
    }

    /// Pop element from front
    pub fn pop(&mut self) -> Option<T> {
        if self.is_empty() {
            return None;
        }
        let val = self.data[self.head].take();
        self.head = (self.head + 1) % self.capacity;
        self.size -= 1;
        val
    }

    /// Peek at front element without removing
    pub fn peek(&self) -> Option<&T> {
        if self.is_empty() {
            None
        } else {
            self.data[self.head].as_ref()
        }
    }

    /// Push with overwrite - drops oldest if full
    pub fn push_overwrite(&mut self, val: T) {
        if self.is_full() {
            self.pop();
        }
        self.push(val).unwrap();
    }

    /// Check if empty
    pub fn is_empty(&self) -> bool {
        self.size == 0
    }

    /// Check if full
    pub fn is_full(&self) -> bool {
        self.size == self.capacity
    }

    /// Get current size
    pub fn len(&self) -> usize {
        self.size
    }

    /// Get capacity
    pub fn capacity(&self) -> usize {
        self.capacity
    }

    /// Clear all elements
    pub fn clear(&mut self) {
        while self.pop().is_some() {}
    }

    /// Iterate over elements (front to back)
    pub fn iter(&self) -> impl Iterator<Item = &T> {
        let mut items = Vec::with_capacity(self.size);
        let mut i = self.head;
        for _ in 0..self.size {
            if let Some(ref val) = self.data[i] {
                items.push(val);
            }
            i = (i + 1) % self.capacity;
        }
        items.into_iter()
    }
}

impl<T: Clone> CircularBuffer<T> {
    /// Convert to Vec
    pub fn to_vec(&self) -> Vec<T> {
        self.iter().cloned().collect()
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_fifo_order() {
        let mut buf: CircularBuffer<i32> = CircularBuffer::new(4);
        buf.push(1).unwrap();
        buf.push(2).unwrap();
        buf.push(3).unwrap();
        assert_eq!(buf.pop(), Some(1));
        assert_eq!(buf.pop(), Some(2));
        assert_eq!(buf.pop(), Some(3));
    }

    #[test]
    fn test_full_error() {
        let mut buf: CircularBuffer<i32> = CircularBuffer::new(2);
        buf.push(1).unwrap();
        buf.push(2).unwrap();
        assert!(buf.push(3).is_err());
    }

    #[test]
    fn test_overwrite_oldest() {
        let mut buf: CircularBuffer<i32> = CircularBuffer::new(3);
        for i in 0..5 {
            buf.push_overwrite(i);
        }
        assert_eq!(buf.pop(), Some(2));
        assert_eq!(buf.pop(), Some(3));
        assert_eq!(buf.pop(), Some(4));
    }

    #[test]
    fn test_peek() {
        let mut buf: CircularBuffer<i32> = CircularBuffer::new(3);
        buf.push(42).unwrap();
        assert_eq!(buf.peek(), Some(&42));
        assert_eq!(buf.len(), 1); // peek doesn't remove
    }

    #[test]
    fn test_wrap_around() {
        let mut buf: CircularBuffer<i32> = CircularBuffer::new(3);
        buf.push(1).unwrap();
        buf.push(2).unwrap();
        buf.pop();
        buf.push(3).unwrap();
        buf.push(4).unwrap();
        assert_eq!(buf.to_vec(), vec![2, 3, 4]);
    }

    #[test]
    fn test_clear() {
        let mut buf: CircularBuffer<i32> = CircularBuffer::new(3);
        buf.push(1).unwrap();
        buf.push(2).unwrap();
        buf.clear();
        assert!(buf.is_empty());
    }
}

(* OCaml: circular buffer with array *)

type 'a ring = {
  data : 'a option array;
  capacity : int;
  mutable head : int;
  mutable tail : int;
  mutable size : int;
}

let make cap = { data=Array.make cap None; capacity=cap; head=0; tail=0; size=0 }

let push r x =
  if r.size = r.capacity then failwith "full"
  else begin
    r.data.(r.tail) <- Some x;
    r.tail <- (r.tail + 1) mod r.capacity;
    r.size <- r.size + 1
  end

let pop r =
  if r.size = 0 then None
  else begin
    let v = r.data.(r.head) in
    r.data.(r.head) <- None;
    r.head <- (r.head + 1) mod r.capacity;
    r.size <- r.size - 1;
    v
  end

let () =
  let r = make 4 in
  push r 1; push r 2; push r 3;
  Printf.printf "Pop: %s\n" (Option.fold ~none:"?" ~some:string_of_int (pop r));
  push r 4; push r 5;
  while r.size > 0 do
    Printf.printf "%s " (Option.fold ~none:"?" ~some:string_of_int (pop r))
  done; print_newline ()

Key Differences

Aspect	Rust `CircularBuffer<T>`	OCaml `'a cbuf`
Storage	`Vec<Option<T>>`	`'a option array`
Index wrap	`% capacity` (modulo)	`mod capacity`
Full detection	`size == capacity`	`size = capacity`
Push error	`Result<(), &str>`	`Result` variant or exception
Production	`VecDeque` or `ringbuf` crate	`Queue` module (unbounded)

OCaml Approach

type 'a cbuf = {
  data: 'a option array;
  mutable head: int;
  mutable tail: int;
  mutable size: int;
  capacity: int;
}

let make capacity =
  { data = Array.make capacity None; head = 0; tail = 0; size = 0; capacity }

let push buf v =
  if buf.size = buf.capacity then Error "full"
  else begin
    buf.data.(buf.tail) <- Some v;
    buf.tail <- (buf.tail + 1) mod buf.capacity;
    buf.size <- buf.size + 1;
    Ok ()
  end

let pop buf =
  if buf.size = 0 then None
  else begin
    let v = buf.data.(buf.head) in
    buf.data.(buf.head) <- None;
    buf.head <- (buf.head + 1) mod buf.capacity;
    buf.size <- buf.size - 1;
    v
  end

The algorithm is identical — circular buffers are inherently imperative, mapping cleanly to both languages' mutable array operations.

Full Source

#![allow(clippy::all)]
//! Circular Buffer (Ring Buffer)
//!
//! Fixed-size FIFO queue with O(1) operations.

/// A circular buffer with fixed capacity
pub struct CircularBuffer<T> {
    data: Vec<Option<T>>,
    head: usize,
    tail: usize,
    size: usize,
    capacity: usize,
}

impl<T> CircularBuffer<T> {
    /// Create a new circular buffer with given capacity
    pub fn new(capacity: usize) -> Self {
        assert!(capacity > 0, "capacity must be > 0");
        let mut data = Vec::with_capacity(capacity);
        for _ in 0..capacity {
            data.push(None);
        }
        Self {
            data,
            head: 0,
            tail: 0,
            size: 0,
            capacity,
        }
    }

    /// Push an element to the back (returns error if full)
    pub fn push(&mut self, val: T) -> Result<(), &'static str> {
        if self.is_full() {
            return Err("buffer full");
        }
        self.data[self.tail] = Some(val);
        self.tail = (self.tail + 1) % self.capacity;
        self.size += 1;
        Ok(())
    }

    /// Pop element from front
    pub fn pop(&mut self) -> Option<T> {
        if self.is_empty() {
            return None;
        }
        let val = self.data[self.head].take();
        self.head = (self.head + 1) % self.capacity;
        self.size -= 1;
        val
    }

    /// Peek at front element without removing
    pub fn peek(&self) -> Option<&T> {
        if self.is_empty() {
            None
        } else {
            self.data[self.head].as_ref()
        }
    }

    /// Push with overwrite - drops oldest if full
    pub fn push_overwrite(&mut self, val: T) {
        if self.is_full() {
            self.pop();
        }
        self.push(val).unwrap();
    }

    /// Check if empty
    pub fn is_empty(&self) -> bool {
        self.size == 0
    }

    /// Check if full
    pub fn is_full(&self) -> bool {
        self.size == self.capacity
    }

    /// Get current size
    pub fn len(&self) -> usize {
        self.size
    }

    /// Get capacity
    pub fn capacity(&self) -> usize {
        self.capacity
    }

    /// Clear all elements
    pub fn clear(&mut self) {
        while self.pop().is_some() {}
    }

    /// Iterate over elements (front to back)
    pub fn iter(&self) -> impl Iterator<Item = &T> {
        let mut items = Vec::with_capacity(self.size);
        let mut i = self.head;
        for _ in 0..self.size {
            if let Some(ref val) = self.data[i] {
                items.push(val);
            }
            i = (i + 1) % self.capacity;
        }
        items.into_iter()
    }
}

impl<T: Clone> CircularBuffer<T> {
    /// Convert to Vec
    pub fn to_vec(&self) -> Vec<T> {
        self.iter().cloned().collect()
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_fifo_order() {
        let mut buf: CircularBuffer<i32> = CircularBuffer::new(4);
        buf.push(1).unwrap();
        buf.push(2).unwrap();
        buf.push(3).unwrap();
        assert_eq!(buf.pop(), Some(1));
        assert_eq!(buf.pop(), Some(2));
        assert_eq!(buf.pop(), Some(3));
    }

    #[test]
    fn test_full_error() {
        let mut buf: CircularBuffer<i32> = CircularBuffer::new(2);
        buf.push(1).unwrap();
        buf.push(2).unwrap();
        assert!(buf.push(3).is_err());
    }

    #[test]
    fn test_overwrite_oldest() {
        let mut buf: CircularBuffer<i32> = CircularBuffer::new(3);
        for i in 0..5 {
            buf.push_overwrite(i);
        }
        assert_eq!(buf.pop(), Some(2));
        assert_eq!(buf.pop(), Some(3));
        assert_eq!(buf.pop(), Some(4));
    }

    #[test]
    fn test_peek() {
        let mut buf: CircularBuffer<i32> = CircularBuffer::new(3);
        buf.push(42).unwrap();
        assert_eq!(buf.peek(), Some(&42));
        assert_eq!(buf.len(), 1); // peek doesn't remove
    }

    #[test]
    fn test_wrap_around() {
        let mut buf: CircularBuffer<i32> = CircularBuffer::new(3);
        buf.push(1).unwrap();
        buf.push(2).unwrap();
        buf.pop();
        buf.push(3).unwrap();
        buf.push(4).unwrap();
        assert_eq!(buf.to_vec(), vec![2, 3, 4]);
    }

    #[test]
    fn test_clear() {
        let mut buf: CircularBuffer<i32> = CircularBuffer::new(3);
        buf.push(1).unwrap();
        buf.push(2).unwrap();
        buf.clear();
        assert!(buf.is_empty());
    }
}

(* OCaml: circular buffer with array *)

type 'a ring = {
  data : 'a option array;
  capacity : int;
  mutable head : int;
  mutable tail : int;
  mutable size : int;
}

let make cap = { data=Array.make cap None; capacity=cap; head=0; tail=0; size=0 }

let push r x =
  if r.size = r.capacity then failwith "full"
  else begin
    r.data.(r.tail) <- Some x;
    r.tail <- (r.tail + 1) mod r.capacity;
    r.size <- r.size + 1
  end

let pop r =
  if r.size = 0 then None
  else begin
    let v = r.data.(r.head) in
    r.data.(r.head) <- None;
    r.head <- (r.head + 1) mod r.capacity;
    r.size <- r.size - 1;
    v
  end

let () =
  let r = make 4 in
  push r 1; push r 2; push r 3;
  Printf.printf "Pop: %s\n" (Option.fold ~none:"?" ~some:string_of_int (pop r));
  push r 4; push r 5;
  while r.size > 0 do
    Printf.printf "%s " (Option.fold ~none:"?" ~some:string_of_int (pop r))
  done; print_newline ()

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_fifo_order() {
        let mut buf: CircularBuffer<i32> = CircularBuffer::new(4);
        buf.push(1).unwrap();
        buf.push(2).unwrap();
        buf.push(3).unwrap();
        assert_eq!(buf.pop(), Some(1));
        assert_eq!(buf.pop(), Some(2));
        assert_eq!(buf.pop(), Some(3));
    }

    #[test]
    fn test_full_error() {
        let mut buf: CircularBuffer<i32> = CircularBuffer::new(2);
        buf.push(1).unwrap();
        buf.push(2).unwrap();
        assert!(buf.push(3).is_err());
    }

    #[test]
    fn test_overwrite_oldest() {
        let mut buf: CircularBuffer<i32> = CircularBuffer::new(3);
        for i in 0..5 {
            buf.push_overwrite(i);
        }
        assert_eq!(buf.pop(), Some(2));
        assert_eq!(buf.pop(), Some(3));
        assert_eq!(buf.pop(), Some(4));
    }

    #[test]
    fn test_peek() {
        let mut buf: CircularBuffer<i32> = CircularBuffer::new(3);
        buf.push(42).unwrap();
        assert_eq!(buf.peek(), Some(&42));
        assert_eq!(buf.len(), 1); // peek doesn't remove
    }

    #[test]
    fn test_wrap_around() {
        let mut buf: CircularBuffer<i32> = CircularBuffer::new(3);
        buf.push(1).unwrap();
        buf.push(2).unwrap();
        buf.pop();
        buf.push(3).unwrap();
        buf.push(4).unwrap();
        assert_eq!(buf.to_vec(), vec![2, 3, 4]);
    }

    #[test]
    fn test_clear() {
        let mut buf: CircularBuffer<i32> = CircularBuffer::new(3);
        buf.push(1).unwrap();
        buf.push(2).unwrap();
        buf.clear();
        assert!(buf.is_empty());
    }
}

Deep Comparison

OCaml vs Rust: Circular Buffer

Both use array with head/tail pointers wrapping around.

Exercises

Overwrite mode audio: Implement a AudioBuffer with push_overwrite that holds the last 4096 samples; show that oldest samples are silently discarded when the buffer is full.

Peek without pop: Add peek(&self) -> Option<&T> that returns a reference to the head element without removing it; useful for lookahead parsing.

Iterator: Implement IntoIterator for CircularBuffer<T> that drains elements from head to tail in O(1) per step (no reallocation), consuming the buffer.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust