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:

```238. <rb-test.c 238> =
#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_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 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;   /* 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 114>

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

<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)   {
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 240 and 585.

```243. <Verify RB node rule 2 compliance 243> =
/* 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 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. 6.5.4 Symmetric Case 6 Red-Black Trees 7 Threaded Binary Search Trees 