You will need to implement a queue data structure for your laser-tag system. You should remember the basics of the queue data structure from some of your CS classes. This web-page provides a quick review of queues. This web page explains the “circular buffer” implementation strategy for queues. I suggest that implement the queue as a circular buffer though it is not required. If you do not use the circular-buffer strategy, then you won't use the queue.c code that I provided below.

The queue that you must implement will be just a little different than a typical queue. It must have the following properties:

1. Your queue must allow you to keep adding (pushing) new elements even after it is full. If the queue is full when you add an additional element, it must remove the oldest element and add the new one, making sure to keep the correct order of things in the queue. For example, let's say that your queue can contain 200 elements. If you add 400 elements to the queue, the queue should contain the last 200 elements that were added, in the same order that they were added. In other words, the queue will contain elements 201 through 400. When you remove an element from the queue, the elements should be removed in order, e.g., element 201, followed by element 202, etc.
2. You must be able to read the contents in the queue without removing them or disturbing them. In other words, your queue must provide a function that can read elements in the queue by index. For example, let's assume that the name of the function is queue_readElementAt(&q, index) and that it takes two arguments (the address of the queue, and the index of the element to read). If index = 0, this will read the oldest element in the queue. Larger values of index will successively read data that arrived later. You must print out an error message if the index-value would access elements beyond what is currently stored in the queue.

1. Your queue code must implement all of the functions listed in the queue.h file shown below. For those of you unfamiliar with how to allocate memory in 'C', I provided the queue_init() and queue_garbageCollect() functions below. Your queue_runTest() code must completely test all queue functions. The TAs will be looking for this.
2. Write your own queue code. Don't download code from the internet, it tends to have bugs in it anyway. Also, because I have added functions that are not typically included in a queue data structure, things will just go faster and easier if you write the code yourselves.
3. Your queue_runTest() must do at least the following:
   1. test all of the functions listed in queue.h.
   2. perform 5 overwritePush(), followed by 3 pop(), followed by 5 overwritePush(), followed by queue_print(). Then, perform readElementAt() for each value remaining in the queue to verify that the contents are correct. TAs will verify that your test code performs at least these functions.
4. You must follow the same coding standards as was done for ECEN 330.
5. You are not allowed to pass off your code if it has more than 5 coding-standard infractions.

1. Your code must follow the coding standard. The TAs will review your source code and not allow you to pass off if you have more than 5 infractions of the source-code standard.
2. Staple the source-code pass-off sheet to the front of your source code. Make sure to fill in the name, lab-number, and submission date.
3. Ensure that the queue_print() function prints out the contents of the queue in order, from oldest value to newest value.
4. Ensure that the queue_runTest() function performs the operations listed in the requirements section above.

1. Quickly review the source code before passing off. Do not pass off if the code has more than 5 coding-standard infractions. Students whose code has many coding-standard infractions must correct their code before passing off the milestone.
2. Ensure that the queue_print() function prints out the contents of the queue in order, from oldest value to newest value.
3. Ensure that the queue_runTest() function performs the operations listed in the requirements section above.

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 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.

The circular-buffer approach uses an array to store the data contained within the queue. However, we want to be able to set the size of the array when the queue is initialized. We do that by allocating a block of memory of the desired size during initialization and then using that block as our array. While a complete treatment of 'C' pointers is beyond this simple explanation, the code shown in queue_init() is pretty simple.

queue_data_t * data

The code above declares a variable named data that should ultimately “point” to a chunk of memory that contains something of type queue_data_t (typedef double queue_data_t). However, at this point, all we have done is to tell the compiler that, when we refer to the pointer data, we will treat what it points to as a queue_data_t. This allows the compiler to ensure that we are consistent when we use this pointer later in our code. By way of reminder, double refers to a number that is double-precision floating point.

It is important to note that when the pointer data is declared, it actually points to nothing. At run-time, we need to allocate memory that data will “point” to. This is the job of malloc() (malloc() stands for “memory-allocation”, if you like). Here is an example where the declaration of the pointer and allocation of memory are done in one line of code:

queue_data_t * data = (queue_data_t *) malloc(4 * sizeof(queue_data_t));

In the simple example shown above, I have told malloc() that I want a chunk of memory that is big enough to hold 4 items, where each item is the size of a queue_data_t (again, queue_data_t is a double). sizeof() is a compiler primitive that will return the number of bytes that a particular data-type requires. If your curious about how many bytes are occupied by a variable of size double, you can write a simple program and find out:

#include <stdio.h>
void main() {
  printf("A double requires %d bytes.\n\r", sizeof(double));
}

If you run this code on the ECEN 330 board, it will print out:

“A double requires 8 bytes.”

In any case, once we have executed the malloc() code above, the data pointer now points to a block of memory that is 32 bytes in size (4 doubles). In 'C', a pointer and a 1-dimensional array are essentially the same thing. With memory properly allocated, I can now treat the data pointer exactly as an array. For example, I could initialize my data array using the code below:

