Circular queues

Three items arrive each tick and two leave, in only eight cells. Watch head and tail go round and round.

⋯17bool put(struct ring *r, int v)18{19    if (r->count == CAP)20        return false;21    r->items[r->tail] = v;22    r->tail = (r->tail + 1) % CAP;23    r->count++;24    return true;25}26 27bool get(struct ring *r, int *v)28{29    if (r->count == 0)30        return false;31    *v = r->items[r->head];32    r->head = (r->head + 1) % CAP;33    r->count--;34    return true;35}36 37int main(void)38{39    struct ring r = { .count = 0 };40    int next = 1, refused = 0, served = 0;41    for (int t = 0; t < TICKS; t++) {42        for (int i = 0; i < IN; i++) {43            if (!put(&r, next))44                refused++;45            next++;46        }47        for (int i = 0; i < OUT; i++) {48            int v;49            if (get(&r, &v))50                served++;51        }52    }53    printf("in %d per tick: %d arrived, %d served, %d refused, %d waiting\n",54           IN, next - 1, served, refused, r.count);55    printf("head %d, tail %d\n", r.head, r.tail);56    return 0;57}

A ring with no end

In Queues, head and tail only ever moved right, so the queue ran out of room with six free cells behind its head. The fix is to let both indices go back to cell 0 when they pass the last cell. Cell 7 is then followed by cell 0, as if the array were bent round into a ring. The tail writes and moves on; the head reads and follows it round; neither ever reaches an end.

Nothing in memory moves or bends. The array is the same eight cells in a row, and the items stay where they were written: only the two indices go round. The picture draws the cells twice to show both views at once, the ring the indices see and the row that is really there.

The code and its cost

Wrapping the indices

#define CAP 8

struct ring {
    int items[CAP];
    int head, tail, count;
};

sizeof (struct ring) is 44 bytes: 32 for the array and 4 each for head, tail and count. In the clip r sits at 0x7fc0, so items[i] is at 0x7fc0 + 4i, head at 0x7fe0, tail at 0x7fe4 and count at 0x7fe8.

bool put(struct ring *r, int v)
{
    if (r->count == CAP)
        return false;
    r->items[r->tail] = v;
    r->tail = (r->tail + 1) % CAP;
    r->count++;
    return true;
}

bool get(struct ring *r, int *v)
{
    if (r->count == 0)
        return false;
    *v = r->items[r->head];
    r->head = (r->head + 1) % CAP;
    r->count--;
    return true;
}

(r->tail + 1) % CAP is the remainder after dividing by 8: for tail 0 to 6 it is one more, and for tail 7 it is 8 % 8 = 0. That one remainder is the whole trick. Because get can find the ring empty, it returns true or false and hands the item back through the pointer v.

When CAP is a power of two, the remainder can be worked out with a mask instead: (i + 1) & (CAP - 1) keeps only the low three bits of i + 1 when CAP is 8, which a processor does in a single instruction, faster than a division. Ring buffers in fast code are usually sized 64, 1024 or 4096 for that reason.

Full or empty?

When the ring is empty, head and tail point at the same cell. They also point at the same cell when it is full: tail has gone all the way round and caught up with head. head == tail cannot tell the two apart. The clip shows both. With 1 or 2 arrivals a tick the ring empties at the end of every tick, and ends with head and tail both at 2 or both at 4; with 3 a tick it fills at tick 6, when count reaches 8, and from tick 7 on it refuses arrivals, with head and tail together on a full ring.

There are two common ways out:

• Keep a count, as this ring does: empty is count 0, full is count CAP.
• Leave one cell unused: the ring is full when the cell after tail is head, so it holds at most CAP − 1 items, and head == tail means empty only.

When the ring is full

put has two choices. It can refuse the new item, as this one does, which suits a keyboard buffer: a key pressed while the buffer is full is lost, and the earlier keys are kept. Or it can overwrite the oldest item, by writing at tail and moving head on as well, which suits a log of the latest entries or the samples of an audio delay line, where only the newest matter.

What the arrival rate does

Each tick, IN items arrive and up to two leave. The slider under the picture runs the same program with IN from 1 to 4; each run lasts 10 ticks:

While arrivals keep up with departures, the ring never fills, however small it is. Once they outrun departures, it fills whatever its size: a larger ring only takes longer. With 3 a tick, one more item is left waiting each tick, 1, 2, 3, 4, 5, 6, and from tick 7 one arrival a tick is refused. With 3 or 4 a tick, 26 items were stored, so tail ended at 26 mod 8 = 2, and 20 were read, so head ended at 20 mod 8 = 4.

What it costs

put and get each take a fixed few steps, whatever the ring holds, and no item ever moves. Unlike the array queue of Queues, no cell is ever lost: every cell is used again once head has passed it. The price is a fixed capacity, chosen when the ring is made.

Running it yourself

gcc -std=c11 -Wall -Wextra -pedantic ring-buffer.c -o ring
./ring
gcc -std=c11 -Wall -Wextra -pedantic -DIN=4 ring-buffer.c -o ring4
./ring4

The first prints the row for 3 arrivals a tick, the second the row for 4.

Worked example

Where the items are. A ring of 8 cells with head 6 and tail 1 holds (1 − 6 + 8) % 8 = 3 items, in cells 6, 7 and 0. In general a ring that leaves no cell unused holds (tail − head + CAP) % CAP items, except when it is full, which is where the count comes in.

One cell unused. With CAP 8 and one cell left empty, the ring is full at 7 items, when the cell after tail is head.

An echo. An echo effect adds to each sound sample the sample from a quarter of a second ago, at half the strength: y[n] = x[n] + 0.5 x[n − 12,000], at 48,000 samples a second. It keeps the last 12,000 samples in a ring. Each new sample reads the oldest one, x[n − 12,000], from the cell at tail, then overwrites it with x[n] and moves tail on. A 10 ms delay at the same rate needs 480 cells. Real-time processing builds such delay lines.

Where it’s used

Keyboards and networks. A keyboard keeps the keys pressed but not yet read in a small ring buffer; a network card keeps arriving packets in a ring until the system takes them.

Audio. Delay lines, echoes and the memory of a filter’s past inputs live in ring buffers, where the index wraps exactly as in Circular vs linear convolution.

Logs. A log that keeps only the latest entries overwrites the oldest when it is full.

Between two threads. One thread puts data in at the tail while another takes it out at the head, and as long as each only moves its own index, they barely need to coordinate.

Reference card

Platform: C11, gcc on x86-64 Linux: int 4 bytes, pointers 8, little-endian. Addresses in the pictures are short stand-ins, by one rule for the whole course; sizes are the real ones.