--- title: 'Ring Buffers and Queues' source: 'https://academia.sh/en/courses/c-systems-programming/ring-buffers-and-queues' course: 'Systems Programming with C' language: en updated: '2026-09-26T03:02:44+00:00' license: 'CC BY-SA 4.0' objectives: - 'Implements a fixed-capacity ring buffer in C with write and read pointers' - 'Measures that a value does not stay in the buffer after being read, that is, that it reaches its destination exactly once' - 'Repeats the same handoff principle at unbounded capacity with a linked queue' --- # Ring Buffers and Queues A fixed-capacity ring buffer and a linked queue in which a value passes exactly once between a producer and a consumer; measuring, through equality, that a read value no longer stays in the buffer. The previous lesson measured the **shared** class, where a node was seen by two pointers at once: a change was there no matter when it was read, because the shared object was permanent. This lesson measures a different class through a different structure: a producer writes a value into a buffer, a consumer reads it — but a read here is a **take** operation, not a **peek**. Once a value is read, it does not stay in the buffer; a second read returns empty. This behavior defines **handoff**, one of the four classes: the value passes through an intermediary and reaches a reader, but has no lasting visibility after that reader. ## Ring Buffer: Fixed-Capacity Write and Read The buffer holds a fixed array of four elements; `head` carries the index of the next read, `tail` the index of the next write, `count` the number of occupied elements. `ring_write` does not write if the buffer is full and returns `0`; `ring_read` does not read if the buffer is empty and returns `0`. Both return `1` if successful. ```c // ring.h — fixed-capacity ring buffer #ifndef RING_H #define RING_H #define RING_CAPACITY 4 struct Ring { int data[RING_CAPACITY]; int head; int tail; int count; }; void ring_init(struct Ring *ring); int ring_write(struct Ring *ring, int value); int ring_read(struct Ring *ring, int *out); #endif ``` ```c // ring.c — write and read at fixed capacity #include "ring.h" void ring_init(struct Ring *ring) { ring->head = 0; ring->tail = 0; ring->count = 0; } int ring_write(struct Ring *ring, int value) { if (ring->count == RING_CAPACITY) { return 0; } ring->data[ring->tail] = value; ring->tail = (ring->tail + 1) % RING_CAPACITY; ring->count = ring->count + 1; return 1; } int ring_read(struct Ring *ring, int *out) { if (ring->count == 0) { return 0; } *out = ring->data[ring->head]; ring->head = (ring->head + 1) % RING_CAPACITY; ring->count = ring->count - 1; return 1; } ``` ## A Value Passing Through the Buffer Exactly Once Three values are written in order, then read in order. The order is preserved (the first value written is the first read), but the real measurement is in the last two lines: trying to read the same value a second time returns empty, because the value was **taken** out of the buffer on the first read, not left there. ```c // one_time_pass.c — three values written and read, then the buffer stays empty #include #include "ring.h" int main(void) { struct Ring ring; ring_init(&ring); ring_write(&ring, 10); ring_write(&ring, 20); ring_write(&ring, 30); int value = 0; ring_read(&ring, &value); printf("%s %d\n", "first value read", value); ring_read(&ring, &value); printf("%s %d\n", "second value read", value); ring_read(&ring, &value); printf("%s %d\n", "third value read", value); int ok = ring_read(&ring, &value); printf("%s %d\n", "fourth read succeeded", ok); printf("%s %d\n", "did value change after the failed fourth read", (int)(value == 30)); return 0; } ``` ``` first value read 10 second value read 20 third value read 30 fourth read succeeded 0 did value change after the failed fourth read 1 ``` **DS4.** The signature of `ring_read` (`int ring_read(struct Ring *ring, int *out)`) does not say **who is responsible for releasing** a pointer, and in the same way it doesn't say whether the value it receives stays in the buffer — what decides that is the line `ring->count = ring->count - 1`, inside the body itself. The three values come out in order (10, 20, 30), because `head` advances by one on every read and the buffer preserves first-in, first-out order. The fourth call returns `0` because `count` has dropped to zero; since nothing is written to `out`, `value` keeps carrying **30** left over from the previous call — this is proof that `value` itself did not change, not that the buffer offered a new value. The class is **handoff**: every value reached exactly one reader, and left no trace in the buffer after that reader; this is where it differs from the **shared** class — there the shared object kept standing even after being read, here the slot that was read empties out. ## Producer and Consumer Interleaving Writes and reads can interleave: two writes, one read, one more write, two reads. This mimics the real situation where a producer and a consumer use the same buffer at different speeds. Because the buffer can hold at most four elements, the read before the third write makes room. ```c // interleaved_order.c — write and read calls interleaved #include #include "ring.h" int main(void) { struct Ring ring; ring_init(&ring); int value = 0; ring_write(&ring, 1); ring_write(&ring, 2); ring_read(&ring, &value); printf("%s %d\n", "read after two writes", value); ring_write(&ring, 3); ring_read(&ring, &value); printf("%s %d\n", "second read after three writes", value); ring_read(&ring, &value); printf("%s %d\n", "third read after three writes", value); int ok = ring_read(&ring, &value); printf("%s %d\n", "fourth read succeeded", ok); return 0; } ``` ``` read after two writes 1 second read after three writes 2 third read after three writes 3 fourth read succeeded 0 ``` **DS5.** No matter what order the write and read calls interleave in, each read returns the oldest **not-yet-read** value — the result of `head` advancing only on a read and `tail` advancing only on a write. This second run produces the same three values as the first (this time 1, 2, 3) in the same order, but the extra write placed between them does not change the outcome: the buffer can hold at most four elements at any moment, and because the read before the third write makes room, no overflow ever happens. This flexibility between when a value is written and when it is read is a second property of handoff: the producer and the consumer do not have to run at the same speed, the buffer between them acts as a cushion — but what happens when a write is attempted beyond capacity (overwriting an unread value) is not this lesson's subject; that question belongs to the next lesson, which measures the **unobserved** class. ## Queue: The Same Principle at Unbounded Capacity The ring buffer has a fixed capacity; the queue applies the same first-in first-out order with linked nodes, without a capacity limit. `queue_enqueue` adds a node at the tail, `queue_dequeue` removes the node at the head, returns its value, and releases the node — here too, the value that was read does not stay in the queue. ```c // queue.h — unbounded FIFO queue #ifndef QUEUE_H #define QUEUE_H struct QueueNode { int value; struct QueueNode *next; }; struct Queue { struct QueueNode *head; struct QueueNode *tail; }; void queue_init(struct Queue *queue); void queue_enqueue(struct Queue *queue, int value); int queue_dequeue(struct Queue *queue, int *out); #endif ``` ```c // queue.c — enqueue at the tail, dequeue from the head #include #include "queue.h" void queue_init(struct Queue *queue) { queue->head = NULL; queue->tail = NULL; } void queue_enqueue(struct Queue *queue, int value) { struct QueueNode *node = malloc(sizeof *node); if (node == NULL) { return; } node->value = value; node->next = NULL; if (queue->tail == NULL) { queue->head = node; } else { queue->tail->next = node; } queue->tail = node; } int queue_dequeue(struct Queue *queue, int *out) { if (queue->head == NULL) { return 0; } struct QueueNode *node = queue->head; *out = node->value; queue->head = node->next; if (queue->head == NULL) { queue->tail = NULL; } free(node); return 1; } ``` ```c // queue_passage.c — a value dequeued also reaches the reader exactly once #include #include "queue.h" int main(void) { struct Queue queue; queue_init(&queue); queue_enqueue(&queue, 100); queue_enqueue(&queue, 200); int value = 0; queue_dequeue(&queue, &value); printf("%s %d\n", "first value dequeued", value); queue_dequeue(&queue, &value); printf("%s %d\n", "second value dequeued", value); int ok = queue_dequeue(&queue, &value); printf("%s %d\n", "dequeue succeeded on an empty queue", ok); return 0; } ``` ``` first value dequeued 100 second value dequeued 200 dequeue succeeded on an empty queue 0 ``` **DS6.** The queue uses a different memory model than the ring buffer — instead of a fixed array, each element sits in its own allocated node, and `queue_dequeue` releases the node after reading it (`free(node)`). But the class being measured is the same: every value reaches exactly one call, and after that call it leaves no trace in the queue. The absence of a capacity limit (`queue_enqueue` always succeeds, unless `malloc` fails) does not change the handoff class; it only removes the ring buffer's notion of "full." ## Reject-on-Full or Overwrite Policy `ring_write` rejects writing to a full buffer. But in some producer/consumer setups the newest value matters more than the oldest — in that case, instead of rejecting on full, overwriting the oldest element is preferred. Both policies can operate on the same `struct Ring`; they differ only in what they do when the buffer is full. ```c // ring_overwrite.h — declaration of a write policy that overwrites the oldest value when full #ifndef RING_OVERWRITE_H #define RING_OVERWRITE_H #include "ring.h" int ring_write_overwrite(struct Ring *ring, int value); #endif ``` ```c // ring_overwrite.c — implementation of a write policy that overwrites the oldest value when full #include "ring_overwrite.h" int ring_write_overwrite(struct Ring *ring, int value) { if (ring->count == RING_CAPACITY) { ring->head = (ring->head + 1) % RING_CAPACITY; } else { ring->count = ring->count + 1; } ring->data[ring->tail] = value; ring->tail = (ring->tail + 1) % RING_CAPACITY; return 1; } ``` ```c // fullness_policy.c — comparing the reject and overwrite policies #include #include "ring_overwrite.h" int main(void) { struct Ring ring; ring_init(&ring); ring_write(&ring, 10); ring_write(&ring, 20); ring_write(&ring, 30); ring_write(&ring, 40); int rejected = ring_write(&ring, 50); printf("%s %d\n", "result of writing to a full buffer under the reject policy", rejected); int overwrite_result = ring_write_overwrite(&ring, 99); printf("%s %d\n", "result of writing to a full buffer under the overwrite policy", overwrite_result); int out; for (int i = 0; i < RING_CAPACITY; i++) { ring_read(&ring, &out); printf("%s %d\n", "value read in order after the overwrite", out); } return 0; } ``` ``` result of writing to a full buffer under the reject policy 0 result of writing to a full buffer under the overwrite policy 1 value read in order after the overwrite 20 value read in order after the overwrite 30 value read in order after the overwrite 40 value read in order after the overwrite 99 ``` **DS15.** Both policies make a different choice on a full buffer, but both are deterministic: `ring_write` returns `0` on full without changing anything — the value `50` never enters the structure at all. `ring_write_overwrite` instead advances `head` by one and writes over the index where the oldest element (`10`) was sitting; `10` disappears without ever reaching a reader. This defines **unobserved**, one of the four classes: a value entered the structure but was overwritten before it reached any reader. The difference between the rejected `50` and the overwritten `10` matters — `50` was never written at all, `10` was written and then disappeared; neither is ever readable in the end, but for different reasons. ## The Bounding Measurement A read function's signature does not say whether the value it reads stays at the source. `int ring_read(struct Ring *ring, int *out)` and `int list_sum(const struct Node *head)` (from the previous lesson) belong to the same family: both read a structure. But one leaves the value it read inside the structure (the list is permanent), the other removes the value it read from the structure (the buffer empties out). This difference does not show up in the parameter types, the return type, or even the function name; it can only be measured by looking at whether the body decrements `count`, or by making two calls in a row and comparing their results — exactly as this lesson did. ## Summary - The ring buffer applies the same first-in-first-out order in a fixed-capacity array that the queue applies in linked nodes without a capacity limit. - A value does not stay in the buffer or the queue after being read; a second read or dequeue returns empty — the class is **handoff**. - Handoff's difference from **shared**: a shared object stays in place after being read, but a handoff's read slot empties and the value can never be read again. - A producer's and a consumer's write/read order can interleave; the buffer acts as a cushion between them. - Reject-on-full and overwrite-oldest are two separate policies: the rejected value never enters the structure at all, the overwritten value enters and then disappears without ever reaching a reader — this second case defines the **unobserved** class. - Whether a read function leaves the value it read behind at the source does not show up in its signature; it can only be measured by reading the body or by comparing two consecutive calls. ## Next Step In this lesson we measured that a value is read exactly once and then leaves the buffer. The next lesson, Hash Tables, moves on with a different question: does a value stored under a key always give the same result when read back repeatedly under that key, or is a copy produced at read time? The class measured there is **copy**: the value read from the table is not the table's own copy, but an independent copy the caller receives.