10.10 Testing

There's nothing new or interesting in the test code.

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

<RTBST print function 414>
<BST traverser check function; bst => rtbst 105>
<Compare two RTBSTs for structure and content 415>
<Recursively verify RTBST structure 416>
<BST verify function; bst => rtbst 110>
<TBST test function; tbst => rtbst 297>
<BST overflow test function; bst => rtbst 123>

414. <RTBST print function 414> =
void 
print_tree_structure (struct rtbst_node *node, int level) 
{
  if (level > 16) 
    {
      printf ("[...]");
      return;
    }

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

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

  if (node->rtbst_link[0] != NULL)
    print_tree_structure (node->rtbst_link[0], level + 1);

  fputs (", ", stdout);

  if (node->rtbst_rtag == RTBST_CHILD) 
    {
      if (node->rtbst_link[1] == node) 
        printf ("loop");
      else 
        print_tree_structure (node->rtbst_link[1], level + 1);
    } 
  else if (node->rtbst_link[1] != NULL) 
    printf (">%d", 
            (node->rtbst_link[1]->rtbst_data
             ? *(int *) node->rtbst_link[1]->rtbst_data : -1));
  else 
    printf (">>");

  putchar (')');
}

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

This code is included in 413, 451, and 484.

415. <Compare two RTBSTs for structure and content 415> =
static int 
compare_trees (struct rtbst_node *a, struct rtbst_node *b) 
{
  int okay;

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

  if (*(int *) a->rtbst_data != *(int *) b->rtbst_data
      || a->rtbst_rtag != b->rtbst_rtag) 
    {
      printf (" Copied nodes differ: a=%d b=%d a:",
              *(int *) a->rtbst_data, *(int *) b->rtbst_data);

      if (a->rtbst_rtag == RTBST_CHILD) 
        printf ("r");

      printf (" b:");
      if (b->rtbst_rtag == RTBST_CHILD) 
        printf ("r");

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

  if (a->rtbst_rtag == RTBST_THREAD)
    assert ((a->rtbst_link[1] == NULL)
            != (a->rtbst_link[1] != b->rtbst_link[1]));

  okay = compare_trees (a->rtbst_link[0], b->rtbst_link[0]);
  if (a->rtbst_rtag == RTBST_CHILD)
    okay &= compare_trees (a->rtbst_link[1], b->rtbst_link[1]);
  return okay;
}

This code is included in 413.

416. <Recursively verify RTBST structure 416> =
static void 
recurse_verify_tree (struct rtbst_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->rtbst_data;

  <Verify binary search tree ordering 115>

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

This code is included in 413.

10.9 Balance

10 Right-Threaded Binary Search Trees

11 Right-Threaded AVL Trees