= Circular buffer operation costs
With storage allocated in advance, each successful insertion, removal, `peek`, `size`, and full/empty check uses $O(1)$ worst-case <time complexity> in <Big O notation>. This assumes constant-cost indexed <array> access, bounded <machine word> index arithmetic and fixed-cost scalar item reads and writes. Each operation touches a bounded number of slots and fields regardless of $n$ and $C$; no shifting, scanning or resizing occurs. Rejected operations also take constant work. Producing a copy of all $n$ live items takes $O(n)$ work under the same scalar-cost assumptions.
The preallocated <array> occupies $O(C)$ scalar slots plus constant bookkeeping. Allocation and any initial slot construction are separate setup costs. Copying a large item, running an expensive destructor or callback, allocating an item, or growing a <dynamic array> changes the operation cost and must be charged separately. The bound is worst-case structural work, with no need for <amortized analysis>, and says nothing about a measured wall-clock deadline.
These formulas describe sequential calls. Wrapping <array indices> implies neither <atomic operations> nor safe access from multiple <software threads>. Publication of an item's contents and reuse of its slot require a protocol justified under the relevant <memory model>, including any necessary <acquire-release synchronization>. The kernel documentation discusses barriers under explicit producer/consumer restrictions; Boost's documentation separately requires <mutual exclusion> for shared access involving writes. Neither property follows merely from choosing a <circular buffer>.<Circular Buffers by David Howells and Paul E. McKenney>[David Howells and Paul E. McKenney, Circular Buffers, Using memory barriers with circular buffers; The producer; The Consumer: explicit synchronization and ordering requirements]{ref}<Boost.Circular Buffer by Jan Gaspar/Implementation>[Jan Gaspar, Boost.Circular Buffer, Implementation, Thread-Safety: shared access involving a writer requires mutual exclusion]{ref}
Back to article page
