CSE Roadmap

Core tier · about 6 hours · 7 parts

Part 3 of 7 · 2 min read

The ring buffer

In plain words: A clock face has twelve places, and the hand returns to the first after the twelfth. A buffer of fixed size can be used the same way. The analogy stops in one place: the clock hand moves by itself, and the buffer needs two separate positions that the program moves.

A ring buffer (circular buffer) is a fixed-size array with two indices: in, the slot where the next item is put, and out, the slot from which the next item is taken. Each index moves forward by one after use and wraps to 0 after the last slot, which is done with the remainder operator:

#define SLOTS 8
int buf[SLOTS];
int in = 0, out = 0;

buf[in] = item;   in  = (in  + 1) % SLOTS;      /* put */
item = buf[out];  out = (out + 1) % SLOTS;      /* get */

With 4 slots, the indices go 0, 1, 2, 3, 0, 1, and so on. A trace of puts and gets, starting empty:

Operation in after out after Items in buffer
put A 1 0 A
put B 2 0 A, B
put C 3 0 A, B, C
get (A) 3 1 B, C
put D 0 1 B, C, D
put E 1 1 B, C, D, E

After the last put, in equals out (both 1), yet the buffer is full. At the start, in equals out and the buffer is empty. So the indices alone cannot tell full from empty. A separate count of items (page 6's condition-variable version) or the two semaphores of section 3 settles this.

Ring buffer

A ring buffer is a fixed-size array used as a queue, with one index at which the next item is put and one from which the next is taken, each advanced modulo the array size, so that the space freed by taken items is reused.

Example: in a buffer of 4 slots, putting an item at index 3 moves in to 0, and the oldest items are read first.

Check yourself: 1. What are in and out after 5 puts and 2 gets in a buffer of 4? 2. Why can in == out mean either empty or full? 3. Why is the ring buffer a queue and not a stack?