Due: Thursday, September 21, at 11:59pm
Update: Due to a temporary outage on mantis, this assignment will instead be due at 11:59pm instead of 10:00pm.

Starter code: queues-package.tar
Upload solutions via Moodle as: handin.tar (see below)

This assignment is an adaptation of this lab developed for the Carnegie Mellon University’s 15-213 (Introduction to Computer Systems) course, which is the course for which our textbook was written. These labs are great, but they come with a lot of infrastructure, which will take you a little while to get used to. We’ll talk about this in detail in class.

Update: There is an extension to Lab 2 that may help you with debugging this assignment. Try it out!

Goals

In this assignment, you will implement a double-ended queue supporting both last-in-first-out (LIFO) and first-in-first-out (FIFO) queueing operations. The underlying data structure is a singly linked list, enhanced to make some of the operations more efficient.

When it comes to data structure sophistication, this queue is completely suitable for study during the first half of CS 201. We’re not aiming at algorithmically complicated structures here. Rather, this assignment is intended to give you practice in the style of C programming that we’ll be doing all term: pointer-based, memory-aware, and robust with respect to system errors. Specifically, this assignment will help you practice:

• explicit memory management with malloc and free
• creating and manipulating pointer-based data structures
• working with strings
• enhancing the performance of key operations by storing redundant information in data structures
• handling system errors appropriately when they occur

Rubric

This assignment is worth a total of 18 points. They are allocated as follows:

1 - author name (and collaborators) in a comment at the top of each C source file
2 - code quality
15 - program correctness and efficiency

Your program will be evaluated for correctness and efficiency using fifteen “traces” described below. You will get credit (between 0.0 and 2.0 points, depending on the trace, for a total of 15 points) for each one that executes correctly. The provided driver.py runs qtest on the traces and computes the score. This is the same program that will be used to compute the automated part of your grade. You can invoke the driver directly with the command:

./driver.py

or with the command:

make test

Getting started

The starter code in queues-package.tar contains many files. Almost all of these files are part of a testing infrastructure that will give you detailed feedback as you write your code. You should feel free to look at all of these files if you’re interested in how a big university CS department thinks about automated grading. However, to complete the assignment, you should only change the contents of queue.h and queue.c.

The queue data structure that we will work with looks like this:

/* Linked list element */
typedef struct list_ele {
    char *value;
    struct list_ele *next;
} list_ele_t;

/* Queue structure */
typedef struct {
    list_ele_t *head;  /* Linked list of elements */
} queue_t;

These are combined to implement a queue of strings, as illustrated in the diagram below. The top-level representation of a queue is a structure of type queue_t. In the starter code, this structure contains only a single field head, but you will want to add other fields. The queue contents are represented as a singly linked list, with each element represented by a structure of type list_ele_t, having fields value and next, storing a pointer to a string and a pointer to the next list element, respectively. The final list element has its next pointer set to NULL. you may add other fields to the structure list_ele, although you need not do so.

Each list element has a value field, pointing to a C string (i.e., a null-terminated array of char) and a next field pointing to the next list element. For this diagram and this assignment, we encode characters using ASCII, which are shown in the diagram as 2-digit hexadecimal integers. Observe how the two instances of the string "cab" are represented by separate arrays—each list element must have a separate copy of its string.

In our C code, a queue is a pointer of type queue_t *. We distinguish two special cases: a NULL queue is one for which the pointer has value NULL. An empty queue is one pointing to a valid struture, but the head field has value NULL. Your code will need to deal properly with both of these caes, as well as queues containing one or more elements.

Your job

Your task is to modify the code in queue.h and queue.c to fully implement the following functions. I recommend working on them in the order they’re listed here, testing after you complete each one.

• q_new: Create a new, empty queue.

• q_free: Free all storage used by a queue.

• q_insert_head: Attempt to insert a new element at the head of the queue (LIFO discipline).

• q_insert_tail: Attempt to insert a new element at the tail of the queue (FIFO discipline).

• q_remove_head: Attempt to remove the element at the head of the queue.

• q_size: Compute the number of elements in the queue.

• q_reverse: Reorder the list so that the queue elements are reversed in order. This function should not allocate or free any list elements (either directly for via calls to other functions that allocate or free elements). Instead, it should rearrange the existing elements.

More details can be found in the comments in queue.h and queue.c, including how to handle invalid operations (e.g., removing from an empty or NULL queue), and what side effects and return values the functions should have.

For functions that provide strings as arguments, you must create and store a copy of the string by calling malloc to allocate space (remember to include space for the null character) and then copying from the source to the newly allocated space. You cannot assume any fixed upper bound on the length of a string—you must allocate space for each string based in its length.

