www.delorie.com/gnu/docs/avl/libavl_77.html

search

	Buy GNU books!

GNU libavl 2.0.1

5.14 Testing

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 <@xref{\NODE\, , 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:(8)

• 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, <@xref{\NODE\, , test.c.>,97}, which has the following structure:

<@xref{\NODE\, , 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" <@xref{\NODE\, , Test declarations.>,121} <@xref{\NODE\, , Test utility functions.>,134} <@xref{\NODE\, , Memory tracker.>,126} <@xref{\NODE\, , Option parser.>,586} <@xref{\NODE\, , Command line parser.>,589} <@xref{\NODE\, , Insertion and deletion order generation.>,642} <@xref{\NODE\, , Random number seeding.>,643} <@xref{\NODE\, , Test main program.>,140}

The code specifically for testing BSTs goes into <@xref{\NODE\, , bst-test.c.>,98}, outlined like this:

<@xref{\NODE\, , License.>,1} #include <assert.h> #include <limits.h> #include <stdio.h> #include "bst.h" #include "test.h" <@xref{\NODE\, , BST print function.>,119} <@xref{\NODE\, , BST traverser check function.>,104} <@xref{\NODE\, , Compare two BSTs for structure and content.>,106} <@xref{\NODE\, , Recursively verify BST structure.>,113} <@xref{\NODE\, , BST verify function.>,109} <@xref{\NODE\, , BST test function.>,100} <@xref{\NODE\, , BST overflow test function.>,122}

The interface between <@xref{\NODE\, , test.c.>,97} and <@xref{\NODE\, , bst-test.c.>,98} is contained in <@xref{\NODE\, , test.h.>,99}:

<@xref{\NODE\, , License.>,1} #ifndef TEST_H #define @cindex TEST_H macro TEST_H 1 <@xref{\NODE\, , Memory allocator.>,5} <@xref{\NODE\, , 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 section B. Supplementary Code).

5.14.1 Testing BSTs
5.14.2 Test Set Generation
5.14.3 Testing Overflow
5.14.4 Memory Manager
5.14.5 User Interaction
5.14.6 Utility Functions
5.14.7 Main Program