C Programming

Due: 11:00pm, Friday September 6, 2024

Reference

Assignment adapted from CMU Introduction to Computer Systems, Fall 2017

Overview

The purpose of this assignment will give you practice manipulating pointers in C. This assignment should mostly be a review of material from CSC 136. Some of the skills tested are:

Explicit memory management.
Creating and manipulating pointer-based data structures.
Implementing robust code that operates correctly with invalid arguments, including NULL pointers.

Get the Assignment Code

  cp -r /export/home/public/schwesin/cpsc235/assignments/cprogramming-handout.tar LOCATION

where LOCATION is a directory of your choosing.

Then execute the command

tar -xvf cprogramming-handout.tar

Description

This assignment involves implementing a queue, supporting both last-in, first-out (LIFO) and first-in, first-out (FIFO) queueing disciplines. The underlying data structure is a singly-linked list, enhanced to make some of the operations more efficient.

The file queue.h contains declarations of the following structures:

/* Linked list element */
typedef struct ELE {
    int value;
    struct 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, as illustrated in the following figure:

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 that has the fields “value” and “next”, storing a queue value and a pointer to the next list element respectively. You may add other fields to this structure, although you should not need to do so.

In the starter code, a queue is a pointer of type queue_t *; we distinguish two special cases: a NULL queue is one for which the pointer is set to NULL, an empty queue is one pointing to a valid queue_t structure with a head field set to NULL. You need to properly handle both of these cases, as well as queues containing one or more elements.

Your task is to modify the code in queue.h and queue.c to fully implement the following functions:

q_new: create a new, empty queue.
q_free: free all storage usted by a queue.
q_insert_head: attempt to insert a new element at the head of the queue.
q_insert_tail: attempt to insert a new element at the tail of the queue.
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.

The following notes are about how you must implement these functions.

The functions q_insert_tail and q_size need to meet the required performance standards. The implementations must operate in constant time, that is, the time required is independent of the queue size. You can do this by including additional fields in the queue_t data structure and managing these values properly as list elements are inserted, removed, and reversed.
You must implement q_reverse in a way that does not require allocating any additional memory. Instead, your code should modify the pointers in the exisitng list. Implementations that require allocating new list elements will fail the performance tests, due to the way the testing code monitors calls to free and malloc.
Your program will be tested on queues with over 1,000,000 elements. You will find that you cannot traverse such long lists using recursive functions, since that would require too much stack space.

Building and Testing

A makefile is included with the assignment code. The code can be compiled by executing the command

linux> make

from within the assignment directory.

If there are no errors, an executable named qtest will be generated. This program provides a command line interface for creating, modifying, and examining queues. Documentation on the available commands can be found by starting the program and running the help command:

linux> ./qtest
cmd>help

The file traces/trace-eg.cmd has the following example command sequence:

# Demonstration of queue testing framework
# Use help command to see list of commands and options
# Initial queue is NULL.
show
# Create empty queue
new
# Fill it with some values.  First at the head
ih 2
ih 1
ih 3
# Now at the tail
it 5
it 1
# Reverse it
reverse
# See how long it is
size
# Delete queue.  Goes back to a NULL queue.
free
# Exit program
quit

This sequence of commands can be executed by running qtest in batch mode:

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

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 that are tested. Each trace consists of a sequence of commands similar to those shown above.

Turning in the Assignment

To turn in the assignment, execute the submit script by running the command

  ~schwesin/bin/submit cpsc235 project1

from within the cprogramming-handout directory.

Grading Criteria

Your program will be evaluated using the 14 traces described above. You will be given credit (either 7 or 8 points, depending on the trace) for each one that executes correctly. The maximum total score is 100. You can run all the traces and get the respective scores by executing the command:

linux> make test