Ring Buffers and Queues

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.

// 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

// 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.

// one_time_pass.c — three values written and read, then the buffer stays empty
#include <stdio.h>
#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.

// interleaved_order.c — write and read calls interleaved
#include <stdio.h>
#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.

// 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

// queue.c — enqueue at the tail, dequeue from the head
#include <stdlib.h>
#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;
}

// queue_passage.c — a value dequeued also reaches the reader exactly once
#include <stdio.h>
#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.

// 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

// 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;
}

// fullness_policy.c — comparing the reject and overwrite policies
#include <stdio.h>
#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.