Testing BSTs - GNU libavl 2.0.2

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:

100. <BST test function 100> =
/* 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;

  <Test creating a BST and inserting into it 102>
  <Test BST traversal during modifications 103>
  <Test deleting nodes from the BST and making copies of it 105>
  <Test deleting from an empty tree 107>
  <Test destroying the tree 108>

  return okay;
}

This code is included in 98, 186, 238, 330, 368, 449, 482, 548, and 583.

101. <Test prototypes 101> =
int test_correctness (struct libavl_allocator *allocator,
                      int insert[], int delete[], int n, int verbosity);

See also 123 and 135.

This code is included in 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 <Comparison function for ints 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:

102. <Test creating a BST and inserting into it 102> =
tree = bst_create (compare_ints, NULL, allocator);
if (tree == NULL) 
  {
    if (verbosity >= 0) 
      printf ("  Out of memory creating tree.\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 ("    Out of memory in insertion.\n");
          bst_destroy (tree, NULL);
          return 1;
        }
      if (*p != &insert[i]) 
        printf ("    Duplicate item in tree!\n");
    }

    if (verbosity >= 3) 
      print_whole_tree (tree, "    Afterward");

    if (!verify_tree (tree, insert, i + 1))
      return 0;
  }

This code is included in 100 and 295.

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.

103. <Test BST traversal during modifications 103> =
for (i = 0; i < n; i++) 
  {
    struct bst_traverser x, y, z;
    int *deleted;

    if (insert[i] == delete[i])
      continue;

    if (verbosity >= 2)
      printf ("   Checking traversal from item %d...\n", insert[i]);

    if (bst_t_find (&x, tree, &insert[i]) == NULL) 
      {
        printf ("    Can't find item %d in tree!\n", insert[i]);
        continue;
      }

    okay &= check_traverser (&x, insert[i], n, "Predeletion");

    if (verbosity >= 3) 
      printf ("    Deleting item %d.\n", delete[i]);

    deleted = bst_delete (tree, &delete[i]);
    if (deleted == NULL || *deleted != delete[i]) 
      {
        okay = 0;
        if (deleted == NULL)
          printf ("    Deletion failed.\n");
        else 
          printf ("    Wrong node %d returned.\n", *deleted);
      }

    bst_t_copy (&y, &x);

    if (verbosity >= 3) 
      printf ("    Reinserting item %d.\n", delete[i]);
    if (bst_t_insert (&z, tree, &delete[i]) == NULL) 
      {
        if (verbosity >= 0) 
          printf ("    Out of memory reinserting item.\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 100 and 295.

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.

104. <BST traverser check function 104> =
/* 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 ("   %s traverser ahead of %d, but should be ahead of %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 ("   %s traverser at %d, but should be at %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 ("   %s traverser behind %d, but should be behind %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 98, 186, 238, 290, 330, 368, 411, 449, 482, 515, 548, and 583.

We also need to test deleting nodes from the tree and making copies of a tree. Here's the code to do that:

105. <Test deleting nodes from the BST and making copies of it 105> =
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 ("    Deletion failed.\n");
        else 
          printf ("    Wrong node %d returned.\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 ("  Copying tree and comparing...\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 ("  Out of memory in copy\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 100 and 295.

The actual comparison of trees is done recursively for simplicity:

106. <Compare two BSTs for structure and content 106> =
/* 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 (" Copied nodes differ: a=%d b=%d a:",
              *(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 98.

As a simple extra check, we make sure that attempting to delete from an empty tree fails in the expected way:

107. <Test deleting from an empty tree 107> =
if (bst_delete (tree, &insert[0]) != NULL) 
  {
    printf (" Deletion from empty tree succeeded.\n");
    okay = 0;
  }

This code is included in 100.

Finally, we're done with the tree and can get rid of it.

108. <Test destroying the tree 108> =
/* Test destroying the tree. */
bst_destroy (tree, NULL);

This code is included in 100 and 295.

Exercises:

1. Which functions in <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]