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