Circular-Buffer Concepts

A circular buffer (also called a ring buffer) maps a logical sequence of indices 0..len onto a fixed-capacity physical array by wrapping indices around the end of the array using modular arithmetic.

Modular Index Arithmetic and Power-of-Two Masking

In a ring buffer of physical capacity $C$ (where $C$ is a power of two, $C = 2^k$), a logical index $i \in [0, \text{len})$ maps to the physical array slot:

$$\text{physical_index}(i) = (\text{head} + i) \bmod C = (\text{head} + i) \ & \ (C - 1)$$

Because VecDeque<T> always rounds its internal buffer allocation up to a power of two, wrapping around the end of the buffer compiles to a single bitwise AND instruction (& (cap - 1)) with zero division overhead.

Physical Array (capacity = 8, mask = 0b0111 = 7, head = 6, len = 4):

  Logical i = 0  ──> (6 + 0) & 7 = 6  ──> physical[6] = 'A'
  Logical i = 1  ──> (6 + 1) & 7 = 7  ──> physical[7] = 'B'
  Logical i = 2  ──> (6 + 2) & 7 = 0  ──> physical[0] = 'C'  (wrapped!)
  Logical i = 3  ──> (6 + 3) & 7 = 1  ──> physical[1] = 'D'

Physical Layout:
+-----+-----+-----+-----+-----+-----+-----+-----+
| 'C' | 'D' |  .  |  .  |  .  |  .  | 'A' | 'B' |
+-----+-----+-----+-----+-----+-----+-----+-----+
  [0]   [1]   [2]   [3]   [4]   [5]   [6]   [7]
  └───────┘                           └───────┘
  2nd slice (&[T])                    1st slice (&[T])

Split Slices (as_slices) vs. Contiguous Rotation (make_contiguous)

When a circular buffer wraps around the physical boundary (head + len > capacity), its active elements live in two disjoint contiguous memory ranges:

1. First slice: physical[head..capacity]
2. Second slice: physical[0..(head + len - capacity)]

VecDeque<T> exposes both representations:

• deque.as_slices() -> (&[T], &[T]) (and as_mut_slices()) returns the two contiguous slices in $O(1)$ time without copying any data. If the buffer does not currently wrap around, the second slice is empty (&[]).
• deque.make_contiguous() -> &mut [T] shifts elements in place so head becomes 0 (or the elements sit contiguously), returning a single &mut [T] slice.

use std::collections::VecDeque;

fn main() {
    let mut ring = VecDeque::with_capacity(4);
    ring.push_back(20);
    ring.push_back(30);
    ring.push_front(10); // Wraps `10` to the end of the physical buffer

    // 1. Inspect the two physical slices without moving elements:
    let (s1, s2) = ring.as_slices();
    println!("Wrapped as_slices():      s1={s1:?}, s2={s2:?}");

    // 2. Rearrange in place into a single contiguous slice:
    let full_slice: &mut [i32] = ring.make_contiguous();
    println!("After make_contiguous():  full={full_slice:?}");
    println!("as_slices() now:          {:?}", ring.as_slices());
}

Wrapped as_slices():      s1=[10], s2=[20, 30]
After make_contiguous():  full=[10, 20, 30]
as_slices() now:          ([10, 20, 30], [])

How Ring Buffer Reallocation Unwraps Elements

When a wrapped VecDeque<T> reaches full capacity (len == capacity) and must grow to $2C$, it allocates the new buffer and copies the wrapped segment so the elements remain valid under the new power-of-two modulus (2C - 1).