Circular Buffer / Ring Buffer

Also Known As

TL;DR

Explanation

A circular buffer has a head (read) and tail (write) pointer. Write: place at tail, advance tail % capacity. Read: take from head, advance head % capacity. Full: tail + 1 == head. Empty: head == tail. O(1) read and write. Fixed memory — no allocation after creation. Overwrite mode: when full, advance head (discard oldest) without blocking. Lock-free single-producer/single-consumer implementations exist using atomic operations. Used in: kernel ring buffers, audio/video streaming, network packet queues, and rolling log windows.

Common Misconception

Why It Matters

Common Mistakes

• Not handling the full condition — writing to a full buffer silently overwrites unread data.
• Using modulo on non-power-of-2 sizes in tight loops — use bitwise AND with power-of-2 size for speed.
• Not making the buffer size a power of 2 — % operation can be replaced with & (size-1).
• Shared circular buffer without synchronisation — concurrent read/write requires locks or atomic operations.

Code Examples

// Dynamic array as log buffer — unbounded memory:
$logs = [];
while (true) {
    $logs[] = readEvent(); // Grows forever — OOM after enough events
}

// Circular buffer — fixed memory, O(1) operations:
class CircularBuffer {
    private array $buffer;
    private int $head = 0;
    private int $tail = 0;
    private int $size = 0;

    public function __construct(private int $capacity) {
        $this->buffer = array_fill(0, $capacity, null);
    }

    public function write(mixed $item): void {
        $this->buffer[$this->tail] = $item;
        $this->tail = ($this->tail + 1) % $this->capacity;
        if ($this->size < $this->capacity) $this->size++;
        else $this->head = ($this->head + 1) % $this->capacity; // Overwrite oldest
    }

    public function read(): mixed {
        if ($this->size === 0) return null;
        $item = $this->buffer[$this->head];
        $this->head = ($this->head + 1) % $this->capacity;
        $this->size--;
        return $item;
    }
}

References

• ↗ https://en.wikipedia.org/wiki/Circular_buffer

Tags

Related Terms