simple queue buffer

I seem to have hit a wall trying to understand some of the queuing examples a search threw up,

I have a decoder giving a 1 - 9 integer output called outdoor.

I want to announce this number from my waveHC SD card reader , and display this number on the HD vga overlay screen for the duration of the announcement (wave.isplaying)

The audio and video sections are working fine, but I just have to control them from a simple queueing routine.

If I have 6 queueing positions Q1 to Q6, would something like below work?

  if (Q1 ==0) { 
  Q1 = outdoor;     } // put number into first empty Q position
  else
  if (Q2 ==0) { 
    Q2 = outdoor;         }
  else
    if (Q3 ==0) { 
      Q3 = outdoor ;            }
    else
      if (Q4 ==0) { 
        Q4 = outdoor ;                }
      else
        if (Q5 ==0) { 
          Q5 = outdoor ;                    }
        else
          if (Q6 ==0) { 
            Q6 = outdoor;                         }

  exit=Q1;  // number to display/announce

  playshow ()  // routineto display and announce the exit number "exit"

  int i = digitalRead ( playingPin ); // from wave.isplaying   from the sd card
  if (i== LOW )  // when its finished first announcement
  {
  Q1 = 0;
  }

  if (Q1 == 0)

  { 
  Q1 = Q2; 
  Q2=Q3;
  Q3=Q4;
  Q4=Q5;
  Q5=Q6; 
  }  // shift all down the queue

A queue is typically created using a doubly linked list. Each node looks like:

struct node
{
   int val;
   Node *next;
   Node *prev;
};
typedef struct node Node;

There are enqueue and dequeue methods, and the queue class maintains pointers to the head and tail.

class Q
{
   public:
   Q();

   void enq(int val);
   int deq();
   
   private:
   Node *head;
   Node *tail;
};

Q::Q()
{
   head = NULL;
   tail = NULL;
}

Adding something to the queue requires manipulating the head, and dequeueing requires manipulating the tail.

void Q::enq(int val)
{
   Node *newNode = new Node();
   if(newNode)
   {
      newNode->val = val;
      if(head)
      {
         head->prev = newNode;
         newNode->next = head;
         newNode->prev = NULL;

         head = newNode;
      }
      else
      {
          head = newNode;
          tail = newNode;

          newNode->next = NULL;
          newNode->prev = NULL;
      }
   }
}

A new node is created to hold the value. If there is already a queue, the new node is added in front of the existing head, and head is modified to point to the new node. The new node doesn’t have anything behind it in the queue, so it’s previous pointer is NULL. Head and tail are arbitrary designations. They are just the ends of the line.

If there is not already a queue, the new node is both the first and last item in the queue.

Dequeuing is simple, too. The tail pointer is changed to point to the node prior to the current tail. The value in the tail’s next node is copied for returning, and the tail’s next node is delete. Finally, the tail’s next pointer is set to NULL.

This is if the queue has any nodes in it.

There are often methods to get the number of items in a queue, and to walk the list.

Since new and delete are feature that are missing from the Arduino, due to it’s limited amount of memory, a typical queue class really isn’t possible.

The alternative is to allow for a fixed length list of values, stored in an array. There is no need to keep track of both head and tail, since one will always be 0.

int Q[10]; // Limit of 10 things in line
int tail = 0; // Nothing currently in line
// Add to line
if(tail < 10)
{
   Q[tail] = newVal;
   tail++;
}
// Remove from queue
if(tail > 0)
{
   theVal = Q[0];
   for(int i=0; i<tail; i++)
   {
      Q[i] = Q[i+1];
   }
   tail--;
}

Thanks Paul, Whoops,, I have obviously bitten off more than I can chew here, despite my wonderful 3 stars, I am still a newbie, and nowhere near on that page yet :).

I was so chuffed when I synced the overlay to the vga, but thats more in my realm of experience. My software is very crude , and I am moving one step at a time through the Arduino experience. and having progressed past the flashing LED, your post has bought me crashing back to earth ! ;D

Perhaps I will stick 8 shift registers in parallel and clock it through :)

Boffin,

if you just need a static ring queue buffer and not somehing dynamic like Paul suggest, you can use a simple array. I assume you store long values as payload, otherwise replace long with whatever datatype you like. The buffer has 8 slots.

const int ringsize = 8;
int head = 0;
int tail = 0;
long ring[ringsize];

// Put something into the buffer. Returns 0 when the buffer was full,
// 1 when the stuff was put sucessfully into the buffer
int enqueue (long val) {
   int newtail = (tail + 1) % ringsize;
   if (newtail == head) {
      // Buffer is full, do nothing
      return 0;
   }
   else {
      ring[tail] = val;
      tail = newtail;
      return 1;
   }
}

// Return number of elements in the queue.
int queuelevel () {
    return tail - head + (head > tail ? ringsize : 0);
}

