C Programming
Due: 11:00pm, Friday September 6, 2024
Max grace days: 0
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
Login to your university Unix account and copy the assignment code to a location under your home directory:
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
andq_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 thequeue_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 tofree
andmalloc
.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
TBD
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