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

Now we'll present a test program to demonstrate that our code works, using the same framework that has been used in past chapters. The additional code needed is straightforward: 

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

<BST print function; bst => rb 119>
<BST traverser check function; bst => rb 104>
<Compare two RB trees for structure and content 239>
<Recursively verify RB tree structure 240>
<RB tree verify function 244>
<BST test function; bst => rb 100>
<BST overflow test function; bst => rb 122>


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

  if (a == NULL || b == NULL) 
    {
      assert (a == NULL && b == NULL);
      return 1;
    }

  if (*(int *) a->rb_data != *(int *) b->rb_data
      || ((a->rb_link[0] != NULL) != (b->rb_link[0] != NULL))
      || ((a->rb_link[1] != NULL) != (b->rb_link[1] != NULL))
      || a->rb_color != b->rb_color) 
    {
      printf (" Copied nodes differ: a=%d%c b=%d%c a:",
              *(int *) a->rb_data, a->rb_color == RB_RED ? 'r' : 'b',
              *(int *) b->rb_data, b->rb_color == RB_RED ? 'r' : 'b');

      if (a->rb_link[0] != NULL) 
        printf ("l");
      if (a->rb_link[1] != NULL) 
        printf ("r");

      printf (" b:");
      if (b->rb_link[0] != NULL) 
        printf ("l");
      if (b->rb_link[1] != NULL) 
        printf ("r");

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

  okay = 1;
  if (a->rb_link[0] != NULL) 
    okay &= compare_trees (a->rb_link[0], b->rb_link[0]);
  if (a->rb_link[1] != NULL) 
    okay &= compare_trees (a->rb_link[1], b->rb_link[1]);
  return okay;
}

This code is included in 238. 

240. <Recursively verify RB tree structure 240> =
/* Examines the binary tree rooted at node.  
   Zeroes *okay if an error occurs.  
   Otherwise, does not modify *okay.
   Sets *count to the number of nodes in that tree, 
   including node itself if node != NULL.
   Sets *bh to the tree's black-height.
   All the nodes in the tree are verified to be at least min 
   but no greater than max. */
static void 
recurse_verify_tree (struct rb_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->rb_data;

  <Verify binary search tree ordering 114>

  recurse_verify_tree (node->rb_link[0], okay, &subcount[0], 
                       min, d - 1, &subbh[0]);
  recurse_verify_tree (node->rb_link[1], okay, &subcount[1], 
                       d + 1, max, &subbh[1]);
  *count = 1 + subcount[0] + subcount[1];
  *bh = (node->rb_color == RB_BLACK) + subbh[0];

  <Verify RB node color 241>
  <Verify RB node rule 1 compliance 242>
  <Verify RB node rule 2 compliance 243>
}

This code is included in 238. 

241. <Verify RB node color 241> =
if (node->rb_color != RB_RED && node->rb_color != RB_BLACK) 
  {
    printf (" Node %d is neither red nor black (%d).\n", 
            d, node->rb_color);
    *okay = 0;
  }

This code is included in 240, 370, 484, and 585. 

242. <Verify RB node rule 1 compliance 242> =
/* Verify compliance with rule 1. */
if (node->rb_color == RB_RED) 
  {
    if (node->rb_link[0] != NULL && node->rb_link[0]->rb_color == RB_RED) 
      {
        printf (" Red node %d has red left child %d\n",
                d, *(int *) node->rb_link[0]->rb_data);
        *okay = 0;
      }

    if (node->rb_link[1] != NULL && node->rb_link[1]->rb_color == RB_RED) 
      {
        printf (" Red node %d has red right child %d\n",
                d, *(int *) node->rb_link[1]->rb_data);
        *okay = 0;
      }
  }

This code is included in 240 and 585. 

243. <Verify RB node rule 2 compliance 243> =
/* Verify compliance with rule 2. */
if (subbh[0] != subbh[1]) 
  {
    printf (" Node %d has two different blackheights: left bh=%d, "
            "right bh=%d\n", d, subbh[0], subbh[1]);
    *okay = 0;
  }

This code is included in 240, 370, 484, and 585. 

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

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

  if (okay) 
    { 
      <Check root is black 245> 
    }

  if (okay) 
    { 
      <Check RB tree structure 246> 
    }

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

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

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

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

  return okay;
}

This code is included in 238, 368, 482, and 583. 

245. <Check root is black 245> =
if (tree->rb_root != NULL && tree->rb_root->rb_color != RB_BLACK) 
  {
    printf (" Tree's root is not black.\n");
    okay = 0;
  }

This code is included in 244. 

246. <Check RB tree structure 246> =
/* Recursively verify tree structure. */
size_t count;
int bh;

recurse_verify_tree (tree->rb_root, &okay, &count, 0, INT_MAX, &bh);
<Check counted nodes 112>

This code is included in 244.

Prev: 6.5.4 Symmetric Case Up: 6 Red-Black Trees 7 Threaded Binary Search Trees Next