for (int16_t i=0; i<4; i++) {
  data[i] = 0.0;
}

Or, I could print out the contents of my data array using the code below:

#include <stdio.h>
for (int16_t i=0; i<4; i++) {
  printf("data[%d]:%le\n\r", i, data[i]);
}

Let's look at a a few simple examples of how the 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:

#include "queue.h"
queue_t myQueue;
queue_init(&myQueue, 4);

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 because this is because this is what the queue_init() code expects. Once we executed 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.

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).

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:

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 indexOut 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).

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.

1. Make sure you implement queue_overwritePush() correctly. If the queue is full, remove an element and push the new element on the queue. If it is not full, just push the new value.
2. For those of you using the extra “empty space” in the queue to determine full/empty, make sure that you allocate one additional location of memory in queue_init(), e.g., a queue of size 4 must be allocated with 5 locations. This does not apply to students who are using elementCount to determine full/empty.
3. Make sure that your pointers are initialized so that the point at memory provided by malloc().

I have provided the source code for your ”.h” file and part of the code for your ”.c” file. As I said before, you are not required to implement the queue as I have shown here. However, you must implement all of the functions that are contained in the ”.h” file.

queue.h

/*
 * queue.h
 *
 */
 
#ifndef QUEUE_H_
#define QUEUE_H_
 
#include <stdint.h>
#include <stdbool.h>
 
typedef uint32_t queue_index_t;
typedef double queue_data_t;
typedef uint32_t queue_size_t;
 
typedef struct {
  queue_index_t indexIn;
  queue_index_t indexOut;
  queue_size_t size;
  queue_size_t elementCount;
  queue_data_t * data;
} queue_t;
 
// Allocates the memory to you queue (the data* pointer) and initializes all parts of the data structure.
void queue_init(queue_t* q, queue_size_t size);
 
// Returns the size of the queue..
queue_size_t queue_size(queue_t* q);
 
// Returns true if the queue is full.
bool queue_full(queue_t* q);
 
// Returns true if the queue is empty.
bool queue_empty(queue_t* q);
 
// Pushes a new element into the queue. Reports an error if the queue is full.
void queue_push(queue_t* q, queue_data_t value);
 
// Removes the oldest element in the queue.
queue_data_t queue_pop(queue_t* q);
 
// If the queue is full, remove the oldest element and then push the new element.
void queue_overwritePush(queue_t* q, queue_data_t value);
 
// Provides random-access read capability to the queue. 
// Low-valued indexes access older queue elements while higher-value indexes access newer elements
// (according to the order that they were added).
queue_data_t queue_readElementAt(queue_t* q, queue_index_t index);
 
// Returns a count of the elements currently contained in the queue.
queue_size_t queue_elementCount(queue_t* q);
 
// Frees the storage that you malloc'd before.
void queue_garbageCollect(queue_t* q);
 
// Prints the current contents of the queue. Handy for debugging.
// This must print out the contents of the queue in the order of oldest element first to newest element last.
void queue_print(queue_t* q);
 
// Performs a comprehensive test of all queue functions. Returns -1 if the test fails, 0 otherwise.
int16_t queue_runTest();
 
 
#endif /* QUEUE_H_ */

/*
 * queue.c
 *
 */
 
#include <stdio.h>
#include <stdlib.h>
#include "queue.h"
 
// Standard queue implementation that leaves one spot empty so easier to check for full/empty.
void queue_init(queue_t* q, queue_size_t size) {
  q->indexIn = 0;
  q->indexOut = 0;
  q->elementCount = 0;
  q->size = size+1;	// Add one additional location for the empty location.
  q->data = (queue_data_t *) malloc(q->size * sizeof(queue_data_t));
}
 
// Just free the malloc'd storage.
void gueue_garbageCollect(queue_t* q) {
  free(q->data);
}

You must write your own queue_runTest() function to thoroughly test your code. Once you have tested the code using your own queue_runTest() function, I suggest testing your queue implementation with the following test code. It verifies the queue against itself. It creates a chain of smaller queues and a single large queue with the same capacity as all of the small queues. It then simultaneously pushes data through the chain of small queues and the large queue and compares the two.

Notes:

1. If your queue fails this test, it means that your queue_runTest() code is not very thorough. As you fix your queue code, update your queue_runTest() function so that it more fully tests your queue.
2. If your queue fails the more thorough test code that I provide, it is your responsibility to add code to your queue_runTest() code until it detects the bug.

Common Bugs:

#include <stdio.h>
#include <stdlib.h>
#include "queue.h"
 
#define SMALL_QUEUE_SIZE 10
#define SMALL_QUEUE_COUNT 10
static queue_t smallQueue[SMALL_QUEUE_COUNT];
static queue_t largeQueue;
 
