How to Create a Circular Queue in C++

[avsrk]

Hi Folks

I want to create a circular queue for high speed data acquistion on
QNX with GNU C++ .
Does any one know of efficient ways either Using STL or in any other
way .
I am thing of using queue or dqueue to implement it ...
any good info is appreciated . I want it to be efficient , high speed
for developing device drivers .

Thanks
subra

[Benry]

What type of data will you be storing in the queue? For the least
amount of overhead, why not make an array of said type, and a counting
number that is incremented until a certain number, then set to 0
again...basical ly a circular buffer in an array. Unless you need a
start and end counter...make sure that they don't cross.

Also, there is a queue class: http://www.cppreference.com/cppqueue/

Now that I think of it, I don't know what you mean by circular
queue...circula r buffer? I'm losing it.

[Roland Pibinger]

On 10 Jan 2006 10:35:37 -0800, av***@mailcity. com wrote:

I want to create a circular queue for high speed data acquistion on
QNX with GNU C++ . Does any one know of efficient ways either Using
STL or in any other way .
I am thing of using queue or dqueue to implement it ...
any good info is appreciated . I want it to be efficient , high speed
for developing device drivers .

Enter 'circular queue' here: http://www.koders.com/

Best wishes,
Roland Pibinger

[Jeremy Jurksztowicz]

Do not use STL queue's unless you are sure you can predict all
allocations/deallocations precisely. It is best you make your own
circular queue that has guaranteed allocator (non) usage, or find one
specifically made for device drivers. Additionally some (easily
avoided) STL container functions throw exceptions, which should never
be used in a device-driver (unless you have a magic compiler which
creates easily predictable throw/catch behavior).

Again, the key point is to make sure you have COMPLETE control over any
unbounded operations (most often allocations/deallocations), if you can
find a way to use an STL container in such a way, go for it.

Jeremy Jurksztowicz

[TB]

av***@mailcity. com sade:

Hi Folks

I want to create a circular queue for high speed data acquistion on
QNX with GNU C++ .
Does any one know of efficient ways either Using STL or in any other
way .
I am thing of using queue or dqueue to implement it ...
any good info is appreciated . I want it to be efficient , high speed
for developing device drivers .

Thanks
subra

Depends upon design, and how fluffy you want your component to be,
in either case, here's a fixed sized circular queue/buffer:

int CQ[1024];

void write(int t) {
static unsigned int idx = 0;
CQ[idx++%1024] = t;
}

int read() {
static unsigned int idx = 0;
return CQ[idx++%1024];
}

TB

[avsrk]

Hi

This implementation and the one suggested by Mr Benry above have a
flaw .
If the writing and reading are happening at different speeds which
would be the case
and which is the whole idea behind the circular queues (to discard the
old data and to get the old data first and then the new data of the
sna shot we have in the queue ).
After the buffer is full and the write starts writing in the beginning
, but the reader
in the situation where it gets to the beginning and start reading from
there could find the
latest data there and after some time when it gets to the next index it
could find old data
there , i.e it could get latest data at some time and a little later
could get old data which should not be the case .
please clarify if iam wrong

Thanks
subra

Depends upon design, and how fluffy you want your component to be,
in either case, here's a fixed sized circular queue/buffer:

int CQ[1024];

void write(int t) {
static unsigned int idx = 0;
CQ[idx++%1024] = t;
}

int read() {
static unsigned int idx = 0;
return CQ[idx++%1024];
}

TB

[Mark P]

av***@mailcity. com wrote:

Hi

This implementation and the one suggested by Mr Benry above have a
flaw .
If the writing and reading are happening at different speeds which
would be the case
and which is the whole idea behind the circular queues (to discard the
old data and to get the old data first and then the new data of the
sna shot we have in the queue ).
After the buffer is full and the write starts writing in the beginning
, but the reader
in the situation where it gets to the beginning and start reading from
there could find the
latest data there and after some time when it gets to the next index it
could find old data
there , i.e it could get latest data at some time and a little later
could get old data which should not be the case .
please clarify if iam wrong

Please don't top-post (i.e., you reply goes after what you're replying
to). You are correct that the code below may read data out of order.
To get around this you need to keep track of more information. Here's
one approach off the top of my head-- it may not be optimal.

Keep a couple boolean state variables:
bool bufferEmpty; // initially true
bool bufferFull; // initially false

bufferEmpty = true means there's nothing available to read.
bufferFull = true means the entire contents of the buffer have been
written to but not been read.

Now you have to devise rules for reading and writing that update these
quantities appropriately:

If bufferEmpty:
read = error
write = advance write index, unset bufferEmpty

If bufferFull:
read = advance read index; unset bufferFull
write = advance read and write indices

