Interested Article - Кольцевой буфер

Кольцевой буфер. Иллюстрация визуально показывает, что у буфера нет настоящего конца. Тем не менее, поскольку физическая память никогда не делается закольцованной, обычно используется линейное представление, как показано ниже

Кольцевой буфер , или циклический буфер ( англ. ring-buffer) — это структура данных , использующая единственный буфер фиксированного размера таким образом, как будто бы после последнего элемента сразу же снова идет первый. Такая структура легко предоставляет возможность буферизации потоков данных .

Применение

Кольцевой буфер находит очень широкое применение в том числе при программировании микроконтроллеров . Данные структуры часто используют для организации различных очередей сообщений и буферов приёма-передачи различных коммуникационных интерфейсов. Популярность КБ обусловлена тем, что это один из самых простых и эффективных способов организовать FIFO ( англ. first in — first out , «первым пришёл — первым вышел») без использования динамической памяти. Существует множество разновидностей КБ.

Внутреннее устройство

Кольцевой буфер создается пустым, с некоторой заранее определённой длиной. Например, это семиэлементный буфер:

Предположим, что в середину буфера записывается «1» (в кольцевом буфере точная начальная ячейка не имеет значения):

Затем предположим, что после единицы были добавлены ещё два элемента — «2» и «3»:

Если после этого два элемента должны быть удалены из буфера, то выбираются два наиболее старых элемента. В нашем случае удаляются элементы «1» и «2», в буфере остается только «3»:

Если в буфере находится 7 элементов, то он заполнен:

Если продолжить запись в буфер, не принимая во внимание его заполненность, то новые данные начнут перезаписывать старые данные. В нашем случае, добавляя элементы «A» и «B», мы перезапишем «3» и «4»:

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

Наконец, если теперь удалить из буфера два элемента, то удалены будут не «3» и «4», а «5» и «6», потому что «A» и «B» перезаписали элементы «3» и «4»; буфер придет в состояние:

Пример реализации на Си

#include <stdlib.h> #define CHAR_SIZE (sizeof(char)) #define RINGBUFFER_OK (0) #define RINGBUFFER_ERR_NULL (-1) #define RINGBUFFER_ERR_EMPTY (-2) #define RINGBUFFER_ERR_FULL (-3) typedef struct { char* start; char* end; volatile char* readptr; volatile char* writeptr; volatile int full; } RingBuffer; RingBuffer* newRingBuffer(unsigned long int capacity) { char* mem = malloc(capacity * CHAR_SIZE); if(mem == NULL) {return NULL;} RingBuffer* rb = malloc(sizeof(RingBuffer)); if(rb == NULL) {free(mem); return NULL;} rb->start = mem; rb->end = mem + capacity; rb->readptr = mem; rb->writeptr = mem; rb->full=0; return rb; } void deleteRingBuffer(RingBuffer* rb) { if(rb == NULL) return; free(rb->start); free(rb); } int RingBuffer_trywrite(RingBuffer* rb, char c) { if(rb == NULL) return RINGBUFFER_ERR_NULL; if((rb->writeptr == rb->readptr)&&rb->full) return RINGBUFFER_ERR_FULL; *(rb->writeptr) = c; char* tmp = rb->writeptr + 1; if(tmp >= rb->end) tmp = rb->start; if(tmp==rb->readptr)rb->full=-1; rb->writeptr = tmp; return RINGBUFFER_OK; } int RingBuffer_tryread(RingBuffer* rb, char* c) { if(rb == NULL) return RINGBUFFER_ERR_NULL; if((rb->readptr == rb->writeptr)&&(!rb->full)) return RINGBUFFER_ERR_EMPTY; *c = (rb->readptr); char* tmp = rb->readptr + 1; if(tmp >= rb->end) tmp = rb->start; if(tmp==rb->readptr)rb->full=0; rb->readptr = tmp; return RINGBUFFER_OK; }