Question about C implementation of Circular Buffer

I have seen the following implementation of circular buffer:

http://en.wikipedia.org/wiki/Circular_buffer

/**< Buffer Size */
#define BUFFER_SIZE    10
#define NUM_OF_ELEMS   (BUFFER_SIZE-1)

/**< Circular Buffer Types */
typedef unsigned char INT8U;
typedef INT8U KeyType;
typedef struct
{
    INT8U writePointer; /**< write pointer */
    INT8U readPointer;  /**< read pointer */
    INT8U size;         /**< size of开发者_开发知识库 circular buffer */
    KeyType keys[0];    /**< Element of circular buffer */
} CircularBuffer;

/**< Init Circular Buffer */
CircularBuffer* CircularBufferInit(CircularBuffer** pQue, int size)
{
    int sz = size*sizeof(KeyType)+sizeof(CircularBuffer);
    *pQue = (CircularBuffer*) malloc(sz);
    if(*pQue)
    {
        printf("Init CircularBuffer: keys[%d] (%d)\n", size, sz);
        (*pQue)->size=size;
        (*pQue)->writePointer = 0;
        (*pQue)->readPointer  = 0;
    }
    return *pQue;
}

int main(int argc, char *argv[])
{
    CircularBuffer* que;
    KeyType a = 101;
    int isEmpty, i;

    CircularBufferInit(&que, BUFFER_SIZE);
    ...
}

Here are the questions:

Q1> Why the code uses the following line to define variable keys?

KeyType keys[0];    /**< Element of circular buffer */

Q2> Why the code computes the size of the allocated buffer as follows:

int sz = size*sizeof(KeyType)+sizeof(CircularBuffer);

Q3> Why pQue pointing to a buffer larger than the size of CircularBuffer, but still can directly referring to the member of it?

(*pQue)->size=size;
(*pQue)->writePointer = 0;
(*pQue)->readPointer  = 0;

---

The first item is just to specify that the element in the struct uses array syntax, but actually isn't declared to be an array of any size.

The malloc allocates the circular buffer size (which accounts for all the of non-key fields) and the key fields (size * sizeof(KeyType)). Note that keys[0] is actually of size zero, so no key field gets counted twice.

The buffer isn't actually larger than the size of the circular buffer, the allocation (as described above) was a one-time allocation to accommodate the circular buffer and the control elements (size, readPointer, writePointer) in one pass.

The whole reason this works is because C doesn't check to see if you walked off the end of an array. In a language that enforces array bounds, the first time you attempted to use this you would get something akin to Java's ArrayOutOfBoundsException, because to use keys[0], you would have had to declare a keys array of size (at least) one, like keys[1].

In other words, it's a couple of C specific hacks to optimize the allocation of the buffer once, without encoding a fixed size. The reason it works is because array offset is strictly implemented as (base address + index * sizeof(array type)).

---

int sz = size*sizeof(KeyType)+sizeof(CircularBuffer);

size = number of elements in circular buffer

sizeof(KeyType) = size of a single KeyType element

(size * sizeof) = total amount of space for storing all the KeyType elements

sizeof (CircularBuffer) = becuase circular buffer stores additional fields than the circular buffer elements

Why the code uses the following line to define variable keys?

KeyType keys[0]; /**< Element of circular buffer */

I can't understand your doubts here. It's pretty common. A circular buffer is represented with an array of element which type is KeyType. If you are wondering why it uses KeyType instead that directly unsigned int that's because:

1. This way it's more clear. The new type introduce explicitely tell us what the array is for.
2. Refactoring purposes: if we decide to change KeyType's type, we can just modify the typedef.

---

What's going on is that there's a "header" structure at the beginnning of a memory block, followed by a variable number of "detail" structures. This used to be a common way to do things, back in the Old Days; you get to create all the structs with one call to malloc(), so it's good for performance. You'll probably also see this pattern often with file-handling code or network protocols, where you'll get a variable-size lump of data, whose precise size is given in a header. (Both the Excel BIFF format and TCP

1: The zero-length array used to be a common way to specify a variable-length array at the end of a struct.

2: It's allocating sizeof(CircularBuffer) bytes for the header, and size*sizeof(KeyType) so that there can be that many KeyTypes. You end up with one memory block, that holds both the header and the keys.

3: Nothin' wrong with pointing to areas WITHIN your allocated memory block. If it were pointing OUTSIDE of the allocated area, that'd be bad, but it isn't.

---

This code implements something sometimes called a "stretchy array". The goal is to create a structure containing an array when the size if the array is not known at compile time. So the structure is defined with a zero sized array as the last element. When it is allocated, the desired size is added to the malloc call. Because C guarantees that malloc'd blocks are contiguous, and because it does not do array bounds checking, it is possible to index past 0 into the additional memory, and treat it just as a regular array element.

Note that this technique only works when you malloc the structure. If it is declared as a local variable, there will be no additional room for the array.