Implementing Circular Queues and Shared Memory Queues in C++ on Linux
A circular queue data structure can be implemented in C++ using an array as the underlying storage. This approach is efficient for handling a fixed number of elements.
#ifndef QUEUE_TEMPLATE_HPP
#define QUEUE_TEMPLATE_HPP 1
#include <iostream>
#include <cstring>
using std::cout;
template <typename DataType, std::size_t QueueCapacity>
class CircularBuffer {
private:
bool initialized_flag;
DataType buffer[QueueCapacity];
int front_index;
int rear_index;
int element_count;
CircularBuffer(const CircularBuffer&) = delete;
CircularBuffer& operator=(const CircularBuffer&) = delete;
public:
CircularBuffer() {
setup();
}
void setup() {
if (!initialized_flag) {
front_index = 0;
rear_index = QueueCapacity - 1;
element_count = 0;
std::memset(buffer, 0, sizeof(buffer));
initialized_flag = true;
}
}
bool enqueue(const DataType& item) {
if (is_full()) {
cout << "Queue capacity reached, cannot add element.\n";
return false;
}
rear_index = (rear_index + 1) % QueueCapacity;
buffer[rear_index] = item;
++element_count;
return true;
}
std::size_t count() const {
return element_count;
}
bool is_empty() const {
return element_count == 0;
}
bool is_full() const {
return element_count == QueueCapacity;
}
DataType& peek_front() {
return buffer[front_index];
}
DataType& peek_back() {
return buffer[rear_index];
}
bool dequeue() {
if (is_empty()) return false;
front_index = (front_index + 1) % QueueCapacity;
--element_count;
return true;
}
void display() const {
for (int i = 0; i < element_count; ++i) {
int pos = (front_index + i) % QueueCapacity;
cout << "buffer[" << pos << "] value = " << buffer[pos] << '\n';
}
}
};
#endif // QUEUE_TEMPLATE_HPP
#include "queue_template.hpp"
int main() {
using ValueType = int;
constexpr int BUFFER_SIZE = 5;
CircularBuffer<ValueType, BUFFER_SIZE> buffer;
cout << "Adding elements 1, 2, 3 to the queue.\n";
buffer.enqueue(1);
buffer.enqueue(2);
buffer.enqueue(3);
cout << "Current queue size: " << buffer.count() << '\n';
buffer.display();
cout << "Front element: " << buffer.peek_front() << '\n';
buffer.dequeue();
cout << "Front element: " << buffer.peek_front() << '\n';
buffer.dequeue();
cout << "Queue size after two dequeues: " << buffer.count() << '\n';
buffer.display();
cout << "Adding elements 11, 12, 13, 14, 15 to the queue.\n";
buffer.enqueue(11);
buffer.enqueue(12);
buffer.enqueue(13);
buffer.enqueue(14);
buffer.enqueue(15);
cout << "Final queue size: " << buffer.count() << '\n';
buffer.display();
return 0;
}
Extending the queue to operate within shared memory enables IPC. The following example demonstrates its usage.
#include "queue_template.hpp"
#include <sys/ipc.h>
#include <sys/shm.h>
#include <sys/sem.h>
int main() {
using ElementT = int;
constexpr int MAX_ITEMS = 5;
const key_t SHM_KEY = 0x5005;
int segment_id = shmget(SHM_KEY, sizeof(CircularBuffer<ElementT, MAX_ITEMS>), 0640 | IPC_CREAT);
if (segment_id == -1) {
cout << "Shared memory allocation failed.\n";
return -1;
}
CircularBuffer<ElementT, MAX_ITEMS>* shm_queue =
reinterpret_cast<CircularBuffer<ElementT, MAX_ITEMS>*>(shmat(segment_id, nullptr, 0));
if (shm_queue == reinterpret_cast<void*>(-1)) {
cout << "Failed to attach shared memory.\n";
return -1;
}
shm_queue->setup();
cout << "Enqueuing 1, 2, 3 into shared memory queue.\n";
shm_queue->enqueue(1);
shm_queue->enqueue(2);
shm_queue->enqueue(3);
cout << "Queue contains " << shm_queue->count() << " elements.\n";
shm_queue->display();
cout << "Dequeued " << shm_queue->peek_front() << '\n';
shm_queue->dequeue();
cout << "Dequeued " << shm_queue->peek_front() << '\n';
shm_queue->dequeue();
cout << "Remaining count: " << shm_queue->count() << '\n';
shm_queue->display();
cout << "Adding elements 11 through 15.\n";
for (int val = 11; val <= 15; ++val) {
shm_queue->enqueue(val);
}
cout << "Final shared memory queue size: " << shm_queue->count() << '\n';
shm_queue->display();
shmdt(shm_queue);
return 0;
}
This shared memory implemantation allows the queue to be accessed by multiple processes, facilitating data exchange.