A Queue With No malloc: The Ring Buffer

A queue that grows by allocating nodes is a luxury you cannot always afford. In an audio callback, a network interrupt handler, or a microcontroller with kilobytes of RAM, you cannot call malloc, you cannot block, and you cannot have unbounded memory. What you can have is a fixed array and the discipline to treat it as a circle. That is a ring buffer (also called a circular buffer), and it is one of the most quietly important data structures in systems programming.

The whole structure

typedef struct {
    int *buf;
    size_t cap;
    size_t head;  // index of the next write
    size_t count; // number of elements currently stored
} RingBuffer;

Storage is provided by the caller, so the buffer itself never allocates. head is where the next value will be written. Instead of also tracking a tail, this design stores count, the number of live elements, and derives the read position from head and count. That choice quietly solves a classic ambiguity, which we will get to.

Push and pop, with wraparound

bool rb_push(RingBuffer *rb, int x) {
    if (rb->count == rb->cap) return false;     // full
    rb->buf[rb->head] = x;
    rb->head = (rb->head + 1) % rb->cap;        // wrap
    rb->count++;
    return true;
}

bool rb_pop(RingBuffer *rb, int *out) {
    if (rb->count == 0) return false;           // empty
    size_t tail = (rb->head + rb->cap - rb->count) % rb->cap;
    *out = rb->buf[tail];
    rb->count--;
    return true;
}

The % rb->cap is the entire trick. When head reaches the end of the array it wraps back to 0 and starts overwriting the slots that have already been popped. The data never moves; only the indices travel around the array in circles. A push advances head; a pop advances the derived tail by shrinking count. The oldest element is always at (head + cap - count) % cap, and the + cap before the modulo keeps the arithmetic positive without signed-underflow surprises.

The empty-versus-full problem, dodged

If you store head and tail instead of head and count, you hit a famous puzzle: an empty buffer has head == tail, but so does a completely full one. You cannot tell them apart from the indices alone. People solve it with an extra "full" flag, or by wasting one slot so full means head is one behind tail. By storing count instead, this design sidesteps the whole issue. Empty is count == 0, full is count == cap, and there is never any doubt. A small representation choice that erases an entire category of off-by-one bugs.

Where these run the world

• Audio and DSP. The driver writes samples into a ring while your callback reads them out, decoupling two threads running at different rates.
• Network stacks and drivers. NIC receive and transmit rings are exactly this structure, shared between hardware and the kernel.
• Logging and telemetry. A fixed-size ring keeps the most recent N events and drops the oldest, giving you a bounded-memory "flight recorder."
• Lock-free queues. The single-producer, single-consumer (SPSC) ring buffer is the foundation of high-performance wait-free message passing, because with one writer and one reader the head and tail never need a lock.

The lessons

• Bounded by design. A ring buffer cannot use more memory than its array, which is a feature, not a limitation. It applies backpressure (rb_push returns false when full) instead of growing without limit.
• Caller-owned storage. By taking the backing array from the caller, the same buffer works on the stack, in a static region, or in memory you got from somewhere exotic. It imposes no allocator.
• Indices, not pointers. Everything is integer arithmetic on one contiguous array, which is cache-friendly and trivially correct to reason about.

It is a structure you can implement in twenty lines and then find everywhere you look, from the kernel to your headphones. The circle is the idea: reuse the same slots forever by wrapping around.

Build it yourself. Solve the Ring Buffer challenge on barehands and get graded on correctness and speed. No libraries, just cc -std=c11.