// smallQueue[SMALL_QUEUE_COUNT-1] contains newest value, smallQueue[0] contains oldest value.
// Thus smallQueue[0](0) contains oldest value. smallQueue[SMALL_QUEUE_COUNT-1](SMALL_QUEUE_SIZE-1) contains newest value.
// Presumes all queue come initialized full of something (probably zeros).
static double popAndPushFromChainOfSmallQueues(double input) {
  // Grab the oldest value from the oldest small queue before it is "pushed" off.
  double willBePoppedValue = queue_readElementAt(&(smallQueue[0]), 0);
  // Sequentially pop from the next newest queue and push into next oldest queue.
  for (int i=0; i<SMALL_QUEUE_COUNT-1; i++) {
    queue_overwritePush(&(smallQueue[i]), queue_pop(&(smallQueue[i+1])));
  }
  queue_overwritePush(&(smallQueue[SMALL_QUEUE_COUNT-1]), input);
  return willBePoppedValue;
}
 
static bool compareChainOfSmallQueuesWithLargeQueue(uint16_t iterationCount) {
  bool success = true;
  static uint16_t oldIterationCount;
  static bool firstPass = true;
  // Start comparing the oldest element in the chain of small queues, and the large queue
  // and move towards the newest values.
  for (uint16_t smallQIdx=0; smallQIdx<SMALL_QUEUE_COUNT; smallQIdx++) {
    for (uint16_t smallQEltIdx=0; smallQEltIdx<SMALL_QUEUE_SIZE; smallQEltIdx++) {
      double smallQElt = queue_readElementAt(&(smallQueue[smallQIdx]), smallQEltIdx);
      double largeQElt = queue_readElementAt(&largeQueue, (smallQIdx*SMALL_QUEUE_SIZE) + smallQEltIdx);
      if (smallQElt != largeQElt) {
	if (firstPass || (iterationCount != oldIterationCount)) {
	  printf("Iteration:%d\n\r", iterationCount);
	  oldIterationCount = iterationCount;
	  firstPass = false;
	}
	printf("largeQ(%d):%lf", (smallQIdx*SMALL_QUEUE_SIZE) + smallQEltIdx, largeQElt);
	printf(" != ");
	printf("smallQ[%d](%d): %lf\n\r", smallQIdx, smallQEltIdx, smallQElt);
        success = false;
      }
    }
  }
  return success;
}
 
#define TEST_ITERATION_COUNT 105
#define FILLER 5
int queue_runTest() {
  int success = 1;  // Be optimistic.
  // Let's make this a real torture test by testing queues against themselves.
  // Test the queue against an array to make sure there is agreement between the two.
  double testData[SMALL_QUEUE_SIZE + FILLER];
  queue_t q;
  queue_init(&q, SMALL_QUEUE_SIZE);
  // Generate test values and place the values in both the array and the queue.
  for (int i=0; i<SMALL_QUEUE_SIZE + FILLER; i++) {
    double value = (double)rand()/(double)RAND_MAX;
    queue_overwritePush(&q, value);
    testData[i] = value;
  }
  // Everything is initialized, compare the contents of the queue against the array.
  for (int i=0; i<SMALL_QUEUE_SIZE; i++) {
    double qValue = queue_readElementAt(&q, i);
    if (qValue != testData[i+FILLER]) {
      printf("testData[%d]:%lf != queue_readElementAt(&q, %d):%lf\n\r", i, testData[i+FILLER], i+FILLER, qValue);
      success = 0;
    }
  }
  if (!success) {
    printf("Test 1 failed. Array contents not equal to queue contents.\n\r");
  } else {
    printf("Test 1 passed. Array contents match queue contents.\n\r");
  }
  success = 1;  // Remain optimistic.
  // Test 2: test a chain of 5 queues against a single large queue that is the same size as the cumulative 5 queues.
  for (int i=0; i<SMALL_QUEUE_COUNT; i++)
    queue_init(&(smallQueue[i]), SMALL_QUEUE_SIZE);
  for (int i=0; i<SMALL_QUEUE_COUNT; i++) {
    for (int j=0; j<SMALL_QUEUE_SIZE; j++)
      queue_overwritePush(&(smallQueue[i]), 0.0);
  }
  queue_init(&largeQueue, SMALL_QUEUE_SIZE * SMALL_QUEUE_COUNT);
  for (int i=0; i<SMALL_QUEUE_SIZE*SMALL_QUEUE_COUNT; i++)
    queue_overwritePush(&largeQueue, 0.0);
  for (int i=0; i<TEST_ITERATION_COUNT; i++) {
    double newInput = (double)rand()/(double)RAND_MAX;
    popAndPushFromChainOfSmallQueues(newInput);
    queue_overwritePush(&largeQueue, newInput);
    if (!compareChainOfSmallQueuesWithLargeQueue(i)) {  // i is passed to print useful debugging messages.
      success = 0;
    }
  }
 
  if (success)
    printf("Test 2 passed. Small chain of queues behaves identical to single large queue.\n\r");
  else
    printf("Test 2 failed. The content of the chained small queues does not match the contents of the large queue.\n\r");
  return success;
}