How do you implement a circular buffer in C

Question

I have a need for a fixed-size  selectable at run-time when creating it  not compile-time  circular buffer which can hold objects of any type and it needs to be very high performance  I don t think there will be resource contention issues since  although it s in a multi-tasking embedded environment  it s a co-operative one so the tasks themselves can manage that   My initial thought were to store a simple struct in the buffer which would contain the type  simple enum define  and a void pointer to the payload but I want this to be as fast as possible so I m open to suggestions that involve bypassing the heap   Actually I m happy to bypass any of the standard library for raw speed - from what I ve seen of the code  it s not heavily optimized for the CPU   it looks like they just compiled C code for things like strcpy   and such  there s no hand-coded assembly   Any code or ideas would be greatly appreciated  The operations required are    create a buffer with specific size  put at the tail  get from the head  return the count  delete a buffer

User · Answer

Extending adam-rosenfield s solution  i think the following will work for multithreaded single producer - single consumer scenario  int cb push back circular buffer  cb  const void  item      void  new head    char   cb- gt head   cb- gt sz    if  new head    cb gt buffer end          new head   cb- gt buffer        if  new head    cb- gt tail        return 1        memcpy cb- gt head  item  cb- gt sz     cb- gt head   new head    return 0     int cb pop front circular buffer  cb  void  item      void  new tail   cb- gt tail   cb- gt sz    if  cb- gt head    cb- gt tail        return 1        memcpy item  cb- gt tail  cb- gt sz     if  new tail    cb- gt buffer end        new tail   cb- gt buffer        cb- gt tail   new tail    return 0

User · Answer

Here is a simple solution in C   Assume interrupts are turned off for each function  No polymorphism  amp  stuff  just common sense      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    amp 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   amp  amp   full          return 0               buffer overrun       pIn     c                 insert c into buffer     if  pIn  gt   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   amp  amp    full          return 0               buffer empty  FAIL       pc    pOut                    pick up next char to be returned     if  pOut  gt   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

User · Answer

The simplest solution would be to keep track of the item size and the number of items  and then create a buffer of the appropriate number of 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- gt buffer   malloc capacity   sz       if cb- gt buffer    NULL             handle error     cb- gt buffer end    char   cb- gt buffer   capacity   sz      cb- gt capacity   capacity      cb- gt count   0      cb- gt sz   sz      cb- gt head   cb- gt buffer      cb- gt tail   cb- gt buffer     void cb free circular buffer  cb        free cb- gt buffer          clear out other fields too  just to be safe    void cb push back circular buffer  cb  const void  item        if cb- gt count    cb- gt capacity              handle error           memcpy cb- gt head  item  cb- gt sz       cb- gt head    char  cb- gt head   cb- gt sz      if cb- gt head    cb- gt buffer end          cb- gt head   cb- gt buffer      cb- gt count       void cb pop front circular buffer  cb  void  item        if cb- gt count    0              handle error           memcpy item  cb- gt tail  cb- gt sz       cb- gt tail    char  cb- gt tail   cb- gt sz      if cb- gt tail    cb- gt buffer end          cb- gt tail   cb- gt buffer      cb- gt count--

User · Answer

