While learning about driver development, I encountered the concept of a ring buffer (also called a circular buffer). This data structure shares remarkable similarities with the queue abstract data type, making it an excellent opportunity to refresh fundamental knowledge about queues.
A ring buffer proves invaluable when the application layer cannot read data fast enough. By temporarily storing incoming data in the ring buffer, we prevent data loss. Larger buffers accommodate more data, providing greater flexibility for handling burst traffic or slower consumer processing.
- Queue Fundamentals
A queue is a linear structure that restricts ensertion and deletion operations to opposite ends. Its defining characteristic is First-In-First-Out (FIFO) behavior, meaning the first element added will be the first one removed.
- The end where elements are added is called the rear or tail
- The end where elements are removed is called the front or head
- When no elements exist in the structure, the queue is considered empty
A sequential queue implementation fundamentally uses an array, but restricts insertions to one end (rear) and deletions to the other end (front). This creates a natural first-in-first-out ordering without requiring element shifting.
- Sequential Queue Data Structure
The following structure defines a fixed-size queue using a preallocated array. Two index variables track the current positions of the front and rear elements:
#define BUFFER_CAPACITY 8
typedef struct {
int storage[BUFFER_CAPACITY];
size_t head_index;
size_t tail_index;
} CircularBuffer;
The head_index points to the next element to remove, while tail_index indicates where the next element will be inserted.
- Core Queue Operations
3.1 Initialization
When initializing an empty queue, both the head and tail indices start at zero, indicating an empty buffer:
void circular_buffer_init(CircularBuffer *cb)
{
cb->head_index = 0;
cb->tail_index = 0;
}
3.2 Checking for Empty State
An empty queue occurs when the head and tail indices are equal. After any sequence of enqueue and dequeue operations, this condition remains valid for detecting an empty buffer:
int is_buffer_empty(const CircularBuffer *cb)
{
return (cb->head_index == cb->tail_index);
}
3.3 Enqueue Operation
Before inserting an element, we must verify that space is available. In circular buffer implementations, we intentionally sacrifice one storage slot to distinguish between full and empty states. When (tail + 1) % capacity equals head, the buffer is considered full:
int circular_buffer_enqueue(CircularBuffer *cb, int new_value)
{
size_t next_tail = (cb->tail_index + 1) % BUFFER_CAPACITY;
if (next_tail == cb->head_index) {
return -1; // Buffer full, insertion failed
}
cb->storage[cb->tail_index] = new_value;
cb->tail_index = next_tail;
return 0; // Success
}
3.4 Dequeue Operation
Before removing an element, we must confirm the buffer contains data. If the head and tail indices are equal, the buffer is empty and no element can be removed:
int circular_buffer_dequeue(CircularBuffer *cb)
{
if (is_buffer_empty(cb)) {
return -1; // Buffer empty, no element to remove
}
int dequeued_value = cb->storage[cb->head_index];
cb->head_index = (cb->head_index + 1) % BUFFER_CAPACITY;
return dequeued_value;
}
- Practical Demonstration
The following program simulates a scenario where data arrives faster than it can be processed, demonstrating the ring buffer's ability to smooth out timing differences between producers and consumers:
#include <stdio.h>
#include <unistd.h>
#define BUFFER_CAPACITY 8
typedef struct {
int storage[BUFFER_CAPACITY];
size_t head_index;
size_t tail_index;
} CircularBuffer;
void circular_buffer_init(CircularBuffer *cb)
{
cb->head_index = 0;
cb->tail_index = 0;
}
int is_buffer_empty(const CircularBuffer *cb)
{
return (cb->head_index == cb->tail_index);
}
int circular_buffer_enqueue(CircularBuffer *cb, int new_value)
{
size_t next_tail = (cb->tail_index + 1) % BUFFER_CAPACITY;
if (next_tail == cb->head_index) {
return -1;
}
cb->storage[cb->tail_index] = new_value;
cb->tail_index = next_tail;
return 0;
}
int circular_buffer_dequeue(CircularBuffer *cb)
{
if (is_buffer_empty(cb)) {
return -1;
}
int dequeued_value = cb->storage[cb->head_index];
cb->head_index = (cb->head_index + 1) % BUFFER_CAPACITY;
return dequeued_value;
}
int main(void)
{
CircularBuffer data_buffer;
circular_buffer_init(&data_buffer);
int incoming_data[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
size_t data_count = sizeof(incoming_data) / sizeof(incoming_data[0]);
for (size_t i = 0; i < data_count; i++) {
circular_buffer_enqueue(&data_buffer, incoming_data[i]);
printf("Enqueued: %d, Tail position: %zu\n",
incoming_data[i], data_buffer.tail_index);
if (i % 2 == 0) {
int result = circular_buffer_dequeue(&data_buffer);
printf("Dequeued: %d, Head position: %zu\n",
result, data_buffer.head_index);
}
sleep(1);
}
printf("\nDraining remaining buffer contents:\n");
while (!is_buffer_empty(&data_buffer)) {
int result = circular_buffer_dequeue(&data_buffer);
printf("Dequeued: %d, Head position: %zu\n",
result, data_buffer.head_index);
}
return 0;
}
Sample Output:
Enqueued: 1, Tail position: 1
Dequeued: 1, Head position: 1
Enqueued: 2, Tail position: 2
Enqueued: 3, Tail position: 3
Dequeued: 2, Head position: 2
Enqueued: 4, Tail position: 4
Enqueued: 5, Tail position: 5
Dequeued: 3, Head position: 3
Enqueued: 6, Tail position: 6
Enqueued: 7, Tail position: 7
Dequeued: 4, Head position: 4
Enqueued: 8, Tail position: 0
Enqueued: 9, Tail position: 1
Dequeued: 5, Head position: 5
Enqueued: 10, Tail position: 2
Dequeued: 6, Head position: 6
Dequeued: 7, Head position: 7
Dequeued: 8, Head position: 0
Dequeued: 9, Head position: 1
Dequeued: 10, Head position: 2
After processing all elements, the head and tail indices converge, confirming the buffer has returned to its empty state.
- Alternative Implementation Approaches
While sacrificing one storage slot provides a simple solution, several approaches enable full buffer utilization without losing a slot.
5.1 Maintaining an Explicit Size Counter
Adding a counter to track the current number of elements allows distinguishing between full and empty states:
#define BUFFER_CAPACITY 10
typedef struct {
int storage[BUFFER_CAPACITY];
size_t head_index;
size_t tail_index;
size_t element_count;
} CircularBufferWithSize;
void buffer_init(CircularBufferWithSize *cb)
{
cb->head_index = 0;
cb->tail_index = 0;
cb->element_count = 0;
}
After a successful enqueue, increment the counter. After a successful dequeue, decremant it. The buffer is empty when element_count equals zero and full when it reaches BUFFER_CAPACITY.
5.2 Using a Tag Flag for Operation Tracking
Another approach adds a flag indicating the most recent operation type:
#define BUFFER_CAPACITY 10
typedef struct {
int storage[BUFFER_CAPACITY];
size_t head_index;
size_t tail_index;
int last_operation; // 0 for dequeue, 1 for enqueue
} TaggedCircularBuffer;
void buffer_init(TaggedCircularBuffer *cb)
{
cb->head_index = 0;
cb->tail_index = 0;
cb->last_operation = 0;
}
Set the flag to zero after any dequeue operation and to one after any enqueue operation. The buffer is empty when head == tail and last_operation == 0. Conversely, the buffer is full when head == tail and last_operation == 1.