How to Create a Circular Queue in C++

Discussion in 'C++' started by avsrk@mailcity.com, Jan 10, 2006.

  1. Guest

    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
    , Jan 10, 2006
    #1
    1. Advertising

  2. Benry Guest

    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...basically 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...circular buffer? I'm losing it.
    Benry, Jan 10, 2006
    #2
    1. Advertising

  3. On 10 Jan 2006 10:35:37 -0800, 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
    Roland Pibinger, Jan 10, 2006
    #3
  4. 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
    Jeremy Jurksztowicz, Jan 10, 2006
    #4
  5. TB Guest

    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
    TB, Jan 10, 2006
    #5
  6. Guest

    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
    , Jan 10, 2006
    #6
  7. Mark P Guest

    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, Jan 10, 2006
    #7
  8. Mark P Guest

    Mark P wrote:
    > 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::CBuffer (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();
    }
    Mark P, Jan 11, 2006
    #8
  9. 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
    Diego Martins, Jan 11, 2006
    #9
  10. Benry Guest

    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.
    Benry, Jan 12, 2006
    #10
  11. Guest

    Thank you folks ,

    Thanks for all the info , i was looking for ring buffer which can be
    used across processes .
    Benry yes you did indicate it the data crossing over with pointers i am
    sorry i overlookd it .

    thanks again
    subra
    , Jan 12, 2006
    #11
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Kiuhnm
    Replies:
    16
    Views:
    728
    Jonathan Mcdougall
    Jan 3, 2005
  2. herrcho

    Circular Queue data structure ..

    herrcho, Oct 1, 2003, in forum: C Programming
    Replies:
    6
    Views:
    20,514
    BruceS
    Oct 2, 2003
  3. Russell Warren

    Is Queue.Queue.queue.clear() thread-safe?

    Russell Warren, Jun 22, 2006, in forum: Python
    Replies:
    4
    Views:
    663
    Russell Warren
    Jun 27, 2006
  4. Kris
    Replies:
    0
    Views:
    462
  5. bintom
    Replies:
    6
    Views:
    603
    Öö Tiib
    Nov 3, 2012
Loading...

Share This Page