Lab 8

Linked Lists

In the prelab, we introduced the linked list data structure and created the struct snode to represent each list item. In this lab we’re going to put this data structure to work in your own complete linked list library. Before we get started we need to first address a problem with our struct snode. Recall, you should have a definition like this in your snode.h file from prelab:

This is perfectly valid (and exactly what we asked you to do), but notice that every struct snode allocated will consume 101 + 4 + 4 bytes (on a 32-bit system). Even if we store the string “The”, we allocate 101 bytes. The extra 97 bytes are wasted. We could change the definition of struct snode to only allocate say, 12 bytes (4 bytes for the string “The”, 4 bytes each for the integer and the pointer, but now what if we want to store a very long string (possibly more than 100 bytes)? It seems we can’t win because we will never be able to predict the optimal size of the str member, because it could change based on the user’s input. We really want to allocate just enough memory to store each string at runtime.

Fortunately, we can do exactly this in C with dynamic memory allocation.

Exercise 1: Adapting the snode module for dynamic memory allocation

Copy your snode.h file to dnode.h , and copy snode.c to dnode.c while you’re at the terminal. Then change the struct snode to be struct dnode. The struct dnode is almost identical to struct snode except that the str member is now a pointer to a string, that is, of type (char *) to support dynamic memory allocation and there is a struct dnode* prev member. This will allow us to create a doubly-linked list and will come in handy later to implement functions like insert

Next, modify the function dnode_create (based on snode_create) to also allocate memory for the str member on the program’s heap using malloc. The function prototype for the function should be similar to that of snode_create, that is:

struct dnode *dnode_create(char *s);

Note that we took the length out of the function prototype because we can use string functions to compute the length of a given string.

The new dnode_create will have to:

  1. Allocate memory that is equal to the length of the string s plus 1 byte for the null terminator (Use Linux manual pages to find out how to compute string length or copy strings.) and save this pointer inside the newly created dnode.
  2. Initialize the length field of the dnode according to the length of the string received as parameter.
  3. Copy the contents of the string argument into the newly allocated memory.
  4. Set the prev and next node pointers to NULL.

Because we are using dynamically allocated memory, we should also create a function to deallocate a single dnode that is, do not destroy the next or previous dnodes!

void dnode_destroy(struct dnode *n);

Be careful when implementing dnode_destroy. In dnode_create you had two calls to the malloc() function. As a result you should have two calls to the free() function in dnode_destroy to destroy the node and free the memory. The first call to free must free the memory used by the string and the second call to malloc will free the memory used by the structure itself. To properly deallocate memory, we need to free() both of these pointers!

If you implement these changes correctly, you should be able to compile your dnode.c to create dnode.o.  Copy your snode_test.c to dnode_test.c and replace the calls to to snode to now use instead a dnode. We have changed the arguments to dnode_create to not require a separate length. You should edit your dnode_test.c to call the modified dnode_create. Add a rule in your Makefile to compile dnode_test.c. When you run your program, everything should now work exactly as it did in snode_test.c. However, we didn’t clean up the dynamic memory, so add the appropriate calls to dnode_destroy to the end of dnode_test.c.

Cleaning up memory

When you have a functioning dnode_test, you can take steps to make sure that you are using dynamically allocated properly in your code. By properly, we mean: everything that is allocated at run time gets deallocated by the time the program terminates. The following instructions guide you through the basic use of a tool to help you detect memory screw ups.

One of the most difficult parts to get right in C is managing memory. A powerful tool to check for memory leaks (among other things) is valgrind. It is a program that instruments a program and monitors all memory allocation and deallocation. You can read the valgrind man page and then run it on your program with the command:

$ valgrind ./dnode_test

When you run this you will get a few lines prefixed with ==12345==, this is valgrind’s output. The number is valgrind’s process id (or pid); this is a numeric identifier that the operating system uses for each program in execution. Each time you execute valgrind (or any process for that matter) you will most likely get a different pid (once a program exists, pid numbers can be reused by the OS). After valgrind’s startup message, your program will run as usual. When you program exits, valgrind will print a summary of dynamic memory usage like the one below.

The line beginning “in use at exit” (just after HEAP SUMMARY) shows we still have 113 bytes allocated when the program ended. This indicates our program is leaking memory! The next line says we made 7 calls to malloc and 1 call to free. Your output will vary depending how well you freed memory. Don’t worry if you have a few leaks, as we said above this is very hard to get right. Now that you can use valgrind to detect memory leaks, you can go back and improve your dnode_test program. Be sure to deallocate the list at the end of your program (call dnode_destroy) and don’t leave any dangling pointers (pointers to freed memory).

In general, you would want to work until your valgrind output has the line “All heap blocks were freed — no leaks are possible” as shown below.

To complete this problem, add dnode.h, dnode.cdnode_test.c, and your updated Makefile to your git repository and push to gitlab.

Exercise 2: Making a doubly-linked list with dnode

In the previous exercise, the driver program manually created a singly-linked list made of just a few nodes (dnodes, though we only used one link). The goal of our next exercise is to automate the creation of a double linked list structure. Begin by thinking about the mechanics of using the dnode_create functions in the context of creating a new list.

To get started, we have provided the file ~cs206/Labs/Lab08/dlist.h. This file defines a new data structure called struct dlist and several useful dlist functions. For this exercise you will implement the functions listed below, which is a part of the header file dlist.h. We will add more functions in exercise 3.

Take a closer look at this file dlist.h (not copied in the above pane). After the comment section at the top, you will find two lines of compiler directive,

The compiler directives work in similar logic of your C programs. The above directive reads “if not defined a symbol called _dlist_H_, we define it.” by the directive in the next line #define _dlist_H_. The end of this if-then-else structure is indicated by the very last line of this file #endif. The reason for this directive is to avoid duplicating definitions. Imagine that if this file dlist.h, or any other header files, is included in a program more than once, e.g., in a program that consists of multiple components, the definitions in the header file would be repeated multiple times, which is not allowed syntactically. Using the if-then-else compiler directive will avoid this problem as the compiler will avoid including this header for the second time because the symbol _dlist_H_ has been defined when (and if) the compiler sees this header file for the second time. When the symbol, in this case _dlist_H_ has been defined, the entire header file will be skipped by the compiler.

Please go back to your dnode.h and add a similar directive.

Now that our structure is defined, create the file dlist.c. This file should include both dlist.h and dnode.h and implement the functions given above. That is, you must implement the functions dlist_create(), dlist_add_front(), dlist_add_back(), dlist_destroy() and dlist_length(). When working with struct dnodes you must call the appropriate function to operate on the dnode (that is: do not duplicate code that exists in dnode.c!).

To test your first dlist implementation, create the file song_list.c. This will be similar to dnode_test, but now use the dlist functionality to create the list. For testing, the code below adds the top 9 songs from 2015 (ranked by Billboard) and then prints the list.

Title Artist(s)
1 Uptown Funk Mark Ronson featuring Bruno Mars
2 Thinking Out Loud Ed Sheeran
3 See You Again Wiz Khalifa featuring Charlie Puth
4 Trap Queen Fetty Wap
5 Sugar Maroon 5
6 Shut Up and Dance Walk the Moon
7 Blank Space Taylor Swift
8 Watch Me Silentó
9 Earned It The Weeknd

Make sure you revise your Makefile to reflect the fact that you are now making an executable called song_list. Before you submit, use valgrind to verify that there are no memory leaks.

When you have created and debugged your dlist.c and Makefile and are sure there are no memory leaks when running song_list, add dlist.h/.c and song_list.c to your git repo and push to gitlab.

Exercise 3: Higher-level list operations

Your dlist implementation is now working but lacks some useful higher-level functions, namely searching, inserting, and removing nodes at arbitrary locations. To support these operations, add the following functions to dlist (they are already declared in dlist.h):

  • struct dnode* dlist_find(struct dlist* l, char * str);
    • Return the first node where the string matches str (use dnode_cmp).
  • struct dnode* dlist_insert_before(struct dlist* l, struct dnode* n, char * str);
    • Insert a new node with <str> before the node n.
  • struct dnode* dlist_insert_after(struct dlist* l, struct dnode *n, char *str);
    • Insert a new node with <str> after the node n.
  • struct dnode* dlist_remove(struct dlist* l, struct dnode* n);
    • Remove a node from the list (but does not destroy the node).

To implement the first function, dlist_find, add a new function to dnode to do the actual comparison:

  • int dnode_cmp(struct dnode *n, char *str);
    • Compares the string in the dnode n to str. Returns <0 if node->str < str, 0 if node->str == str, and >0 if node->str > str. (see strcmp)

To test your functions we provide you with the dlist test program ~cs206/Labs/Lab08/dlist_test.c. Add a rule to build dlist_test in your Makefile. Notice that in the provided dlist_test.c file, we defined a symbol called DEBUG at the top of the program. If the symbol is defined, the program runs with a smaller test size. When your program works properly, comment out the #define DEBUG line, the program will then run with much larger test size. Recompile and run the program.

When you have added the above functions to your dlist library, debugged everything, and verified (with valgrind) there are no memory leaks, add dlist_test.c to your git repo and push to gitlab.

Files to submit: You are to submit the following files in addition to the prelab submission.

  • dnode.h
  • dnode.c
  • dnode_test.c
  • dlist.h
  • dlist.c
  • song_list.c
  • dlist_test.c
  • Makefile

Grading

Pre-Lab [25 points]

  • [10 points] snode.h has a working definition of struct snode and declaration for rsnode_create.
  • [10 points] snode.c has a correct snode_create that uses malloc and strcpy; -3 if it does not set length, str, or next.
  • [5 points] snode-test works and compiles with a valid Makefile.

Lab [75 points]

  • [25 points] dnode.h / .c created and dnode_test.c runs without memory leaks.
  • [15 points] dlist.h / .c created with correct basic functions (create, destroy, add_front, add_back).
  • [10 points] song_list runs correctly (5 points) without memory leaks (5 points).
  • [15 points] higher level functions (insert_before, insert_after, find, remove) added to dlist.
  • [10 points] dlist_test runs correctly (5 points) without memory leaks (5 points).

Print Friendly
Posted in Lab Tagged with:

Leave a Reply

Your email address will not be published. Required fields are marked *

*

This blog is kept spam free by WP-SpamFree.