Ring Buffer
What it is
A ring buffer is an array with a fixed size. After the last slot, the next slot is the first one again. It stores values in arrival order without shifting them. Audio systems and log buffers use this shape to keep memory use small.
The core idea
Positions wrap around a fixed array, so adding or removing a value does not need to shift the others. This gives O(1) work per call. The trade-off is a fixed size limit and careful handling of full and empty states. A peek observes the oldest value without consuming it.
Example
With capacity 2:
- Push 10, then 20. Both succeed.
- Push 30. It fails because the buffer is full.
- Pop returns 10.
- Push 30 now succeeds.
- The next two pops return 20, then 30.
Where you meet this
- io_uring "gets its name from ring buffers which are shared between user space and kernel space": one ring for requests (the submission queue) and one for results (the completion queue). (io_uring(7))
- The kernel tracing ring buffer has two modes. Overwrite mode loses the oldest events when it is full. Producer and consumer mode stops writing and loses the newest events. (Ring buffer design)
- The LMAX Disruptor: "At the heart of the disruptor mechanism sits a pre-allocated bounded data structure in the form of a ring-buffer." (Disruptor paper)
When to choose it: a queue with a fixed upper size, where you never want to allocate memory after start, like audio samples, log or trace events, or messages between two threads.
When not to: you cannot pick a size up front, or losing or refusing a value when it is full is not acceptable. Then a growing queue fits better, with a separate limit so it cannot eat all memory. Decide early what "full" means for you: refuse the new value (this challenge), or overwrite the oldest one (a trace log that only cares about recent events).
Common bugs
- Reading the newest value first.
- Letting peek consume a value.
- Wasting one slot to tell full and empty apart.
- Overwriting the oldest value when this challenge requires rejection.
- Computing length by subtracting wrapped positions.
- Using a bit mask for a size that is not a power of two.
Check it yourself
Try capacity 1, then capacity 3 or 7. Fill, drain, and refill the buffer. Check length when a position wraps and when a push is rejected.
Keep it fast
Advance positions instead of shifting values. Allocate the array once.
Learn more
Linux kfifo uses a power-of-two ring. The LMAX Disruptor paper explains a ring shared by several threads.