# Задача 03 — кольцевой буфер (C++)

> Разминка уровня «основная»: структура маленькая, но встречается везде. Ориентир — 40–60 минут.

## Глава I. Общая информация

- **Цель:** научиться писать структуру с фиксированной памятью и без сдвигов элементов.
- **Почему это в Eltex:** приём/передача пакетов, буферы DMA, очереди между потоками —
  всё это кольцевые буферы. Понимание wrap-around и «полный/пустой» — прямой вопрос на
  собеседовании. Механизм тот же, что у сетевой карты: пакеты пишутся в кольцо по мере
  прихода, драйвер вычитывает их с другого конца, и обе стороны никогда не двигают уже
  записанные данные по памяти — двигаются только индексы `head`/`tail`.
- **Что сдаётся:** `solution.cpp`, проходящий `python3 grade.py 03`.

## Глава II. Что нужно знать до старта

Идея: массив фиксированного размера + два индекса. `head` — куда писать, `tail` — откуда
читать. Когда индекс доходит до конца, он возвращается в начало: `idx = (idx + 1) % capacity`.
Сдвигать элементы не нужно никогда — в этом весь смысл: `push`/`pop` двигают только индекс,
а не байты в памяти, поэтому обе операции остаются O(1) независимо от размера буфера.

Ловушка, из-за которой задача попадает в собеседования: **как отличить пустой буфер от
полного, если оба индекса совпали?** При `head == tail` возможны оба состояния — буфер мог
быть только что создан (пуст) или заполнен ровно `capacity` раз (полон) — по одним индексам
это не различить. Варианты: хранить счётчик `size`, либо оставлять одну ячейку свободной.
В нашем интерфейсе есть `size()`, поэтому проще хранить счётчик.

Почему дальше: тот же счётчик `size_` вместо пересчёта по индексам — частый приём и в
`std::deque`, и в реализациях lock-free очередей, где индексы вообще нельзя лишний раз читать.

## Глава III. Задание

```c++
class RingBuffer {
public:
    explicit RingBuffer(size_t capacity);
    ~RingBuffer();
    bool   push(int v);       // false, если буфер полон (перезапись НЕ делать)
    bool   pop(int& out);     // false, если буфер пуст
    size_t size() const;
    size_t capacity() const;
    bool   empty() const;
    bool   full() const;
};
```

Требования:

- O(1) на `push`/`pop`, никаких сдвигов элементов;
- память выделяется один раз в конструкторе и освобождается в деструкторе;
- корректное поведение после заворачивания индексов (записали до конца, продолжили с начала);
- двойного освобождения быть не должно.

## Глава IV. Ступени

**Ступень 1 (10 минут).** Поля: указатель на массив, `capacity_`, `size_`, `head_`, `tail_`.
Конструктор выделяет массив и обнуляет поля. Деструктор освобождает. Если хочешь короче —
`std::vector<int>` вместо ручного `new[]`, тогда деструктор не нужен вовсе.

**Ступень 2 (10 минут).** `empty()` — это `size_ == 0`, `full()` — `size_ == capacity_`.
Проверь на буфере ёмкости 1: после одного `push` он полон, после одного `pop` пуст.

**Ступень 3 (15 минут).** `push`: если полон — вернуть `false` и ничего не менять; иначе
записать в `head_`, сдвинуть `head_ = (head_ + 1) % capacity_`, увеличить `size_`, вернуть `true`.

**Ступень 4 (15 минут).** `pop`: если пуст — `false`; иначе отдать `buffer_[tail_]`, сдвинуть
`tail_`, уменьшить `size_`, вернуть `true`.

**Ступень 5.** Проверь руками wrap-around: ёмкость 4, положи 4 элемента, сними 2, положи
ещё 3 — все значения должны идти в правильном порядке. Затем `python3 grade.py 03`.

## Глава V. Критерии приёмки

`PASS` от `grade.py 03`: сборка без предупреждений, ASAN/UBSAN чистые, все проверки `ok`,
включая порядок FIFO и корректный wrap-around.

## Глава VI. Подсказки (после первой попытки)

<details>
<summary>Значения после заворота идут не в том порядке</summary>

Проверь, что `pop` читает именно `tail_`, а `push` пишет именно в `head_`, и что оба индекса
инкрементируются **после** операции. Классическая ошибка — сдвинуть `head_` до записи.
</details>

<details>
<summary>Перезапись при полном буфере</summary>

Ты не проверяешь `full()` в `push`. По условию перезапись запрещена: полный буфер возвращает
`false` и не портит старые данные.
</details>

<details>
<summary>ASAN: утечка или двойное освобождение</summary>

Если память выделена через `new[]`, освобождать нужно `delete[]` (не `delete`). Проще взять
`std::vector<int>` — тогда вопрос исчезает.
</details>

## Глава VII. Ловушки

- Сдвиг элементов вместо индексов → цена `push`/`pop` вырастает до O(n) → теряется весь
  смысл структуры, видно по сравнению с наивным `std::vector` на бенчмарке.
- Путаница «пусто/полно» при совпавших индексах (`head_ == tail_`) без отдельного `size_` →
  `full()` и `empty()` дают одинаковый ответ на разных состояниях → тест на заполненный буфер
  ёмкости > 1 падает.
- `%` на каждом шаге там, где можно было обойтись условием — не ошибка, но на собеседовании
  спросят «а быстрее можно?» (ответ: `if (++idx == cap) idx = 0;`, деление по модулю дороже
  сравнения).
- Копирование объекта без правила трёх/пяти → два объекта владеют одним и тем же `new[]`-буфером
  → двойное освобождение при выходе обоих из области видимости, ловится ASAN. Если сдаёшь с
  ручным `new[]`, запрети копирование (`= delete`).

**Факты для карточек**
- base | Сложность `push`/`pop` кольцевого буфера? — O(1)
- core | Как отличить пустой буфер от полного при `head_ == tail_`? — хранить отдельный
  счётчик `size_` (или жертвовать одной ячейкой)
- core | Чем `delete[]` отличается от `delete` для массива, выделенного `new[]`? — `delete`
  без `[]` на массиве — UB, вызовет деструктор только для первого элемента и испортит подсчёт
  размера аллокации
- base | Какое условие делает `push` дешевле, чем `% capacity_` на каждый вызов? —
  `if (++idx == cap) idx = 0;`

## После сдачи

Разбор: как устроены буферы в драйверах (ring buffer с head/tail для DMA), почему в
многопоточном варианте нужны атомарные индексы и `memory_order`.