Wie implementieren Sie einen zirkulären Puffer in C?

Question

Ich brauche eine feste Größe (wählbar zur Laufzeit, wenn es, nicht zur Kompilierzeit) Ringpuffer, der Objekte aller Art halten kann und es muss sehr hohe Leistung sein. Ich glaube nicht, dass es Probleme mit der Ressourcenkonkurrenz geben wird, da es zwar in einer Multi-Tasking-Embedded-Umgebung liegt, aber kooperativ ist, so dass die Aufgaben selbst dies bewältigen können.

Meine erste Idee war es, eine einfache Struktur im Puffer zu speichern, die den Typ (einfache enum/define) und einen Zeiger auf die Nutzlast enthalten würde, aber ich möchte das so schnell wie möglich, also bin ich offen für Vorschläge, die das Umgehen des Heaps umfassen.

Eigentlich bin ich glücklich, irgendeine der Standardbibliothek für rohe Geschwindigkeit zu umgehen - von dem, was ich vom Code gesehen habe, ist es nicht stark für die CPU optimiert: es sieht aus wie kompiliert C-Code für Dinge wie strcpy() und so, es gibt keine handcodierte Baugruppe.

Jeder Code oder Ideen würden sehr geschätzt werden. Die erforderlichen Operationen sind:

• Erstellen Sie einen Puffer mit bestimmter Größe.
• an den Schwanz gelegt.
• von Kopf bekommen.
• geben Sie die Anzahl zurück.
• löschen Sie einen Puffer.

Answer 1

Können Sie die Arten aufzählen benötigt bei die Zeit, die Sie den Puffer codieren, oder müssen Sie Typen zur Laufzeit über dynamische Aufrufe hinzufügen können? Wenn der erste, dann würde ich den Puffer als Heap-Allocated-Array von n Strukturen erstellen, wobei jede Struktur aus zwei Elementen besteht: ein Enum-Tag, das den Datentyp identifiziert, und eine Vereinigung aller Datentypen. Was Sie in Bezug auf zusätzlichen Speicher für kleine Elemente verlieren, ist, dass Sie nicht mit der Zuordnung/Freigabe und der daraus resultierenden Speicherfragmentierung fertig werden müssen. Dann müssen Sie nur die Start- und Endindizes verfolgen, die die Kopf- und Endelemente des Puffers definieren, und sicherstellen, dass mod n berechnet wird, wenn die Indizes inkrementiert/dekrementiert werden.

Answer 2

wäre die einfachste Lösung Spur der Elementgröße und die Anzahl der Elemente zu halten, und dann einen Puffer der entsprechenden Anzahl von Bytes erstellen:

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

Answer 3

konnte Eine einfache Implementierung bestehen:

• A-Puffer, als ein Array der Größe n implementiert, welcher Art auch immer Sie
• Ein Lesezeiger oder Index benötigen (je nachdem, was für Ihren Prozessor effizienter ist)
• Ein Schreibzeiger oder Index
• Ein Zähler, wie viele Daten angibt, in dem Puffer (ableitbar aus der Lese- und Schreibzeiger, aber schneller getrennt, es zu verfolgen)

Jedes Mal, wenn Sie Daten schreiben, rücken Sie den Schreibzeiger vor und inkrementieren den Zähler. Wenn Sie Daten lesen, erhöhen Sie den Lesezeiger und dekrementieren den Zähler. Wenn einer der Zeiger den Wert n erreicht, setzen Sie ihn auf Null.

Sie können nicht schreiben, wenn counter = n. Sie können nicht lesen, wenn Zähler = 0 ist.

Answer 4

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

Solange Ihr Ringpuffers Länge eine Zweierpotenz ist, die unglaublich schnelle binäre „&“ Betrieb wird für Sie rund um Ihren Index wickeln. Für meine Anwendung zeige ich dem Benutzer ein Audiosegment aus einem Ringpuffer an, der von einem Mikrofon aufgenommen wurde.

Ich stelle immer sicher, dass die maximale Menge an Audio, die auf dem Bildschirm angezeigt werden kann, viel kleiner ist als die Größe des Ringpuffers. Sonst könnten Sie aus dem gleichen Stück lesen und schreiben. Dies würde Ihnen wahrscheinlich seltsame Anzeigeartefakte bescheren.

Answer 5

Zuerst die Überschrift. Sie benötigen keine Modulo-Arithmetik, um den Puffer zu umhüllen, wenn Sie Bit-Ints verwenden, um den Kopf "& Tail" Zeiger zu halten, und sie so zu dimensionieren, dass sie perfekt synchron sind. IE: 4096 in einem 12-Bit unsigned Int gefüllt ist 0 allein, unbelästigt in irgendeiner Weise. Das Eliminieren der Modulo-Arithmetik, sogar für Zweierpotenzen, verdoppelt die Geschwindigkeit - fast genau.

10 Millionen Iterationen zum Füllen und Entleeren eines 4096-Puffers beliebiger Datenelemente dauert 52 Sekunden auf meinem 3. Generation i7 Dell XPS 8500 mit Visual Studio 2010 C++ - Compiler mit Standard-Inlining und 1/8192 Datum.

