Laboratory

Objectives

Assessment

Deadline
2 December 2018, 23:59:59
Marks
3
Submission
give cs2521 lab01

This lab should be done individually.

You must get your tutor in your lab to mark the exercises during allocated lab time, or the following week if you submitted your lab on time using Give. Try to get them to mark each exercise as you complete it in your lab time, if possible.

In addition to the code that the exercise calls for, you will of course have to write some additional code to test the correctness of your implementation. Your tutor may want to see your testing code, too; good style requires good tests!

Code submitted by the deadline for a lab may be marked the following week at the beginning of the lab with no penalty. Late submissions will receive a 1 mark penalty. Once solutions are available, labs will be given 0.

Setting up

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

2521 fetch lab01
`./lists.h' -> `.../lists.h'
./
Makefile
lists.c
test_lists.c

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

lists.h
contains linked-list definitions and function prototypes. Do not change this file.
Makefile
contains build rules.
lists.c
contains a list_print function, and stubs for functions you need to implement to complete this lab.
test_lists.c
contains a main function to test your list implementation. You will need to add your own tests to this file.

Download all the files.

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

Exercise 1: Linked Lists (0.5 marks)

Using the code given in the tutorial, or otherwise, implement the functions in lists.c:

link node_new (Item it);
void list_insert_next (link list, link node);

Modify the test_lists.c code to use these functions to create a list with 3 nodes, and use the list_print function to print them out.

Compile your program –

make
2521 3c    -c -o test_lists.o test_lists.c
2521 3c    -c -o lists.o lists.c
2521 3c   test_lists.o lists.o   -o test_lists

Execute your program in gdb, and show your tutor that you can:

  1. set a breakpoint at the beginning of a function, and at a given line in the program;
  2. inspect the elements of a list using the print command; and
  3. inspect the call stack.

Now implement the function list_sum_items, which adds all the items in a list and returns the resulting integer value. Add some tests to test_lists.c, for cases with zero, one, and more elements. Use gdb to help debug your code, if needed.

Exercise 2: Six Bytes In A Leaky Boat (0.5 marks)

Our compiler, 3c, supports memory leak checking. You’ll have to invoke it by hand, though, adding +leak as the first argument –

2521 3c +leak test_lists.c lists.c -o test_lists
./test_lists

The output should show you that you have some memory leaks, assuming you have written some code in test_lists.c that actually adds some nodes to your linked list.

Implement a function list_drop that frees all the memory for each node in your list. Once you have written the function, test it in your test_lists.c code.

Run 3c +leak again, and check that all the memory leaks have gone. You must be able to show this to your tutor.

Exercise 3: Ouraboros! (1 mark)

Implement the functions

link clist_new (int n_nodes);
void clist_print (link clist);

The first function creates a circular linked list with the specified number of nodes. The second function prints the data in each node, starting with the node specified.

Test it in your test_lists.c code for lists with zero, one, and more elements.

What happens if you try to run list_sum_items on your circular linked list? You must be able to explain this to your tutor, but you do not need to fix it.

What happens if you try to run list_drop on your circular list? Modify list_drop so it works for both regular linked lists and circular linked lists. You should be able to show your tutor using 3c +leak or Valgrind that no memory leaks exist.

Exercise 4: Double, Double, Linked-List Trouble (1 mark)

Write a function dlist_new_from_list which, given a singly-linked list, creates a new doubly-linked list, with the same items as elements. You might want to write a dlist_print function to test it.

You must also write a function dlist_drop, and make sure you can demonstrate that you have freed the memory correctly to your tutor.

Submitting

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

Submit your work with the give command, like so:

give cs2521 lab01 lists.c

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