Circular buffers or queues are also very common algorithms in computing, their utility ranges from communicating processes securely, storing information to be used later, or as a synchronization mechanism for processes that run at different intervals. A common buffer in memory is basically an single index array that is used to store data, the data is written to the buffer using index form 0 to the size of the buffer - 1, and read from the buffer using the same index.
/*declare a buffer of 10 bytes*/
unsigned char buffer[10];
/*write data to the buffer using the index*/
buffer[0] = 0x01;
buffer[1] = 0x02;
buffer[2] = 0x03;
...
buffer[9] = 0x0A;
Ok, but how can we make this buffer circular? The idea is when the last index is reached, the next index to be written is the first index of the buffer, this way the buffer has no actual end or beginning, and the data is always being written and read in a circular fashion.
/*declare a buffer of 10 bytes*/
unsigned char buffer[10];
unsigned char index = 7;
/*write data to the buffer using the index*/
buffer[index++] = 0x01;
buffer[index++] = 0x02;
if( index == 9 ) index = 0;
buffer[index++] = 0x02;
But if it has no end or beginning, how do we know when the buffer is full or empty? The answer is simple, we use two indexes, one to write data to the buffer and another to read data from the buffer, when the two indexes are equal, the buffer is empty or full. After a write operation the write index is incremented and the compared with the read index, if they are equal, the buffer is full. And after a read operation the read index is incremented and compared with the write index, if they are equal, the buffer is empty.
/*declare a buffer of 4 bytes*/
unsigned char buffer[4];
unsigned char write_index = 0;
unsigned char read_index = 0;
/*write data to the buffer using the index*/
buffer[write_index++] = 0x01;
buffer[write_index++] = 0x02;
if( write_index == read_index ) buffer_full = true;
...
/*read data from the buffer using the index*/
data = buffer[read_index++];
data = buffer[read_index++];
if( read_index == write_index ) buffer_empty = true;
...
The previous code is a simple example of a circular buffer, it incomplete, and it is not optimized, but it is a good starting point to understand how circular buffers work. Try to write a complete circular buffer implementation, and test it with some data, you will see how useful this data structure is in computing. the following image shows a graphical representation of a Circular buffer made from a memory array
Circular buffer manager Driver
Time to create a driver that configures and controls a circular buffer, the driver will be written in the files Buffer.h and Buffer.c. The circular buffer should handle n elements of type uint8_t (elements of just one byte). and the following interfaces
- It should have an interface to initialize the buffer.
void Buffer_Init( BufferType *Buffer, uint8_t Elements, uint8_t *Memory );
Initialize the circular buffer by setting the head and tail elements to zero, and the values of empty to TRUE and full to FALSE. And set the number of elements to manage and the memoery where those elements will be stored using the BufferType.Buffer
elements
- It should have an interface that allows writing to the buffer.
void Buffer_WriteData( BufferType *hbuffer, unsigned char data );
Write a new 8-bit data to the buffer if there is available space; if there is no space, no data will be written. Function will determine if the queue is full with the last data written
- It should have an interface that allows reading from the buffer.
unsigned char Buffer_ReadData( BufferType *Buffer);
Reads a data from the buffer, the data that is read will no longer exist within the buffer. If the buffer is empty, no data will be read, and the value returned by the function will not be valid. Function will determine if the queue is empty with the last data read
- It should have an interface that reports if the buffer is empty.
unsigned char Buffer_isBufferEmpty( BufferType *Buffer);
The function returns one if there are no more elements that can be read from the circular buffer, and zero if there is at least one element that can be read. It is necessary to use this function before using the read function.
- The control structure of the buffer must have the following elements:
typedef struct _BufferType
{
unsigned char *Buffer; /*pointer to buffer memory*/
unsigned long Elements; /*number of elements in the buffer*/
unsigned long Head; /*head index*/
unsigned long Tail; /*read index*/
unsigned char Empty; /*flag to signal if the buffer is empty*/
unsigned char Full; /*flag to signal if the buffer is full*/
} BufferType;
Example
int main( void )
{
unsigned char dato;
unsigned char data;
unsigned char arreglo[200];
BufferType CircBuffer;
//inicialización
Buffer_Init( &CircBuffer, 200u, arreglo );
//writting in the buffer
dato = 100;
Buffer_WriteData( &CircBuffer, dato );
dato = 120;
Buffer_WriteData( &CircBuffer, dato );
dato = 200;
Buffer_WriteData( &CircBuffer, dato );
//read all the messages
while( Buffer_isBufferEmpty( &CircBuffer ) == 0u )
{
data = Buffer_ReadData( &CircBuffer );
printf( "data read from the queue %d\n", data );
}
}
Buffer plays really well when using a scheduler
#include <stdio.h>
#include "Scheduler.h"
#include "Queue.h"
#define TASKS_N 2
#define TICK_VAL 100
static TaskType tasks[ TASKS_N ];
static SchedulerType Sche;
static unsigned char arreglo[ 20 ];
static BufferType CircBuffer;
void Task_500ms(void);
void Task_1000ms(void);
int main( void )
{
unsigned char TaskID1;
unsigned char TaskID2;
/*queue inicialización*/
Buffer_Init( &CircBuffer, 200u, arreglo );
/*init the scheduler with two tasks and a tick time of 100ms and run for 10 seconds only*/
Scheduler_InitScheduler( &Sche, TICK_VAL, TASKS_N, &tasks );
/*register two task with thier corresponding init fucntions and their periodicyt, 100ms and 500ms*/
TaskID1 = Scheduler_RegisterTask( &Sche, NULL, Task_500ms, 500 );
TaskID2 = Scheduler_RegisterTask( &Sche, NULL, Task_1000ms, 1000 );
/*run the scheduler forever*/
Scheduler_MainFunction( &Sche );
return 0;
}
void Task_500ms(void)
{
uint8_t dato = 100;
Buffer_WriteData( &CircBuffer, dato );
}
void Task_1000ms(void)
{
uint8_t data = Buffer_ReadData( &CircBuffer );
printf("Data receive from another task: %d", data);
}
Improving our algorithm
That was cool, but there are some limitations in our circular buffer, like using only elements of one byte, and real queues or circular buffer should be capable of handle any kind of data type, that is why we are going to improve our algorithm with the following specification
You can found here our own queue implementation, the purpose of the code it is only to be taken as reference to clarify your potential doubts, but we encourage you to write your own implementation
Code Snippets
Exercises:
- Rewrite the exercises you did in the scheduler but this time pass information between tasks using Queues