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

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

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

Применение[править | править код]

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

Внутреннее устройство[править | править код]

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

Circular buffer - empty.svg

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

Circular buffer - XX1XXXX.svg

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

Circular buffer - XX123XX.svg

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

Circular buffer - XXXX3XX.svg

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

Circular buffer - 6789345.svg

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

Circular buffer - 6789AB5.svg

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

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

Circular buffer - X789ABX.svg

Пример реализации на Си[править | править код]

#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;
} 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;
	
	
	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 + 1 == rb->readptr) return RINGBUFFER_ERR_FULL;
	
	
	*(rb->writeptr) = c;
	
	char* tmp = rb->writeptr + 1;
	if(tmp >= rb->end) tmp = rb->start;
	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) return RINGBUFFER_ERR_EMPTY;
	
	
	*c = (rb->readptr);
	
	char* tmp = rb->readptr + 1;
	if(tmp >= rb->end) tmp = rb->start;
	rb->readptr = tmp;
	
	
	return RINGBUFFER_OK;
}

Ссылки[править | править код]