end pointer problem of a circular buffer

Question

I'm using Visual c++.

I'm trying to implement a circular buffer, this CB must handle a specific type of data...in fact, it's a structure data where we have some kind of raw data to be stored in a char type and a date associated to that data...this has been implemented using a strucuture.

here is the code for more details:

#include <stdio.h>
#include <time.h>
#include <windows.h>



//data=date_label+raw_data
typedef struct DataFragment 
{
    char data[4];
    clock_t date;

 }DataFragment;

typedef struct CircularBuffer
{
    DataFragment *buffer;     // data buffer
    DataFragment *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
DataFragment *head;       // pointer to head
    DataFragment *tail;       // pointer to tail
 } CircularBuffer;


void cb_init(struct CircularBuffer *cb, size_t capacity, size_t sz)
 {

 if((cb->buffer = (DataFragment*) malloc(capacity * sz))!=NULL)
    puts("success alocation");
//if(cb->buffer == NULL)
     //handle error
cb->buffer_end = (DataFragment *)cb->buffer + (capacity-1)*sz;
cb->capacity = capacity;
cb->count = 0;
cb->sz = sz;
cb->head = cb->buffer;
cb->tail = cb->buffer;
}

 void cb_free(struct CircularBuffer *cb)
 {
     free(cb->buffer);
     // clear out other fields too, just to be safe
 }

 void cb_push_back(struct CircularBuffer *cb, const DataFragment *item)
  {
     //if(cb->count == cb->capacity)
       //handle error when it's full
memcpy(cb->head->data, item->data,4);
cb->head->date=item->date;
cb->head = (DataFragment*)cb->head + cb->sz;
    if(cb->head == cb->buffer_end)
      cb->head = cb->buffer;
    cb->count++;
   }

 void cb_pop_front(struct CircularBuffer *cb, DataFragment *item)
 {
   //if(cb->count == 0)
     //handle error
memcpy(item->data, cb->tail->data,4);
item->date=cb->tail->date;
cb->tail = (DataFragment*)cb->tail + cb->sz;
    if(cb->tail == cb->buffer_end)
      cb->tail = cb->buffer;
    cb->count--;
  }

int main(int argc, char *argv[])
 {

struct CircularBuffer pbuf;

pbuf.buffer=NULL;
pbuf.buffer_end=NULL;
pbuf.capacity=0;
pbuf.count=0;
pbuf.head=NULL;
pbuf.sz=0;
pbuf.tail=NULL;
struct CircularBuffer *buf= &pbuf;
size_t sizz = sizeof(DataFragment);

//initialisation of the circlar buffer to a total bytes 
//of capacity*sizz=100*sizeof(struct DataFragment)
cb_init(buf,100,sizz);

//temporary container of data
DataFragment temp,temp2;

for(int i=0;i<4;i++)
    temp.data[i]='k';
for(int i=0;i<4;i++)
    temp2.data[i]='o';

//pushing temporary buffer to the CB...40*2=80<capacity of the CB
for(int i=0;i<40;i++)
{
    Sleep(20);
    temp.date=clock();
    cb_push_back(buf,&temp);
    Sleep(10);
    temp2.date=clock();
    cb_push_back(buf,&temp2);
}

DataFragment temp3;
for(int i=0;i<20;i++)
{
    cb_pop_front(buf,&temp3);
    printf("%d\n", temp3.data); //print integers....no need of end caracter
}
cb_free(buf);

return 0;
}

When I compile the code, everything is fine, but when I debug, I noticed a problem with the buffer_end pointer, it says bad_pointer....this happens if the capacity is greater than 56...I don't know why the pointer can't point to end of the buffer.But if the capacity is less than 56 the pointer points exactly on the end of the buffer

If anyone knows why this happens like this, and how to fix it, please help me..

thanks in advance

Answer 1

It seems you are misunderstanding pointer arithmetic

cb->buffer_end = (DataFragment *)cb->buffer + (capacity-1)*sz;
cb->head = (DataFragment*)cb->head + cb->sz;
cb->tail = (DataFragment*)cb->tail + cb->sz;

Pointer arithmetic already takes into account the size of the underlying type. All you really need is

++cb->head;
++cb->tail;

---

If the idea is to hack around sizeof(DataFragment) - perhaps to allocate more storage for one item than the struct's size - for some evil purpose - you'll need to first cast the pointer to a char* (because sizeof(char) == 1).

cb->tail = (DataFragment*)((char*)cb->tail + cb->sz);

---

Design-wise the struct appears to have too many members: buffer_end and capacity duplicate each other (given one you can always find the other), and the sz member is not necessary (it should always be sizeof(DataFragment).

Also, I believe you can just assign structs

*(cb->head) = *item;

there seem to be completely unnecessary casts (probably resulting from the misunderstanding of pointer arithmetic):

cb->buffer_end = (DataFragment *)cb->buffer + (capacity-1)*sz;

And if it is supposed to be C++, then it contains lots of "C-isms" (typedeffing structs, using struct XXX var; - despite having it typedeffed, etc), and the code is generally designed in a purely C style (not taking advantage of C++'s greatest strength, automatic resource management with RAII).

---

May I also point out that clock() hardly gives you a date :)

Answer 2

I think you need to remove the * sz. (And I don't think you need the cast.)

cb->buffer_end = cb->buffer + (capacity-1);

Arithmetic on pointers automatically accounts for the size of the type pointed to.

I should also point out boost::circular_buffer.

Answer 3

you are assuming that pointers are 4 byte wide. This may not be the case on all platforms (x86_64). Hence, the memcpy()'s should make use of the sizeof operator. There seems to be another bug with "end = buffer + (capacity - 1 ) * size. In conjunction with cb_push_back() you are allocating one element too much (or you are not using the last element of the ringbuffer). cb_count gets increased in every push_back too, so your buffer can have more "counts" than elements.

Answer 4

If you are going to code in C++, at least use STL. Try std::list