GNU libavl 2.0.1
5.14.1 Testing BSTs
As suggested above, the main way we will test the BST routines is by
using them and checking the results, with checks performed by slow but
simple routines. The idea is that bugs in the BST routines are unlikely
to be mirrored in the check routines, and vice versa. This way,
identical results from the BST and checks tend to indicate that both
implementations are correct.
The main test routine is designed to exercise as many of the BST
functions as possible. It starts by creating a BST and inserting nodes
into it, then deleting the nodes. Midway, various traversals are
tested, including the ability to traverse a tree while its content is
changing. After each operation that modifies the tree, its structure
and content are verified for correspondence with expectations. The
function for copying a BST is also tested. This function, test(), has
the following outline:
| | /* Tests tree functions.
insert[] and delete[] must contain some permutation of values
0...n - 1.
Uses allocator as the allocator for tree and node data.
Higher values of verbosity produce more debug output. */
int
test_correctness (struct libavl_allocator *allocator,
int insert[], int delete[], int n, int verbosity)
{
struct bst_table *tree;
int okay = 1;
int i;
<@xref{\NODE\, , Test creating a BST and inserting into it.>,102}
<@xref{\NODE\, , Test BST traversal during modifications.>,103}
<@xref{\NODE\, , Test deleting nodes from the BST and making copies of it.>,105}
<@xref{\NODE\, , Test deleting from an empty tree.>,107}
<@xref{\NODE\, , Test destroying the tree.>,108}
return okay;
}
|
This code is included in @refalso{98
| | int test_correctness (struct libavl_allocator *allocator,
int insert[], int delete[], int n, int verbosity);
|
See also @refalso{123
This code is included in @refalso{99
The first step is to create a BST and insert items into it in the order
specified by the caller. We use the comparison function
compare_ints() from <@xref{\NODE\, , Comparison function for int.>s,3} to put the
tree's items into ordinary numerical order. After each insertion we
call verify_tree(), which we'll write later and which checks that the
tree actually contains the items that it should:
| | tree = bst_create (compare_ints, NULL, allocator);
if (tree == NULL)
{
if (verbosity >= 0)
printf ("Outofmemorycreatingtree.\n");
return 1;
}
for (i = 0; i < n; i++)
{
if (verbosity >= 2)
printf ("Inserting%d...\n", insert[i]);
/* Add the ith element to the tree. */
{
void **p = bst_probe (tree, &insert[i]);
if (p == NULL)
{
if (verbosity >= 0)
printf ("Outofmemoryininsertion.\n");
bst_destroy (tree, NULL);
return 1;
}
if (*p != &insert[i])
printf ("Duplicateitemintree!\n");
}
if (verbosity >= 3)
print_whole_tree (tree, "Afterward");
if (!verify_tree (tree, insert, i + 1))
return 0;
}
|
This code is included in @refalso{100
If the tree is being modified during traversal, that causes a little
more stress on the tree routines, so we should test this specially. We
initialize one traverser, x, at a selected item, then delete and
reinsert a different item in order to invalidate that traverser. We
make a copy, y, of the traverser in order to check that bst_t_copy()
works properly and initialize a third traverser, z, with the inserted
item. After the deletion and reinsertion we check that all three of the
traversers behave properly.
| | for (i = 0; i < n; i++)
{
struct bst_traverser x, y, z;
int *deleted;
if (insert[i] == delete[i])
continue;
if (verbosity >= 2)
printf ("Checkingtraversalfromitem%d...\n", insert[i]);
if (bst_t_find (&x, tree, &insert[i]) == NULL)
{
printf ("Can'tfinditem%dintree!\n", insert[i]);
continue;
}
okay &= check_traverser (&x, insert[i], n, "Predeletion");
if (verbosity >= 3)
printf ("Deletingitem%d.\n", delete[i]);
deleted = bst_delete (tree, &delete[i]);
if (deleted == NULL || *deleted != delete[i])
{
okay = 0;
if (deleted == NULL)
printf ("Deletionfailed.\n");
else
printf ("Wrongnode%dreturned.\n", *deleted);
}
bst_t_copy (&y, &x);
if (verbosity >= 3)
printf ("Re-insertingitem%d.\n", delete[i]);
if (bst_t_insert (&z, tree, &delete[i]) == NULL)
{
if (verbosity >= 0)
printf ("Outofmemoryre-insertingitem.\n");
bst_destroy (tree, NULL);
return 1;
}
okay &= check_traverser (&x, insert[i], n, "Postdeletion");
okay &= check_traverser (&y, insert[i], n, "Copied");
okay &= check_traverser (&z, delete[i], n, "Insertion");
if (!verify_tree (tree, insert, n))
return 0;
}
|
This code is included in @refalso{100
The check_traverser() function used above checks that a traverser
behaves properly, by checking that the traverser is at the correct item
and that the previous and next items are correct as well.
| | /* Checks that the current item at trav is i
and that its previous and next items are as they should be.
label is a name for the traverser used in reporting messages.
There should be n items in the tree numbered 0...n - 1.
Returns nonzero only if there is an error. */
static int
check_traverser (struct bst_traverser *trav, int i, int n, const char *label)
{
int okay = 1;
int *cur, *prev, *next;
prev = bst_t_prev (trav);
if ((i == 0 && prev != NULL)
|| (i > 0 && (prev == NULL || *prev != i - 1)))
{
printf ("%straverseraheadof%d,butshouldbeaheadof%d.\n",
label, prev != NULL ? *prev : -1, i == 0 ? -1 : i - 1);
okay = 0;
}
bst_t_next (trav);
cur = bst_t_cur (trav);
if (cur == NULL || *cur != i)
{
printf ("%straverserat%d,butshouldbeat%d.\n",
label, cur != NULL ? *cur : -1, i);
okay = 0;
}
next = bst_t_next (trav);
if ((i == n - 1 && next != NULL)
|| (i != n - 1 && (next == NULL || *next != i + 1)))
{
printf ("%straverserbehind%d,butshouldbebehind%d.\n",
label, next != NULL ? *next : -1, i == n - 1 ? -1 : i + 1);
okay = 0;
}
bst_t_prev (trav);
return okay;
}
|
This code is included in @refalso{98
We also need to test deleting nodes from the tree and making copies of a
tree. Here's the code to do that:
| | for (i = 0; i < n; i++)
{
int *deleted;
if (verbosity >= 2)
printf ("Deleting%d...\n", delete[i]);
deleted = bst_delete (tree, &delete[i]);
if (deleted == NULL || *deleted != delete[i])
{
okay = 0;
if (deleted == NULL)
printf ("Deletionfailed.\n");
else
printf ("Wrongnode%dreturned.\n", *deleted);
}
if (verbosity >= 3)
print_whole_tree (tree, "Afterward");
if (!verify_tree (tree, delete + i + 1, n - i - 1))
return 0;
if (verbosity >= 2)
printf ("Copyingtreeandcomparing...\n");
/* Copy the tree and make sure it's identical. */
{
struct bst_table *copy = bst_copy (tree, NULL, NULL, NULL);
if (copy == NULL)
{
if (verbosity >= 0)
printf ("Outofmemoryincopy\n");
bst_destroy (tree, NULL);
return 1;
}
okay &= compare_trees (tree->bst_root, copy->bst_root);
bst_destroy (copy, NULL);
}
}
|
This code is included in @refalso{100
The actual comparison of trees is done recursively for simplicity:
| | /* Compares binary trees rooted at a and b,
making sure that they are identical. */
static int
compare_trees (struct bst_node *a, struct bst_node *b)
{
int okay;
if (a == NULL || b == NULL)
{
assert (a == NULL && b == NULL);
return 1;
}
if (*(int *) a->bst_data != *(int *) b->bst_data
|| ((a->bst_link[0] != NULL) != (b->bst_link[0] != NULL))
|| ((a->bst_link[1] != NULL) != (b->bst_link[1] != NULL)))
{
printf ("Copiednodesdiffer:a=%db=%da:",
*(int *) a->bst_data, *(int *) b->bst_data);
if (a->bst_link[0] != NULL)
printf ("l");
if (a->bst_link[1] != NULL)
printf ("r");
printf ("b:");
if (b->bst_link[0] != NULL)
printf ("l");
if (b->bst_link[1] != NULL)
printf ("r");
printf ("\n");
return 0;
}
okay = 1;
if (a->bst_link[0] != NULL)
okay &= compare_trees (a->bst_link[0], b->bst_link[0]);
if (a->bst_link[1] != NULL)
okay &= compare_trees (a->bst_link[1], b->bst_link[1]);
return okay;
}
|
This code is included in @refalso{98
As a simple extra check, we make sure that attempting to delete from
an empty tree fails in the expected way:
| | if (bst_delete (tree, &insert[0]) != NULL)
{
printf ("Deletionfromemptytreesucceeded.\n");
okay = 0;
}
|
This code is included in @refalso{100
Finally, we're done with the tree and can get rid of it.
| | /* Test destroying the tree. */
bst_destroy (tree, NULL);
|
This code is included in @refalso{100
Exercises:
1. Which functions in <@xref{\NODE\, , bst.c.>,25} are not exercised by test()?
[answer]
2. Some errors within test() just set the okay flag to zero, whereas
others cause an immediate unsuccessful return to the caller without
performing any cleanup. A third class of errors causes cleanup followed
by a successful return. Why and how are these distinguished?
[answer]
