A circular buffer (also called a ring buffer) is a fixed-size, first-in-first-out data structure where the write position wraps around to the beginning when it reaches the end. It is the right data structure for streaming data, producer-consumer queues, audio buffers, and log ringbuffers. No malloc per element, O(1) push and pop.

The Core Idea

/* A circular buffer of size N has N-1 usable slots.
   When head == tail, the buffer is empty.
   When (tail + 1) % capacity == head, the buffer is full. */

 head                tail
  |                   |
  v                   v
 [3] [4] [5] [_] [_] [1] [2]
      ^                        ^
      Elements go here         Older elements dequeued from here

Implementation

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

typedef struct {
    int    *buffer;
    size_t  capacity;   /* allocated slots — usable slots = capacity - 1 */
    size_t  head;       /* next dequeue position */
    size_t  tail;       /* next enqueue position */
} CircBuf;

CircBuf *circbuf_new(size_t capacity) {
    CircBuf *cb = malloc(sizeof(CircBuf));
    cb->buffer   = malloc(capacity * sizeof(int));
    cb->capacity = capacity;
    cb->head     = 0;
    cb->tail     = 0;
    return cb;
}

bool circbuf_empty(const CircBuf *cb) {
    return cb->head == cb->tail;
}

bool circbuf_full(const CircBuf *cb) {
    return (cb->tail + 1) % cb->capacity == cb->head;
}

size_t circbuf_count(const CircBuf *cb) {
    return (cb->tail - cb->head + cb->capacity) % cb->capacity;
}

bool circbuf_push(CircBuf *cb, int value) {
    if (circbuf_full(cb)) return false;   /* or overwrite oldest if desired */
    cb->buffer[cb->tail] = value;
    cb->tail = (cb->tail + 1) % cb->capacity;
    return true;
}

bool circbuf_pop(CircBuf *cb, int *out) {
    if (circbuf_empty(cb)) return false;
    *out = cb->buffer[cb->head];
    cb->head = (cb->head + 1) % cb->capacity;
    return true;
}

void circbuf_free(CircBuf *cb) {
    free(cb->buffer);
    free(cb);
}

int main() {
    CircBuf *cb = circbuf_new(8);   /* 7 usable slots */

    for (int i = 1; i <= 7; i++) circbuf_push(cb, i * 10);

    printf("Full: %d  Count: %zun", circbuf_full(cb), circbuf_count(cb));

    int val;
    while (circbuf_pop(cb, &val)) {
        printf("%d ", val);   /* 10 20 30 40 50 60 70 */
    }
    printf("n");

    circbuf_free(cb);
    return 0;
}

Why capacity – 1 Usable Slots?

We need one sentinel slot to distinguish empty (head == tail) from full ((tail+1) % cap == head). If all slots were usable, both states would look identical when the buffer fills. Alternatives:

  • Store a separate count field — allows full capacity use but adds state to keep synchronized
  • Use a power-of-two capacity and bitmask instead of modulo — faster on hot paths

Power-of-Two Optimization

#define BUF_SIZE 8  /* must be a power of two */
#define BUF_MASK (BUF_SIZE - 1)

typedef struct {
    int    buffer[BUF_SIZE];
    size_t head;
    size_t tail;
} FastBuf;

void fast_push(FastBuf *fb, int val) {
    if (((fb->tail + 1) & BUF_MASK) != fb->head) {
        fb->buffer[fb->tail & BUF_MASK] = val;
        fb->tail++;
    }
}

bool fast_pop(FastBuf *fb, int *out) {
    if (fb->head == fb->tail) return false;
    *out = fb->buffer[fb->head & BUF_MASK];
    fb->head++;
    return true;
}

With a power-of-two size, index % capacity becomes index & (capacity - 1) — a bitwise AND, which is faster than division. The head and tail counters are allowed to wrap at their natural integer overflow point — the masking handles it correctly, and since they are unsigned, the arithmetic is defined.

Thread Safety — What You Need to Add

The single-producer, single-consumer (SPSC) case is safe on most architectures if:

  • head and tail are declared volatile (prevents register caching)
  • Or better: use _Atomic size_t (C11 atomics) for the index variables
  • Data items are written before the tail is advanced (memory barrier)

For multi-producer or multi-consumer, you need a mutex or a lock-free algorithm (significantly more complex). For embedded systems and real-time audio, the SPSC pattern is the standard approach.

For contrast, see how linked lists handle dynamic growth — a circular buffer gives up flexibility for predictable performance and zero allocation per element. Test the implementation in our c compiler — start with a small capacity (4) to force wrap-around early and verify the head/tail logic works correctly.

TL;DR

  • A circular buffer has fixed size, O(1) push/pop, and no per-element allocation
  • Use one sentinel slot: empty = head == tail; full = (tail+1)%cap == head
  • Or use a separate count field to allow 100% capacity utilization
  • Use power-of-two sizes and bitwise AND for fast index wrapping
  • For SPSC lock-free use, mark indices as _Atomic and write data before advancing the tail
  • Circular buffers are ideal for streaming I/O, producer-consumer queues, and fixed-size log ringbuffers
  • The wrapping formula with modulo is correct for any capacity; bitmasking works only for powers of two