Algorithms and data structures · Intermediate

Circular buffers

Trace circular-buffer head and tail indexes, distinguish empty from full, and examine wraparound, overflow and producer-consumer ordering assumptions.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Reuse a finite array by wrapping indexes
  2. Give empty and full distinct representations
  3. Trace a four-slot wraparound
  4. Respect the condition for mask arithmetic
  5. Publish data and index progress consistently
  6. Test overflow, underflow and repeated wrapping
  7. Ask Logeia about this articleCheck your understanding

Reuse a finite array by wrapping indexes

A circular buffer reuses finite array storage by wrapping an index from the end back to the beginning. Here head names the next write position and tail the next read position. Some implementations reverse those naming conventions, so inspect the actual definitions rather than relying on variable names. Enqueue advances head and dequeue advances tail. Changing the logical front does not require shifting every remaining item physically toward index zero. Distinguish physical array layout from the FIFO order presented to a user. That distinction explains why a wrapped buffer can contain a contiguous logical sequence spread over two separate physical regions.

Give empty and full distinct representations

If equal head and tail mean empty, reusing that identical state for full creates ambiguity. One approach always leaves a slot unused and defines full as the next head position equaling tail. An N-slot array then has capacity N minus one. Other designs retain an occupancy count or generation information and can use all slots. State whether capacity means physical slots or accepted elements. The N-minus-one rule belongs to the selected representation rather than every ring buffer by definition. Establish how empty and full are encoded before deriving arithmetic or interpreting a producer apparently refusing to fill the final physical slot.

Trace a four-slot wraparound

Use four slots with one reserved slot, initially head=0 and tail=0. Enqueuing A,B,C yields head=3 and tail=0, a full buffer. Removing A advances tail to1. Enqueuing D then wraps head from3 to0. Logical contents are B,C,D, not necessarily the order produced by printing physical storage starting at index zero. Head being zero does not indicate emptiness by itself; it must be interpreted with tail. Each operation in this example completes sequentially. The trace does not claim that arbitrary concurrent observers see both indexes as one atomic snapshot or that the same observations are valid without a synchronization protocol.

Respect the condition for mask arithmetic

The next position is generally computed modulo N. For a power-of-two size, suitable nonnegative integer arithmetic can use a bit mask with N minus one. That replacement is not valid for an arbitrary size such as six. Forgetting the premise can visit the wrong subset of indexes or wrap incorrectly. Batch operations introduce another distinction: total free or occupied space may span the end and beginning of the array rather than one contiguous region. Check both total capacity and immediately contiguous space. Validate the representation and arithmetic boundaries before treating a faster-looking index expression as an interchangeable optimization for every buffer size.

Publish data and index progress consistently

Publishing head before an element is initialized can let a consumer access unfinished data. Returning space before a consumer finishes can let a producer overwrite an element still in use. A single-producer single-consumer protocol has different requirements from several producers competing at one end. Linux kernel ordering idioms also cannot simply be copied into user-space C++ using ordinary racing integers. Use atomics or locks appropriate to the language and execution environment, and include object lifetime. Explain which observation authorizes safe access to an element. Correct modulo arithmetic alone is not a complete concurrent queue implementation or proof of safe memory publication.

Test overflow, underflow and repeated wrapping

Rejecting a full enqueue, overwriting the oldest value, and waiting for space are different policies. A recent-log history and a queue of unprocessed jobs need not accept the same loss behavior. Test dequeue on empty, enqueue on full, more than one complete wrap, and alternating single-item operations. Comparing order and accepted-item count against a reference queue helps detect off-by-one mistakes. The four-slot example is state arithmetic rather than a measured performance result. A useful circular buffer combines storage reuse with explicit capacity, waiting, and synchronization rules; none of those policies is automatically supplied merely by drawing the array as a ring.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 9

Choose a learning path