Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Ring buffers: make capacity and overwrite rules explicit

Last updated: 5 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A ring buffer stores a fixed number of elements in a reusable array. Head identifies the next read slot; tail identifies the next write slot; count distinguishes empty from full when the indices coincide. Each enqueue and dequeue uses O(1) time without shifting elements. The API must choose whether a full buffer rejects new data, blocks a producer, or overwrites the oldest item. Those choices have different correctness effects. A telemetry sampler might overwrite old samples, while a payment queue must not silently discard a pending request.

Operational case

A sensor gateway reserves three slots for latest pressure readings. It writes 47, 52, and 61, reads 47, then writes 58 into the freed physical slot. Logical read order is now 52, 61, 58 even though physical array order wraps. The fourth write before a read would be rejected under this contract. The gateway might choose overwrite semantics for a dashboard, but that would need a different method name and a lost-sample counter. Capacity is part of the interface, not a hidden implementation setting.

Working Python program

python
capacity = 3
slots = [None] * capacity
head = tail = count = 0
for reading in (47, 52, 61):
    slots[tail] = reading
    tail = (tail + 1) % capacity
    count += 1
oldest = slots[head]
head = (head + 1) % capacity
count -= 1
slots[tail] = 58
tail = (tail + 1) % capacity
count += 1
print(oldest, [slots[(head + offset) % capacity] for offset in range(count)])

Output

Output
47 [52, 61, 58]

Time, space, and tradeoff

Storage is O(capacity), and each index update is O(1). The demonstration collects current readings in O(count) time only to display them. A real implementation should check count before every write and read; this short trace has known valid operations. Under concurrent producers and consumers, index changes need synchronization or a proven lock-free protocol. Modulo arithmetic is cheap relative to shifting a long list, but a zero capacity must be rejected before the first operation.

Common Mistakes

  • Do not use head == tail alone to distinguish full from empty.
  • Do not overwrite unread items unless the contract says so.
  • Do not share mutable indices across threads without coordination.

Connected lessons

CLOCK caches: revisit pages through reference bits extends the retention comparison.

Hashed timing wheels: bucket incident expiries by tick extends the retention comparison.

data structures
stacks-and-queues
Storage details