C에서 순환 버퍼를 어떻게 구현합니까?

C에서 순환 버퍼를 어떻게 구현합니까?

---

모든 유형의 객체를 보유 할 수있는 고정 크기 (컴파일 시간이 아닌 런타임에 선택 가능) 순환 버퍼가 필요하며 매우 높은 성능이 필요합니다 . 멀티 태스킹 임베디드 환경이긴하지만, 작업 자체가 그것을 관리 할 수있는 협동적인 환경이기 때문에 리소스 경합 문제가 없을 것이라고 생각합니다.

내 초기 생각은 유형 (단순 열거 / 정의)과 페이로드에 대한 void 포인터를 포함하는 버퍼에 간단한 구조체를 저장하는 것이었지만 가능한 한 빨리 우회하기를 포함하는 제안에 열려 있습니다. 힙.

사실 나는 원시 속도에 대한 표준 라이브러리의 우회에 행복 해요 - 나는 코드로 본 적이 무엇인지, 그것이 무겁게 CPU에 최적화 아니에요에서 : 그들은 단지 같은 것들에 대한 C 코드를 컴파일처럼 보이는 strcpy()등, 더 없다 손으로 코딩 한 어셈블리.

어떤 코드 나 아이디어라도 대단히 감사하겠습니다. 필요한 작업은 다음과 같습니다.

• 특정 크기의 버퍼를 만듭니다.
• 꼬리에 넣어.
• 머리에서 얻으십시오.
• 카운트를 반환합니다.
• 버퍼를 삭제합니다.

---

버퍼를 코딩 할 때 필요한 유형을 열거 할 수 있습니까? 아니면 동적 호출을 통해 런타임에 유형을 추가 할 수 있어야합니까? 전자의 경우 버퍼를 n 구조체의 힙 할당 배열로 생성합니다. 여기서 각 구조체는 데이터 유형을 식별하는 열거 형 태그와 모든 데이터 유형의 합집합으로 구성됩니다. 작은 요소에 대한 추가 스토리지 측면에서 잃어버린 부분은 할당 / 할당 해제 및 그에 따른 메모리 조각화를 처리 할 필요가 없다는 점에서 보상합니다. 그런 다음 버퍼의 헤드 및 테일 요소를 정의하는 시작 및 끝 인덱스를 추적하고 인덱스를 증가 / 감소 할 때 mod n을 계산해야합니다.

---

가장 간단한 해결책은 항목 크기와 항목 수를 추적 한 다음 적절한 바이트 수의 버퍼를 만드는 것입니다.

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

링 버퍼의 길이가 2의 거듭 제곱 인 한, 믿을 수 없을만큼 빠른 바이너리 "&"연산이 인덱스를 감싸줍니다. 내 응용 프로그램의 경우 마이크에서 얻은 오디오의 링 버퍼에서 사용자에게 오디오 세그먼트를 표시하고 있습니다.

저는 항상 화면에 표시 할 수있는 최대 오디오 양이 링 버퍼의 크기보다 훨씬 작은 지 확인합니다. 그렇지 않으면 동일한 청크에서 읽고 쓸 수 있습니다. 이것은 당신에게 이상한 디스플레이 아티팩트를 줄 것입니다.

---

첫째, 헤드 라인입니다. 비트 정수를 사용하여 머리와 꼬리 "포인터"를 유지하고 완벽하게 동기화되도록 크기를 조정하는 경우 버퍼를 래핑하기 위해 모듈로 산술이 필요하지 않습니다. IE : 12 비트 unsigned int에 채워진 4096은 자체적으로 0이며 어떤 식 으로든 영향을받지 않습니다. 2의 거듭 제곱에 대해서도 모듈로 산술을 제거하면 속도가 거의 두 배가됩니다.

모든 유형의 데이터 요소의 4096 버퍼를 채우고 배출하는 1,000 만 번의 반복 작업은 Visual Studio 2010의 C ++ 컴파일러 (기본 인라인 포함)를 사용하는 3 세대 i7 Dell XPS 8500에서 52 초가 걸리며, 그 중 1/8192 번이 데이텀을 서비스하는 데 걸립니다.