Adam Rosenfield s solution  although correct  could be implemented with a more lightweight circular buffer structure that does not invlove count and capacity  The structure could only hold the following 4 pointers   buffer  Points to the start of the buffer in memory  buffer end  Points to the end of the buffer in memory  head  Points to the end of stored data  tail  Points to the start of stored data   We could keep the sz attribute to allow the parametrisation of the unit of storage  Both the count and the capacity values should be derive-able using the above pointers  Capacity capacity is straight forward  as it can be derived by dividing the distance between the buffer end pointer and the buffer pointer by the unit of storage sz  snippet below is pseudocode   capacity    buffer end - buffer    sz  Count For count though  things get a bit more complicated  For example  there is no way to determine whether the buffer is empty or full  in the scenario of head and tail pointing to the same location  To tackle that  the buffer should allocate memory for an additional element  For example  if the desired capacity of our circular buffer is 10   sz  then we need to allocate 11   sz  Capacity formula will then become  snippet below is pseudocode   capacity bytes   buffer end - buffer - sz capacity   capacity bytes   sz  This extra element semantic allows us to construct conditions that evaluate whether the buffer is empty or full  Empty state conditions In order for the buffer to be empty  the head pointer points to the same location as the tail pointer  head    tail  If the above evaluates to true  the buffer is empty  Full state conditions In order for the buffer to be full  the head pointer should be 1 element behind the tail pointer  Thus  the space needed to cover in order to jump from the head location to the tail location should be equal to 1   sz  if tail is larger that head  tail - head    sz  If the above evaluates to true  the buffer is full  if head is larger that tail   buffer end - head returns the space to jump from the head to the end of the buffer  tail - buffer returns the space needed to jump from the start of the buffer to the  tail  Adding the above 2 should equal to the space needed to jump from the head to the tail The space derived in step 3  shold not be more than 1   sz   buffer end - head     tail - buffer     sz   gt  buffer end - buffer - head   tail    sz   gt  buffer end - buffer - sz    head - tail   gt  head - tail    buffer end - buffer - sz   gt  head - tail    capacity bytes  If the above evaluates to true  the buffer is full  In practice Modifying  Adam Rosenfield s to use the above circular buffer structure   include  lt string h gt    define CB SUCCESS 0           CB operation was successful     define CB MEMORY ERROR 1      Failed to allocate memory     define CB OVERFLOW ERROR 2    CB is full  Cannot push more items      define CB EMPTY ERROR 3       CB is empty  Cannot pop more items      typedef struct circular buffer     void  buffer    void  buffer end    size t sz    void  head    void  tail    circular buffer   int cb init circular buffer  cb  size t capacity  size t sz      const int incremented capacity   capacity   1     Add extra element to evaluate count   cb- gt buffer   malloc incremented capacity   sz     if  cb- gt buffer    NULL      return CB MEMORY ERROR    cb- gt buffer end    char   cb- gt buffer   incremented capacity   sz    cb- gt sz   sz    cb- gt head   cb- gt buffer    cb- gt tail   cb- gt buffer    return CB SUCCESS     int cb free circular buffer  cb      free cb- gt buffer     return CB SUCCESS     const int  cb length circular buffer  cb      return  char   cb- gt buffer end -  char   cb- gt buffer     int cb push back circular buffer  cb  const void  item      const int buffer length    cb length cb     const int capacity length   buffer length - cb- gt sz     if   char   cb- gt tail -  char   cb- gt head    cb- gt sz           char   cb- gt head -  char   cb- gt tail    capacity length      return CB OVERFLOW ERROR     memcpy cb- gt head  item  cb- gt sz      cb- gt head    char  cb- gt head   cb- gt sz    if cb- gt head    cb- gt buffer end      cb- gt head   cb- gt buffer     return CB SUCCESS     int cb pop front circular buffer  cb  void  item      if  cb- gt head    cb- gt tail      return CB EMPTY ERROR     memcpy item  cb- gt tail  cb- gt sz      cb- gt tail    char  cb- gt tail   cb- gt sz    if cb- gt tail    cb- gt buffer end      cb- gt tail   cb- gt buffer     return CB SUCCESS

User · Answer

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- gt sizeOfBuffer   kNumPointsInMyBuffer  myRingBuffer- gt 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- gt sizeOfBuffer - 1      int lastWrittenSample   myRingBuffer- gt currentIndex       int idx      for  int i 0  i  lt  numsamples    i               modulo will automagically wrap around our index         idx    i   lastWrittenSample   amp  buffLen           myRingBuffer- gt data idx    myData i                 Update the current index of our ring buffer      myRingBuffer- gt currentIndex    numsamples      myRingBuffer- gt currentIndex  amp   myRingBuffer- gt sizeOfBuffer - 1      As long as your ring buffer s length is a power of two  the incredibly fast binary   amp   operation will wrap around your index for you  For my application  I m displaying a segment of audio to the user from a ring buffer of audio acquired from a microphone    I always make sure that the maximum amount of audio that can be displayed on screen is much less than the size of the ring buffer  Otherwise you might be reading and writing from the same chunk  This would likely give you weird display artifacts

User · Answer

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  lt  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 gt   cRingBufCount  a  0          return a

User · Answer

A simple implementation could consist of    A buffer  implemented as an array of size n  of whatever type you need A read pointer or index  whichever is more efficient for your processor  A write pointer or index A counter indicating how much data is in the buffer  derivable from the read and write pointers  but faster to track it separately    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

User · Answer

