7.12 Testing [ToC] [Index]     [Skip Back]     [Prev] [Up] [Next]

There's little new in the testing code. We do add an test for tbst_balance(), because none of the existing tests exercise it. This test doesn't check that tbst_balance() actually balances the tree, it just verifies that afterwards the tree contains the items it should, so to be certain that balancing is correct, turn up the verbosity and look at the trees printed.

Function print_tree_structure() prints thread node numbers preceded by `>', with null threads indicated by `>>'. This notation is compatible with the plain text output format of the texitree program used to draw the binary trees in this book. (It will cause errors for PostScript output because it omits node names.) 

292. <tbst-test.c 292> =
<Program License 2>
#include <assert.h>
#include <limits.h>
#include <stdio.h>
#include "tbst.h"
#include "test.h"

<TBST print function 293>
<BST traverser check function; bst => tbst 105>
<Compare two TBSTs for structure and content 294>
<Recursively verify TBST structure 295>
<TBST verify function 296>
<TBST test function 297>
<BST overflow test function; bst => tbst 123>


293. <TBST print function 293> =
void 
print_tree_structure (struct tbst_node *node, int level) 
{
  int i;

  if (level > 16) 
    {
      printf ("[...]");
      return;
    }

  if (node == NULL) 
    {
      printf ("<nil>");
      return;
    }

  printf ("%d(", node->tbst_data ? *(int *) node->tbst_data : -1);

  for (i = 0; i <= 1; i++) 
    {
      if (node->tbst_tag[i] == TBST_CHILD) 
        {
          if (node->tbst_link[i] == node) 
            printf ("loop");
          else 
            print_tree_structure (node->tbst_link[i], level + 1);
        }
      else if (node->tbst_link[i] != NULL)
        printf (">%d", 
                (node->tbst_link[i]->tbst_data
                ? *(int *) node->tbst_link[i]->tbst_data : -1));
      else 
        printf (">>");

      if (i == 0) 
        fputs (", ", stdout);
    }

  putchar (')');
}

void 
print_whole_tree (const struct tbst_table *tree, const char *title) 
{
  printf ("%s: ", title);
  print_tree_structure (tree->tbst_root, 0);
  putchar ('\n');
}

This code is included in 292, 332, and 370. 

294. <Compare two TBSTs for structure and content 294> =
static int 
compare_trees (struct tbst_node *a, struct tbst_node *b) 
{
  int okay;

  if (a == NULL || b == NULL) 
    {
      if (a != NULL || b != NULL) 
        {
          printf (" a=%d b=%d\n",
                  a ? *(int *) a->tbst_data : -1, 
                  b ? *(int *) b->tbst_data : -1);
          assert (0);
        }
      return 1;
    }
  assert (a != b);

  if (*(int *) a->tbst_data != *(int *) b->tbst_data
      || a->tbst_tag[0] != b->tbst_tag[0] 
      || a->tbst_tag[1] != b->tbst_tag[1]) 
    {
      printf (" Copied nodes differ: a=%d b=%d a:",
              *(int *) a->tbst_data, *(int *) b->tbst_data);

      if (a->tbst_tag[0] == TBST_CHILD) 
        printf ("l");
      if (a->tbst_tag[1] == TBST_CHILD) 
        printf ("r");

      printf (" b:");
      if (b->tbst_tag[0] == TBST_CHILD) 
        printf ("l");
      if (b->tbst_tag[1] == TBST_CHILD) 
        printf ("r");

      printf ("\n");
      return 0;
    }

  if (a->tbst_tag[0] == TBST_THREAD)
    assert ((a->tbst_link[0] == NULL) != (a->tbst_link[0] != b->tbst_link[0]));
  if (a->tbst_tag[1] == TBST_THREAD)
    assert ((a->tbst_link[1] == NULL) != (a->tbst_link[1] != b->tbst_link[1]));

  okay = 1;
  if (a->tbst_tag[0] == TBST_CHILD)
    okay &= compare_trees (a->tbst_link[0], b->tbst_link[0]);
  if (a->tbst_tag[1] == TBST_CHILD)
    okay &= compare_trees (a->tbst_link[1], b->tbst_link[1]);
  return okay;
}

This code is included in 292. 

295. <Recursively verify TBST structure 295> =
static void 
recurse_verify_tree (struct tbst_node *node, int *okay, size_t *count, 
                     int min, int max) 
{
  int d;                /* Value of this node's data. */
  size_t subcount[2];   /* Number of nodes in subtrees. */

  if (node == NULL) 
    {
      *count = 0;
      return;
    }
  d = *(int *) node->tbst_data;

  <Verify binary search tree ordering 115>

  subcount[0] = subcount[1] = 0;
  if (node->tbst_tag[0] == TBST_CHILD)
    recurse_verify_tree (node->tbst_link[0], okay, &subcount[0], min, d - 1);
  if (node->tbst_tag[1] == TBST_CHILD)
    recurse_verify_tree (node->tbst_link[1], okay, &subcount[1], d + 1, max);
  *count = 1 + subcount[0] + subcount[1];
}

This code is included in 292. 

296. <TBST verify function 296> =
static int 
verify_tree (struct tbst_table *tree, int array[], size_t n) 
{
  int okay = 1;

  <Check tree->bst_count is correct; bst => tbst 111>

  if (okay) 
    { 
      <Check BST structure; bst => tbst 112> 
    }

  if (okay) 
    { 
      <Check that the tree contains all the elements it should; bst => tbst 116> 
    }

  if (okay) 
    { 
      <Check that forward traversal works; bst => tbst 117> 
    }

  if (okay) 
    { 
      <Check that backward traversal works; bst => tbst 118> 
    }

  if (okay) 
    { 
      <Check that traversal from the null element works; bst => tbst 119> 
    }

  return okay;
}

This code is included in 292. 

297. <TBST test function 297> =
int 
test_correctness (struct libavl_allocator *allocator,
                 int insert[], int delete[], int n, int verbosity) 
{
  struct tbst_table *tree;
  int okay = 1;
  int i;

  <Test creating a BST and inserting into it; bst => tbst 103>
  <Test BST traversal during modifications; bst => tbst 104>
  <Test deleting nodes from the BST and making copies of it; bst => tbst 106>
  <Test destroying the tree; bst => tbst 109>

  <Test TBST balancing 298>

  return okay;
}

This code is included in 292, 413, and 517. 

298. <Test TBST balancing 298> =
/* Test tbst_balance(). */
if (verbosity >= 2) 
  printf ("  Testing balancing...\n");

tree = tbst_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++) 
  {
    void **p = tbst_probe (tree, &insert[i]);
    if (p == NULL) 
      {
        if (verbosity >= 0) 
          printf ("    Out of memory in insertion.\n");
        tbst_destroy (tree, NULL);
        return 1;
      }
    if (*p != &insert[i]) 
      printf ("    Duplicate item in tree!\n");
  }

if (verbosity >= 4) 
  print_whole_tree (tree, "    Prebalance");
tbst_balance (tree);
if (verbosity >= 4) 
  print_whole_tree (tree, "    Postbalance");

if (!verify_tree (tree, insert, n))
  return 0;

tbst_destroy (tree, NULL);

This code is included in 297.

Prev: 7.11.2 From Vine to Balanced Tree Up: 7 Threaded Binary Search Trees 8 Threaded AVL Trees Next