www.delorie.com/gnu/docs/avl/libavl_78.html   search  
 
Buy GNU books!

GNU libavl 2.0.1

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

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;
  &#60;@xref{\NODE\, , Test creating a BST and inserting into it.&#62;,102}
  &#60;@xref{\NODE\, , Test BST traversal during modifications.&#62;,103}
  &#60;@xref{\NODE\, , Test deleting nodes from the BST and making copies of it.&#62;,105}
  &#60;@xref{\NODE\, , Test deleting from an empty tree.&#62;,107}
  &#60;@xref{\NODE\, , Test destroying the tree.&#62;,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 &#60;@xref{\NODE\, , Comparison function for int.&#62;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-&#62;bst_root, copy-&#62;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-&#62;bst_data != *(int *) b-&#62;bst_data
      || ((a-&#62;bst_link[0] != NULL) != (b-&#62;bst_link[0] != NULL))
      || ((a-&#62;bst_link[1] != NULL) != (b-&#62;bst_link[1] != NULL))) 
    {
      printf ("Copiednodesdiffer:a=%db=%da:",
              *(int *) a-&#62;bst_data, *(int *) b-&#62;bst_data);
      if (a-&#62;bst_link[0] != NULL) 
        printf ("l");
      if (a-&#62;bst_link[1] != NULL) 
        printf ("r");
      printf ("b:");
      if (b-&#62;bst_link[0] != NULL) 
        printf ("l");
      if (b-&#62;bst_link[1] != NULL) 
        printf ("r");
      printf ("\n");
      return 0;
    }
  okay = 1;
  if (a-&#62;bst_link[0] != NULL) 
    okay &= compare_trees (a-&#62;bst_link[0], b-&#62;bst_link[0]);
  if (a-&#62;bst_link[1] != NULL) 
    okay &= compare_trees (a-&#62;bst_link[1], b-&#62;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 &#60;@xref{\NODE\, , bst.c.&#62;,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]

5.14.1.1 BST Verification  
5.14.1.2 Displaying BST Structures  

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

  webmaster   donations   bookstore     delorie software   privacy  
  Copyright © 2003   by The Free Software Foundation     Updated Jun 2003  

Please take a moment to fill out this visitor survey
You can help support this site by visiting the advertisers that sponsor it! (only once each, though)