If !bufferEmpty && !bufferFull:
read = advance read index; if read index = write index, set bufferEmpty
write = advance write index; if read index = write index, set bufferFull

Like I said, this is improvised so you should check it and correct it if
needed. Hope that helps.

-Mark
Thanks
subra

Depends upon design, and how fluffy you want your component to be,
in either case, here's a fixed sized circular queue/buffer:

int CQ[1024];

void write(int t) {
static unsigned int idx = 0;
CQ[idx++%1024] = t;
}

int read() {
static unsigned int idx = 0;
return CQ[idx++%1024];
}

TB

[Mark P]

Mark P wrote:

av***@mailcity. com wrote:

Hi

This implementation and the one suggested by Mr Benry above have a
flaw .
If the writing and reading are happening at different speeds which
would be the case
and which is the whole idea behind the circular queues (to discard the
old data and to get the old data first and then the new data of the
sna shot we have in the queue ).
After the buffer is full and the write starts writing in the beginning
, but the reader
in the situation where it gets to the beginning and start reading from
there could find the
latest data there and after some time when it gets to the next index it
could find old data
there , i.e it could get latest data at some time and a little later
could get old data which should not be the case .
please clarify if iam wrong

Please don't top-post (i.e., you reply goes after what you're replying
to). You are correct that the code below may read data out of order. To
get around this you need to keep track of more information. Here's one
approach off the top of my head-- it may not be optimal.

Keep a couple boolean state variables:
bool bufferEmpty; // initially true
bool bufferFull; // initially false

bufferEmpty = true means there's nothing available to read.
bufferFull = true means the entire contents of the buffer have been
written to but not been read.

Now you have to devise rules for reading and writing that update these
quantities appropriately:

If bufferEmpty:
read = error
write = advance write index, unset bufferEmpty

If bufferFull:
read = advance read index; unset bufferFull
write = advance read and write indices

If !bufferEmpty && !bufferFull:
read = advance read index; if read index = write index, set bufferEmpty
write = advance write index; if read index = write index, set bufferFull

Like I said, this is improvised so you should check it and correct it if
needed. Hope that helps.

-Mark

Just for fun, here's some code which seems to do the right thing. Use
at your own risk...

-Mark

#include <vector>
#include <iostream>

class CBuffer
{
public:
CBuffer (unsigned int size);
int read ();
void write (int value);

// simple test functions
void testWrite ()
{
std::cout << "write " << ++count << std::endl;
write(count);
}

void testRead ()
{
std::cout << "read " << read() << std::endl;
}

private:
std::vector<int > buffer;
unsigned int size;
unsigned int rIdx;
unsigned int wIdx;
bool empty;
bool full;

int count; // index for test functions
};

CBuffer::CBuffe r (unsigned int size) :
buffer(size), size(size), rIdx(0), wIdx(0),
empty(true), full(false), count(0) {}

int CBuffer::read()
{
if (empty)
{
std::cerr << "Error: can't read from empty buffer." << std::endl;
exit(1);
}
full = false; // buffer can't be full after a read
int result = buffer[rIdx];
rIdx = (rIdx + 1) % size;
empty = (rIdx == wIdx); // true if read catches up to write
return result;
}

void CBuffer::write (int value)
{
empty = false; // buffer can't be empty after a write
buffer[wIdx] = value;
wIdx = (wIdx + 1) % size;
if (full)
rIdx = wIdx;
full = (wIdx == rIdx); // true if write catches up to read
}

int main()
{
CBuffer cb(4);
cb.testWrite();
cb.testWrite();
cb.testWrite();
cb.testWrite();
cb.testWrite();
cb.testWrite();
cb.testWrite();
cb.testWrite();
cb.testRead();
cb.testRead();

cb.testWrite();
cb.testWrite();
cb.testRead();
cb.testRead();
cb.testRead();

cb.testWrite();
cb.testWrite();
cb.testRead();
cb.testRead();

cb.testWrite();
cb.testWrite();
cb.testWrite();
cb.testWrite();
cb.testWrite();
cb.testWrite();
cb.testWrite();
cb.testWrite();
cb.testRead();
cb.testRead();
}

[Diego Martins]

Make it a template class and put some policies for dealing with
overflow and underflow (maybe with some throws) and you will have a
good utility class for general purpose circular queues

[Benry]

Well, I explained that with a pointer to the location:

beginning end
\/---------------------------------------------------\/

this would be how it starts. Now, when data starts to be written to
the queue:
beginning end
--------------\/-------------------------------------\/

And when you start reading:

end beginning
---\/-----------\/--------------------------------------

However, the situation you're talking about is if beginning "laps" end,
and starts to write new data over data that is still in the queue. I
wrote something where beginning and end can never cross.