Ich würde RX die Testschleifen in main() neu schreiben, so dass sie nicht mehr den Fluss steuern - was durch die Rückgabewerte, die anzeigen, dass der Puffer voll oder leer ist, und der Attendant break; Aussagen. IE: Der Füller und der Abtropfbehälter sollten in der Lage sein, ohne Beschädigung oder Instabilität aufeinander zu schlagen. Irgendwann hoffe ich, diesen Code zu multi-thread, worauf dieses Verhalten entscheidend sein wird.

Die QUEUE_DESC (Warteschlangendeskriptor) und Initialisierungsfunktion zwingt alle Puffer in diesem Code, eine Potenz von 2 zu sein. Das obige Schema funktioniert andernfalls nicht. Beachten Sie bei diesem Thema, dass QUEUE_DESC nicht fest codiert ist, sondern eine Manifest-Konstante (#define BITS_ELE_KNT) für die Konstruktion verwendet. (Ich nehme an, eine Leistung von 2 ist ausreichend Flexibilität hier)

Um die Puffergröße Laufzeit auswählbar zu machen, versuchte ich verschiedene Ansätze (hier nicht gezeigt), und setzte auf USHRTs für Head, Tail, EleKnt fähig der Verwaltung eines FIFO-Puffers [USHRT]. Um Modulo-Arithmetik zu vermeiden, habe ich mit Head, Tail eine Maske nach & & erstellt, aber diese Maske stellt sich als (EleKnt -1) heraus, also benutze das einfach. Using USHRTS anstelle von Bit-Ints erhöhte Leistung ~ 15% auf einer ruhigen Maschine. Intel-CPU-Cores waren schon immer schneller als ihre Busse, sodass Sie auf einem ausgelasteten, gemeinsam genutzten Rechner durch das Packen Ihrer Datenstrukturen vor anderen konkurrierenden Threads geladen und ausgeführt werden. Kompromisse.

Beachten Sie, dass der tatsächliche Speicher für den Puffer auf dem Heap mit Calloc() zugewiesen wird, und der Zeiger an der Basis der Struktur ist, so haben die Struktur und der Zeiger GENAU die gleiche Adresse. IE; Es ist kein Offset erforderlich, der zur Strukturadresse hinzugefügt werden muss, um Register zu binden.

In diesem Sinne sind alle mit dem Bedienen des Puffers verbundenen Variablen physisch neben dem Puffer, in die gleiche Struktur gebunden, so dass der Compiler schöne Assemblersprache machen kann. Sie müssen die Inline-Optimierung beenden, um eine Assembly zu sehen, da sie ansonsten in Vergessenheit gerät.

Um die Polymorphie jedes Datentyps zu unterstützen, habe ich memcpy() anstelle von Zuweisungen verwendet. Wenn Sie nur die Flexibilität benötigen, einen zufälligen Variablentyp pro Kompilierung zu unterstützen, dann funktioniert dieser Code perfekt.

Für Polymorphie müssen Sie nur den Typ und die Speicheranforderungen kennen. Das DATA_DESC-Array von Deskriptoren bietet eine Möglichkeit, jedes Datum zu verfolgen, das in QUEUE_DESC abgelegt wird.pBuffer, so dass es richtig abgerufen werden kann. Ich würde einfach genug pBuffer-Speicher zuweisen, um alle Elemente des größten Datentyps zu speichern, aber verfolgen, wie viel von diesem Speicher ein bestimmtes Datum tatsächlich in DATA_DESC.dBytes verwendet. Die Alternative besteht darin, einen Heap-Manager neu zu erfinden.

Dies bedeutet, dass der UCHAR * pBuffer von QUEUE_DESC über ein paralleles Companion-Array verfügt, um den Datentyp und die Größe zu verfolgen, während der Speicherort des Datenelements in pBuffer unverändert bleibt. Das neue Member wäre etwas wie DATA_DESC * pDataDesc oder vielleicht DATA_DESC DataDesc [2^BITS_ELE_KNT], wenn Sie einen Weg finden können, Ihren Compiler mit einer solchen Vorwärtsreferenz zu unterwerfen. Calloc() ist in diesen Situationen immer flexibler.

Sie würden immer noch memcpy() in Q_Put(), Q_Get, aber die Anzahl der tatsächlich kopierten Bytes würde von DATA_DESC.dBytes bestimmt werden, nicht von QUEUE_DESC.EleBytes. Die Elemente sind möglicherweise alle verschiedenen Arten/Größen für jede gegebene Put oder Get.

Ich glaube, dass dieser Code erfüllt die Geschwindigkeit und Puffergröße Anforderungen, und kann gemacht werden, um die Anforderung für 6 verschiedene Datentypen zu erfüllen. Ich habe die vielen Testgeräte in Form von printf() -Aussagen verlassen, damit Sie sich selbst davon überzeugen können (oder nicht), dass der Code richtig funktioniert. Der Zufallszahlengenerator demonstriert, dass der Code für jede zufällige Kopf/Tail-Kombination funktioniert.

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

Answer 6

Hier ist eine einfache Lösung in C. Angenommen Interrupts sind für jede Funktion ausgeschaltet. Kein Polymorphismus & Zeug, nur gesunden Menschenverstand.

---

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

Answer 7

C-Stil, einfache Ringpuffer für ganze Zahlen. Benutze zuerst init als put und hole. Wenn der Puffer keine Daten enthält, gibt er "0" Null zurück.

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