www.delorie.com/gnu/docs/avl/libavl_128.html   search  
 
Buy GNU books!


GNU libavl 2.0.1

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

7.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:

 
&#60;@xref{\NODE\, , License.&#62;,1}
#include &#60;assert.h&#62;
#include &#60;limits.h&#62;
#include &#60;stdio.h&#62;
#include "rb.h"
#include "test.h"
&#60;@xref{\NODE\, , BST print function; bst =>.&#62; rb,119}
&#60;@xref{\NODE\, , BST traverser check function; bst =>.&#62; rb,104}
&#60;@xref{\NODE\, , Compare two RB trees for structure and content.&#62;,239}
&#60;@xref{\NODE\, , Recursively verify RB tree structure.&#62;,240}
&#60;@xref{\NODE\, , RB tree verify function.&#62;,244}
&#60;@xref{\NODE\, , BST test function; bst =>.&#62; rb,100}
&#60;@xref{\NODE\, , BST overflow test function; bst =>.&#62; rb,122}

 
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-&#62;rb_data != *(int *) b-&#62;rb_data || ((a-&#62;rb_link[0] != NULL) != (b-&#62;rb_link[0] != NULL)) || ((a-&#62;rb_link[1] != NULL) != (b-&#62;rb_link[1] != NULL)) || a-&#62;rb_color != b-&#62;rb_color)
{ printf ("Copiednodesdiffer:a=%d%cb=%d%ca:", *(int *) a-&#62;rb_data, a-&#62;rb_color == RB_RED ? 'r' : 'b', *(int *) b-&#62;rb_data, b-&#62;rb_color == RB_RED ? 'r' : 'b'); if (a-&#62;rb_link[0] != NULL)
printf ("l"); if (a-&#62;rb_link[1] != NULL)
printf ("r"); printf ("b:"); if (b-&#62;rb_link[0] != NULL)
printf ("l"); if (b-&#62;rb_link[1] != NULL)
printf ("r"); printf ("\n"); return 0; } okay = 1; if (a-&#62;rb_link[0] != NULL)
okay &= compare_trees (a-&#62;rb_link[0], b-&#62;rb_link[0]); if (a-&#62;rb_link[1] != NULL)
okay &= compare_trees (a-&#62;rb_link[1], b-&#62;rb_link[1]); return okay; }
This code is included in @refalso{238

 
/* 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-&#62;rb_data; &#60;@xref{\NODE\, , Verify binary search tree ordering.&#62;,114} recurse_verify_tree (node-&#62;rb_link[0], okay, &subcount[0], min, d - 1, &subbh[0]); recurse_verify_tree (node-&#62;rb_link[1], okay, &subcount[1], d + 1, max, &subbh[1]); *count = 1 + subcount[0] + subcount[1]; *bh = (node-&#62;rb_color == RB_BLACK) + subbh[0]; &#60;@xref{\NODE\, , Verify RB node color.&#62;,241} &#60;@xref{\NODE\, , Verify RB node rule 1 compliance.&#62;,242} &#60;@xref{\NODE\, , Verify RB node rule 2 compliance.&#62;,243} }
This code is included in @refalso{238

 
if (node-&#62;rb_color != RB_RED && node-&#62;rb_color != RB_BLACK) 
{ printf ("Node%disneitherrednorblack(%d).\n",
d, node-&#62;rb_color); *okay = 0; }
This code is included in @refalso{240

 
/* Verify compliance with rule 1. */
if (node-&#62;rb_color == RB_RED) 
{ if (node-&#62;rb_link[0] != NULL && node-&#62;rb_link[0]-&#62;rb_color == RB_RED)
{ printf ("Rednode%dhasredleftchild%d\n", d, *(int *) node-&#62;rb_link[0]-&#62;rb_data); *okay = 0; } if (node-&#62;rb_link[1] != NULL && node-&#62;rb_link[1]-&#62;rb_color == RB_RED)
{ printf ("Rednode%dhasredrightchild%d\n", d, *(int *) node-&#62;rb_link[1]-&#62;rb_data); *okay = 0; } }
This code is included in @refalso{240

 
/* Verify compliance with rule 2. */
if (subbh[0] != subbh[1]) 
{ printf ("Node%dhastwodifferentblack-heights:leftbh=%d," "rightbh=%d\n", d, subbh[0], subbh[1]); *okay = 0; }
This code is included in @refalso{240

 
static int 
verify_tree (struct rb_table *tree, int array[], size_t n)
{ int okay = 1; &#60;@xref{\NODE\, , Check tree.&#62;-&#62;bst_count is correct; bst => rb,110} if (okay)
{
&#60;@xref{\NODE\, , Check root is black.&#62;,245}
} if (okay)
{
&#60;@xref{\NODE\, , Check RB tree structure.&#62;,246}
} if (okay)
{
&#60;@xref{\NODE\, , Check that the tree contains all the elements it should; bst =>.&#62; rb,115}
} if (okay)
{
&#60;@xref{\NODE\, , Check that forward traversal works; bst =>.&#62; rb,116}
} if (okay)
{
&#60;@xref{\NODE\, , Check that backward traversal works; bst =>.&#62; rb,117}
} if (okay)
{
&#60;@xref{\NODE\, , Check that traversal from the null element works; bst =>.&#62; rb,118}
} return okay; }
This code is included in @refalso{238

 
if (tree-&#62;rb_root != NULL && tree-&#62;rb_root-&#62;rb_color != RB_BLACK) 
{ printf ("Tree'srootisnotblack.\n"); okay = 0; }
This code is included in @refalso{244

 
/* Recursively verify tree structure. */
size_t count;
int bh;
recurse_verify_tree (tree-&#62;rb_root, &okay, &count, 0, INT_MAX, &bh);
&#60;@xref{\NODE\, , Check counted nodes.&#62;,112}
This code is included in @refalso{244


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

  webmaster   donations   bookstore     delorie software   privacy  
  Copyright 2003   by The Free Software Foundation     Updated Jun 2003