371: Circular Buffer / Ring Buffer

Difficulty: 3 Level: Advanced Fixed-capacity FIFO queue where new writes overwrite the oldest data when full.

The Problem This Solves

A sliding window of recent events: the last 1000 log lines, the last 60 seconds of sensor readings, the last N keystrokes for undo history. A `Vec` grows indefinitely and needs explicit truncation. A `VecDeque` works but doesn't enforce a capacity contract. What you want is a fixed-size buffer where pushing a new element automatically discards the oldest one — no allocation, no shifting, just a rotating write head. Circular buffers are the classic solution for streaming data with bounded memory. They're used in network packet buffers, audio processing rings, real-time telemetry systems, and anywhere you need "most recent N" semantics without unbounded growth.

The Intuition

A circular buffer is an array with two indices: `read_head` and `write_head`. Write advances `write_head % capacity`. Read advances `read_head % capacity`. When the buffer is full and you write, `write_head` laps `read_head`, overwriting the oldest slot. No allocation. No shifting. O(1) push and pop. The tricky part: distinguishing "buffer is full" from "buffer is empty" — both have `read_head == write_head` naively. Solutions: track a count separately, or use `capacity + 1` slots and never fill the last one. Rust's standard library provides `VecDeque` which is a heap-allocated ring buffer. For a fixed-capacity version that overwrites on overflow, use the `circular-buffer` crate or implement it yourself.

How It Works in Rust

use std::collections::VecDeque;

struct RingBuffer<T> {
 buf: VecDeque<T>,
 capacity: usize,
}

impl<T> RingBuffer<T> {
 fn new(capacity: usize) -> Self {
     Self { buf: VecDeque::with_capacity(capacity), capacity }
 }

 fn push(&mut self, item: T) {
     if self.buf.len() == self.capacity {
         self.buf.pop_front(); // discard oldest
     }
     self.buf.push_back(item);
 }

 fn iter(&self) -> impl Iterator<Item = &T> {
     self.buf.iter()
 }
}

let mut ring = RingBuffer::new(3);
ring.push(1);
ring.push(2);
ring.push(3);
ring.push(4); // 1 is gone
// Contains: [2, 3, 4]

For a zero-allocation fixed-size variant on the stack:

circular-buffer = "0.1"

What This Unlocks

Bounded log buffers — keep last N log lines without ever allocating more.
Audio/video processing — constant-size frame windows with no GC pressure.
Sliding window algorithms — time-series averages, rate limiting, event debouncing.

Key Differences

Concept	OCaml	Rust
Queue	`Queue.t` (linked list, unbounded)	`VecDeque<T>` (ring buffer, growable)
Fixed-size queue	Manual array + indices	`RingBuffer` wrapper or `circular-buffer` crate
Overwrite-on-full	Manual logic	Encapsulated in `push()` method
Memory layout	Heap-allocated, GC-managed	`VecDeque` is heap; `[T; N]` ring is stack

struct CircularBuffer<T> {
    data: Vec<Option<T>>,
    head: usize,
    tail: usize,
    size: usize,
    capacity: usize,
}

impl<T> CircularBuffer<T> {
    fn new(capacity: usize) -> Self {
        assert!(capacity > 0);
        let mut data = Vec::with_capacity(capacity);
        for _ in 0..capacity { data.push(None); }
        Self { data, head: 0, tail: 0, size: 0, capacity }
    }

    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(())
    }

    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
    }

    fn peek(&self) -> Option<&T> {
        self.data[self.head].as_ref()
    }

    fn push_overwrite(&mut self, val: T) {
        if self.is_full() { self.pop(); } // drop oldest
        self.push(val).unwrap();
    }

    fn is_empty(&self) -> bool { self.size == 0 }
    fn is_full(&self) -> bool { self.size == self.capacity }
    fn len(&self) -> usize { self.size }
}

fn main() {
    let mut buf: CircularBuffer<i32> = CircularBuffer::new(4);
    buf.push(1).unwrap(); buf.push(2).unwrap(); buf.push(3).unwrap();
    println!("Pop: {:?}", buf.pop());
    buf.push(4).unwrap(); buf.push(5).unwrap();
    while let Some(v) = buf.pop() { print!("{v} "); }
    println!();

    // Overwrite mode (ring buffer of fixed size)
    let mut ring: CircularBuffer<i32> = CircularBuffer::new(3);
    for i in 0..6 { ring.push_overwrite(i); }
    println!("Ring (size 3, filled with 0..5):");
    while let Some(v) = ring.pop() { print!("{v} "); }
    println!();
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test] fn fifo_order() {
        let mut b: CircularBuffer<i32> = CircularBuffer::new(4);
        b.push(1).unwrap(); b.push(2).unwrap(); b.push(3).unwrap();
        assert_eq!(b.pop(), Some(1)); assert_eq!(b.pop(), Some(2));
    }
    #[test] fn full_err() {
        let mut b: CircularBuffer<i32> = CircularBuffer::new(2);
        b.push(1).unwrap(); b.push(2).unwrap();
        assert!(b.push(3).is_err());
    }
    #[test] fn overwrite_oldest() {
        let mut b: CircularBuffer<i32> = CircularBuffer::new(3);
        for i in 0..5 { b.push_overwrite(i); }
        assert_eq!(b.pop(), Some(2));
    }
}

(* 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 ()