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

Кольцевой буфер, или циклический буфер (англ. 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->writeptr)rb->full=0;
	rb->readptr = tmp;
		
	return RINGBUFFER_OK;
}

Ссылки

• CircularBuffer на сайте Portland Pattern Repository (англ.)
• Boost: Templated Circular Buffer Container (англ.)
• Chapter 28: Digital Signal Processors / Steven W. Smith, The Scientist and Engineer’s Guide to Digital Signal Processing (англ.)