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


GNU libavl 2.0.1

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

10.5 Testing

The testing code harbors no surprises.

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

 
static int 
compare_trees (struct trb_node *a, struct trb_node *b)
{ int okay; if (a == NULL || b == NULL)
{ if (a != NULL || b != NULL)
{ printf ("a=%db=%d\n", a ? *(int *) a-&#62;trb_data : -1,
b ? *(int *) b-&#62;trb_data : -1); assert (0); } return 1; } assert (a != b); if (*(int *) a-&#62;trb_data != *(int *) b-&#62;trb_data || a-&#62;trb_tag[0] != b-&#62;trb_tag[0]
|| a-&#62;trb_tag[1] != b-&#62;trb_tag[1] || a-&#62;trb_color != b-&#62;trb_color)
{ printf ("Copiednodesdiffer:a=%d%cb=%d%ca:", *(int *) a-&#62;trb_data, a-&#62;trb_color == TRB_RED ? 'r' : 'b', *(int *) b-&#62;trb_data, b-&#62;trb_color == TRB_RED ? 'r' : 'b'); if (a-&#62;trb_tag[0] == TRB_CHILD)
printf ("l"); if (a-&#62;trb_tag[1] == TRB_CHILD)
printf ("r"); printf ("b:"); if (b-&#62;trb_tag[0] == TRB_CHILD)
printf ("l"); if (b-&#62;trb_tag[1] == TRB_CHILD)
printf ("r"); printf ("\n"); return 0; } if (a-&#62;trb_tag[0] == TRB_THREAD) assert ((a-&#62;trb_link[0] == NULL) != (a-&#62;trb_link[0] != b-&#62;trb_link[0])); if (a-&#62;trb_tag[1] == TRB_THREAD) assert ((a-&#62;trb_link[1] == NULL) != (a-&#62;trb_link[1] != b-&#62;trb_link[1])); okay = 1; if (a-&#62;trb_tag[0] == TRB_CHILD) okay &= compare_trees (a-&#62;trb_link[0], b-&#62;trb_link[0]); if (a-&#62;trb_tag[1] == TRB_CHILD) okay &= compare_trees (a-&#62;trb_link[1], b-&#62;trb_link[1]); return okay; }
This code is included in @refalso{368

 
static void 
recurse_verify_tree (struct trb_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;trb_data; &#60;@xref{\NODE\, , Verify binary search tree ordering.&#62;,114} subcount[0] = subcount[1] = 0; subbh[0] = subbh[1] = 0; if (node-&#62;trb_tag[0] == TRB_CHILD) recurse_verify_tree (node-&#62;trb_link[0], okay, &subcount[0], min, d - 1, &subbh[0]); if (node-&#62;trb_tag[1] == TRB_CHILD) recurse_verify_tree (node-&#62;trb_link[1], okay, &subcount[1], d + 1, max, &subbh[1]); *count = 1 + subcount[0] + subcount[1]; *bh = (node-&#62;trb_color == TRB_BLACK) + subbh[0]; &#60;@xref{\NODE\, , Verify RB node color; rb =>.&#62; trb,241} &#60;@xref{\NODE\, , Verify TRB node rule 1 compliance.&#62;,371} &#60;@xref{\NODE\, , Verify RB node rule 2 compliance; rb =>.&#62; trb,243} }
This code is included in @refalso{368

 
/* Verify compliance with rule 1. */
if (node-&#62;trb_color == TRB_RED) 
{ if (node-&#62;trb_tag[0] == TRB_CHILD
&& node-&#62;trb_link[0]-&#62;trb_color == TRB_RED)
{ printf ("Rednode%dhasredleftchild%d\n", d, *(int *) node-&#62;trb_link[0]-&#62;trb_data); *okay = 0; } if (node-&#62;trb_tag[1] == TRB_CHILD
&& node-&#62;trb_link[1]-&#62;trb_color == TRB_RED)
{ printf ("Rednode%dhasredrightchild%d\n", d, *(int *) node-&#62;trb_link[1]-&#62;trb_data); *okay = 0; } }
This code is included in @refalso{370


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

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