CMSC 216 Project #8

Description

1 Introduction and purpose

In this project you will extend upon your graph implementation from Project #7 in two ways: new functions will be added that allow removing components of graphs as well as an entire graph; and the graph functions will have to free any allocated memory when it is no longer needed. Some tests in this project will check for memory leaks and memory errors resulting in heap corruption (making parts of the heap invalid); Section 4 explains how these tests do this. Your functions in Project #7 could have passed some (or even all) of their tests despite having errors of these types, but in this project you will have to fix this. The purpose of the project is to ensure that you are not only able to create a more complex dynamically allocated data structure, but also able to correctly free memory for such a data structure.

You must again have a makefile (still named Makefile) in your submission that will compile your code for all of the public tests. Other than two points mentioned in Appendix B below, the requirements for your makefile are the same as in the previous project, so they are not repeated here. See Project #7 and the notes in Appendix B about makefile dependencies. Note that Project #7 explained in detail how to test your makefile before submitting.

Due to the size of the course it is not possible for us to provide project information or help via email/ELMS messages, so we will be unable to answer such questions. But you are welcome to ask them verbally during the TAs’ office hours.

1.1 Fixing problems in your Project #7 code

Even if you had trouble with Project #7 and may not get a high score on it, you can still do fine in the course (one project just isn’t worth much toward your grade). But you do have to get Project #7 to work though, so you can reuse it and expand upon it in this project. So if you know that you have bugs in your Project #7 code, fix them right away. (Hint– valgrind is your friend; see the rest of this section.)

A few days after this project is assigned we will provide the Project #7 secret tests in ~/216public/project07.

You can use them to figure out changes needed in your Project#7 code when reusing it in this project.

But even if you aren’t aware of any bugs in your Project #7 code your functions might still, as mentioned above, have some errors in the heap, despite being able to pass the Project #7 tests. But in this case your code will fail many of the tests in this project (the ones that are checking for consistency and correctness of the heap). So it is strongly recommended, before even trying to write the new functions in this project, that you first use valgrind to test for– and fix– any heap problems in your Project #7 code as follows:

