你如何执行一个圆形的缓冲器在C？
https://stackoverflow.com/questions/827691
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我有一个需要一种固定的尺寸(可选择在运行时创建时，不compile-time)圆形的缓冲器，它可举行任何类型的对象，它需要 非常 高性能。我不认为会有资源的竞争问题，因为，虽然这是在一个多任务嵌入环境，这是一个共同执行一项以任务本身能够达到这个目标。
我最初的想法是要储存一个简单的结构，在缓冲区，其中将包括类型(简单枚举的定义)和无效的指针到有效负荷，但我希望这是尽可能快地让我很开放的建议，涉及旁的堆。
实际上我很高兴绕过的任何标准图书馆原的速度-从我所看到的码的，它不是很大程度上优化的CPU：它看起来像他们只是汇编C码之类的东西 strcpy() 而这样的，有没有手工编码的组件。
任何代码或想法，将不胜感激。该行动需要是：
- 创建一个缓冲器与具体的大小。
- 把尾巴。
- 获得从头。
- 返回的数量。
- 删除一个缓冲区。
解决方案
你可以列举的类型需要时间，你代码的缓冲区，或者是否需要能够添加类型在运行时间通过动态的电话？如果是前者，然后我会创造的缓冲作为一堆分配的阵列的n结构，其中每个结构包括两个要素：一枚标记识别的数据类型，以及联盟的所有数据的类型。你失去了什么方面的额外储存的小元素，你让条款不具有处理分配/释放和得到的记忆碎片。然后你只需要跟踪的开始和结束的指数，定义的头部和尾部因素的缓冲区，并确保计算国防部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;
}
只要你的戒指缓冲区的长度是一个权力的两个，令人难以置信的快速进制"&"操作将围绕你的指数。对我的应用程序，我显示的一段音频用户从一个环缓冲区的声音获得离麦克风。
我总是确保最大数量的音频，可以在屏幕上显示的要少得多于戒指的尺寸的缓冲区。否则你可能会阅读和写作的自同一块。这可能会让你奇怪显示的文物。
第一，标题。你不需要的模算包裹的缓冲，如果你使用位int举行的头部和尾"的指针"，并且它们的大小所以他们完全同步。即：4096酿成一个12位unsigned int是0所有由本身，不受干扰以任何方式。消除模算，甚至权力的2,加倍的速度几乎完全一致。
10万次填装和排水4096缓冲区的任何类型的数据元素需要52秒在我艮第3i7Dell；尽管8500使用Visual Studio2010C++编译器与默认的内联和1/8192nd的服务的一个基准。
我RX改写测试循环在主要()使他们不再控制的流动是，并且应该是，通过控制的返回值表示缓冲区的完整或空，以及随之而来的休息；发言。即：填充和下水应该能够邦对每个其他没有腐败或不稳定。在某些时候，我希望多线程的这个代码，在这种情况下，该行为将是至关重要的。
该QUEUE_DESC(队列中的描述符)和初始功能的部队的所有缓冲区，在这个码是一个功率为2。上述方案不会的工作。同时，关于这个问题，注意QUEUE_DESC不是硬盘编码，它使用一个清单定(#define BITS_ELE_KNT)为它的建设。(我假设2足够的灵活性)
使缓冲区大小的运行时间可选择的，我尝试了不同的做法(这里没有显示)，并决定使用USHRTs头，尾巴，EleKnt能够管理一个先进先出缓冲[USHRT].为了避免模算我创建了一个面罩以&&头，尾巴，但是这掩盖事实证明将(EleKnt-1)，因此仅使用。使用USHRTS，而不是位整数增加的表现~15%在一个安静的机。英特尔处理器核心一直快于他们的车,所以在一个繁忙的,公共机、包装你的数据结构得到你装和执行其他相互竞争的螺纹。权衡。
注意到实际储存对缓冲区被分配在堆与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.元素是潜在的所有不同种类/尺寸，对于任何给定的放或得到的。
我相信这个代码满足了速度和缓冲区大小的要求，可以满足要求的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;
}
这是一个简单的解决方案。承担中断被关闭每一个功能。没有多&东西，只是常识。
#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，无论何种类型，你需要
- 一个读取指标或指数(无论是更有效处理器)
- 一个写入指标或指数
- 反指示的数据是在缓冲区(从可导读和写指针，但速度更快，跟踪它分开)
每一次你写的数据，则提前写指针和递增。当你读数据，增加阅读指针和递减计数器。如果指针到达n，将其设置为零。
你不能写如果计数器=n。你可以不读，如果计数器=0.
C风格，简单的环缓冲区用于整数。第一次使用init于使用和获得。如果缓冲区不包含任何数据，返回"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;
}