When it comes time to free a list element, you must also free the space used by the string. The general rule to follow is that every call to malloc needs to be matched by a call to free elsewhere in your code. I expect q_new, q_insert_head, and q_insert_tail to contain calls to malloc, and q_free and q_remove_head to contain calls to free.

Two of the functions, q_insert_tail and q_size, will require some effort on your part to meet the required performance standards. Naive implementations would require O(n) steps for a queue with n elements. We require that your implmentations operate in O(1) time, i.e., that the operation will require only a fixed number of steps, regardless of the number of items in the queue. You can do this by including other fields in the queue_t data structure and managing these values properly as list elements are inserted, removed, and reversed.

Your program will be tested on queues with over 1,000,000 elements. You will find that you cannot operate on such long lists using recursive functions, as that would require too much stack space. Instead, you’ll need to use a loop to traverse the elements in a list.

Additional resources

Update: There is an extension to Lab 2 that may help you with debugging this assignment. Try it out!

Did any of the terminology above not make sense? Here are a few links that may help.

Structs:

• C for Java programmers - Chapter 7, Structured Types (it’s only two pages)
• Pointers and Structs

Memory management:

• C for Java programmers - Chapter 8, Memory Management (longer but very useful)
• Dynamic Memory Allocation
• C Strings

If you find any other really helpful resources, please let me know and I’ll add them!

Testing

It will be very useful to test your code incrementally as you implement each function. The traces directory contains 14 trace files, with names of the form trace-k-cat.txt, where k is the trace number and cat specifies the category of properties being tested. Each trace consists of a sequence of commands to interact with the queue. They test different aspects of the correctness, robustness, and performance of your program. You can use these, your own trace files, and direct interactions with the provided qtest program to test and debug your implementation. Read the comment at the top of each trace file to see a description of what it tests.

You can compile your code using the command:

make

If there are no errors, the compiler will generate an executable program qtest, providing a command interface with which you can create, modify, and examine queues. Documentation on the available commands can be found by starting this program and running the help command:

./qtest
cmd>help

The file traces/trace-eg.cmd illustrates an example command sequence. You can see the effect of these commands by operating qtest in batch mode on a trace file:

./qtest -f traces/trace-eg.cmd

With the starter code, you will see that many of these operations are not implemented properly.

Segmentation faults

A hallmark of C programming is the ominous segmentation fault. This error crashes the program immediately, and provides no information as to the cause.

Fortunately, gdb (the GNU debugger) can help us discover the line of code where the fault occurs and even which pointer dereference is responsible (“segfaults” are usually the result of dereferencing a null or invalid pointer). Our CS 208 resources page has a good tutorial video, a cheat sheet, and some other links to help you get started.

You’ll use gdb a lot later in the term. For now, however, here’s something you can do to track down segfaults:

• cd queues-package

• make qtest

• Suppose make test is telling you that you have a segmentation fault for "trace-10-malloc". In that case, you can run the specific test without using make like so:

  ./qtest -v 1 -f traces/trace-10-malloc.cmd
  

This is exactly what the driver.py program executes for trace #10 when you do make test, but now you’re doing it manually. You should see another report of a segmentation fault.

• Launch the for-now-mysterious program gdb, ready to help you debug the executable program qtest (which itself includes your queue.c file):

  gdb qtest
  

• After a bunch of copyright text, you will see the prompt (gdb). Here, you’re going to run your program inside the debugger, using the command run and specifying the command-line arguments you want to pass to qtest:

  (gdb) run -v 1 -f traces/trace-10-malloc.cmd
  

• Maybe now, you’ll see a result like this:

  (gdb) run -v 1 -f traces/trace-10-malloc.cmd
  Starting program: /Accounts/tamert/cs208/queues-package/qtest -v 1 -f traces/trace-10-malloc.cmd
  # Test of malloc failure on new
  
  Program received signal SIGSEGV, Segmentation fault.
  0x00005555555598b7 in q_new () at queue.c:29
  29	    q->head = NULL;
  (gdb)
  

There it is, the specific line number (29, in this case) that is causing trouble.

• You can use gdb to inspect the values of variables at this point in the code. In this specific example, the only local variable is q. You can see its value like so:

  (gdb) print q
  

• Once you’ve found the problematic line of code, how should you fix it? That’s up to you!

Handing it in

Whenever you compile your code by running make, it will produce a handin.tar file containing your queue.c and queue.h. To submit this assignment, you should upload your handin.tar to the Queues in C assignment on Moodle.