RX는 main ()에서 테스트 루프를 다시 작성하여 더 이상 흐름을 제어하지 않습니다. 즉, 버퍼가 꽉 찼거나 비어 있음을 나타내는 반환 값에 의해 제어되어야하며 제어되어야합니다. 진술. IE : 충전제와 배수기는 손상이나 불안정 함없이 서로 부딪 힐 수 있어야합니다. 어느 시점에서 나는이 코드를 멀티 스레드하기를 희망하며, 그 결과 그 동작이 중요 할 것입니다.

QUEUE_DESC (대기열 설명자) 및 초기화 함수는이 코드의 모든 버퍼가 2의 거듭 제곱이되도록 강제합니다. 위의 체계는 그렇지 않으면 작동하지 않습니다. 주제에 대해 QUEUE_DESC는 하드 코딩되지 않았으며 구성에 매니페스트 상수 (#define BITS_ELE_KNT)를 사용합니다. (여기서 2의 거듭 제곱은 충분한 유연성이라고 가정합니다)

버퍼 크기 런타임을 선택할 수 있도록하기 위해 다른 접근 방식 (여기에 표시되지 않음)을 시도하고 FIFO 버퍼 [USHRT]를 관리 할 수있는 Head, Tail, EleKnt에 USHRT를 사용하기로 결정했습니다. 모듈로 산술을 피하기 위해 Head, Tail을 사용하여 &&에 마스크를 만들었지 만 그 마스크는 (EleKnt -1)로 판명되었으므로 그냥 사용하십시오. bit int 대신 USHRTS를 사용하면 조용한 시스템에서 성능이 ~ 15 % 향상되었습니다. Intel CPU 코어는 항상 버스보다 빠르기 때문에 바쁜 공유 시스템에서 데이터 구조를 패킹하면 다른 경쟁 스레드보다 먼저로드되고 실행됩니다. 트레이드 오프.

버퍼의 실제 저장소는 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 ()은 이러한 상황에서 항상 더 유연합니다.

Q_Put (), Q_Get에서 여전히 memcpy ()이지만 실제로 복사 된 바이트 수는 QUEUE_DESC.EleBytes가 아닌 DATA_DESC.dBytes에 의해 결정됩니다. 요소는 잠재적으로 주어진 풋 또는 겟에 대해 서로 다른 유형 / 크기입니다.

이 코드는 속도 및 버퍼 크기 요구 사항을 충족하며 6 가지 데이터 유형에 대한 요구 사항을 충족하도록 만들 수 있다고 생각합니다. 나는 많은 테스트 픽스처를 printf () 문 형태로 남겨 두었으므로 코드가 제대로 작동하는지 스스로 만족할 수 있습니다. 난수 생성기는 임의의 머리 / 꼬리 콤보에서 코드가 작동 함을 보여줍니다.

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

---

다음은 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
}

---

간단한 구현은 다음으로 구성 될 수 있습니다.

• 필요한 모든 유형의 크기 n 배열로 구현 된 버퍼
• 읽기 포인터 또는 인덱스 (둘 중 프로세서에 더 효율적인 것)
• 쓰기 포인터 또는 인덱스
• 버퍼에있는 데이터의 양을 나타내는 카운터 (읽기 및 쓰기 포인터에서 파생 가능하지만 별도로 추적하는 것이 더 빠름)

Every time you write data, you advance the write pointer and increment the counter. When you read data, you increase the read pointer and decrement the counter. If either pointer reaches n, set it to zero.

You can't write if counter = n. You can't read if counter = 0.

---

C style, simple ring buffer for integers. First use init than use put and get. If buffer does not contain any data it returns "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;
}

참고URL : https://stackoverflow.com/questions/827691/how-do-you-implement-a-circular-buffer-in-c