15.5 Testing

No comment is necessary.

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

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

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

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

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

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

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

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

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

This code is included in 583.

585. <Recursively verify PRB tree structure 585> =
/* 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 prb_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. */
  int i;

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

  <Verify binary search tree ordering 114>

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

  <Verify RB node color; rb => prb 241>
  <Verify RB node rule 1 compliance; rb => prb 242>
  <Verify RB node rule 2 compliance; rb => prb 243>

  <Verify PBST node parent pointers; pbst => prb 518>
}

This code is included in 583.

15.4.4 Symmetric Case

15 Red-Black Trees with Parent Pointers

Appendix A References