First  the headline  You don t need modulo arithmetic to wrap the buffer if you use bit ints to hold the head  amp  tail  pointers   and size them so they are perfectly in synch  IE  4096 stuffed into a 12-bit unsigned int is 0 all by itself  unmolested in any way  Eliminating modulo arithmetic  even for powers of 2  doubles the speed - almost exactly   10 million iterations of filling and draining a 4096 buffer of any type of data elements takes 52 seconds on my 3rd Gen i7 Dell XPS 8500 using Visual Studio 2010 s C   compiler with default inlining  and 1 8192nd of that to service a datum   I d RX rewriting the test loops in main   so they no longer control the flow - which is  and should be  controlled by the return values indicating the buffer is full or empty  and the attendant break  statements  IE  the filler and drainer should be able to bang against each other without corruption or instability  At some point I hope to multi-thread this code  whereupon that behavior will be crucial   The QUEUE DESC  queue descriptor  and initialization function forces all buffers in this code to be a power of 2  The above scheme will NOT work otherwise  While on the subject  note that QUEUE DESC is not hard-coded  it uses a manifest constant   define BITS ELE KNT  for its construction   I m assuming a power of 2 is sufficient flexibility here   To make the buffer size run-time selectable  I tried different approaches  not shown here   and settled on using USHRTs for Head  Tail  EleKnt capable of managing a FIFO buffer USHRT   To avoid modulo arithmetic I created a mask to  amp  amp  with Head  Tail  but that mask turns out to be  EleKnt -1   so just use that  Using USHRTS instead of bit ints increased performance   15  on a quiet machine  Intel CPU cores have always been faster than their buses  so on a busy  shared machine  packing your data structures gets you loaded and executing ahead of other  competing threads  Trade-offs   Note the actual storage for the buffer is allocated on the heap with calloc    and the pointer is at the base of the struct  so the struct and the pointer have EXACTLY the same address  IE  no offset required to be added to the struct address to tie up registers    In that same vein  all of the variables attendant with servicing the buffer are physically adjacent to the buffer  bound into the same struct  so the compiler can make beautiful assembly language  You ll have to kill the inline optimization to see any assembly  because otherwise it gets crushed into oblivion    To support the polymorphism of any data type  I ve used memcpy   instead of assignments  If you only need the flexibility to support one random variable type per compile  then this code works perfectly    For polymorphism  you just need to know the type and it s storage requirement  The DATA DESC array of descriptors provides a way to keep track of each datum that gets put in QUEUE DESC pBuffer so it can be retrieved properly  I d just allocate enough pBuffer memory to hold all of the elements of the largest data type  but keep track of how much of that storage a given datum is actually using in DATA DESC dBytes  The alternative is to reinvent a heap manager   This means QUEUE DESC s UCHAR  pBuffer would have a parallel companion array to keep track of data type  and size  while a datum s storage location in pBuffer would remain just as it is now  The new member would be something like DATA DESC  pDataDesc  or  perhaps  DATA DESC DataDesc 2 BITS ELE KNT  if you can find a way to beat your compiler into submission with such a forward reference  Calloc   is always more flexible in these situations   You d still memcpy   in Q Put   Q Get  but the number of bytes actually copied would be determined by DATA DESC dBytes  not QUEUE DESC EleBytes  The elements are potentially all of different types sizes for any given put or get   I believe this code satisfies the speed and buffer size requirements  and can be made to satisfy the requirement for 6 different data types  I ve left the many test fixtures in  in the form of printf   statements  so you can satisfy yourself  or not  that the code works properly  The random number generator demonstrates that the code works for any random head tail combo    enter code here    Queue Small cpp   Defines the entry point for the console application      include  stdafx h   include  lt stdio h gt   include  lt time h gt   include  lt limits h gt   include  lt stdlib h gt   include  lt malloc h gt   include  lt memory h gt   include  lt math h gt    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  lt  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- gt EleKnt        USHRT pow 2 0  BitsForEleKnt       Q- gt 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- gt Head   Q- gt Tail   rand       supposed to be set to zero here  or by memset     Q- gt Head   Q- gt Tail   0          allocate queue s storage     if NULL     Q- gt pBuffer    UCHAR   calloc Q- gt EleKnt  Q- gt EleBytes               return NULL          else              return Q              --------------------------------------------------------------------------- int Q Put QUEUE DESC  Q  UCHAR  pNew           memcpy Q- gt pBuffer    Q- gt Tail   Q- gt EleBytes   pNew  Q- gt EleBytes       if Q- gt Tail     Q- gt Head   Q- gt EleKnt                 Q- gt IsFull   1          Q- gt Tail    1             return QUEUE FULL FLAG      queue is full           Q- gt 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- gt pBuffer    Q- gt Head   Q- gt EleBytes   Q- gt EleBytes       Q- gt Head    1        the bit int MUST wrap around  just like modulo      if Q- gt Head    Q- gt Tail                     Q- gt 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  amp Queue  BITS ELE KNT  sizeof int               printf   nProgram failed to initialize  Aborting  n n            return 0             start   clock        for k 0  k lt LoopKnt  k                   printf   n n Fill er up please    n              Q- gt Head   Q- gt Tail   rand            for i 1  i lt   Q- gt EleKnt  i                     Qview   i i              if QUEUE FULL FLAG    Q Put Q   UCHAR    amp 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    amp 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- gt Head  Q- gt Tail             printf   nQueue time was  5 3f to fill  amp  drain  i element queue   i times  n                          dbl  clock  -start   dbl CLOCKS PER SEC Q- gt EleKnt  LoopKnt       printf   nQueue head value is  i  tail is  i n   Q- gt Head  Q- gt Tail       getchar        return 0

User · Answer

Can you enumerate the types needed at the time you code up the buffer  or do you need to be able to add types at run time via dynamic calls   If the former  then I would create the buffer as a heap-allocated array of n structs  where each struct consists of two elements  an enum tag identifying the data type  and a union of all the data types   What you lose in terms of extra storage for small elements  you make up in terms of not having to deal with allocation deallocation and the resulting memory fragmentation   Then you just need to keep track of the start and end indices that define the head and tail elements of the buffer  and make sure to compute mod n when incrementing decrementing the indices

[c] How do you implement a circular buffer in C?

Examples related to c

Examples related to data-structures

Examples related to circular-buffer