Как реализовать циклический буфер в C?

Ответ 1

Можете ли вы перечислить типы, необходимые во время кодирования буфера, или вам нужно иметь возможность добавлять типы во время выполнения через динамические вызовы? Если бы первый, то я бы создал буфер в виде массива, выделенного кучей n структур, где каждая структура состоит из двух элементов: тега enum, идентифицирующего тип данных, и объединения всех типов данных. То, что вы теряете с точки зрения дополнительного хранения для небольших элементов, вы считаете, что вам не приходится иметь дело с распределением/освобождением и результирующей фрагментацией памяти. Затем вам нужно просто отслеживать начальные и конечные индексы, определяющие элементы заголовка и хвоста буфера, и обязательно вычислять mod n при добавлении/уменьшении индексов.

Ответ 2

Простейшим решением было бы отслеживать размер элемента и количество элементов, а затем создавать буфер соответствующего количества байтов:

typedef struct circular_buffer
{
    void *buffer;     // data buffer
    void *buffer_end; // end of data buffer
    size_t capacity;  // maximum number of items in the buffer
    size_t count;     // number of items in the buffer
    size_t sz;        // size of each item in the buffer
    void *head;       // pointer to head
    void *tail;       // pointer to tail
} circular_buffer;

void cb_init(circular_buffer *cb, size_t capacity, size_t sz)
{
    cb->buffer = malloc(capacity * sz);
    if(cb->buffer == NULL)
        // handle error
    cb->buffer_end = (char *)cb->buffer + capacity * sz;
    cb->capacity = capacity;
    cb->count = 0;
    cb->sz = sz;
    cb->head = cb->buffer;
    cb->tail = cb->buffer;
}

void cb_free(circular_buffer *cb)
{
    free(cb->buffer);
    // clear out other fields too, just to be safe
}

void cb_push_back(circular_buffer *cb, const void *item)
{
    if(cb->count == cb->capacity){
        // handle error
    }
    memcpy(cb->head, item, cb->sz);
    cb->head = (char*)cb->head + cb->sz;
    if(cb->head == cb->buffer_end)
        cb->head = cb->buffer;
    cb->count++;
}

void cb_pop_front(circular_buffer *cb, void *item)
{
    if(cb->count == 0){
        // handle error
    }
    memcpy(item, cb->tail, cb->sz);
    cb->tail = (char*)cb->tail + cb->sz;
    if(cb->tail == cb->buffer_end)
        cb->tail = cb->buffer;
    cb->count--;
}

Ответ 3

// Note power of two buffer size
#define kNumPointsInMyBuffer 1024 

typedef struct _ringBuffer {
    UInt32 currentIndex;
    UInt32 sizeOfBuffer;
    double data[kNumPointsInMyBuffer];
} ringBuffer;

// Initialize the ring buffer
ringBuffer *myRingBuffer = (ringBuffer *)calloc(1, sizeof(ringBuffer));
myRingBuffer->sizeOfBuffer = kNumPointsInMyBuffer;
myRingBuffer->currentIndex = 0;

// A little function to write into the buffer
// N.B. First argument of writeIntoBuffer() just happens to have the
// same as the one calloc'ed above. It will only point to the same
// space in memory if the calloc'ed pointer is passed to
// writeIntoBuffer() as an arg when the function is called. Consider
// using another name for clarity
void writeIntoBuffer(ringBuffer *myRingBuffer, double *myData, int numsamples) {
    // -1 for our binary modulo in a moment
    int buffLen = myRingBuffer->sizeOfBuffer - 1;
    int lastWrittenSample = myRingBuffer->currentIndex;

    int idx;
    for (int i=0; i < numsamples; ++i) {
        // modulo will automagically wrap around our index
        idx = (i + lastWrittenSample) & buffLen; 
        myRingBuffer->data[idx] = myData[i];
    }

    // Update the current index of our ring buffer.
    myRingBuffer->currentIndex += numsamples;
    myRingBuffer->currentIndex &= myRingBuffer->sizeOfBuffer - 1;
}

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

Я всегда убеждаюсь, что максимальный объем звука, который может отображаться на экране, намного меньше размера кольцевого буфера. В противном случае вы можете читать и писать из одного куска. Это, скорее всего, даст вам странные экспонаты.

Ответ 4

Сначала заголовок. Вам не нужна по модулю арифметика для обертывания буфера, если вы используете бит ints для удержания указателей головы и хвоста и их размер, чтобы они были полностью синхронизированы. IE: 4096, забитый в 12-битный неподписанный int, равен 0, сам по себе, без каких-либо ограничений. Устранение по модулю арифметики, даже для степеней 2, удваивает скорость - почти точно.

10 миллионов итераций заполнения и слива буфера 4096 любого типа элементов данных занимают 52 секунды на моем третьем поколении i7 Dell XPS 8500 с использованием компилятора Visual Studio 2010 С++ с установкой по умолчанию и 1/8192nd для обслуживания нулевой точки.

Я бы RX переписал тестовые циклы в main(), чтобы они больше не контролировали поток - который и должен контролироваться возвращаемыми значениями, указывающими, что буфер заполнен или пуст, а оператор break; оператора, IE: наполнитель и осушитель должны быть в состоянии столкнуться друг с другом без коррупции или нестабильности. В какой-то момент я надеюсь многопоточность этого кода, после чего это поведение будет иметь решающее значение.

QUEUE_DESC (дескриптор очереди) и функция инициализации заставляют все буферы в этом коде быть степенью 2. Эта схема не будет работать иначе. Обратите внимание, что QUEUE_DESC не жестко закодирован, он использует константу манифеста (#define BITS_ELE_KNT) для своей конструкции. (Я предполагаю, что сила 2 - достаточная гибкость здесь)

Чтобы сделать выборку времени выполнения буфера, я попробовал разные подходы (не показано здесь) и остановился на использовании USHRT для Head, Tail, EleKnt, способных управлять буфером FIFO [USHRT]. Чтобы избежать арифметики по модулю, я создал маску для && с Head, Tail, но эта маска оказывается (EleKnt -1), поэтому просто используйте это. Использование USHRTS вместо bit ints увеличило производительность ~ 15% на тихой машине. Процессоры ядра Intel всегда были быстрее, чем их шины, поэтому на занятой общей машине упаковка ваших структур данных загружается и выполняется впереди других конкурирующих потоков. Компромиссы.

Обратите внимание, что фактическое хранилище для буфера выделено в куче с помощью calloc(), а указатель находится в базе структуры, поэтому структура и указатель имеют ТОЧНО один и тот же адрес. IE; никакое смещение, требуемое для добавления в адрес структуры для привязки регистров.

В том же ключе все переменные, обслуживающие буфер, физически смежны с буфером, привязанные к одной и той же структуре, поэтому компилятор может сделать красивый язык ассемблера. Вам нужно будет убить встроенную оптимизацию, чтобы увидеть какую-либо сборку, потому что в противном случае она будет подавлена ​​в забвение.

Чтобы поддерживать полиморфизм любого типа данных, я использовал memcpy() вместо назначений. Если вам нужна только гибкость для поддержки одного типа случайной переменной для компиляции, тогда этот код работает отлично.

Для полиморфизма вам просто нужно знать тип и требования к хранению. Массив дескрипторов DATA_DESC обеспечивает способ отслеживания каждого элемента данных, который помещается в QUEUE_DESC.pBuffer, чтобы он мог быть правильно восстановлен. Я бы просто выделил достаточно памяти pBuffer, чтобы удерживать все элементы самого большого типа данных, но отслеживать, сколько из этого хранилища фактически используется в DATA_DESC.dBytes. Альтернативой является повторное использование кучного менеджера.

Это означает, что QUEUE_DESC UCHAR * pBuffer будет иметь параллельный массив компаньонов для отслеживания типа данных и размера, в то время как место хранения данных в pBuffer останется таким же, как сейчас. Новый член будет чем-то вроде DATA_DESC * pDataDesc или, возможно, DATA_DESC DataDesc [2 ^ BITS_ELE_KNT], если вы сможете найти способ превзойти ваш компилятор в представлении с такой прямой ссылкой. Calloc() всегда более гибкий в этих ситуациях.

Вы все еще memcpy() в Q_Put(), Q_Get, но количество фактически скопированных байтов будет определено DATA_DESC.dBytes, а не QUEUE_DESC.EleBytes. Элементы потенциально имеют разные типы/размеры для любого заданного put или get.

Я считаю, что этот код удовлетворяет требованиям к скорости и размеру буфера и может быть выполнен для удовлетворения требований к 6 различным типам данных. Я оставил множество тестов в формате printf(), поэтому вы можете сами убедиться (или нет), что код работает правильно. Генератор случайных чисел демонстрирует, что код работает для любой случайной комбинации head/tail.

enter code here
// Queue_Small.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <stdio.h>
#include <time.h>
#include <limits.h>
#include <stdlib.h>
#include <malloc.h>
#include <memory.h>
#include <math.h>

#define UCHAR unsigned char
#define ULONG unsigned long
#define USHRT unsigned short
#define dbl   double
/* Queue structure */
#define QUEUE_FULL_FLAG 1
#define QUEUE_EMPTY_FLAG -1
#define QUEUE_OK 0
//  
#define BITS_ELE_KNT    12  //12 bits will create 4.096 elements numbered 0-4095
//
//typedef struct    {
//  USHRT dBytes:8;     //amount of QUEUE_DESC.EleBytes storage used by datatype
//  USHRT dType :3; //supports 8 possible data types (0-7)
//  USHRT dFoo  :5; //unused bits of the unsigned short host storage
// }    DATA_DESC;
//  This descriptor gives a home to all the housekeeping variables
typedef struct  {
    UCHAR   *pBuffer;   //  pointer to storage, 16 to 4096 elements
    ULONG Tail  :BITS_ELE_KNT;  //  # elements, with range of 0-4095
    ULONG Head  :BITS_ELE_KNT;  //  # elements, with range of 0-4095
    ULONG EleBytes  :8;     //  sizeof(elements) with range of 0-256 bytes
    // some unused bits will be left over if BITS_ELE_KNT < 12
    USHRT EleKnt    :BITS_ELE_KNT +1;// 1 extra bit for # elements (1-4096)
    //USHRT Flags   :(8*sizeof(USHRT) - BITS_ELE_KNT +1);   //  flags you can use
    USHRT   IsFull  :1;     // queue is full
    USHRT   IsEmpty :1;     // queue is empty
    USHRT   Unused  :1;     // 16th bit of USHRT
}   QUEUE_DESC;

//  ---------------------------------------------------------------------------
//  Function prototypes
QUEUE_DESC *Q_Init(QUEUE_DESC *Q, int BitsForEleKnt, int DataTypeSz);
int Q_Put(QUEUE_DESC *Q, UCHAR *pNew);
int Q_Get(UCHAR *pOld, QUEUE_DESC *Q);
//  ---------------------------------------------------------------------------
QUEUE_DESC *Q_Init(QUEUE_DESC *Q, int BitsForEleKnt, int DataTypeSz)    {
    memset((void *)Q, 0, sizeof(QUEUE_DESC));//init flags and bit integers to zero
    //select buffer size from powers of 2 to receive modulo 
    //                arithmetic benefit of bit uints overflowing
    Q->EleKnt   =   (USHRT)pow(2.0, BitsForEleKnt);
    Q->EleBytes =   DataTypeSz; // how much storage for each element?
    //  Randomly generated head, tail a test fixture only. 
    //      Demonstrates that the queue can be entered at a random point 
    //      and still perform properly. Normally zero
    srand(unsigned(time(NULL)));    // seed random number generator with current time
    Q->Head = Q->Tail = rand(); // supposed to be set to zero here, or by memset
    Q->Head = Q->Tail = 0;
    //  allocate queue storage
    if(NULL == (Q->pBuffer = (UCHAR *)calloc(Q->EleKnt, Q->EleBytes)))  {
        return NULL;
    }   else    {
        return Q;
    }
}
//  ---------------------------------------------------------------------------
int Q_Put(QUEUE_DESC *Q, UCHAR *pNew)   
{
    memcpy(Q->pBuffer + (Q->Tail * Q->EleBytes), pNew, Q->EleBytes);
    if(Q->Tail == (Q->Head + Q->EleKnt)) {
        //  Q->IsFull = 1;
        Q->Tail += 1;   
        return QUEUE_FULL_FLAG; //  queue is full
    }
    Q->Tail += 1;   //  the unsigned bit int MUST wrap around, just like modulo
    return QUEUE_OK; // No errors
}
//  ---------------------------------------------------------------------------
int Q_Get(UCHAR *pOld, QUEUE_DESC *Q)   
{
    memcpy(pOld, Q->pBuffer + (Q->Head * Q->EleBytes), Q->EleBytes);
    Q->Head += 1;   //  the bit int MUST wrap around, just like modulo

    if(Q->Head == Q->Tail)      {
        //  Q->IsEmpty = 1;
        return QUEUE_EMPTY_FLAG; // queue Empty - nothing to get
    }
    return QUEUE_OK; // No errors
}
//
//  ---------------------------------------------------------------------------
int _tmain(int argc, _TCHAR* argv[])    {
//  constrain buffer size to some power of 2 to force faux modulo arithmetic
    int LoopKnt = 1000000;  //  for benchmarking purposes only
    int k, i=0, Qview=0;
    time_t start;
    QUEUE_DESC Queue, *Q;
    if(NULL == (Q = Q_Init(&Queue, BITS_ELE_KNT, sizeof(int)))) {
        printf("\nProgram failed to initialize. Aborting.\n\n");
        return 0;
    }

    start = clock();
    for(k=0; k<LoopKnt; k++)    {
        //printf("\n\n Fill'er up please...\n");
        //Q->Head = Q->Tail = rand();
        for(i=1; i<= Q->EleKnt; i++)    {
            Qview = i*i;
            if(QUEUE_FULL_FLAG == Q_Put(Q, (UCHAR *)&Qview))    {
                //printf("\nQueue is full at %i \n", i);
                //printf("\nQueue value of %i should be %i squared", Qview, i);
                break;
            }
            //printf("\nQueue value of %i should be %i squared", Qview, i);
        }
        //  Get data from queue until completely drained (empty)
        //
        //printf("\n\n Step into the lab, and see what on the slab... \n");
        Qview = 0;
        for(i=1; i; i++)    {
            if(QUEUE_EMPTY_FLAG == Q_Get((UCHAR *)&Qview, Q))   {
                //printf("\nQueue value of %i should be %i squared", Qview, i);
                //printf("\nQueue is empty at %i", i);
                break;
            }
            //printf("\nQueue value of %i should be %i squared", Qview, i);
        }
        //printf("\nQueue head value is %i, tail is %i\n", Q->Head, Q->Tail);
    }
    printf("\nQueue time was %5.3f to fill & drain %i element queue  %i times \n", 
                     (dbl)(clock()-start)/(dbl)CLOCKS_PER_SEC,Q->EleKnt, LoopKnt);
    printf("\nQueue head value is %i, tail is %i\n", Q->Head, Q->Tail);
    getchar();
    return 0;
}

Ответ 5

Вот простое решение в C. Предположим, что прерывания отключены для каждой функции. Никакой полиморфизм и прочее, просто здравый смысл.

#define BUFSIZE 128
char buf[BUFSIZE];
char *pIn, *pOut, *pEnd;
char full;

// init
void buf_init()
{
    pIn = pOut = buf;       // init to any slot in buffer
    pEnd = &buf[BUFSIZE];   // past last valid slot in buffer
    full = 0;               // buffer is empty
}

// add char 'c' to buffer
int buf_put(char c)
{
    if (pIn == pOut  &&  full)
        return 0;           // buffer overrun

    *pIn++ = c;             // insert c into buffer
    if (pIn >= pEnd)        // end of circular buffer?
        pIn = buf;          // wrap around

    if (pIn == pOut)        // did we run into the output ptr?
        full = 1;           // can't add any more data into buffer
    return 1;               // all OK
}

// get a char from circular buffer
int buf_get(char *pc)
{
    if (pIn == pOut  &&  !full)
        return 0;           // buffer empty  FAIL

    *pc = *pOut++;              // pick up next char to be returned
    if (pOut >= pEnd)       // end of circular buffer?
        pOut = buf;         // wrap around

    full = 0;               // there is at least 1 slot
    return 1;               // *pc has the data to be returned
}

Ответ 6

Простая реализация может состоять из:

• Буфер, реализованный как массив размера n, любого типа, который вам нужен.
• Чтение указателя или индекса (в зависимости от того, что более эффективно для вашего процессора)
• Указатель записи или индекс
• Счетчик, указывающий, сколько данных находится в буфере (выводится из указателей чтения и записи, но быстрее отслеживается отдельно)

Каждый раз, когда вы записываете данные, вы указываете указатель записи и увеличиваете счетчик. Когда вы читаете данные, вы увеличиваете указатель чтения и уменьшаете счетчик. Если любой указатель достигает n, установите его в ноль.

Вы не можете писать, если counter = n. Вы не можете прочитать, если counter = 0.

Ответ 7

C стиль, простой кольцевой буфер для целых чисел. Сначала используйте init, а не используйте put и get. Если буфер не содержит никаких данных, он возвращает нулевое значение "0".

//=====================================
// ring buffer address based
//=====================================
#define cRingBufCount   512
int     sRingBuf[cRingBufCount];    // Ring Buffer
int     sRingBufPut;                // Input index address
int     sRingBufGet;                // Output index address
Bool    sRingOverWrite;

void    GetRingBufCount(void)
{
int     r;
`       r= sRingBufPut - sRingBufGet;
        if ( r < cRingBufCount ) r+= cRingBufCount;
        return r; 
}

void    InitRingBuffer(void)
{
        sRingBufPut= 0;
        sRingBufGet= 0;
}       

void    PutRingBuffer(int d)
{
        sRingBuffer[sRingBufPut]= d;
        if (sRingBufPut==sRingBufGet)// both address are like ziro
        {
            sRingBufPut= IncRingBufferPointer(sRingBufPut);
            sRingBufGet= IncRingBufferPointer(sRingBufGet);
        }
        else //Put over write a data
        {
            sRingBufPut= IncRingBufferPointer(sRingBufPut);
            if (sRingBufPut==sRingBufGet)
            {
                sRingOverWrite= Ture;
                sRingBufGet= IncRingBufferPointer(sRingBufGet);
            }
        }
}

int     GetRingBuffer(void)
{
int     r;
        if (sRingBufGet==sRingBufPut) return 0;
        r= sRingBuf[sRingBufGet];
        sRingBufGet= IncRingBufferPointer(sRingBufGet);
        sRingOverWrite=False;
        return r;
}

int     IncRingBufferPointer(int a)
{
        a+= 1;
        if (a>= cRingBufCount) a= 0;
        return a;
}