Testing BST Functions - GNU libavl 2.0.2

Whew! We're finally done with building functions for performing BST operations. But we haven't tested any of our code. Testing is an essential step in writing programs, because untested software cannot be assumed to work.

Let's build a test program that exercises all of the functions we wrote. We'll also do our best to make parts of it generic, so that we can reuse test code in later chapters when we want to test other BST-based structures.

The first step is to figure out how to test the code. One goal in testing is to exercise as much of the code as possible. Ideally, every line of code would be executed sometime during testing. Often, this is difficult or impossible, but the principle remains valid, with the goal modified to testing as much of the code as possible.

In applying this principle to the BST code, we have to consider why each line of code is executed. If we look at the code for most functions in <bst.c 25>, we can see that, if we execute them for any BST of reasonable size, most or all of their code will be tested.

This is encouraging. It means that we can just construct some trees and try out the BST functions on them, check that the results make sense, and have a pretty good idea that they work. Moreover, if we build trees in a random fashion, and delete their nodes in a random order, and do it several times, we'll even have a good idea that the bst_probe() and bst_delete() cases have all come up and worked properly. (If you want to be sure, then you can insert printf() calls for each case to record when they trip.) This is not the same as a proof of correctness, but proofs of correctness can only be constructed by computer scientists with fancy degrees, not by mere clever programmers.

There are three notably missing pieces of code coverage if we just do the above. These are stack overflow handling, memory allocation failure handling, and traverser code to deal with modified trees. But we can mop up these extra problems with a little extra effort:¹

Stack overflow handling can be tested by forcing the stack to overflow. Stack overflow can occur in many places, so for best effect we must test each possible spot. We will write special tests for these problems.
Memory allocation failure handling can be tested by simulating memory allocation failures. We will write a replacement memory allocator that “fails” after a specified number of calls. This allocator will also allow for memory leak detection.
Traverser code to deal with modified trees. This can be tested by modifying trees during traversal and making sure that the traversal functions still work as expected.

The testing code can be broken into the following groups of functions:

Testing and verification: These functions actually try out the BST routines and do their best to make sure that their results are correct.
Test set generation: Generates the order of node insertion and deletion, for use during testing.
Memory manager: Handles memory issues, including memory leak detection and failure simulation.
User interaction: Figures out what the user wants to test in this run.
Main program: Glues everything else together by calling functions in the proper order.
Utilities: Miscellaneous routines that don't fit comfortably into another category.

Most of the test code will also work nicely for testing other binary tree-based structures. This code is grouped into a single file, <test.c 97>, which has the following structure:

97. <test.c 97> =
<License 1>
#include <assert.h>
#include <limits.h>
#include <stdarg.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include "test.h"

<Test declarations 121>
<Test utility functions 134>
<Memory tracker 126>
<Option parser 586>
<Command line parser 589>
<Insertion and deletion order generation 642>
<Random number seeding 643>
<Test main program 140>

The code specifically for testing BSTs goes into <bst-test.c 98>, outlined like this:

98. <bst-test.c 98> =
<License 1>
#include <assert.h>
#include <limits.h>
#include <stdio.h>
#include "bst.h"
#include "test.h"

<BST print function 119>
<BST traverser check function 104>
<Compare two BSTs for structure and content 106>
<Recursively verify BST structure 113>
<BST verify function 109>
<BST test function 100>
<BST overflow test function 122>

The interface between <test.c 97> and <bst-test.c 98> is contained in <test.h 99>:

99. <test.h 99> =
<License 1>
#ifndef TEST_H
#define TEST_H 1

<Memory allocator 5>
<Test prototypes 101>

#endif /* test.h */

Although much of the test program code is nontrivial, only some of the interesting parts fall within the scope of this book. The remainder will be listed without comment or relegated to the exercises. The most tedious code is listed in an appendix (see Supplementary Code).

Footnotes

[1] Some might scoff at this amount of detail, calling it wasted effort, but this thorough testing in fact revealed a number of subtle bugs during development of libavl that had otherwise gone unnoticed.