I know this is an old thread, but I just found it and felt like implementing my own solution.
Code:
#include <iostream>
using namespace std;
////////////////////////////////////////////////////////////////////////////////
typedef unsigned char uchar;
typedef unsigned long Q;
////////////////////////////////////////////////////////////////////////////////
// we use an array of Q to manage the shared queue memory; each
// element can be composed of 3 units:
// |-|-------|--------|
// | | | |
// |-|-------|--------|
// ^ ^ ^-- 8 bits: offset to next item in this queue
// | |-- 7 bits: queue ID
// |-- 1 bit: used by root of queue
// set if item has been popped, unset if item
// content is valid
struct QMan {
enum { MEMORY_SIZE = 2048 };
enum { FIRST_ITEM = MEMORY_SIZE };
enum { LAST_ITEM = MEMORY_SIZE + 1 };
static uchar data[MEMORY_SIZE];
static Q q_info[MEMORY_SIZE];
static short used_slots;
static Q *end;
// print all data about each item in shared queue memory
static void print_all() {
for (int i = 0; i < MEMORY_SIZE; ++i)
cout << "[" << i << "] = " << ((q_info[i] & 0x80000000) >> 31) << ", " <<
((q_info[i] & 0x7FFF0000) >> 16) << ", " << (q_info[i] & 0x0000FFFF) <<
", value = " << (short)data[i] << endl;
cout << endl;
}
// find the first free slot starting from qitem_start
// (looping around if necessary)
static Q* get_first_free(Q *qitem_start = 0) {
Q *q = qitem_start;
Q *lastitem = end;
if (qitem_start == 0)
q = q_info;
if (*q == 0)
return q;
while (*++q > 0) {
if (q == lastitem) {
if (qitem_start > q_info) {
q = q_info;
lastitem = qitem_start;
}
return 0;
}
}
return q;
}
// all slots are free
static bool is_empty() {
return used_slots == 0;
}
// all slots are used
static bool is_full() {
return used_slots == MEMORY_SIZE;
}
// index of queue item
static int get_index(Q *qitem) {
return qitem - q_info;
}
// this modifies only the root
static void set_root_popped(Q *qitem, bool is_popped = true) {
if (is_popped)
*qitem |= 0x80000000;
else
*qitem &= ~0x80000000;
}
// true if root item has been popped and is not the first
// valid item in the queue
static bool get_root_popped(Q *qitem) {
return (*qitem & 0x80000000) != 0;
}
// set the queue id
static void set_qid(Q *qitem, short qid) {
*qitem &= 0x8000FFFF;
*qitem |= 0x7FFF0000 & (qid << 16);
}
// retrieve queue id
static short get_qid(const Q *qitem) {
return (*qitem & 0x7FFF0000) >> 16;
}
// the offset is the number of elements to the next item
// in this queue; set to FIRST_ITEM if root is available
// but unset; set to LAST_ITEM if item is the queue's tail
static void set_offset_to_next(Q *qitem, short offset) {
*qitem &= 0xFFFF0000;
*qitem |= 0x0000FFFF & offset;
}
// retrieve the offset to the next
static short get_offset_to_next(const Q *qitem) {
return *qitem & 0x0000FFFF;
}
} q_man;
////////////////////////////////////////////////////////////////////////////////
uchar QMan::data[] = { 0 };
Q QMan::q_info[] = { 0 };
short QMan::used_slots = 0;
Q *QMan::end = q_info + QMan::MEMORY_SIZE;
////////////////////////////////////////////////////////////////////////////////
Q* createQ(); // Creates a FIFO byte queue, returning a handle to it.
void destroyQ(Q *q); // Destroy an earlier created byte queue.
void enQ(Q *q, unsigned char b); // Adds a new byte to a queue.
unsigned char deQ(Q *q); // Pops the next byte off the FIFO queue.
////////////////////////////////////////////////////////////////////////////////
void onOutOfMemory() { cout << "\nOut of Memory" << endl; }
void onIllegalOperation() { cout << "\nIllegal Operation" << endl; }
////////////////////////////////////////////////////////////////////////////////
int main() {
Q * q0 = createQ();
enQ(q0, 0);
enQ(q0, 1);
Q * q1 = createQ();
enQ(q1, 3);
enQ(q0, 2);
enQ(q1, 4);
printf("%d", deQ(q0));
printf("%d\n", deQ(q0));
enQ(q0, 5);
enQ(q1, 6);
printf("%d", deQ(q0));
printf("%d\n", deQ(q0));
destroyQ(q0);
printf("%d", deQ(q1));
printf("%d", deQ(q1));
printf("%d\n", deQ(q1));
destroyQ(q1);
return 0;
}
////////////////////////////////////////////////////////////////////////////////
Q* createQ() {
if (q_man.is_full()) {
onOutOfMemory();
return 0;
}
Q *pQ = q_man.get_first_free();
if (pQ == 0) {
onOutOfMemory();
return 0;
}
// increment the number of used slots
++q_man.used_slots;
// set the id of this new queue item
q_man.set_qid(pQ, q_man.get_index(pQ) + 1);
// set the offset to the next item denoting
// that the root is the last item
q_man.set_offset_to_next(pQ, QMan::FIRST_ITEM);
return pQ;
}
void destroyQ(Q *q) {
// no queues to destroy
if (q_man.is_empty()) {
onIllegalOperation();
return;
}
// the specified queue is invalid; it does
// not contain a queue id
if (q_man.get_qid(q) == 0) {
onIllegalOperation();
return;
}
while (true) {
// decrement used item count
--q_man.used_slots;
// retrieve the offset to the next item (of course,
// this may be negative)
short offset = q_man.get_offset_to_next(q);
// free up the slot for other queues to use
*q = 0;
// the last item in the queue (it does not have
// an offset to the next item)
if (offset == QMan::LAST_ITEM)
break;
q += offset;
}
}
void enQ(Q *q, unsigned char b) {
short offset = q_man.get_offset_to_next(q);
// the root has been popped and there are no other
// items in the queue; make it available again
if (q_man.get_root_popped(q) &&
q_man.get_offset_to_next(q) == QMan::LAST_ITEM)
q_man.set_root_popped(q, false);
// the root is not empty
else if (offset != QMan::FIRST_ITEM) {
// find the last item in this queue
while (true) {
short offset = q_man.get_offset_to_next(q);
if (offset == QMan::LAST_ITEM)
break;
q += offset;
}
// there are no free slots; exit
if (q_man.is_full()) {
onOutOfMemory();
return;
}
// we have a free slot to add an item
Q *pQ = q_man.get_first_free(q);
// insure we really retrieved a free item
if (pQ == 0) {
onOutOfMemory();
return;
}
// set the queue id for the new item
q_man.set_qid(pQ, q_man.get_qid(q));
// set the offset from the previous item to the new item
q_man.set_offset_to_next(q, pQ - q);
// point at the new item
q = pQ;
}
// set the value for the current item
q_man.data[q_man.get_index(q)] = b;
// set the offset to a unique value, so we
// know it has been used, but is not pointing
// to a next item
q_man.set_offset_to_next(q, QMan::LAST_ITEM);
}
unsigned char deQ(Q *q) {
unsigned char value = 0;
short offset = q_man.get_offset_to_next(q);
// if we have previously popped the root item, pop
// the next item; we handle it this way so a dequeue
// occurs in constant time (as opposed to copying all
// the items down and deleting the last)
if (q_man.get_root_popped(q)) {
// there are no items in this queue
if (q_man.get_offset_to_next(q) == QMan::LAST_ITEM)
onIllegalOperation();
else {
Q *next = q + offset;
// get the value of the first valid item
value = q_man.data[q_man.get_index(next)];
// calculate the offset from the root to the new next
// valid item (the one after the popped item)
short offset_next = q_man.get_offset_to_next(next);
// there are no more items
if (offset_next == QMan::LAST_ITEM)
q_man.set_offset_to_next(q, QMan::LAST_ITEM);
// do the calculation
else
q_man.set_offset_to_next(q, offset + offset_next);
// free the popped item
*next = 0;
}
}
else {
// get the value for the root item
value = q_man.data[q_man.get_index(q)];
// now set it as popped
q_man.set_root_popped(q);
}
return value;
}