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.) 

290. <tbst-test.c 290> =
<License 1>
#include <assert.h>
#include <limits.h>
#include <stdio.h>
#include "tbst.h"
#include "test.h"

<TBST print function 291>
<BST traverser check function; bst => tbst 104>
<Compare two TBSTs for structure and content 292>
<Recursively verify TBST structure 293>
<TBST verify function 294>
<TBST test function 295>
<BST overflow test function; bst => tbst 122>


291. <TBST print function 291> =
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 290, 330, and 368. 

292. <Compare two TBSTs for structure and content 292> =
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 290. 

293. <Recursively verify TBST structure 293> =
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 114>

  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 290. 

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

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

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

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

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

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

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

  return okay;
}

This code is included in 290. 

295. <TBST test function 295> =
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 102>
  <Test BST traversal during modifications; bst => tbst 103>
  <Test deleting nodes from the BST and making copies of it; bst => tbst 105>
  <Test destroying the tree; bst => tbst 108>

  <Test TBST balancing 296>

  return okay;
}

This code is included in 290, 411, and 515. 

296. <Test TBST balancing 296> =
/* 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 295.

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