Objectives

In this Lab, you will practise:

• Abstracting a data type
• Writing ADT unit tests
• Implementing ADTs

Preparation

Before the lab you should re-read the relevant lecture slides and their accompanying examples

Getting Started

Login and run following commands inside a Unix terminal

Create a new directory for this lab called labB1 by typing:

mkdir labB1

Change to this directory by typing:

cd labB1

Autotests and Freeing Memory

As you know, every time we use malloc, we need to use a corresponding free when we are finished with the memory.
If we don't we will use more and more memory as our program runs.
It is given back to the system as soon as the program terminates, so for our short toy programs it has not been an issue.

However, users do not want memory leaks in their ADTs.
So in this lab and the next lab we want to make sure you correctly implement your destroy functions.
And use them correctly in your client program so we know that you can manage your memory accurately.

In the labs and the exam we will be testing your programs with the additional --leak-check option for dcc. For example:

dcc --leak-check prog.c -o prog

So your program will need to generate the correct output AND free all malloced memory to pass the autotests.
Keep this in mind when you are testing your ADTs in this lab.

Getting Provided Files

To get all of the provided files for this lab you can run the following command:

$ cp /web/cs1911/current/tlb/B1/code/*.[ch] .

How to Compile

For multi-file projects you must give all required C files to the compiler at the same time.
You don't need to include H files, but they must be in the current directory.

$ dcc ADT-file.c main-file.c -o executable
$ ./executable

Exercise 1: Writing Assert Based Black Box Tests

For this lab there will be no autotest.
You will be writing your own test code.

It is a good idea to write tests for your ADT before you have even implemented it to make sure you understand exactly how the ADT should behave.
This is a concept called test driven development

In this exercise you are going to write tests for a set ADT.
Your tests should test the required behaviour of the set.
It should rely only on the functions and typedefs from the set.h file.

A set here is a collection of unique values, without any particular order.
That is to say that each element of the set can either be in the set or not be in the set.
Nothing can be in the set multiple times.

And once something is in the set it has no order.
That is to say there is no first, second, or last element of a set.

To get you started we have supplied you with a testSet.c file,
But you need to add more tests of your own.

Since the tests are not a complete program on their own, you will not be able to run your tests yet,
but you can compile them to check your syntax using the following:

$ gcc -Wall -Werror -c testSet.c

Once you are happy with your tests, move onto the next exercises where you will actually implement a set and use your testSet.c to test them!

Exercise 2: Implementing a set using an array

In a file named setArray.c, you will be implementing the set data type. To do this you will need to:

• #include "set.h" in your setAray.c file.
• Create a struct Set that stores all the necessary data for your ADT.
• Copy and paste all the function prototypes from the set.h file into your setArray.c file and then actually implement the functions.

When implementing your set you MUST use a malloced array which is grown with realloc as needed,
so there is no limited on how many items can be stored in the set.

You should implement the re-sizing in the following way:

• When an attempt is made to insert an item into a set that is already full, the array is resized to accomodate the extra element.
  Make sure the set is only resized when it is full and make the resized array be 2 times bigger.
• Also when the size of the set drops below 1/4 of the size of the array, the array size should be resized to half of its size.
  However the array size should never drop below its original starting size.
• Make the default starting size 64.

Compile and run your setArray.c with the tests your wrote by running:

$ dcc testSet.c setArray.c -o set
$ ./set
...
All tests passed!

and then to check for memory leaks use:

$ dcc --leak-check testSet.c setArray.c -o set
$ ./set
...
All tests passed!

Make sure you fix any errors (including memory leaks).

Note:
You can't really test whether your array is being resized when the set shrinks, using black box testing.
For this kind of thing, you would need to use whitebox testing.
To do this you could create a main inside your setArray.c and do some testing in there.
You would need to compile and run it as a stand alone program.
You would need to comment out your main when you are finished,
so your ADT could be used with other programs again,
since we can only have one main function per program.

Exercise 3: Implementing a set using a linked list

Repeat the previous exercise, but instead of using an array, use a linked list.

Write your code in a file named setList.c

Compile and run your setList.c with the tests your wrote by running:

$ dcc testSet.c setList.c -o set
$ ./set
...
All tests passed!

and then to check for memory leaks use:

$ dcc --leak-check testSet.c setList.c -o set
$ ./set
...
All tests passed!

Make sure you fix any errors (including memory leaks).

Submission/Assessment

There are no autotests for this lab. When you are satisfied with your work, submit it electronically by typing (run this command in your labB1 directory):

give cs1911 labB1 testSet.c setArray.c setList.c