queue.h

/* * Code for basic C skills diagnostic. * Developed for courses 15-213/18-213/15-513 by R. E. Bryant, 2017 * Extended to store strings, 2018 */

/* * This program implements a queue supporting both FIFO and LIFO * operations. * * It uses a singly-linked list to represent the set of queue elements */

#include

/************** Data structure declarations ****************/

/* Linked list element (You shouldn't need to change this) */ typedef struct ELE { /* Pointer to array holding string. This array needs to be explicitly allocated and freed */ char *value; struct ELE *next; } list_ele_t;

/* Queue structure */ typedef struct { list_ele_t *head; /* Linked list of elements */ /* You will need to add more fields to this structure to efficiently implement q_size and q_insert_tail */ } queue_t;

/************** Operations on queue ************************/

/* Create empty queue. Return NULL if could not allocate space. */ queue_t *q_new();

/* Free ALL storage used by queue. No effect if q is NULL */ void q_free(queue_t *q);

/* Attempt to insert element at head of queue. Return true if successful. Return false if q is NULL or could not allocate space. Argument s points to the string to be stored. The function must explicitly allocate space and copy the string into it. */ bool q_insert_head(queue_t *q, char *s);

/* Attempt to insert element at tail of queue. Return true if successful. Return false if q is NULL or could not allocate space. Argument s points to the string to be stored. The function must explicitly allocate space and copy the string into it. */ bool q_insert_tail(queue_t *q, char *s);

/* Attempt to remove element from head of queue. Return true if successful. Return false if queue is NULL or empty. If sp is non-NULL and an element is removed, copy the removed string to *sp (up to a maximum of bufsize-1 characters, plus a null terminator.) The space used by the list element and the string should be freed. */ bool q_remove_head(queue_t *q, char *sp, size_t bufsize);

/* Return number of elements in queue. Return 0 if q is NULL or empty */ int q_size(queue_t *q);

/* Reverse elements in queue No effect if q is NULL or empty This function should not allocate or free any list elements (e.g., by calling q_insert_head, q_insert_tail, or q_remove_head). It should rearrange the existing ones. */ void q_reverse(queue_t *q);

queue.c

* * Code for basic C skills diagnostic. * Developed for courses 15-213/18-213/15-513 by R. E. Bryant, 2017 * Modified to store strings, 2018 */

/* * This program implements a queue supporting both FIFO and LIFO * operations. * * It uses a singly-linked list to represent the set of queue elements */

#include #include #include

#include "harness.h" #include "queue.h"

/* Create empty queue. Return NULL if could not allocate space. */ queue_t *q_new() { queue_t *q = malloc(sizeof(queue_t)); /* What if malloc returned NULL? */ q->head = NULL; return q; }

/* Free all storage used by queue */ void q_free(queue_t *q) { /* How about freeing the list elements and the strings? */ /* Free queue structure */ free(q); }

/* Attempt to insert element at head of queue. Return true if successful. Return false if q is NULL or could not allocate space. Argument s points to the string to be stored. The function must explicitly allocate space and copy the string into it. */ bool q_insert_head(queue_t *q, char *s) { list_ele_t *newh; /* What should you do if the q is NULL? */ newh = malloc(sizeof(list_ele_t)); /* Don't forget to allocate space for the string and copy it */ /* What if either call to malloc returns NULL? */ newh->next = q->head; q->head = newh; return true; }

/* Attempt to insert element at tail of queue. Return true if successful. Return false if q is NULL or could not allocate space. Argument s points to the string to be stored. The function must explicitly allocate space and copy the string into it. */ bool q_insert_tail(queue_t *q, char *s) { /* You need to write the complete code for this function */ /* Remember: It should operate in O(1) time */ return false; }

/* Attempt to remove element from head of queue. Return true if successful. Return false if queue is NULL or empty. If sp is non-NULL and an element is removed, copy the removed string to *sp (up to a maximum of bufsize-1 characters, plus a null terminator.) The space used by the list element and the string should be freed. */ bool q_remove_head(queue_t *q, char *sp, size_t bufsize) { /* You need to fix up this code. */ q->head = q->head->next; return true; }

/* Return number of elements in queue. Return 0 if q is NULL or empty */ int q_size(queue_t *q) { /* You need to write the code for this function */ /* Remember: It should operate in O(1) time */ return 0; }

/* Reverse elements in queue No effect if q is NULL or empty This function should not allocate or free any list elements (e.g., by calling q_insert_head, q_insert_tail, or q_remove_head). It should rearrange the existing ones. */ void q_reverse(queue_t *q) { /* You need to write the code for this function */ }

Test

This is the handout directory for the 15-213 C Lab.

************************ Running the autograders: ************************

Before running the autograders, compile your code to create the testing program qtest linux> make

Check the correctness of your code: linux> make test

****** Using qtest: ******

qtest provides a command interpreter that can create and manipulate queues.

Run ./qtest -h to see the list of command-line options

