ECEN 390 - Laser Tag Project

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
==== Using an Array to Implement a Circular Buffer ====

Let's look at a a few simple examples of how an array can be used to implement a circular buffer, using the ''queue_t'' data structure that I provide below. First, to keep things simple, let's make our queue big enough to hold 3 elements (3 elements of type double, in our case). Using the code that I provided below, you would say the following:
<code C>
#include "queue.h"
queue_t myQueue;
queue_init(&myQueue, 4);
</code>

One thing to note in the code above is that we pass the address of ''myQueue'' to ''queue_init''. We do this for the sake of efficiency in 'C', and this is because this is what the ''queue_init()'' code expects. Once we execute the code above, a pictorial view of ''myQueue'' would look something like right after ''queue_init()'' has been called) is shown below. Note that enough memory for 5 doubles has been allocated. But, as I said before, this queue can only hold 4 doubles.

{{ ::queueinit.jpg?300 |}}

This queue, is by definition, empty because ''indexIn'' and ''indexOut'' are the same value (0, in this case). Now, let's look at what the queue looks like after we have "pushed" 4 values (23.4, 3,14, 72.1, 89.4).

{{ ::queuepushed4.jpg?300 |}}

Even though there appears to be one empty location in the queue (location 4), the queue is now considered to be full. Why is this so? Because ''indexIn'' always points to the empty location where the next "push" will store data. If we were to do another "push" when the queue is in its current state, ''indexIn'' would be wrapped around so that is back to 0, and because the queue is considered to be empty anytime ''indexIn'' and ''indexOut'' are the same value, the queue would become empty. Thus, whenever we "push" a new value onto the queue, the queue needs to do a simple test: if ''indexIn'' were incremented, would it be equal to ''indexOut''? If so, the queue is currently full and it is not possible to "push" another value onto the queue. 

Now, let's perform two "pops" on our queue, removing two elements. After two "pops", our queue would be shown pictorially below:

{{ ::queuetwopops.jpg?300 |}}

As shown, ''indexOut'' has moved up two locations. Now, let's say that we want to "push" two new values onto our queue. When "pushing" a new value, the queue would need to check if it is full. It is not because, if indexIn is incremented and wraps around to location 0, it will not be equal to ''indexOut'' because ''indexOut'' now has the value of 2.

Now, let's look at the queue after "pushing" two new values (51.5 and 49.2).

{{ ::queuetwopushes.jpg?300 |}}

''indexIn'' now has the value of 1 and you can see that two values have been "pushed" onto the queue. Is our queue full? It must be, because the queue can only hold 4 elements. Our "empty" location is location 1 (currently showing 3.14 but remember that value was previously "popped" off). Let's try the "full test". If we were to increment ''indexIn'' it would have the same value as ''indexOut'', so the queue is currently full.

Carefully study the example above so you can see how the circular buffer works with an array, and also so you can see why there is always an empty location in the queue when implemented this way.

----
==== Why the Extra Location? ====

Why the extra location? In the queue.c code that I provided you will note that I allocate one additional memory location. My presumption is that you will implement the queue as a circular buffer that uses an empty location to deal with the empty/full problem. Please see this web page on [[http://en.wikipedia.org/wiki/Circular_buffer|circular buffers]] as it explains this issue. You are not required to implement the queue using a circular buffer. However, it is usually about the easiest thing to debug and get running.

----
ECEN 390 - Laser Tag Project

User Tools

Site Tools

Page Tools
