Goals

• Practice with the creation of a Makefile.
• Get reacquainted with C programming.
• Practice your code reading skills.

Credits

This lab was developed by Prof. L. Felipe Perrone. Permission to reuse this material in parts or in its entirety is granted provided that this credits note is not removed. Additional students files associated with this lab, as well as any existing solutions can be provided upon request by e-mail to: perrone[at]bucknell[dot]edu

---

It should go without saying that all the work that you will turn in for this lab will be yours. Do not surf the web to get inspiration for this assignment, do not include code that was not written by you. You should try your best to debug your code on your own, but it’s fine to get help from a colleague as long as that means getting assistance to identify the problem and doesn’t go as far as receiving source code to fix it (in writing or orally).

---

Set Up

• You will work in your ~/csci315/Labs/Lab0 directory for this lab. All your submission files should be at this location. Copy into this directory all the source files from ~cs315/Labs/Lab0. Remember that ~/csci315/… contains your work, and ~cs315/… contains the lab materials distributed by your instructors.
• We recommend that you start working on developing your Unix terminal prowess and avoiding the use of GUIs. In order to copy the files over, you should type the following at the terminal prompt:
  • cp -R ~cs315/Labs/Lab0 ~/csci315/Labs
• If you don’t understand the syntax of the copy command above, be sure to ask!

Problem 1 (40 points)

Take a look at the files you were given. They contain a C module that implements the doubly-linked list abstract data type (ADT). Assume for now that these files are complete and ready to execute. You can compile them individually with invocations to gcc to generate object files. For instance, if you want to create an object file for dnode.c, what you need to do is:

gcc -c dnode.c -o dnode.o

If you want to instrument this object for debugging with gdb, you need to pass the -g flag. If you want your compilation to follow the gnu99 C standard, you need to pass the flag -std=gnu99. And if you want to enable the compiler to produce the maximum level of warnings, you need to pass in the -Wall flag. Adding all these flags to the compiler invocation above would give you:

gcc -std=gnu99 -g -Wall -c dnode.c -o dnode.o

You would need to invoke gcc again to compile file dlist.c into an object called dlist.o. And yet again, to compile the program dlisttest.c and link it with the separately generated dnode.o and dlist.o. If you start debugging or augmenting these three source files and recompiling them frequently, you quickly realize that you want a Makefile to avoid all the tedious, repetitive, manual work.

So… let’s have you write this Makefile. First of all, you will want a rule to generate the object file dnode.o taking into account that this object depends on two files: dnode.c and dnode.h.

Second, you will want a rule to generate object file dlist.o taking into account that this object depends on three files: dlist.h, dlist.c, and dnode.h.

Third, you will want a rule to compile dlisttest.c, link it with dnode.o and dlist.o, and produce the executable dlisttest.

Finally, you should want a rule called “clean” to remove all the object and executable files generated. Why? Simple: you don’t need to put compiled code into your source version control, so you will benefit from having a way to junk objects and executables before committing updated sources to your git repo.

Use the skeleton given to you to build up this Makefile into one that has the four rules outlined above. Be sure to use the variables already defined in the skeleton! Make sure to test whether your Makefile works to expectations.

Note that if you run:

make -n

You will be able to see what make would do to generate your executable dlisttest without actually doing anything. This is a helpful trick to see if you got things correctly implemented in your Makefile.

If I were you, I’d commit and push my Makefile with git before testing out my clean rule, just in case something goes awry and I would end up removing code that I didn’t mean to lose.

When you are done with this problem, you need to:

• cd ~/csci315/Labs/Lab0
• git add Makefile
• git commit -m “Lab 0.1 completed”
• git push

Problem 2 (30 points)

Spend some time reading the files given to you for this lab. The dnode.c file implements functions to create and manipulate a node in a doubly-linked list ADT. The dlist.c file implements various functions for a doubly-linked list ADT. The dlisttest.c file implements tests to shake the code around and verify that it works. Spend time reading these files carefully to understand the implementation – note that the header files are instrumented with plenty of documentation comments that will help your understanding.

Here is the catch. Some of these functions in dlist.c are not implemented and it’s your task to code them up correctly. Namely, what is missing are the following functions:

dlist_add_front: create a node, attach the pointer you receive in the function’s argument to the pointer called data inside the newly created node, hook up the new node to the one currently at the head of the list, and finally increment the counter of nodes in the list data structure.

dlist_add_back: similar to dlist_add_front, except that the new node is hooked up after the last node in the list data structure.

dlist_remove_front: unhook the node at the front of the list, save the value of the data pointer in the node to pass back to the caller of the function, free the node, and return the saved value of the data pointer.

Implement these functions and then use your Makefile to compile all the code and to build dlisttest, which you will use to verify whether your code is correct.

When you are done with this problem, you need to:

• cd ~/csci315/Labs/Lab0
• make clean
• git add *
• git commit -m “Lab 0.2 completed”
• git push

Hand In

Before turning in your work for grading, create a text file in your Lab 0 directory called submission.txt. In this file, provide a list to indicate to the grader, problem by problem, if you completed the problem and whether it works to specification. Wrap everything up by turning in this file:

• git add ~/csci315/Labs/Lab0/submission.txt
• git commit -m “Lab 0 completed”
• git push

Grading Rubric

Problem 1 [40 points total]

• [40 points] for a Makefile that compiles dnode.o, dlist.o, and dlisttest.c.
• [30 points] for a Makefile that compiles only two of the three files.
• [20 points] for a Makefile that compiles only one of the three files.
• [10 points] for the attempt to create a Makefile.

Problem 2 [30 points total]

• [10 points] for the correct implementation of dlist_add_front; [4 points] for an incorrect implementation.
• [10 points] for the correct implementation of dlist_add_back; [4 points] for an incorrect implementation.
• [10 points] for the correct implementation of dlist_remove_front; [4 points] for an incorrect implementation.