When you execute ./qtest, it will give a command prompt "cmd>". Type "help" to see a list of available commands

****** Files: ******

# You will handing in these two files queue.h Modified version of declarations including new fields you want to introduce queue.c Modified version of queue code to fix deficiencies of original code

# Tools for evaluating your queue code Makefile Builds the evaluation program qtest README This file driver.py* The C lab driver program, runs qtest on a standard set of traces

# Helper files

console.{c,h}: Implements command-line interpreter for qtest report.{c,h}: Implements printing of information at different levels of verbosity harness.{c,h}: Customized version of malloc and free to provide rigorous testing framework qtest.c Code for qtest

# Trace files

traces/trace-XX-CAT.cmd Trace files used by the driver. These are input files for qtest. They are short and simple. We encourage to study them to see what tests are being performed. XX is the trace number (1-15). CAT describes the general nature of the test.

traces/trace-eg.cmd: A simple, documented trace file to demonstrate the operation of qtest

1 Objective This lab will give us practice with the C programming language. It will introduce us to various different aspects of C. Some of the skills tested are: Explicit memory management, as required in C. Creating and manipulating pointer-based data structures and functions malloc and free. . Working with strings and functions strlen, strcpy, and strncpy. (Beware of the behavior of strncpy when truncating 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. The lab 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 e client. 2 Overview The file queue.h contains declarations of the following structures: /* Linked list element */ typedef struct list ele { char *value; struct list ele *next; } list_ele_t; /* Queue structure */ typedef struct { list_ele *head; /* First element in in the queue */ } queue_t; Queue List head List tail head NULL Additional Fields 63616200 6265 61 6400 63 61 62 00 b e a d a b Figure 1: Linked-list implementation of a queue. Each list element has a value field, pointing to an array of characters (C's representation of strings), and a next field pointing to the next list element. Characters are encoded according to the ASCII encoding (shown in hexadecimal.) These are combined to implement a queue of strings, as illustrated in Figure 1. 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. Recall that a string is represented in C as an array of values of type char. In most machines, data type char is represented as a single byte. To store a string of length 1, the array has 1 + 1 elements, with the first / storing the codes (typically ASCIII format) for the characters and the final one being set to 0. 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 eparate 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 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. 3 Programming Task Your task is to modify the code in the files queue.h and queue.c to fully implement the following functions. queue_new: Create a new, empty queue. queue_free: Free all storage used by a queue. queue_insert_head: Attempt to insert a new element at the head of the queue (LIFO discipline) queue_insert_tail: Attempt to insert a new element at the tail of the queue (FIFO discipline) queue_remove_head: Attempt to remove the element at the head of the queue. queue_size: Compute the number of elements in the queue. queue_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. When it comes time to free a list element, you must also free the space used by the string. You cannot assume any fixed upper bound on the length of a string and you must allocate space for each string based on its length. Note: malloc, calloc, and realloc are the only supported functions in this lab for memory allocation, any other functions that allocate memory on the heap may cause you to lose points. Two of the functions, queue_insert_tail and queue_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 implementations operate in time 0(1), i.e., that the operation will require only a fixed number of steps, regardless of the queue size. 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. Please work on nding a solution better than the O(n2) solution for all of the functions. 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. 4. let P(m, n) be "n is greater than or equal to m" where the domain (universe of discourse) is the set of nonnegative integers. 4 Testing You can compile your code using the command: linux> make If there are no errors, the compiler will generate a executable program qtest, providing a command interface with which we can create, modify, and exam queues. Documentation on the available commands can be found by starting the program and running the help command: linux> ./qtest cmd> help The following file (traces/trace-eg.cmd) illustrates an example command sequence, which you can type into the qtest program: # Demonstration of queue testing framework # Initial queue is NULL. show # Create empty queue new # Fill it with some values. First at the head. ih dolphin ih bear ih gerbil # Now at the tail it meerkat it bear # Reverse it reverse # See how long it is size # Delete queue. Goes back to a NULL queue. free # Exit program quit You can also run qtest on an entire trace file all at once, as follows: linux> ./qtest -f traces/trace-eg.cmd # An example trace. linux> ./qtest -f traces/trace-01-ops.cmd # The first real trace. If you try to test the starter code, you will see that it does not implement many of the operations properly. The traces directory contains 15 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. We can use these traces and direct interactions with qtest to test and debug your program. 5 Evaluation Your program will be evaluated using the fteen traces described above. You will be given credit (either 6 or 7 points, depending on the trace) for each one that executes correctly, summing to a maximum score of 100. This will be your score for the assignment, the grading is completely automated. This lab will not be graded on style. The driver program driver.py runs qtest on the traces and computes the score. This is the same program that will be used to compute your score. You can invoke the driver directly with the command: linux> ./driver.py or with the command: linux> make test 6 Logistics Our lab materials are contained in a Linux archive file cprogramminglab- handout.tar, which you can upload from Mimir. After uploading the file, give the command: linux> tar xvf cprogramminglab-handout.tar This will create a directory called cprogramminglab-handout that contains a number of files. Consult file README for descriptions of the files. You will modify the files queue.h and queue.c. score that you receive. Using make to generate qtest also has the effect of generating a tar file, handin.tar. Upload this file (and only this file!). You may hand-in as often as you like until the due date. IMPORTANT: Do not upload files in other archive formats, such as those with extensions .zip,.gzip, or.tgz. 1 Objective This lab will give us practice with the C programming language. It will introduce us to various different aspects of C. Some of the skills tested are: Explicit memory management, as required in C. Creating and manipulating pointer-based data structures and functions malloc and free. . Working with strings and functions strlen, strcpy, and strncpy. (Beware of the behavior of strncpy when truncating 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. The lab 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 e client. 2 Overview The file queue.h contains declarations of the following structures: /* Linked list element */ typedef struct list ele { char *value; struct list ele *next; } list_ele_t; /* Queue structure */ typedef struct { list_ele *head; /* First element in in the queue */ } queue_t; Queue List head List tail head NULL Additional Fields 63616200 6265 61 6400 63 61 62 00 b e a d a b Figure 1: Linked-list implementation of a queue. Each list element has a value field, pointing to an array of characters (C's representation of strings), and a next field pointing to the next list element. Characters are encoded according to the ASCII encoding (shown in hexadecimal.) These are combined to implement a queue of strings, as illustrated in Figure 1. 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. Recall that a string is represented in C as an array of values of type char. In most machines, data type char is represented as a single byte. To store a string of length 1, the array has 1 + 1 elements, with the first / storing the codes (typically ASCIII format) for the characters and the final one being set to 0. 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 eparate 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 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. 3 Programming Task Your task is to modify the code in the files queue.h and queue.c to fully implement the following functions. queue_new: Create a new, empty queue. queue_free: Free all storage used by a queue. queue_insert_head: Attempt to insert a new element at the head of the queue (LIFO discipline) queue_insert_tail: Attempt to insert a new element at the tail of the queue (FIFO discipline) queue_remove_head: Attempt to remove the element at the head of the queue. queue_size: Compute the number of elements in the queue. queue_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. When it comes time to free a list element, you must also free the space used by the string. You cannot assume any fixed upper bound on the length of a string and you must allocate space for each string based on its length. Note: malloc, calloc, and realloc are the only supported functions in this lab for memory allocation, any other functions that allocate memory on the heap may cause you to lose points. Two of the functions, queue_insert_tail and queue_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 implementations operate in time 0(1), i.e., that the operation will require only a fixed number of steps, regardless of the queue size. 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. Please work on nding a solution better than the O(n2) solution for all of the functions. 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. 4. let P(m, n) be "n is greater than or equal to m" where the domain (universe of discourse) is the set of nonnegative integers. 4 Testing You can compile your code using the command: linux> make If there are no errors, the compiler will generate a executable program qtest, providing a command interface with which we can create, modify, and exam queues. Documentation on the available commands can be found by starting the program and running the help command: linux> ./qtest cmd> help The following file (traces/trace-eg.cmd) illustrates an example command sequence, which you can type into the qtest program: # Demonstration of queue testing framework # Initial queue is NULL. show # Create empty queue new # Fill it with some values. First at the head. ih dolphin ih bear ih gerbil # Now at the tail it meerkat it bear # Reverse it reverse # See how long it is size # Delete queue. Goes back to a NULL queue. free # Exit program quit You can also run qtest on an entire trace file all at once, as follows: linux> ./qtest -f traces/trace-eg.cmd # An example trace. linux> ./qtest -f traces/trace-01-ops.cmd # The first real trace. If you try to test the starter code, you will see that it does not implement many of the operations properly. The traces directory contains 15 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. We can use these traces and direct interactions with qtest to test and debug your program. 5 Evaluation Your program will be evaluated using the fteen traces described above. You will be given credit (either 6 or 7 points, depending on the trace) for each one that executes correctly, summing to a maximum score of 100. This will be your score for the assignment, the grading is completely automated. This lab will not be graded on style. The driver program driver.py runs qtest on the traces and computes the score. This is the same program that will be used to compute your score. You can invoke the driver directly with the command: linux> ./driver.py or with the command: linux> make test 6 Logistics Our lab materials are contained in a Linux archive file cprogramminglab- handout.tar, which you can upload from Mimir. After uploading the file, give the command: linux> tar xvf cprogramminglab-handout.tar This will create a directory called cprogramminglab-handout that contains a number of files. Consult file README for descriptions of the files. You will modify the files queue.h and queue.c. score that you receive. Using make to generate qtest also has the effect of generating a tar file, handin.tar. Upload this file (and only this file!). You may hand-in as often as you like until the due date. IMPORTANT: Do not upload files in other archive formats, such as those with extensions .zip,.gzip, or.tgz