Jak zaimplementować bufor kołowy w C?

Najprostszym rozwiązaniem byłoby śledzenie rozmiaru i liczby elementów, a następnie utworzenie bufora o odpowiedniej liczbie bajtów:

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--;
}

// 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;
}

Tak długo, jak długość bufora pierścienia jest potęgą dwóch, niewiarygodnie szybka operacja binarna " & " będzie owijana wokół twojego indeksu. Dla mojej aplikacji wyświetlam użytkownikowi segment audio z bufora pierścieniowego audio pozyskanego z mikrofonu.

Zawsze upewniam się, że maksymalna ilość dźwięku, która może być wyświetlana na ekranie, jest znacznie mniejsza niż rozmiar bufora pierścienia. W przeciwnym razie możesz czytać i pisać z tego samego kawałka. To prawdopodobnie daje Ci dziwne artefakty.

Najpierw nagłówek. Nie potrzebujesz arytmetyki modulo, aby zawinąć bufor, jeśli używasz bitów ints, aby trzymać "wskaźniki" head & tail i rozmiar ich tak, aby były idealnie zsynchronizowane. IE: 4096 wpchnięty do 12-bitowej niepodpisanej liczby całkowitej ma wartość 0 samo w sobie, niezastosowany w żaden sposób. Eliminacja arytmetyki modulo, nawet dla potęg 2, podwaja prędkość-prawie dokładnie.

RX przepisuje pętle testowe w main (), aby nie kontrolowały już przepływu - co jest i powinno być kontrolowane przez zwracane wartości wskazujące, że bufor jest pełny lub pusty, a towarzyszące mu instrukcje break;. IE: wypełniacz i osuszacz powinny być w stanie uderzać o siebie bez uszkodzenia lub niestabilności. W pewnym momencie mam nadzieję, że wielowątkowy ten kod, po czym takie zachowanie będzie kluczowe.

QUEUE_DESC (deskryptor kolejki) i funkcja inicjalizacji wymusza, aby wszystkie bufory w tym kodzie miały moc 2. Powyższy schemat nie będzie działał inaczej. Podczas gdy w tym temacie, zauważ, że QUEUE_DESC nie jest kodowane na twardo, używa stałej manifestu (#define BITS_ELE_KNT) do swojej konstrukcji. (Zakładam, że moc 2 jest tutaj wystarczającą elastycznością)

Aby wybrać rozmiar bufora run-time, próbowałem różnych podejść (nie pokazano tutaj) i zdecydowano się na wykorzystanie USHRTs dla głowy, ogona, EleKnt zdolnych do zarządzania buforem FIFO[USHRT]. Aby uniknąć arytmetyki modulo stworzyłem maskę do & & Z głową, ogonem, ale ta maska okazuje się być (Elektnt -1), więc po prostu użyj tego. Użycie USHRTS zamiast bit ints zwiększyło wydajność ~ 15% na cichej maszynie. Rdzenie procesora Intel zawsze były szybsze niż ich autobusy, więc na ruchliwej, współdzielonej maszynie pakowanie struktur danych pozwala załadować i wykonać przed innymi, konkurencyjnymi wątkami. Kompromisy.

Zauważ, że rzeczywiste miejsce przechowywania bufora jest przydzielane na stercie za pomocą calloc (), a wskaźnik znajduje się u podstawy struktury, więc struktura i wskaźnik mają dokładnie ten sam adres. IE; nie ma potrzeby dodawania offsetu do adresu struct, aby powiązać rejestry.

W tym samym duchu, wszystkie zmienne towarzyszące z obsługą bufora są fizycznie sąsiadujące z buforem, powiązane w tę samą strukturę, więc kompilator może stworzyć piękny język asemblacji. Będziesz musiał zabić optymalizację inline, aby zobaczyć dowolny zespół, ponieważ w przeciwnym razie zostanie zmiażdżony w zapomnienie.

Aby wspierać polimorfizm dowolnego typu danych, użyłem metody memcpy () zamiast przypisań. Jeśli potrzebujesz tylko elastyczności, aby obsługiwać jeden typ zmiennej losowej na kompilację, ten kod działa idealnie.

W przypadku polimorfizmu wystarczy znać typ i wymagania dotyczące przechowywania. Tablica deskryptorów DATA_DESC umożliwia śledzenie każdego datum to zostanie umieszczone w QUEUE_DESC.pBuffer, dzięki czemu można go prawidłowo odzyskać. Po prostu przydzieliłbym wystarczającą ilość pamięci pBuffer do przechowywania wszystkich elementów największego typu danych, ale śledziłbym, ile tego miejsca dane DANE źródło danych faktycznie używa w DATA_DESC.dBytes. Alternatywą jest wymyślenie na nowo menedżera sterty.

Oznacza to, że QUEUE_DESC ' s UCHAR * pBuffer będzie miał równoległą tablicę towarzyszącą do śledzenia typu i rozmiaru danych, podczas gdy miejsce przechowywania danych w pbuffer pozostanie takie samo teraz tak. Nowy członek będzie czymś w rodzaju DATA_DESC * pDataDesc, lub, być może, DATA_DESC DataDesc [2 ^ BITS_ELE_KNT], jeśli znajdziesz sposób, aby pokonać kompilator do złożenia z takim odwołaniem do przodu. Calloc () jest zawsze bardziej elastyczny w takich sytuacjach.

Nadal można by używać memcpy() w Q_Put (), Q_Get, ale liczba bajtów faktycznie skopiowanych byłaby określona przez DATA_DESC.dBytes, nie QUEUE_DESC.EleBytes. Elementy są potencjalnie wszystkie różne typy/rozmiary dla danego put albo get.

Wierzę, że ten kod spełnia wymagania prędkości i wielkości bufora i może być spełniony w celu spełnienia wymagań dla 6 różnych typów danych. Pozostawiłem wiele opraw testowych w formie instrukcji printf (), więc możesz się upewnić (lub nie), że kod działa poprawnie. Generator liczb losowych pokazuje, że kod działa dla dowolnej losowej kombinacji głowa / ogon.

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's 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's 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's 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;
}

Oto proste rozwiązanie w C. Załóżmy, że przerwania są wyłączone dla każdej funkcji. Bez polimorfizmu i rzeczy, tylko zdrowy rozsądek.

#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
}

Prosta implementacja może składać się z:

• bufor, zaimplementowany jako tablica o rozmiarze n, dowolnego typu
• wskaźnik odczytu lub indeks (w zależnoÅ›ci od tego, który jest bardziej wydajny dla procesora)
• wskaźnik zapisu lub indeks
• licznik wskazujÄ…cy, ile Danych znajduje siÄ™ w buforze (wyprowadzalny ze wskaźników odczytu i zapisu, ale szybszy do Å›ledzenia osobno)

Za każdym razem, gdy zapisujesz dane, przesuwasz wskaźnik zapisu i zwiększasz licznik. Podczas odczytu danych zwiększasz wskaźnik odczytu i zmniejszasz licznik. Jeśli któryś ze wskaźników osiągnie wartość n, ustaw go na zero.

Nie możesz pisać if counter = n. nie możesz czytać if counter = 0.

Styl C, prosty bufor pierścieniowy dla liczb całkowitych. Najpierw użyj init niż użyj put and get. Jeśli bufor nie zawiera żadnych danych to zwraca " 0 " zero.

//=====================================
// 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;
}