Lab 0: Welcome to C¹

• Assigned: Friday, April 1
• Check-in Post: Before 9pm Wednesday, April 6 (check-in forum)
• Due: 9pm Monday, April 11
• Collaboration: This is an individual assignment
• Handout: starter project
• Submit: Upload queue.c to Lab 0
• Reference:
  • Bits & Bytes and 3/30 readings
  • C Memory Management and 4/1 readings
  • C library string functions
  • Essential C
  • C Tutor Example
  • Linked Lists – The Basics
  • What’s a Linked List, Anyway?

Introduction

This lab will give you practice in the style of C programming you will need to be able to do proficiently, especially for the later assignments in the class. Specific skills include

• Explicit memory management, as required in C
• Creating and manipulating pointer-based data structures
• Working with strings
• Enhancing the performance of key operations by storing redundant information in data structures
• Implementing robust code that operates correctly with invalid arguments, including NULL pointers

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

This is an individual project. You can do this assignment on any machine you choose. The testing for your code will be done on the CS department mantis server. Before you begin, please take the time to review the course policy on academic honesty and collaboration at http://cs.carleton.edu/faculty/awb/cs208/s22\#academic-honesty.

Logistics

wget http://cs.carleton.edu/faculty/awb/cs208/s22/handouts/lab0-handout.tar

tar xvf lab0-handout.tar

Read this writeup all the way through before diving straight into the code!

As the Academic Honesty Policy states, you should not search the web or ask others for solutions to the lab. That means that search queries such as “reversing a linked-list in C” are off limits. Searching for basic C functionality is encouraged (e.g., “allocating a struct in C”).

Overview

The starter code contains many files—don’t be intimated! Almost all of them are for simulating and testing your queue implementation. The only ones you have to care about are queue.c and queue.h

The file queue.h contains declarations of the following structures (you should not need to modify these):

/* Linked list element */
typedef struct node {
    char *value;
    struct node *next;
} Node;

/* Queue structure */
typedef struct {
    Node *head; /* Linked list of elements */
    Node *tail;
    long size;
} Queue;

These are combined to implement a queue of strings, as illustrated below. The top-level representation of a queue is a structure of type Queue. 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 Node, 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.

A string is represented in C as an array of values of type char. On most machines, data type char is represented as a single byte. To store a string of length n, the array has n + 1 elements, with the first n storing the codes (typically ASCII² format) for the characters and the final one being set to 0x00. The value field of the list element is a pointer to the array of characters. The figure indicates the representation of the list ["cab", "bead", "cab"], with characters a-e represented in hexadecimal as ASCII codes 61-65. Observe how the two instances of the string "cab" are represented by separate arrays—each list element should have a separate copy of its string.

In our C code, a queue is a pointer of type Queue *. 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 structure, but the head field has value NULL. Your code will need to deal properly with both of these cases, as well as queues containing one or more elements.

Implementation

Your task is to modify the code in queue.c to fully implement the following functions. We recommend working on them in the order we’ve listed them 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 behavior).
• q_remove_head: Attempt to remove the element at the head of the queue.
• q_insert_tail: Attempt to insert a new element at the tail of the queue (FIFO behavior).
• 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 or via calls to other functions that allocate or free list elements.) Instead, it should rearrange the existing elements.

More details can be found in the comments in these two files, 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 terminating 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 on 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.

You will also need to use malloc to allocate space for new list nodes as they are inserted. Why do you need to malloc space for nodes and strings, instead of just declaring nodes as local variables and using the char* that’s passed into the function? Because when pointers go stale or get reused, we don’t want that to interfere with our queue. Take a look at the C Tutor example in the list of references to see this in action. There are three different versions of a q_add function: q_add doesn’t use malloc at all, q_add2 uses malloc for the list node, and q_add3 uses malloc for both the list node and the string. This code is also an example of how to use the C library string functions to copy a string.

We require that your implementations of q_insert_tail and q_size operate in time O(1), i.e., that the operation will require only a fixed number of steps, regardless of the queue size. Make sure to use the tail and size fields of the queue to accomplish this.

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, since that would require too much stack space. Instead, you need to use a loop to traverse the elements in a list.

Testing

It will 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, similar to those shown above. 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 qtest to test and debug your program. 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:

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

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

Segmentation Fault

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 (seg faults are usually the result of dereferencing a null or invalid pointer). The course webpage has a gdb tutorial and cheat sheet. Follow this link to see demo of getting started with the lab and using gdb to diagnose a seg fault in the starter code. Note how the message in gdb

Program received signal SIGSEGV, Segmentation fault.
0x0000555555559370 in q_insert_head (q=0x0, s=0x555555761b60 "bear") at queue.c:56
56          newh->next = q->head;

indicates the line where the seg fault occurred (line 56 of queue.c). You can then use gdb to print out variable values at that point in the code. Doing so reveals that the pointer q is 0 (NULL).

Grading

./driver.py

make test

Definitely leave q_reverse for last. It’s really more of an extra-credit problem than a core part of the lab. You can earn 59/60 without attempting it.

While the autograder will assign 0 points for a test that doesn’t pass, partial credit can be earned for evidence of a good-faith effort. Comments explaining your approach can help earn partial credit.