Como você implementar um buffer circular em C?
https://stackoverflow.com/questions/827691
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Eu tenho uma necessidade para um tamanho fixo (selecionável em tempo de execução quando criá-la, não em tempo de compilação) buffer circular que pode conter objetos de qualquer tipo e ele precisa ser muito alta desempenho. Eu não acho que haverá problemas de contenção de recursos, já que, embora seja em um multi-tasking ambiente incorporado, é uma co-operatória para as tarefas a si mesmos pode gerenciar isso.
Meu pensamento inicial era para armazenar um simples struct no buffer que contém o tipo (simples enumeração / definir) e um ponteiro nulo para a carga útil, mas eu quero que este seja o mais rápido possível, então estou aberto a sugestões que envolvem ignorando o heap.
Na verdade, eu estou feliz em ignorar qualquer da biblioteca padrão de velocidade crua - pelo que tenho visto do código, não é altamente otimizado para a CPU: parece que eles apenas código compilado C para coisas como strcpy() e tal, não há nenhum conjunto codificado mão.
Qualquer código ou idéias seria muito apreciada. As operações necessárias são:
- criar um buffer com tamanho específico.
- colocar na cauda.
- começar a partir da cabeça.
- retornar a contagem.
- excluir um buffer.
Solução
Você pode enumerar os tipos necessários no momento em que o código se o buffer, ou que você precisa para ser capaz de adicionar tipos em tempo de execução através de chamadas dinâmicos? No primeiro caso, em seguida, criaria o tampão como uma matriz alocada-pilha de estruturas n, onde cada estrutura consiste em dois elementos: um tag enumeração que identifica o tipo de dados, e uma união de todos os tipos de dados. O que você perde em termos de armazenamento extra para pequenos elementos, você faz-se em termos de não ter que lidar com a alocação / desalocação e a fragmentação de memória resultante. Então você só precisa manter o controle dos índices de início e fim que definem os elementos de cabeça e cauda do buffer, e certifique-se de modificação de computação n quando incrementar / decrementar os índices.
Outras dicas
A solução mais simples seria a de manter o controle do tamanho do item eo número de itens e, em seguida, criar um buffer de um número adequado de bytes:
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;
}
Enquanto o comprimento do seu buffer de anel é uma potência de dois, o "&" operação incrivelmente rápido binário vai envolver em torno de seu índice para você. Para o meu pedido, eu estou mostrando um segmento de áudio para o usuário de um buffer de anel de áudio adquirido a partir de um microfone.
Eu sempre certificar-se de que a quantidade máxima de áudio que podem ser exibidos na tela é muito menor do que o tamanho do buffer de anel. Caso contrário, você pode estar lendo e escrevendo a partir do mesmo pedaço. Isso provavelmente lhe dar artefatos de exibição estranhas.
Em primeiro lugar, a manchete. Você não precisa módulo aritmética para embrulhar o tampão se você usar ints bits para segurar a cabeça e cauda "ponteiros", e tamanho los para que eles estão em perfeita sincronia. IE: 4096 recheado em um int não assinado de 12 bits é de 0 por si só, sem serem molestados de qualquer forma. Eliminando módulo aritmética, mesmo para potências de 2, duplica a velocidade -. Quase exatamente
10 milhões de iterações de enchimento e drenagem de um buffer de qualquer tipo de elementos de dados 4096 leva 52 segundos no meu 3 Gen i7 Dell XPS 8500 usando Visual compilador Studio 2010 do C ++ com padrão inlining, e 1/8192 de que a manutenção de um datum .
eu RX reescrevendo os circuitos de teste em principal (), de modo que eles já não controlar o fluxo - que é, e deve ser, controlada pelos valores de retorno, indicando o buffer está cheio ou vazio, e a ruptura do tratador; afirmações. IE: o enchimento e escorredor deve ser capaz de bater uns contra os outros, sem corrupção ou instabilidade. Em algum momento eu espero multi-thread este código, ficando assim esse comportamento será crucial.
O QUEUE_DESC (descritor de fila) e as forças função de inicialização todos os buffers neste código para ser uma potência de 2. O esquema acima não irá funcionar de outra maneira. Enquanto sobre o assunto, nota que QUEUE_DESC não é codificado, que utiliza uma constante de manifesto (#define BITS_ELE_KNT) para a sua construção. (Estou assumindo uma potência de 2 é suficiente flexibilidade aqui)
Para fazer o tamanho do buffer selecionável de tempo de execução, eu tentei abordagens diferentes (não mostrado aqui), e estabeleceu-se em usar USHRTs de cabeça, cauda, ??EleKnt capaz de gerenciar um buffer FIFO [USHRT]. Para evitar modulo I aritmética criado uma máscara para && com cabeça, cauda, ??mas essa máscara acaba por ser (EleKnt -1), então é só usar isso. Usando USHRTS em vez de ints bit maior desempenho ~ 15% em uma máquina silenciosa. núcleos Intel CPU têm sido sempre mais rápido do que seus ônibus, por isso em uma máquina ocupado, compartilhada, embalar suas estruturas de dados você fica carregado e executando à frente de outros, tópicos concorrentes. Trade-offs.
o armazenamento real para o buffer é atribuído na pilha com calloc (), e o ponteiro se encontra na base da estrutura, de modo que a estrutura e o ponteiro têm exactamente o mesmo endereço. IE; nenhum deslocamento necessário para ser adicionado ao endereço struct para amarrar registros.
Nesse mesmo sentido, todas as variáveis ??atendente com manutenção do tampão são fisicamente adjacente ao buffer, atados dentro da mesma estrutura, para que o compilador pode fazer linguagem assembly bonito. Você terá que matar a otimização inline para ver qualquer montagem, porque senão fica esmagado no esquecimento.
Para suportar o polimorfismo de qualquer tipo de dados, eu tenho memcpy utilizado () em vez de atribuições. Se você só precisam de flexibilidade para suportar um tipo variável aleatória per compilação, em seguida, esse código funciona perfeitamente.
Para o polimorfismo, você só precisa saber o tipo e da exigência de armazenamento. A matriz DATA_DESC de descritores fornece uma maneira de manter o controle de cada dado que é colocado em QUEUE_DESC.pBuffer para que ele possa ser recuperado adequadamente. Eu tinha acabado de alocar memória suficiente pBuffer para manter todos os elementos do maior tipo de dados, mas manter o controle de quanto desse armazenamento de um determinado dado está realmente usando no DATA_DESC.dBytes. A alternativa é reinventar um gerente heap.
Este meio de QUEUE_DESC UCHAR * pBuffer teria uma matriz companheiro paralelo para acompanhar o tipo de dados e tamanho, enquanto local de armazenamento de um dado em pBuffer permaneceria assim como é agora. O novo membro seria algo como DATA_DESC * pDataDesc, ou, talvez, DATA_DESC DataDesc [2 ^ BITS_ELE_KNT] se você pode encontrar uma maneira de vencer o seu compilador em sua apresentação com uma referência tais frente. Calloc () é sempre mais flexível nestas situações.
Você ainda memcpy () in Q_Put (), Q_Get, mas o número de bytes realmente copiados seria determinado por DATA_DESC.dBytes, não QUEUE_DESC.EleBytes. Os elementos são potencialmente todos diferentestipos / tamanhos para qualquer posto ou obter.
Eu acredito que este satisfaz código a velocidade e buffer requisitos de tamanho, e pode ser feita para satisfazer a exigência de 6 tipos de dados diferentes. Eu deixei os muitos dispositivos de teste em, na forma de printf () declarações, para que possa satisfazer a si mesmo (ou não) que o código funciona corretamente. O gerador de números aleatórios demonstra que o código funciona para qualquer aleatória de combinação de cabeça / cauda.
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;
}
Aqui está uma solução simples em C. Suponha interrupções são desligadas para cada função. Nenhum polimorfismo & coisas, apenas o senso comum.
#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
}
Uma implementação simples poderia consistir em:
- Um buffer, implementada como uma matriz de tamanho n, de qualquer tipo que você precisa
- Um ponteiro ou índice (o que for mais eficiente para o seu processador) ler
- Um ponteiro de escrita ou índice
- Um contador que indica a quantidade de dados no buffer (produzidos a partir de ponteiros ler e escrever, mas mais rápido para segui-lo separadamente)
Cada vez que você gravar dados, você avança o ponteiro de escrita e incrementar o contador. Quando você ler os dados, você aumenta o ponteiro de leitura e diminuir o contador. Se qualquer um ponteiro atingir n, defini-la como zero.
Você não pode escrever se o contador = n. Você não pode ler se contador = 0.
estilo C, tampão de anel simples para inteiros. Primeira inicialização uso de uso colocar e obter. Se tampão não contém quaisquer dados que ele retorna zero "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;
}
