Build Lab: Dynamic Circular Buffer & Amortized O(1) Vector

Ring Buffer Indexing: Power-of-Two Masking & Full vs. Empty Disambiguation

Why do production ring buffers (Rust's std::collections::VecDeque<T>, Java's ArrayDeque<E>, Linux kernel kfifo, and LMAX Disruptor) enforce that capacity $C$ is always a power of two ($C = 2^p$)? Because wrapping an index modulo $C$ normally requires an integer division instruction (div on x86-64 takes 14–26 clock cycles and cannot be pipelined), whereas when $C = 2^p$, modulo reduces to a 1-cycle bitwise AND with $M = C - 1$:

$$\text{physical\_index}(i) = (\text{head} + i) \bmod 2^p = (\text{head} + i) \mathrel{\&} (C - 1)$$

How do we distinguish a completely full ring buffer from a completely empty ring buffer when both states have $\text{head} \equiv \text{tail} \pmod C$? There are two canonical engineering designs:

1. Explicit head_ + size_ (Rust VecDeque style): Store the physical index head_ $\in [0, C)$ and element count size_ $\in [0, C]$. The tail index is computed on the fly as (head_ + size_) & (cap_ - 1),Empty is size_ == 0, and Full is size_ == cap_.
2. Unmasked Monotonic read_idx_ & write_idx_ (Linux kfifo style): Store monotonically increasing 64-bit unsigned counters read_idx_ and write_idx_ that are only masked with & (cap_ - 1) at the moment of array indexing! Then size() == write_idx_ - read_idx_, Empty is write_idx_ == read_idx_, and Full is write_idx_ - read_idx_ == cap_ (critical for lock-free Single-Producer Single-Consumer queues).

Architectural Comparison of Deque Implementations

Visualizing Wrapped Physical Spans & Unwrapping Upon $2\times$ Growth

Circular Deque Operations & Two-Span Reallocation Flow

Production Implementation: Power-of-Two Dynamic Circular Deque

#include <cassert>
#include <cstddef>
#include <memory>
#include <new>
#include <utility>

template <typename T>
class CircularDeque {
  T* data_ = nullptr;
  std::size_t head_ = 0;
  std::size_t size_ = 0;
  std::size_t cap_ = 0; // Always a power of 2 when allocated (0 initially)

  std::size_t mask() const noexcept { return cap_ - 1; }

  void grow() {
    const std::size_t new_cap = (cap_ == 0) ? 8 : (cap_ * 2);
    T* new_data = static_cast<T*>(::operator new(new_cap * sizeof(T), std::align_val_t{alignof(T)}));

    if (size_ > 0) {
      // Unwrap the two physical spans [head_ .. cap_) and [0 .. head_) into [0 .. size_)
      const std::size_t span1 = cap_ - head_;
      if (span1 >= size_) {
        std::uninitialized_move_n(data_ + head_, size_, new_data);
      } else {
        std::uninitialized_move_n(data_ + head_, span1, new_data);
        std::uninitialized_move_n(data_, size_ - span1, new_data + span1);
      }
      for (std::size_t i = 0; i < size_; ++i) {
        std::destroy_at(data_ + ((head_ + i) & mask()));
      }
    }
    if (data_) {
      ::operator delete(data_, std::align_val_t{alignof(T)});
    }
    data_ = new_data;
    head_ = 0;
    cap_ = new_cap;
  }

public:
  CircularDeque() = default;

  ~CircularDeque() {
    for (std::size_t i = 0; i < size_; ++i) {
      std::destroy_at(data_ + ((head_ + i) & mask()));
    }
    if (data_) ::operator delete(data_, std::align_val_t{alignof(T)});
  }

  void push_back(T value) {
    if (size_ == cap_) grow();
    const std::size_t tail = (head_ + size_) & mask();
    std::construct_at(data_ + tail, std::move(value));
    ++size_;
  }

  void push_front(T value) {
    if (size_ == cap_) grow();
    // Unsigned wrap-around: (0 - 1) & (cap_ - 1) == cap_ - 1!
    head_ = (head_ - 1) & mask();
    std::construct_at(data_ + head_, std::move(value));
    ++size_;
  }

  void pop_front() noexcept {
    assert(size_ > 0);
    std::destroy_at(data_ + head_);
    head_ = (head_ + 1) & mask();
    --size_;
  }

  void pop_back() noexcept {
    assert(size_ > 0);
    --size_;
    const std::size_t tail = (head_ + size_) & mask();
    std::destroy_at(data_ + tail);
  }

  T& operator[](std::size_t i) noexcept {
    return data_[(head_ + i) & mask()];
  }

  const T& operator[](std::size_t i) const noexcept {
    return data_[(head_ + i) & mask()];
  }

  std::size_t size() const noexcept { return size_; }
  std::size_t capacity() const noexcept { return cap_; }
};