Creating a circular queue

[nickc86]

I am interested in creating a circular queue. I am trying to think about how to do it.

The queue will hold an array of 20 8 byte items.

So, I assume starting at the beginning would be best --- So I will work out what I am thinking here.

Code Select Expand


.data
packet byte packetsize "12345678" ;my first packet
packetsize equ 8  ;size of each array slot
numpackets equ 20 ;number of slots in array
queuesize equ numpackets*packetsize ;size of queue
queue byte queuesize dup (?) ;the queue
dword qbeg ? ;ptr to beg of queue
dword qend ? ;ptr to end  of queue
dword cur ? ;ptr to the current 8 bytes in queue

.code
mov eax, queuesize ;get the size of the queue in a register
mov qbeg, OFFSET queue ;store the beg of the queue
mov qend, OFFSET queue[eax] ;store the end of the queue
mov cur, OFFSET queue ;point cur slot to the beg of queue

;so now I want to move something there
mov ecx, packetsize ;set the number of times to repeat
mov esi, OFFSET packet ;source location
mov edi, cur ;destination location
cld ;clear direction flag
rep movsb ;repeat the move
add cur, 8 ;update current pointer to next location



Am I right so far?

[jj2007]

Looks promising :t

Now complete the program and test it.

[nickc86]

Ok. so I have messed with this a bit and I am getting stuck on when to update the pointer, when the queue is full and when the queue is empty.

Here is the logic that I am using (first in first out queue):

Code Select Expand


.data
packetsize equ 8  ;size of each array slot
numpackets equ 5 ;number of slots in array
packet byte packetsize "12345678" ;my first packet -- doesn't really matter what's in it - Just 8 bytes of data for show
queuesize equ numpackets*packetsize ;size of queue
queue byte queuesize dup (?) ;the queue (currently 40 bytes)
dword qPtr queue ;ptr to beg of queue
dword qInPtr queue ;ptr to slot to store data
dword qOutPtr queue ;ptr slot to get data

So, the first iteration, everything points to the beginning of the queue. Great. I want to put my packet in to the queue....

Code Select Expand


;put something in queue
mov edi, OFFSET qInPtr
mov esi, OFFSET packet
mov ecx, packetsize
cld
rep movsb
add qInPtr, packetsize

Now, I will add something else by completing the same above code. I should now have a queue that has 16 bytes used. My qInPtr is pointing to the 17th byte and the qOutPtr is pointing to the 1st byte. Now I want to get something from the queue

Code Select Expand


mov esi, OFFSET qInPtr
mov edi, OFFSET packet
mov ecx, packetsize
cld
rep movsb
add qOutPtr, packetsize

So, now I have my current piece of data in my packet data location. I've moved my qOutPtr to my next piece of information in my queue. Now I add 3 more pieces of data. This is where I am having trouble with the code...
I am at the end of my queue, but the "first slot" is technically empty. So, after I update the inPtr, should I do some type of compare (psuedocode)?:
if (qInPtr - queuesize == qPtr)
then qInPtr = qPtr

Also, I am thinking that if the qInPtr == qOutPtr before I add anything, then it is empty in the beginning. But, how do I know if it's full? The qInPtr will point to qOutPtr when it is full after adding data and not removing anything.

[mineiro]

I'm thinking on a snake trying to eat it's own tail. Each time head go one step foward, tail go one step foward.
You need compare bounds.
If ptr reached end of buffer, so ptr == start of buffer

;pseudocode
mov eax,offset queue
add eax,sizeofqueue
mov ebx,ptr Inptr
if ebx == eax              ;if ebx > eax
mov Inptr,offset queue

[FORTRANS]

Hi,

Also, I am thinking that if the qInPtr == qOutPtr before I add anything, then it is empty in the beginning. But, how do I know if it's full? The qInPtr will point to qOutPtr when it is full after adding data and not removing anything.

   Probably the easiest thing to do there is keep a count of the data.
Zero the count at the beginning.  When you add data to the queue
then increment the counter.  When you remove data, decrement the
counter.  If the counter is zero, then don't remove data (none there).
If the counter equals the queue size then the queue is full, so don't
add more data.  It helps to debug things as well.

HTH,

Steve N.

[newrobert]

this seems like line queue,not circle queue.

[avcaballero]

I did it some years ago.

[hutch--]

A circular buffer is nothing more than a linear buffer with a loopback at the end. Create an array of the member count you require and with a member length that is both long enough for the longest entry AND an interval of 4, write the loopback code, maintain a current member pointer and let 'er rip !

[newrobert]

commonly, one pointer maybe not enough, need two pointers for header and tailer;

[avcaballero]

A queue or a stack are based in the same principle (FIFO or LIFO). They are composed by boxes that have data and a pointer that points to the next box, when we reach to the last box, its pointer points to the header. And that's all.

They can be simple or double. The first one have only a pointer to the next box, the second one have two pointers: one to the next box and other to the previous. Each one have their advantages and disadvantages. The first one saves space but it is a bit hard navigate backward, and the second one wastes more space but is simpler.

[nickc86]

I know how a queue should work. I'm just trying to figure out how I'll know if it's empty or full. I'd like to do this without keeping track of the number of items in the queue as well. I get the logic of how the queue works, but wrapping my head around empty and full is where I'm hung up.

[FORTRANS]

Hi,

I'm just trying to figure out how I'll know if it's empty or full. I'd like to do this without keeping track of the number of items in the queue as well.

   Then you will have to make a special case of some sort.

   Make an empty flag that is set when reading from the queue and
the pointers are the same is one option.  Writing to the queue resets
the flag.  But then you have to test the flag before reading.

   Make the buffer for the queue one larger than the queue.  Then if
the pointers match, the queue is empty.  You just cannot make the
pointers equal any other way.

   Just two quick ideas.  You can come up with something different
that you like better.  Or try one of those two if they sound good to
you.  My tastes go to keeping a count as in my earlier reply.

Regards,

Steve N.

[avcaballero]

Hello. Are you interested yet on it? I have started an example of siple lineal queue from the scratch in masm32. I am in the first stage, now you can only use the "new" button and a message will appear with the surname taken from the queue to assure that it has been inserted correctly.

For now, each time you click on "new", it is allocated a space from memory to has the block of the queue with the data you have entered onto the edit blocks.

I will make it anyway, but if you are not interested, I'll take it more calmly. This is the communion month and today I have one, you know, not much free time.

Regards

[avcaballero]

Hello. This is my Simply lineal linked queue example with full source code in masm32.

* Simply/Double
* Lineal/Circular
* Queue/Stack

Now you can write name/surname/age and press the "add" button for insert it in the list. It is inserted in the position where you are positioned. At the moment it is not possible to do it at the tail, but it is easy to implement it.

You can navigate with the first four buttons:
* |<. Move to the header
* >|. MOve to the tail
* <. Move to the previous register
* >. Move to the next register

There is a box that indicates the register where you are positioned and the number of records.

The button "Show" dumps the entire list to the "Lista.txt" file. Warning, each time you use it, the file is truncated with the new data.

WARNING: The "Del" button is not working for now, don't hit on it. I will fix it shortly.

Despite it is lineal, it is easy to make the navigation buttons working as it were circular.

If you like it, would be welcome:
  - Feedbak
  - Credit
 
If you don't like it: delete it.

The rest of list types are much the same.
Boran

Regards.

[newrobert]

good jobl