6.6 Testing       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:

```240. <rb-test.c 240> =
#include <assert.h>
#include <limits.h>
#include <stdio.h>
#include "rb.h"
#include "test.h"

<BST print function; bst => rb 120>
<BST traverser check function; bst => rb 105>
<Compare two RB trees for structure and content 241>
<Recursively verify RB tree structure 242>
<RB tree verify function 246>
<BST test function; bst => rb 101>
<BST overflow test function; bst => rb 123>
```

```241. <Compare two RB trees for structure and content 241> =
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_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 != NULL)         printf ("l");
if (a->rb_link != NULL)         printf ("r");

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

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

okay = 1;
return okay;
}
```

This code is included in 240.

```242. <Recursively verify RB tree structure 242> =
/* 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;   /* Number of nodes in subtrees. */
int subbh;         /* Black-heights of subtrees. */

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

<Verify binary search tree ordering 115>

min, d - 1, &subbh);
d + 1, max, &subbh);
*count = 1 + subcount + subcount;
*bh = (node->rb_color == RB_BLACK) + subbh;

<Verify RB node color 243>
<Verify RB node rule 1 compliance 244>
<Verify RB node rule 2 compliance 245>
}
```

This code is included in 240.

```243. <Verify RB node color 243> =
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 242, 372, 486, and 587.

```244. <Verify RB node rule 1 compliance 244> =
/* Verify compliance with rule 1. */
if (node->rb_color == RB_RED)   {
printf (" Red node %d has red left child %d\n",
*okay = 0;
}

printf (" Red node %d has red right child %d\n",
*okay = 0;
}
}
```

This code is included in 242 and 587.

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

This code is included in 242, 372, 486, and 587.

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

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

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

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

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

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

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

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

return okay;
}
```

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

```247. <Check root is black 247> =
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 246.

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

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

This code is included in 246. 6.5.4 Symmetric Case 6 Red-Black Trees 7 Threaded Binary Search Trees 