Laboratory

Objectives

• To practise implementing and testing ADTs

Assessment

Deadline

9 December 2018, 23:59:59

Marks

3

Submission

give cs2521 lab02

This lab should be done individually.

Setting up

Create a directory for this lab, change into it, and retrieve the files with the fetch command:

2521 fetch lab02
'./item.h' -> '/web/cs2521/19T0/week02/files.ln/item.h'
'./item_int.h' -> '/web/cs2521/19T0/week02/files.ln/item_int.h'
'./queue.h' -> '/web/cs2521/19T0/week02/files.ln/queue.h'
'./stack.h' -> '/web/cs2521/19T0/week02/files.ln/stack.h'
'./testable.h' -> '/web/cs2521/19T0/week02/files.ln/testable.h'
./
Makefile
queue_array.c
queue_list.c
stack_array.c
test_queue.c
test_stack.c

This will have provided you with several files (as you may have guessed by its output):

Makefile

contains build rules

stack.h

a Stack ADT interface.

test_stack.c

some simple tests for a Stack ADT; you will need to add more!

stack_array.c

an array-based implementation of a Stack ADT.

queue.h

A Queue ADT interface.

test_queue.c

A very empty file, for you to write tests for a Queue ADT in.

queue_array.c

An array-based implementation of a Queue ADT.

queue_list.c

A linked-list-based Queue ADT implementation … with bugs.

item.h

The generic Item type, specialised for integers.

testable.h

A ‘trait’ of things providing either white-box or black-box tests.

Download all the files.

These programs are incomplete, and you will need to modify the .c files as outlined in the instructions below. As for last week, you’ll be able to use make to build and rebuild the programs you change.

make
2521 3c    -c -o test_stack.o test_stack.c
2521 3c    -c -o stack_array.o stack_array.c
2521 3c   test_stack.o stack_array.o   -o test_stack
2521 3c    -c -o test_queue.o test_queue.c
2521 3c    -c -o queue_array.o queue_array.c
2521 3c   test_queue.o queue_array.o   -o test_queue_array
2521 3c    -c -o queue_list.o queue_list.c
2521 3c   test_queue.o queue_list.o   -o test_queue_list

The provided code contains tags marking unused variables. You should remove these tags as you implement those functions.

Exercise 1: Implementing a Stack ADT with Bounds Checking (1 mark)

In the lecture, we developed a stack ADT implementation which used arrays. This had some serious shortcomings!

Pushing an item onto the stack when the maximum number of items has been reached, or popping from the stack when the stack is empty, leads to out of bounds array access. Without protections in place (like those offered by 3c) this can cause other program variables to be unintentionally overwritten, or may result in apparently-random crashes. It is good programming practice to make ADT implementations robust against out-of-bounds errors and similar memory errors.

The provided file, stack_array.c, has the same problems. You need to modify the implementation in stack_array.c to provide the following behaviour:

• when an attempt is made to push an item onto a stack that is already full, the array is resized to accommodate the extra element. Make sure the stack is only resized when it is full, and make the resized array be two times bigger.

• when an attempt is made to pop from an empty stack, it prints the message "stack underflow" to standard error, and calls the function abort to terminate the program.

• when the size of the stack drops below $\frac{1}{4}$ of the size of the array, the array size should be resized to half of its size. The array size should never drop below its original starting size.

HINT Look at the C function realloc(3). Note that this can only be used to resize memory that has been dynamically allocated using malloc(3) or calloc(3). If you declare an array as a local variable (e.g., int array[100];), you cannot use realloc(3) to resize it.

While you are developing your implementation, add some unit tests which have access to, and can verify the correctness of, the internal structure of your ADT to the white_box_tests function in stack_array.c.

Add test cases to test_stack.c that would have triggered the out of bounds conditions to test that your code works properly. Be brutal with your tests! Also check that popping an empty stack generates the appropriate error messages. Remember that the tests you create in test_stack.c should be black box tests, and can only use the typedefs and functions declared in the stack.h interface.

Exercise 2: Creating black box tests for a Queue (0.5 marks)

In test_queue.c, write a comprehensive set of black box tests for the queue.h interface.

When you have finished writing your tests, use the provided Makefile to compile test_queue.c: it is set up to compile queue_array.c or queue_list.c, and test_queue.c together to give test_queue_array and test_queue_list, respectively.

Try running the test_queue_array program. Does the provided code pass your tests? It should … provided that you do not insert more than 10 items. The code contains an abort(3) statement that will kill the program in this situation.

Try running the test_queue_list program. Does the provided code pass your tests? It should not; it should contain errors that you need to fix.

Exercise 3: Debugging a linked-list Queue (0.5 marks)

In queue_list.c, write some white-box tests, and try to find and fix any errors in the queue_list.c implementation provided. Make sure the implementation passes all your black-box and white-box tests.

Exercise 4: Queue Faster! (1 marks)

The array-based Queue implementation in queue_array.c is woefully inefficient. When an item is removed, all the remaining items shuffle down one place in the array. This means the queue_de function has time complexity $O(n)$, because if we have $n$ items in the array, we would need to shift approximately $n$ items.

Modify the queue implementation so that both queue_en and queue_de are $O(1)$ operations – that is, the amount of work done in the function does not depend on the size of the queue.

HINT Store the index of the start of the queue and the end of the queue. This way when you get an element, you do not have to shift all the elements over; you can just update the index of the start of the queue.

You should also still make sure your implementation checks that the queue never exceeds its maximum and that it never tries to get an element from an empty queue. In this case, you should print out an error message and call abort(3). (Unlike the first part of this lab, you do not have to resize the array when it becomes full).

Write some white-box unit tests to confirm that your new implementation works, and recompile and run against your original black box tests. If your implementation and tests are correct, they should all still work.

Submitting

You must get the lab marked by your tutor in your lab.

Submit your work with the give command, like so:

give cs2521 lab02 stack_array.c test_stack.c queue_array.c queue_list.c test_queue.c

Or, if you are working from home, upload the relevant file(s) to the lab02 activity on WebCMS3 or on Give Online.