Debugging with gdb

The goal of the following debugging exercises is not simply to find the errors; it is to learn about and use gdb. For each of the first two exercises, you should run the programs under the control of the gdb debugger, and use it to find the bugs. You should write about the experience. What debugger commands did you use? Why? What did they reveal? What were the bugs? Write your answer as a short essay, and turn it in along with a working copy of the program, in which you have fixed all bugs. For the third exercise, you should figure out what the bug is and write up your answer in a short essay; whether you use the debugger to help you find the problem is up to you. You can write up your essays separately, or you can include your essay about each program as a comment in the program source code.

Exercise 1: factorial.c. Compile the program factorial.c, using the -g option to include debugging information in the executable. Run the program and enter a (small) positive integer. The program gives an incorrect answer for the factorial of the input number. Use the debugger to find the errors.

Exercise 2: selection.c. Debug the program selection.c. This program tries to use the selection sort algorithm to sort an array. However, it crashes with a dreaded Segmentation Fault. Usually, to debug a segfault, you want to run the program under the debugger and let it crash. You can then use debugger commands to get information about the state of the program when it crashed. The backtrace command can be particularly useful.

After you have fixed the segmentation fault, you might find that the program still doesn't sort the array correctly. You should find and fix that bug too.

After selection.c correctly sorts the array, the program will go into an infinite loop when it tries to use the binary_search function. Use the debugger to find and fix the problem. Since you don't usually know where a program is going into an infinite loop, note that you can use Control-C inside gdb to pause the program. You can then inspect the state of the program, install breakpoints, and so on.

Exercise 3: insertion.c. For this exercise, you should explain the error in insertion.c. This program tries to use the insertion sort algorithm to sort an array. However, the result is not correct. Your job is to explain, clearly and completely, how and why the program produces the output that it does. You can use the debugger to help you, if you like, but you are not required to use it for this exercise.

Programming with Pointers

The file sort_tree.c contains an incomplete implementation of a binary sort tree of strings, and a main program that reads in a data file and uses the tree to sort the words from that file. There is a complete function for inserting an item into the tree, and an empty function for printing the contents of the tree. You should write the body of the tree_print function. This should be easy! It will only be a few lines long. You might want to test your function by adding a few strings to the tree by hand in the main program, and see if they get printed in the correct order.

But your main task is to write the body of the build_tree function. This function is supposed to add all of the words from the file to the tree. The file data has already been read into the program. The global variable data is a pointer to the start of the block of memory that holds the data. The global variable data_size is the number of bytes (that is, chars) in the data.

Read the comments on the program. Note that in the data, the end of a word is marked by a '\n' character, which has to be changed to a zero to comply with the convention for C strings. Also note that you should not put copies of the string into the tree. The tree will contain pointers into the existing block of data.