Кольцевой FIFO буфер в языке Си

Фундаментальная вещь организации любой цифровой системы — буферы. Они используются везде: память, шины, сети, алгоритмы. Рассмотрим реализацию такого буфера на языке Си для использования в своих проектах.

Function Reference

Как обычно, методы возвращают статусы:

typedef enum RINGBUF_STATUS {
    RINGBUF_OK,        ///< Успех
    RINGBUF_ERR,       ///< Ошибка
    RINGBUF_PARAM_ERR, ///< Ошибка в аргументах
    RINGBUF_OVERFLOW,  ///< Попытка записи > буфера
} RINGBUF_STATUS;

Сам буфер инициализируется через структуру:

typedef struct RINGBUF_t {
    u8_t *buf;            ///< Указатель на буфер
    volatile size_t tail; ///< Точка чтения [ячейка]
    volatile size_t head; ///< Точка записи [ячейка]
    volatile size_t size; ///< Размер буфера [ячейка]
    volatile size_t cell_size; ///< Размер одной ячейки [байт]
} RINGBUF_t;

Описание методов:
(Описание аргументов представлено в DoxyGen-формате в .с-файле)

/* Главные методы */
// Инициализация буфера
RINGBUF_STATUS RingBuf_Init(void *buf, u16_t size, size_t cellsize, RINGBUF_t *rb); 
// Очистка буфера
RINGBUF_STATUS RingBuf_Clear(RINGBUF_t *rb);
// Считать количество доступных для чтения ячеек
RINGBUF_STATUS RingBuf_Available(u16_t *len, RINGBUF_t *rb);

/* Запись */
// Записать 1 байт в буфер
RINGBUF_STATUS RingBuf_BytePut(const u8_t data, RINGBUF_t *rb);
// Записать 1 ячейку заданного размера в буфер
RINGBUF_STATUS RingBuf_CellPut(const void *data, RINGBUF_t *rb);
// Записать произвольное количество данных в буфер 
RINGBUF_STATUS RingBuf_DataPut(const void *data, u16_t len, RINGBUF_t *rb);

/* Чтение (Считывание и очистка) */
// Прочесть 1 байт
RINGBUF_STATUS RingBuf_ByteRead(u8_t *data, RINGBUF_t *rb);
// Прочесть 1 ячейку заданного размера
RINGBUF_STATUS RingBuf_CellRead(void *data, RINGBUF_t *rb);
// Прочесть произвольное количество данных
RINGBUF_STATUS RingBuf_DataRead(void *data, u16_t len, RINGBUF_t *rb);

/* Просмотр (Считывание без очистки) */
// Подсмотреть 1 байт
RINGBUF_STATUS RingBuf_ByteWatch(u8_t *data, RINGBUF_t *rb);
// Подсмотреть 1 ячейку заданного размера
RINGBUF_STATUS RingBuf_CellWatch(void *data, RINGBUF_t *rb);
// Подсмотреть произвольное количество данных
RINGBUF_STATUS RingBuf_DataWatch(void *data, u16_t len, RINGBUF_t *rb);

Принцип кольцевого буфера

Кольцевые буферы по умолчанию строятся по топологии “FIFO”.

Это один из способов организации данных. Ещё он называется очередью.
FIFO расшифровывается как “First Input — First Output”. Первым вошёл — первым вышел.

Другой способ — “LIFO” или стек. Last input, first output — последним вошёл — первым вышел.
Практически применение закольцованности для LIFO бессмысленно, по крайней мере я ни разу такого не встречал.
LIFO применяется в алгоритмах, например DFS.
Также стек применяется для низкоуровневых задач, таких как стек вызовов подпрограмм или прерываний.
Гипотетически, все нижеописанные выкладки и рассуждения подходят для реализации LIFO.

Суть FIFO в том, что те данные, которые первыми записали, первыми и должны быть считаны.
Проще представить это схематично.

Представим себе мусоропровод. Это такая труба для мусора в многоквартирных домах, с люками на каждом этаже.
(Такую аналогию я в сети ещё не встречал)
В начальный момент времени он пуст. Мы кинули туда мешок, то есть некоторый пакет данных.

Кольцевой FIFO буфер в языке Си — *Типичный подъезд* *в панельке*

Остальные жильцы в течение дня накидали ещё мусора. Образовалась горочка. Ну, предположим, 5 пакетов. Пришла уборщица, открыла люк, мешки посыпались. Какой мешок выпадет первым? Правильно. Наш первый. Далее вывалится мешок жильца №2, затем жильца №3, и так далее…

А теперь представим, что уборщица вовремя не собирает мусор, труба мусоропровода забилась. Вызвали аварийную бригаду из ЖЭКа, доблестный Жека прочистил трубу, она вновь доступна для жильцов.
Это и есть закольцованность FIFO буфера. Некоторое допущение, которое позволяет потеряться данным, но которое всегда оставляет возможность для записи новых, релевантных данных.

FIFO блокируется при переполнении, в отличие от кольцевого буфера

Какое этому применение?
В любых асинхронных процессах, например для шины USB, или для приёма данных по UART, требуется своевременно обрабатывать принятые данные.
Так как посылки могут прийти в любой момент, а контроллер в это время может заниматься более приоритетными задачами, вызывается быстрое прерывание, которое лишь перекладывает данные из одного буфера в другой.
Таким образом, когда придёт время обработать шину, программа обратится к долгосрочному буферу, который обеспечит обработку данных так, как будто они были получены в реальном времени.

Реализация в языке

Читатель может задаться вопросом: зачем же прописывать всё это руками, если это есть почти в любом языке?
Ответ прост: в языке Си, основном для разработки для микроконтроллеров, всего этого нет.
На мой взгляд, для создания высокоэффективных систем, в целях максимальной оптимизации, разработчик обязан “прощупать” всё своими руками. Тем более, что подобные вещи пишутся один раз, и применяются во всех последующих проектах.
Это есть в том же C++, но там подобные структуры — динамические. Для нашей крохотной относительно ПК ОЗУ динамическая память — зло злющее.

Сначала поймём, как представить эту очередь в памяти. Естественно, делать это будем с помощью массива. Он будет хранилищем данных. Создадим ещё 2 переменные — некоторые счётчики. В них будут лежать индексы чтения и записи.

Создадим также методы. Основные:

Чтение
Запись
Размер (ячеек для чтения)
Очистка

Так как буферов может использоваться несколько, используем структурный подход. В структуре будут лежать:

Массив данных — а лучше указатель на выделенное пространство памяти
Размер этого массива
Точка записи или head
Точка чтения или tail

В каждый метод будем передавать указатель на instance структуры. То есть сами методы будут реализовывать лишь логику.

Начнём с размера. Количество доступных для чтения ячеек считается так: tail-head. Всё просто. Самое главное — проверить, если tail > head, то нужно учесть ещё и размер всего буфера.

Операция записи: положили данные, начиная с head, прибавили head.

Операция чтения: считали данные, начиная с tail, прибавили tail.

Теперь можно писать саму реализацию. Пример можно найти на GitHub.
В своём фирменном стиле я использовал ещё и статусы, но в вашем коде это совершенно необязательно.

Благодарность можно оставить тут.

Function Reference

Принцип кольцевого буфера

Реализация в языке

Ссылки