// Get something from the queue. 0 will be returned if the queue
// is empty
long dequeue () {
   if (head == tail) {
      return 0;
   }
   else {
      long val = ring[head];
      head  = (head + 1) % ringsize;
      return val;
   }
}

Perhaps that helps.

Korman

Thanks Korman, and Paul,

I will see if I can get that going, I only have values of 1 - 9 as the data, so I wont need long.

I will make up a small sample sketch and see if I can run it..

If I set my data ( 1-9 ) as val, then run that sketch, I get out the first value of val? or must I call enqueue and dequeue? I am not sure of the usage...

You call enqueue to add a value to the queue (“Hey, you, get in line”).

You call dequeue to get a value from the queue ('Next!").

OK great, thanks guys, I will give it a go

And you do:

while (queuelevel()) {
    doSomethingWithYourValueLikeFeedingItToYourDog (dequeue());
}

to process all your accumulated data.

And by the way, I fixed a small bug that loses the first entry in my code above. tail points to the next free slot where to add new data, head points to the oldest data in the queue, the next to be taken out. My original code didn't do that properly, I used newtail where tail should have been used in enqueue. So much for publishing untested code - you get what you pay for.

Korman

Once used a really simple queue implemented in a string object. Not a performance killer but easy to understand how a queue works. besides relative poor performance its biggest drawback is that the deque() action is not atomic (in source) - so kids don't do this at home:) Code looked like:

String Queue = "123456789";  

void setup()
{
  Serial.begin(19200);
}

void loop()
{
  char c = Queue[0];           // copy the first element
  Queue = Queue.substring(1);  // remove the first element

  Serial.println(Queue);       // whats in it 

  Queue.concat(c);             // add a char to the queue
  delay(1000);                 // not so fast
}

The other problem might be that I want to add this code to the micro that does the lookup and refresh of the video shift registers every 20 uS, so I think I should perhaps do this with an interrupt routine so that it doesn't run every loop? just when a new command comes in.........?

Or I can do it on the other chip that does the SD card reader and DA with the waveHC library, but I did get the idea that it was also pushed for time ???

I also have just one number coming in every minute , or ten minutes, or perhaps two different ones in 2 seconds,

It must play that first numbers audio, and wait for the next, or take from the queue if something came in while it was playing..............

Did you test this: http://wiring.uniandes.edu.co/source/trunk/wiring/lib/FIFO/FIFO.h?revision=770&view=markup ?

Example:

#include <FIFO.h>

void setup() {
  Serial.begin(9600);
  
  FIFO<int,10> fifo; //store 10 ints
  
  fifo.enqueue(1);
  fifo.enqueue(2);
  fifo.enqueue(3);
  fifo.enqueue(4);
  fifo.enqueue(5);
  
  Serial.print("Peek: ");
  Serial.println(fifo.peek());
  
  for (int i=0; i<fifo.count(); i++) {
    Serial.print("Dequeue ");
    Serial.println(fifo.dequeue());
  }
}

void loop() {
  //nothing
}

That also looks very interesting,

So if I get a signal from my decoder,say “int door” which I convert from bcd to dec, how do I imput it to the routine

fifo.enqueue = door; ?

and to get the first queued number out

resultant = fifo.dequeue; ???

Thanks robtillaart, similar question, how do I get intermittent single bytes into this as opposed to the predetermined string?

fifo.enqueue = door; ? [...] resultant = fifo.dequeue; ???

Almost.

Try:

fifo.enqueue(door);

resultant = fifo.dequeue();

Thanks AlphaBeta, I saved the library as FIFO.h and tried to compile your example, but it said that FIFO is undeclared in this scope, I tried upper and lower case, and defining as int, but it wont compile ???

My first question is: Where did you save it?

I saved it in the same library folder that I have for all the arduino libraries arduino21/ libraries/FIFO/FIFO.h

Theres no ccp file though ??

And does it matter that its upper case for the name and only one instance in the sketch?

I tried various combinations of declaring fifo, but it keeps telling me it expects a primary expression before int in line 7 ?

And it looks like this is all in setup loop, is that right?

For me it compiles.

#include <FIFO.h>

void setup() {
  Serial.begin(9600);

  FIFO<int,10> fifo; //store 10 ints

  fifo.enqueue(1);
  fifo.enqueue(2);
  fifo.enqueue(3);
  fifo.enqueue(4);
  fifo.enqueue(5);

  Serial.print("Peek: ");
  Serial.println(fifo.peek());

  for (int i=0; i<fifo.count(); i++) {
    Serial.print("Dequeue ");
    Serial.println(fifo.dequeue());
  }
}

void loop() {
  //nothing
}

I have tried with the library in the same dir as you, and in the documents/arduino/libraries.
Both works fine.

?