• Before even extracting the files from the project08.tgz tarfile, make a complete second copy of your entire project07 directory, with a different name. (This is just so you can make changes to your previous code while still keeping a backup of your Project #7 code as it was submitted.)

• In the new copy of your project07 directory, add the -g compilation option to your makefile (if it’s not already in your compilation options), run make clean, then rebuild all of the public tests.

• Now run valgrind –leak-check=no public01.x and look for any errors reported by valgrind.

As the Project #7 assignment mentioned, the Project #7 tests will unavoidably have memory leaks, because there are no Project #7 functions that remove any components of a graph, so the tests have no way to free the memory used by String_graph variables when they finish. But the –leak-check=no option to valgrind prevents it from checking for memory leaks, so it will only check for other types of problems in the heap.

valgrind was explained in discussion section and a number of small examples were shown (the tarfile with the examples is in ~/216public on Grace). The examples had different kinds of memory problems that could occur, and allowed you to see how valgrind identified the different kinds of problems.

• Fix any memory problems in your string-graph.c that valgrind identified. If you need help understanding what valgrind is saying, after carefully reviewing and rerunning the valgrind examples in ~/216public, you can ask the TAs in office hours to help you understand what valgrind is telling you.

• Repeat the same command for the rest of the public tests, fixing any problems reported for any of the later tests as well.

• Then you can use your fixed string-graph.c in writing this project.

Of course this procedure assumes that you were in discussion section when valgrind was demonstrated and ex-plained by the TAs (on Monday, March 27), so you understand it. If you weren’t in discussion then, you’re on your own for figuring valgrind out. Try to ask a friend who was in discussion that day to explain it to you and show you the examples.

1.2 Extra credit and number of submissions

You can again get extra credit for this project. If you make only one submission that passes all the public tests you will get 3 extra–credit bonus points. And if your single submission is made at least 48 hours before the on–time deadline you will get 3 additional extra credit bonus points, for 6 extra credit points total. (Obviously you can’t get the second 3 extra credit points if you don’t get the first 3, but you can get the first 3 without getting these second 3.)

But as before, if you make too many submissions you may again lose credit. To avoid making submissions that don’t compile or don’t pass all the public tests you should compile the tests, run them, check your output, and fix any problems, all before submitting. And you should write your makefile first, and test it before submitting, as discussed below.

(If for some reason your code passes all the public tests on Grace but doesn’t work when you submit it, so you have to submit more than once– and this is not due to an error on your part, a bug in your code, or a problem with your makefile– you can talk with me in my office hours about receiving extra credit despite having more than one submission.)

2 New functions to be written

Just copy your string-graph.c and string-graph-datastructure.h files from your project07 directory (or copy the corrected versions from the new copy of your project07 directory if you followed the procedure in Section 1.1 above) to the new project08 directory that will be created by extracting the files from this project’s tarfile. As mentioned above, make whatever changes are needed to fix any bugs in your Project #7 code that was copied to the project08 directory, and add the new functions described below to it. But before starting to code, look at the public tests so you see how the functions are called.

Write one function at a time (entirely or even partially), then test it (as soon as that is possible) thoroughly before going on! Write and test helper functions before writing code that uses them, and test them separately first as well.

Project #7 said that if a pointer passed into a parameter of any function is NULL the function should have no effect, and (with two exceptions) if it returns an integer value it should return 0. This also applies (with one exception to the return value) to the new functions being added in this project

2.1 void free_vertex_name_list(char **const names)

This is a helper or utility function that is not actually part of a graph. It should free all the dynamically–allocated memory of the strings in the array names, then free the array names itself. It should have no effect if the pointer names itself is NULL. If names is non–NULL the function may assume that its last element will always be NULL (i.e., the array will be like those returned by the function get_vertex_list(), and by the new function get_neighbor_names() explained below). So the user of your code can use this function to free the memory returned by get_vertex_list() and get_neighbor_names() when they are no longer needed, to avoid memory leaks.

2.2 char **get_neighbor_names(String_graph *const graph, const char vertex[])

If its parameter graph itself is NULL, or if the graph does not have a vertex with the name vertex, this function should just return NULL. Otherwise it should return a newly–created dynamically–allocated array, say new_arr, of pointers to characters, where the pointers point to copies of the names of the neighbors of the vertex vertex in the parameter graph. (Recall that a neighbor of the parameter vertex is a vertex, say OTHER, such that there is an edge from the parameter vertex to OTHER.) The names pointed to by the pointers in new_arr must be in increasing lexicographic (dictionary) order. Each name must be stored in a newly–created dynamically–allocated character array; that is, the pointers in new_arr should not just be aliases of the names stored somewhere in your graph data structure.

If vertex has N neighbors, the array returned by the function must be an array with N + 1 elements, where the last element must be NULL. (So if the vertex vertex has no neighbors the function must return a dynamically allocated array of one element, which will be NULL.)

(The return value of this function for NULL parameters is the exception referred to in the third paragraph in Section 2.)

2.3 int remove_graph_edge(String_graph *const graph, const char source[], const char dest[])

This function should remove the edge going from source to dest in its parameter graph. If either source or dest are not vertices in the graph, or if they are vertices but there is no edge from source to dest, the function should just return 0 without changing anything, otherwise it should remove the edge and return 1. Any dynamically–allocated memory used by the edge must be freed.

Recall that your data structure must contain at least one linked list or binary search tree somewhere. If, given your data structure, it’s necessary to remove elements from linked lists or binary search trees in order to remove graph edges, how to do these things was covered in CMSC 132.

2.4 int remove_vertex_from_graph(String_graph *const graph, const char vertex[])

If vertex is not a vertex in its parameter graph this function should just return 0 without changing anything, otherwise it should remove vertex from the graph and return 1. If a vertex is removed then all its outgoing as well as incoming edges must also be removed, because an edge needs both its source and destination vertices to exist. Any dynamically– allocated memory used by the vertex and its associated edges must be freed.

2.5 void graph_delete(String_graph *const graph)

This function should deallocate all dynamically–allocated memory that is used in the String_graph variable that its parameter graph points to, releasing the graph and all its data in the process. So when this function returns, the graph data structure that graph previously pointed to effectively no longer exists in memory.

See Section 3 for explanation about when this function can– and must– be called.

3 Valid sequences of calls to the functions

A sequence of calls to the graph functions (including the ones from Project #7 as well as the new ones added in this project) on a given String_graph variable is valid if and only if the sequence satisfies the following:

• graph_init() is the first call in the sequence.

• Unless it is the last call in the sequence of calls to the graph functions, a call to graph_delete() must be followed immediately by a call to graph_init().

So following a graph_init() call and until the next graph_delete() call (if any), there can be any sequence of calls of functions other than graph_init() and graph_delete(). And it is invalid to call any other functions on a String_graph variable after graph_delete() is called on it, until graph_init() is called on it.

The effect of an invalid sequence of calls is undefined. Ensuring that the sequence of calls of your function is valid is the responsibility of the CALLER of your functions– which includes your own tests– your code does not have to try to detect violations of these properties, and in fact it has no way to do so.

If the user of your functions wants to avoid memory leaks they must make only valid sequences of calls to the graph functions, and they must also ensure that the last function call they make in any sequence of calls to the functions on

• String_graph variable must be graph_delete(). They must also call free_vertex_name_list() exactly once on every pointer returned by the two functions get_vertex_list() and get_neighbor_names(), and after that they must not use the pointers again. (Note that a String_graph variable will still be valid even if this is not done.)

4 Memory checking and memory errors

We have included an object file memory-functions.o in the project tarfile, which has two functions named setup_memory_checking() and check_heap() that are similar to the functions from Project #6. The header file

© 2023 L. Herman; all rights reserved

3

memory-functions.h contains their prototypes. They have no parameters or return value. We use them as follows in some of our tests to detect memory leaks and corruption:

• setup_memory_checking() must be called once in a program before any memory is dynamically allocated; it sets up things to check the consistency and correctness of the heap. If this function has been called initially, and the program has any memory errors later (such as overwriting beyond the end of an allocated memory region in the heap) the program will crash (consequently failing a test).

• If there is any memory in use in the heap at all when check_heap() is called it prints a message and causes the program to immediately quit. If there is no memory in use in the heap at all then calling it just has no effect.

Some tests will initially call setup_memory_checking(), then call check_heap() after functions are called on the different data structures and their memory is cleared. If the functions that are supposed to remove all or part of your graph data structure are not freeing memory properly, your program will report that there is some allocated memory in the heap– meaning a memory leak occurred- causing these tests to fail. (This could also happen if the user calls your functions in an invalid order, for example by calling graph_init() on a nonempty String_graph variable without calling graph_delete() on it first, but this is their fault. If you are using our memory checking functions in your own tests and you make an invalid sequence of calls to these functions, such tests would fail.)

The facilities we use to perform this memory checking are not compatible with memcheck (valgrind), because memcheck uses its own versions of the memory management functions, that themselves use some memory in the heap. Consequently, if you run any tests that use our memory checking functions under valgrind, the test will appear to fail with a memory leak, even if your code does not have memory leaks. You can use either our memory checking functions with a program, or valgrind with it, but not both at the same time, or they will give incorrect results. Appendix B describes how to easily use valgrind in this project.

The functions discussed in this section are for tests of your code to use. Do not try to call them from your graph functions– this won’t work. And since your code in string-graph.c will not be calling these functions, your string-graph.c should not include memory-functions.h. (Any of your own tests that want to check the correctness of the heap will include memory-functions.h, and will have to be linked with memory-functions.o.)

• Development procedure review

A.1 Obtaining the project files, compiling, checking your results, and submitting

Log into the Grace machines and use commands similar to those from before:

cd ~/216

tar -zxvf ~/216public/project08/project08.tgz

This will create a directory project08 that contains the necessary files for the project, including the header files string-graph.h, compare-vertex-lists.h, and memory-functions.h, the object files compare-vertex-lists.o and memory-functions.o, and the public tests. As was discussed above, copy both of your string-graph.c and string-graph-datastructure.h files from your project07 directory (or copy the corrected versions from the new copy of your project07 directory if you followed the procedure in Section 1.1 above) to the project08 directory after extracting it from the project tarfile, so you can add the new functions in it.

As in Project #7 you will not be compiling your code from the command line; you will use make and your makefile to compile everything. diff can be used as before to check whether your code passes a public test or not, for example:

make public01.x

public01.x | diff – public01.output

(You can also run make from Emacs if desired.)

Note that your makefile cannot run each test when building it, because this will probably not work on the submit server. If you want to create a separate target in your makefile that runs the tests this will not cause a problem on the submit server (although a better way to do this will be explained in discussion section soon).

Running submit from the project directory will submit your project, but you first must make sure your makefile works and you have passed all the public tests, by compiling them– using your makefile– and running them yourself.

Unless you have versions of all required functions that will at least compile, your program will fail to compile at all on the submit server. (Suggestion– create skeleton versions of all functions when starting to code, that just have an appropriate return statement.)

A.2 Grading criteria

Your grade for this project will be based on:

public tests	40 points
secret tests	45 points
programming style	15 points

Some secret tests may test your makefile. Section 4 of Project #7 explains the requirements for your makefile, so review that to ensure that you are satisfying them, in case they are tested by secret tests in this project.

• Project–specific requirements, suggestions, and other notes

• • The data structure requirements are the same in this project as in Project #7. Be sure you have followed them– reread them in the Project #7 assignment.

• • Note that different public tests in this project use different things and include different header files, so different tests will have different dependencies in your makefile, and different files will have to be linked to create the executables for different tests.

We emphasize again that you should not wait to write your makefile. Write it first– before you even start writing the graph functions. This will avoid having to type commands for compiling the public tests, but more importantly, using your makefile all during development, every time you compile your code, will allow you to ensure it works correctly before you submit. You can copy your makefile from your project07 directory to the directory for this project as a starting point, but the tests in this project will have different dependencies than they did in Project #7, and different files will have to be linked to create their executables than in Project #7.

• • Now that the preprocessor has been covered, and the conditional compilation directives that are actually always used in C header files have been explained in class, you must now have correct conditional compilation directives in your header file string-graph-datastructure.h.

(Note that part of using conditional compilation correctly is that you must spell the name of the preprocessor symbol used for conditional compilation either as described in class and in the lecture slides, or in the form that the Reek text uses, or you may lose some credit.)

• • Since one header file in this project includes another one, your makefile must now use one of the approaches recently discussed in class for handling dependencies in this situation, otherwise it may not perform needed recompilations. (If your makefile doesn’t use one of these approaches you might lose a few points due to failing a secret test.)

• • As mentioned earlier, you cannot use valgrind together with our memory checking functions. We want to make it easy for you to use valgrind if you have memory problems that arise while writing this project, so we wrote the tests to allow you to easily turn off our memory checking, by just compiling with the preprocessor symbol

ENABLE_VALGRIND defined.

To be able to use valgrind (this assumes your Makefile is correct):

– Add a definition of ENABLE_VALGRIND (e.g., -D ENABLE_VALGRIND) to the compiler options in your Makefile. (Recall you also have to add the -g option to be able to use valgrind, as well as gdb.)

– Force all the tests to be recompiled using make clean (or touching all source/header files would also work), and recompile everything (our tests and yours).

– Now you can use valgrind on any test. When you’ve found the problem and are done using valgrind, don’t forget to remove the definition of ENABLE_VALGRIND from the compilation options in your makefile and recompile everything again, otherwise you will not be running the same versions of the tests as the submit server is, because it will be using our memory checking for some tests. After re–enabling our memory checking by removing -D ENABLE_VALGRIND and recompiling, rerun the tests to confirm that they pass.

– When running valgrind, add the option –leak-check=no to turn off checking for memory leaks for any test that is not calling graph_delete() on any String_graph variables when they are no longer needed and is also not calling free_vertex_name_list() on any pointers returned by get_vertex_list() and and get_neighbor_names() when they are no longer needed.

• Do not write code using loops (or recursion) that has the same effect as any string library functions. If you need to perform an operation on strings and there is a string library function already written that accomplishes that task, you are expected to use it, otherwise you will lose credit.

• You will lose credit if you cast the return value of the memory allocation functions. Besides being completely unnecessary, in some cases this can mask certain errors in code.

• For this project you will lose one point from your final project score for every submission that you make in excess of four submissions, for any reason.

• You cannot modify anything in the header files string-graph.h, compare-vertex-lists.h, or memory-functions.h, or add anything to them, because your submission will be compiled on the sub-mit server using our versions of these files. You cannot write any new header files of your own other than string-graph-datastructure.h. Your code may not comprise any source (.c) files other than string-graph.c, so all your code must be in that file.

• Any helper functions that you write in string-graph.c, whose prototypes are not already in string-graph.h, will be “private”, so they should be declared static, and their prototypes should be placed at the top of string-graph.c, not in string-graph.h or string-graph-datastructure.h.

• If you have a problem with your code and have to come to the TAs’ office hours for debugging help you must come with tests you have written yourself that illustrate the problem (not the public tests), what cases it occurs in, and what cases it doesn’t occur in. In particular you will need to show the smallest test you were able to write that illustrates the problem, so whatever the cause is can be narrowed down as much as possible before the TAs even start helping you. You must also have used the gdb debugger, explained in discussion section, and be prepared to show the TAs how you attempted to debug your program using it and what results you got.

And besides having used gdb, you must have also run memcheck (valgrind) if your code has any bugs, and be able to understand the results it shows.

• Recall that the course project policies handout on ELMS says that all your projects must work on at least half of the public tests (by the end of the semester) in order for you to be eligible to get a C− or better in the course.

• Academic integrity

Please carefully read the academic honesty section of the syllabus. Any evidence of impermissible cooperation on projects, use of disallowed materials or resources, publicly providing others access to your project code online, or unauthorized use of computer accounts, will be submitted to the Office of Student Conduct, which could result in an XF for the course, or suspension or expulsion from the University. Be sure you understand what you are and what you are not permitted to do in regards to academic integrity when it comes to projects. These policies apply to all students, and the Student Honor Council does not consider lack of knowledge of the policies to be a defense for violating them. More information is in the course syllabus – please review it now.

The academic integrity requirements also apply to any test data for projects, which must be your own original work. Exchanging test data or working together to write test cases is also prohibited.

© 2023 L. Herman; all rights reserved 6