How to Check Sort Function with GDB

Question

I've implemented my sort function in helpers.c and I have no clue as to how to check if it does actually sort. I've tried to call on the printf function so it can print out the sorted array, but find.c can't be edited (clever, cs50 staff).

I'm trying to use gdb and I can't seem to run pipe generate's output as input into find nor can I actually print the sorted array with find itself by inputting my own numbers.

How do I navigate gdb so I can see if my sort function works?

Answer 1

This can be tricky. I'll explain how to use GDB, and then show another way.

GDB

The commands below should be entered in a terminal window.

First, compile your program using make, then run GDB and tell it to load the find program, like this:

gdb ./find

GDB will start and load the find program. From this point on you will be 'inside' the GDB program, and any commands you enter will be instructions to GDB. Note that the find program won't actually be running yet.

You will need to set a breakpoint in order to pause the program so that you can inspect the result of the sort function. The sort() function is a good place to set a breakpoint, because you can step through the code as it executes, and then inspect the values when the function completes. Set a breakpoint on the sort() function like this:

break sort

This lets GDB know to pause the program when that function is called. GDB will output something like:

Breakpoint 1 at 0x8048a43: file helpers.c, line 129.

Now you can run the find program. The program requires one command line argument, which is a number to search for:

run 97

This will run the find program, and pass in the number 97 as the number to search for. GDB will output this:

Running program: /home/jharvard/cs50/pset3/find/find 97

When the program runs it will start prompting you for input. Enter some numbers. A good set to test with would include negative numbers, zero, and duplicates. When you are done entering numbers, enter Ctrl+D to perform the search. As soon as you do this you should see some output like this:

Breakpoint 1, sort (values=0xbffbeff0, n=3) at helpers.c:129
129    if (n < 2)

This is GDB letting you know that the program has been paused at the line you set the breakpoint at earlier. Entering the list command will show you a several lines of code around the point where the program is paused. You can now continue to execute the rest of the sort() function, one line at a time, with the next command.

next

GDB will execute and display the next line of code, e.g.:

137    bubble_sort(values, n)

In my code, the line number jumped from 129 to 137 because it skipped over the body of the if statement.

You can continue executing lines of code, inspecting the values of the variables. Useful commands are print and info locals. The print command will display the value of a single variable, e.g.:

140    print values[0]

GDB will output something like:

$1 = 2 

The actual value is the number to the right of the = sign, so in this case, values[0] contains the number 2.

The info locals command will output the values for all the variables in the local scope.

A shortcut in GDB is to just keep hitting enter to repeat the previous command.

Keep executing the code line by line, until you reach the last line of the sort() function. Compare the line number to your source code, and be careful not to step too far as this will return from the function. At this point you can inspect each of the numbers in the values array to ensure that they are in the correct order, e.g.:

147    print values[0]
$1 = 20
147    print values[1]
$2 = 58
147    print values[2]
$3 = 97
147    print values[3]
$4 = 113

Test function

GDB is great for narrowing down on a bug, but manually testing with GDB can become tedious. One solution is to write a small function that checks that a list is sorted. The function simply needs to check that each value is greater than, or equal to, the value before it.

bool check_sorted(int values[], int n)
{
    // list contains 0 or 1 element(s), which cannot be 'unsorted'
    if (n < 2)
    {
        return true;
    }

    // note that loop to n - 1
    for (int i = 0, m = n - 1; i < m; i++)
    {
        // return false if next value is greater than current value  
        if (values[i] > values[i + 1])
        {
            return false;
        }
    }

    // all values are in expected order
    return true;
}

This function can used at the end of the sort() function during development. You can inspect the return value in GDB, or use a printf statement to display an error message if the function returns false.

Another idea would be to use an assert statement to quit the program if the sort function returns an incorrect result. Use man assert from the command line for more info.

Note that this won't detect if the sort function is corrupting the output (like losing values and so on), but you can write another function to do that.

Unit test

A unit test is similar to the test function mentioned above. The difference is that you would write an entirely separate program, with the sole purpose to test the sort() function.

The general idea is that the test program would contain input data, as well as the corresponding expected 'correct' output. The input data would be fed into the sort function, and the resulting output compared to the known result. As long as the sort function returns the same answers that the test is expecting, it is assumed that it will return correct results given other input data as well. If the sort function returns an incorrect result, it indicates a bug which needs to be fixed.

Print values

If you just want to see the values during testing, a simple for loop with a printf statement should suffice:

void print_values(int values[], int n) 
{
    for (int i = 0; i < n; i++) 
    {
        printf("value [%d] = %d\n", i, values[i]);
    }
}

This code can be at the end of the sort function to inspect the results. However, if the sort function is coded so that it returns before this is executed, it may be necessary to place the actual sorting code into another function called by sort, and then inspect the results of that function.

Here is an example of how the all these examples might be used together:

void sort(int values[], int n)
{
    // perform actual sort
    bubble_sort(values, n);

    // print the sorted values
    print_values(values, n);

    // check sort order
    if (check_sorted(values, n)) 
    {
        printf("List is sorted.\n");
    }
    else 
    {
        printf("Error: List is not sorted.\n");
    }
}