Circular Buffer – Part II

Last week I was chatting with software engineer about Circular Buffers. As far as I understand a circular buffer is a data structure typically implemented with an array of fixed length. There are two indices which are used to determine where to put / add / insert the next element and the other were to pull / remove the last element. The data structure implements a LIFO buffer.

I have used “Circular Buffers” on many occasions. The oldest implementations, besides college assignments, have been in device drivers on different real time operating systems to manage keyboard input, serial input and Internet input. A year or so ago I recalled a situation in which I used a Circular Buffer to implement copying files between two networked computers; one was the client and the other a server.

Given my background in this subject, I like to use arrays that have size in multiples of two (e.g., 64, 128, 256, etc). The reason is for memory utilization. Drives are loaded at system startup and are kept (locked) in system memory while the computer is up and running. Due to this restriction, it is a good practice to attempt to save a byte when possible.

In this example I will implement the code using C. The reason is that I have written several libraries with documented APIs to deal with algorithms and data structures that are commonly used in the type of projects we work. It is not a good idea to reinvent the wheel and then spend the time testing and maintaining code that is already proven and tested. At the time I wrote the libraries there were not too many open-source implementations that were applicable and portable across operating systems. Today the world has changed. In case of a real-time system libraries in C++ are readily available. In case of OO there are many Java libraries out there. The same seems to hold true for different languages and different application domains.

In this blog I will show the operation of a circular buffer implemented in C. I will also show the header file including the API and the circular buffer data structure.

As usual, I always implement a test before the actual code. Following is the test scaffold used to test my implementation:

* * * * Test Circular Buffer * * * *

1      CBAlloc()

2      CBIsEmpty()

3      CBPeek()

4      CBPut()

5      CBGet()

6      CBFree()

7      CBIsFull()

8      CBDump()

-1      QUIT

The API for the Circular Buffer from the header file follows:

// **** Circular Buffer related ****

#define       CIRCULAR_BUFFER_ELEMENTS   4

#define       CIRCULAR_BUFFER_LEN        512

// **** Circular Buffer data structure ****

typedef struct CIRCULAR_BUFFER {

SENCOR_QUEUE  queue;

void          *arr[CIRCULAR_BUFFER_ELEMENTS];

int           p;

int           q;

unsigned char filler[CIRCULAR_BUFFER_LEN – 88];

} CIRCULAR_BUFFER;

To make things simpler, I reduced the number of entries in the array down to 4. A typical size would be in a higher power of 2 (i.e., 128). Please note that the size of the array tends to be application specific. More on this in a future post.

The size of the CIRCULAR_BUFFER data structure is set to 512 bytes. I like to have data structures of a size that optimizes memory allocations. This practice tends to be quite efficient when allocating data in heaps specially in real-time operating systems.

You might be wondering the purpose of the queue element in the CIRCULAR_BUFFER data structure. The idea is to allow the data structure to be inserted in a queue. For the purpose of this discussion we can ignore its presence.

The API for the use of the CIRCULAR_BUFFER follows:

// **** circular buffer related ****

SENCOR_EXPORT INT_CALL      CBAlloc              (

CIRCULAR_BUFFER      **cb

);

SENCOR_EXPORT INT_CALL      CBDump        (

CIRCULAR_BUFFER      *cb

);

SENCOR_EXPORT INT_CALL      CBFree        (

CIRCULAR_BUFFER      **cb

);

SENCOR_EXPORT INT_CALL      CBGet         (

CIRCULAR_BUFFER      *cb,

void                 **element

);

SENCOR_EXPORT INT_CALL      CBIsEmpty     (

CIRCULAR_BUFFER      *cb,

BOOL                 *isEmpty

);

SENCOR_EXPORT INT_CALL      CBIsFull      (

CIRCULAR_BUFFER      *cb,

BOOL                 *isFull

);

SENCOR_EXPORT INT_CALL      CBPeek        (

CIRCULAR_BUFFER      *cb,

void                 **element

);

SENCOR_EXPORT INT_CALL      CBPut         (

CIRCULAR_BUFFER      *cb,

void                 *element

);

The following console screen capture illustrates testing the operation of the circular buffer:

[3] >>> 8

CBDump <<< unexpected cb == NULL line: 1260 file ==>c:\sencorsource\source\sncrbuff.c<==

TestCircularBuffer <<< CBDump status: -1049

