For homework #1, you will finish our implementation of two C data structures: in part A, a doubly-linked list, and in part B, a chained hash table.

Please read through this entire document before beginning the assignment, and please start early! This assignment involves messy pointer manipulation and malloc/free puzzles, and these can cause arbitrarily awful bugs that take time and patience to find and fix.

Part A: doubly linked list

If you’ve programmed in Java, you’re used to having a fairly rich library of elemental data structures upon which you can build, such as vectors and hash tables. In C, you don’t have that luxury: the C standard library provides you with very little. In this assignment, you will add missing pieces of code in our implementation of a generic doubly-linked list.

At a high-level, a doubly-linked list is incredibly simple; it looks like this:

Each node in a doubly-linked list has three fields:

If the list is empty, there are no nodes. If the list has a single element, both of its next and previous pointers are NULL.

So, what makes implementing this in C tricky? Quite a few things:

Given all of these complications, our actual linked list data structure ends up looking like this:

Specifically, we define the following types and structures:

What to do

You should follow these steps to do this assignment:

Make sure you are comfortable with C pointers, structures, malloc, and free. We will cover them in detail in lecture, but you might need to brush up and practice a bit on your own; you should have no problem Googling for practice programming exercises on the Web for each of these topics.

To fetch the source files for hw1, navigate to the directory where you want to store your work. (You will use this directory for this assignment and the remaining three parts of the project over the rest of the quarter. Be sure to back up this directory regularly if it is on your own computer. You may want to use a source control system like git or subversion to manage your files.).

Click (or right-click if needed) on this hw1.tar.gz link to download the archive containing the starter code. Extract its contents and verify that you have everything. (If your hw0 directory is also stored here, that’s fine. It won’t have any affect on the project.)

$ tar xzf hw1.tar.gz
$ ls
clint.py  gtest  hw1  hw1.tar.gz  LICENSE.TXT

Look inside the hw1 directory. You’ll see a number of files and subdirectories, including these that are relevant to Part A:

Run make to verify that you can build your own versions of example_program_ll and test_suite. Make should print out a few things, and you should end up with new binaries inside the hw1 directory.

Since you haven’t yet finished the implementation of LinkedList.c, the binaries you just compiled won’t work correctly yet. Try running them, and note that example_program_ll halts with an assertion error or a segfault and test_suite prints out some information indicating failed tests, and may crash before terminating.

This is the hard step: finish the implementation of LinkedList.c. Go through LinkedList.c, find each comment that says “STEP X”, and replace that comment with working code. The initial steps are meant to be relatively straightforward, and some of the later steps are trickier. You will probably find it helpful to read through the code from top to bottom to figure out what’s going on. You will also probably find it helpful to recompile frequently to see what compilation errors you’ve introduced and need to fix. When compilation works again, try running the test driver to see if you’re closer to being finished.

Debugging hint

Verify333 is used in many places in the code to check for errors and terminate execution if something is wrong. You might find it helpful to discover the function that is called when this happens so you can place a debugger breakpoint there.

We’ll also be testing whether your program has any memory leaks. We’ll be using Valgrind to do this. To try out Valgrind for yourself, do this:

$ valgrind --leak-check=full ./example_program_ll

Note that Valgrind prints out that no memory leaks were found.

$ valgrind --leak-check=full ./test_suite

Note that Valgrind again indicates that no memory leaks were found.

Part B: a chained hash table

A chained hash table is also a fairly simple data structure. It consists of an array of buckets, and each bucket contains a linked list of elements. When a user inserts a key/value pair into the hash table, the hash table uses a hash function to map the key into one of the buckets, and then adds the key/value pair onto the linked list. (As an important corner case, if the key of the inserted key/value pair already exists in the hash table, the hash table replaces the existing key/value pair with the new one, and returns the old key/value pair to the customer.)

So, over time, as more and more elements are added to the hash table, the linked lists hanging off of each bucket will start to grow. As long as the number of elements is a small multiple of the number of buckets, lookup time is small: you hash the key to find the bucket, then iterate through the chain (linked list) hanging off the bucket until you find the key. As the number of elements gets longer, lookup gets less efficient, so our hash table includes logic to resize itself to maintain short chains.

As with the linked list in Part A, we’ve given you a partial implementation of a hash table. Our hash table implementation looks approximately like this:

Specifically, we defined the following types and structures:

What to do

You should follow these steps to do this assignment:

Bonus

You’ll note that we provided a second Makefile called Makefile.coverage. You can use it to invoke the gcov code coverage generation tool. Figure out how to

The bonus task is simple, but we’re (deliberately) providing next to no detailed instructions on how to do it—figuring out how is part of the bonus task!

Please make sure your additional unit tests don’t change the scoring mechanism that we use, obviously. (We’ll be checking that.) Place your additional unit tests in a separate file from the original test suite. That will make it easier for us to find and evaluate your tests.

What to turn in

When you’re ready to turn in your assignment, do the following:

In the hw1 directory:

$ make clean
$ cd ..
$ tar czf hw1_<username>.tar.gz hw1
$ # make sure the tar file has no compiler output files in it, but
$ # does have all your source
$ tar tzf hw1_<username>.tar.gz

Turn in hw1_<username>.tar.gz using the course dropbox linked on the main course webpage.

Grading

We will be basing your grade on several elements: