Ivan's wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
# Circular buffer
A **circular buffer** (also called a ring buffer) is a fixed-capacity [[queue]] backed by a flat [[array]] with two indices: a read head and a write head. When either index reaches the end of the array it wraps back to zero, making the array appear circular. This gives O(1) enqueue and dequeue with no allocation and no data movement, at the cost of a fixed maximum size.

```c
struct ring {
    int    data[N];
    size_t head;   // next read position
    size_t tail;   // next write position
    size_t count;
};

bool enqueue(struct ring *r, int val) {
    if (r->count == N) return false;   // full
    r->data[r->tail] = val;
    r->tail = (r->tail + 1) % N;
    r->count++;
    return true;
}

int dequeue(struct ring *r) {
    int val = r->data[r->head];
    r->head = (r->head + 1) % N;
    r->count--;
    return val;
}
```

The modulo arithmetic can be replaced by a bitmask (`& (N-1)`) when N is a power of two, which is faster on most hardware. The `count` field disambiguates full from empty; an alternative is to leave one slot unused and detect full by `(tail + 1) % N == head`.

Circular buffers are ubiquitous in embedded systems and OS kernels where dynamic allocation is undesirable: UART receive buffers, audio driver ring buffers, network driver packet queues, and kernel log buffers (`/dev/kmsg`) all use this structure. The fixed size is a feature rather than a limitation in these contexts — it provides a bounded memory footprint and predictable latency.

| Operation | Time |
|---|---|
| Enqueue | O(1) |
| Dequeue | O(1) |
| Peek | O(1) |
| Search | O(n) |