A call is made to CBDump() but the buffer had not been allocated. The API fails and returns an error. Each error in the libraries has a specific meaning. Of interest to this post are:

<<<                 WAR_INVALID_ARGUMENT (-1049) Unexpected argument

<<<           WAR_INVALID_ARGUMENT_VALUE (-1050) Unexpected argument value

<<<                     WAR_BUFFER_EMPTY (-1358) Buffer is FULL

<<<                      WAR_BUFFER_FULL (-1359) Buffer is EMPTY

After allocating a circular buffer (# 1) in the test, we invoke CBDump() and in this case it shows:

[1] >>> 8

<<<      cb: 0x014187f0

<<<       p: 0

<<<       q: 0

<<< arr[ 0]: 0x00000000 <— p, q

<<< arr[ 1]: 0x00000000

<<< arr[ 2]: 0x00000000

<<< arr[ 3]: 0x00000000

Lets now check the operation of CBIsEmpty():

[8] >>> 2

<<< isEmpty: 1 (bool)

As expected the circular buffer is empty.

Let’s put some random integer values into the buffer:

[2] >>> 4

<<< *widget: 24

CBPut <<< element: 0x013eec70 line: 936

<<< *widget: 24

[4] >>>

<<< *widget: 31

CBPut <<< element: 0x013eeeb0 line: 936

<<< *widget: 31

[4] >>> 4

<<< *widget: 22

CBPut <<< element: 0x013eeca0 line: 936

<<< *widget: 22

We inserted 3 widgets as illustrated by the following call to CBDump():

[4] >>> 8

<<<      cb: 0x014187f0

<<<       p: 3

<<<       q: 0

<<< arr[ 0]: 0x00000000 <— q

<<< arr[ 1]: 0x013eec70

<<< arr[ 2]: 0x013eeeb0

<<< arr[ 3]: 0x013eeca0 <— p

A call to CBIsFull() indicates that the circular buffer is full:

[8] >>> 7

<<< isFull: 1 (bool)

If we attempt to insert an additional element to the full circular buffer:

[7] >>> 4

<<< *widget: 14

CBPut <<< element: 0x013eecd0 line: 936

CBPut <<< UNEXPECTED isFull: 1 (bool) line: 952 file ==>c:\sencorsource\source\sncrbuff.c<==

TestCircularBuffer <<< CBPut status: -1359

As we can see, the test program tried inserting a new widget with value 14 but the circular buffer was full.

Now let’s get all the elements from the circular buffer which currently is holding 3 elements:

[4] >>> 5

TestCircularBuffer <<< widget: 0x013eec70

<<< *widget: 24

[5] >>> 5

TestCircularBuffer <<< widget: 0x013eeeb0

<<< *widget: 31

[5] >>> 5

TestCircularBuffer <<< widget: 0x013eeca0

<<< *widget: 22

[5] >>> 5

CBGet <<< UNEXPECTED isEmpty: 1 (bool) line: 1104 file ==>c:\sencorsource\source\sncrb

TestCircularBuffer <<< CBGet status: -1358

As you can verify the 3 elements in the proper order were removed from the circular buffer. We also tried to get an element from an empty buffer. The operation failed.

All is fine with the circular buffer. Please note that the buffer is not protected from asynchronous calls. If we would be using it as a keyboard buffer in a real-time system, all would work with the inserts performed at an interrupt level. The gets would have to raise the interrupt level to the same or higher used by the keyboard. This is typically performed buy a call to the PIC.

At the application level, if we used multiple processes or threads the current implementation world not work. We need to make use of an inter process communication call which I will demonstrate in a following post.

A section (for blog post size) of the test code for the circular buffer data structure follows:

// **** LOOP testing circular buffer functions ****

for (done = (BOOL)(0 == 1), selection = 1; !done;) {

// **** DISPLAY the menu selections ****

printf(“\n* * * * Test Circular Buffer * * * *\n”);

printf(“\n”);

printf(” 1\tCBAlloc()\n”);

printf(” 2\tCBIsEmpty()\n”);

printf(” 3\tCBPeek()\n”);

printf(” 4\tCBPut()\n”);

printf(” 5\tCBGet()\n”);

printf(” 6\tCBFree()\n”);

printf(” 7\tCBIsFull()\n”);

printf(” 8\tCBDump()\n”);

printf(“-1\tQUIT\n”);

// **** PROMPT the user for an item selection ****

printf(“\n”); printf(“[%d] >>> “, selection);

// **** GET the response from the user ****

if (fgets(buffer, BUFSIZ, stdin) == (char *)NULL) {

EventLog(EVENT_ERROR, “TestCircularBuffer <<< fgets line: %d file ==>%s<==\n”, __LINE__, __FILE__);

retVal = WAR_INTERNAL_ERROR;                                                             // flag the problem

goto done;

}

// **** CHECK for blank responses ****

buffer[strlen(buffer) – 1] = ‘\0’;                                                       // remove the CR

if (*buffer != ‘\0’)

selection = atoi(buffer);

// **** DISPATCH the selected function ****

switch (selection) {

case -1:

done = (BOOL)(1 == 1);                                                                          // we are done

break;

case 1:

// **** FREE the previous circular buffer (just in case) ****

status = CBFree(&cb);

if (status != 0) {

EventLog(EVENT_ERROR, “TestCircularBuffer <<< CBFree status: %d\n”, status);

retVal = status;

goto done;

}

// **** ALLOCATE a new circular buffer ****

status = CBAlloc(&cb);

if (status != 0) {

EventLog(EVENT_ERROR, “TestCircularBuffer <<< CBAlloc status: %d\n”, status);

retVal = status;

goto done;

}

break;

case 2:

status = CBIsEmpty(cb, &isEmpty);

if (status != 0)                                                                                // something went wrong

EventLog(EVENT_ERROR, “TestCircularBuffer <<< CBIsEmpty status: %d\n”, status);

else printf(“<<< isEmpty: %d (bool)\n”, (int)isEmpty);

break;

case 3:

widget = (void *)NULL;

status = CBPeek(cb, &widget);

if (status != 0)                                                                                // something went wrong

EventLog(EVENT_ERROR, “TestCircularBuffer <<< CBPeek status: %d\n”, status);

else {

EventLog(EVENT_ERROR, “TestCircularBuffer <<< widget: 0x%08lx\n”, widget);

printf(“<<< *widget: %d\n”, *((int *)widget));

widget = (void *)NULL;

}

break;

case 4:

widget = (void *)calloc((size_t)1,

(size_t)sizeof(int));

if (widget == (void *)NULL) {

EventLog(EVENT_ERROR, “TestQueInsert <<< calloc line: %d file ==>%s<==\n”, __LINE__, __FILE__);

retVal = WAR_NO_MORE_MEMORY;

goto done;                                                                                      // to perform clean up

}

*((int *)widget) = rand() % 100;

printf(“<<< *widget: %d\n”, *((int *)widget));

status = CBPut(cb, (void *)widget);

if (status != 0)

EventLog(EVENT_ERROR, “TestCircularBuffer <<< CBPut status: %d\n”, status);

else printf(“<<< *widget: %d\n”, *((int *)widget));

widget = (void *)NULL;

break;

case 5:

widget = (void *)NULL;

status = CBGet(cb, &widget);

if (status != 0)

EventLog(EVENT_ERROR, “TestCircularBuffer <<< CBGet status: %d\n”, status);

else {

EventLog(EVENT_ERROR, “TestCircularBuffer <<< widget: 0x%08lx\n”, widget);

printf(“<<< *widget: %d\n”, *((int *)widget));

free(widget);

widget = (void *)NULL;

}

break;

case 6:

status = CBFree(&cb);

if (status != 0)

EventLog(EVENT_ERROR, “TestCircularBuffer <<< CBFree status: %d\n”, status);

break;

case 7:

status = CBIsFull(cb, &isFull);

if (status != 0)

EventLog(EVENT_ERROR, “TestCircularBuffer <<< CBIsFull status: %d\n”, status);

printf(“<<< isFull: %d (bool)\n”, (int)isFull);

break;

case 8:

status = CBDump(cb);

if (status != 0)

EventLog(EVENT_ERROR, “TestCircularBuffer <<< CBDump status: %d\n”, status);

break;

default:

EventLog(EVENT_INFO, “TestCircularBuffer <<< UNEXPECTED selection: %d or function NOT implemented yet line: %d\n”, selection, __LINE__);

break;

}

}

If you have comments or questions regarding this or any other post in this blog, please do not hesitate and send me a message. Will reply as soon as possible and will not use your name unless you explicitly allow me to do so.

John

john.canessa@gmail.com

Follow me on Twitter: @john_canessa

 

 

 

 

 

Leave a Reply

Your email address will not be published. Required fields are marked *