9.5 Testing

The testing code harbors no surprises.

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

<TBST print function; tbst => trb 293>
<BST traverser check function; bst => trb 105>
<Compare two TRB trees for structure and content 371>
<Recursively verify TRB tree structure 372>
<RB tree verify function; rb => trb 246>
<BST test function; bst => trb 101>
<BST overflow test function; bst => trb 123>

371. <Compare two TRB trees for structure and content 371> =
static int 
compare_trees (struct trb_node *a, struct trb_node *b) 
{
  int okay;

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

  if (*(int *) a->trb_data != *(int *) b->trb_data
      || a->trb_tag[0] != b->trb_tag[0] 
      || a->trb_tag[1] != b->trb_tag[1]
      || a->trb_color != b->trb_color) 
    {
      printf (" Copied nodes differ: a=%d%c b=%d%c a:",
              *(int *) a->trb_data, a->trb_color == TRB_RED ? 'r' : 'b',
              *(int *) b->trb_data, b->trb_color == TRB_RED ? 'r' : 'b');

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

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

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

  if (a->trb_tag[0] == TRB_THREAD)
    assert ((a->trb_link[0] == NULL) != (a->trb_link[0] != b->trb_link[0]));
  if (a->trb_tag[1] == TRB_THREAD)
    assert ((a->trb_link[1] == NULL) != (a->trb_link[1] != b->trb_link[1]));

  okay = 1;
  if (a->trb_tag[0] == TRB_CHILD)
    okay &= compare_trees (a->trb_link[0], b->trb_link[0]);
  if (a->trb_tag[1] == TRB_CHILD)
    okay &= compare_trees (a->trb_link[1], b->trb_link[1]);
  return okay;
}

This code is included in 370.

372. <Recursively verify TRB tree structure 372> =
static void 
recurse_verify_tree (struct trb_node *node, int *okay, size_t *count, 
                     int min, int max, int *bh) 
{
  int d;                /* Value of this node's data. */
  size_t subcount[2];   /* Number of nodes in subtrees. */
  int subbh[2];         /* Black-heights of subtrees. */

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

  <Verify binary search tree ordering 115>

  subcount[0] = subcount[1] = 0;
  subbh[0] = subbh[1] = 0;
  if (node->trb_tag[0] == TRB_CHILD)
    recurse_verify_tree (node->trb_link[0], okay, &subcount[0], 
                         min, d - 1, &subbh[0]);
  if (node->trb_tag[1] == TRB_CHILD)
    recurse_verify_tree (node->trb_link[1], okay, &subcount[1], 
                         d + 1, max, &subbh[1]);
  *count = 1 + subcount[0] + subcount[1];
  *bh = (node->trb_color == TRB_BLACK) + subbh[0];

  <Verify RB node color; rb => trb 243>
  <Verify TRB node rule 1 compliance 373>
  <Verify RB node rule 2 compliance; rb => trb 245>
}

This code is included in 370.

373. <Verify TRB node rule 1 compliance 373> =
/* Verify compliance with rule 1. */
if (node->trb_color == TRB_RED) 
  {
    if (node->trb_tag[0] == TRB_CHILD 
        && node->trb_link[0]->trb_color == TRB_RED) 
      {
        printf (" Red node %d has red left child %d\n",
                d, *(int *) node->trb_link[0]->trb_data);
        *okay = 0;
      }

    if (node->trb_tag[1] == TRB_CHILD 
        && node->trb_link[1]->trb_color == TRB_RED) 
      {
        printf (" Red node %d has red right child %d\n",
                d, *(int *) node->trb_link[1]->trb_data);
        *okay = 0;
      }
  }

This code is included in 372.

9.4.5 Symmetric Case

9 Threaded Red-Black Trees

10 Right-Threaded Binary Search Trees