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


GNU libavl 2.0.1

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

11.10 Testing

There's nothing new or interesting in the test code.

 
&#60;@xref{\NODE\, , License.&#62;,1}
#include &#60;assert.h&#62;
#include &#60;limits.h&#62;
#include &#60;stdio.h&#62;
#include "rtbst.h"
#include "test.h"
&#60;@xref{\NODE\, , RTBST print function.&#62;,412}
&#60;@xref{\NODE\, , BST traverser check function; bst =>.&#62; rtbst,104}
&#60;@xref{\NODE\, , Compare two RTBSTs for structure and content.&#62;,413}
&#60;@xref{\NODE\, , Recursively verify RTBST structure.&#62;,414}
&#60;@xref{\NODE\, , BST verify function; bst =>.&#62; rtbst,109}
&#60;@xref{\NODE\, , TBST test function; tbst =>.&#62; rtbst,295}
&#60;@xref{\NODE\, , BST overflow test function; bst =>.&#62; rtbst,122}

 
void 
print_tree_structure (struct rtbst_node *node, int level)
{ if (level > 16)
{ printf ("[...]"); return; } if (node == NULL)
{ printf ("<nil>"); return; } printf ("%d(", node-&#62;rtbst_data ? *(int *) node-&#62;rtbst_data : -1); if (node-&#62;rtbst_link[0] != NULL) print_tree_structure (node-&#62;rtbst_link[0], level + 1); fputs (",", stdout); if (node-&#62;rtbst_rtag == RTBST_CHILD)
{ if (node-&#62;rtbst_link[1] == node) printf ("loop"); else
print_tree_structure (node-&#62;rtbst_link[1], level + 1); } else if (node-&#62;rtbst_link[1] != NULL)
printf (">%d",
(node-&#62;rtbst_link[1]-&#62;rtbst_data ? *(int *) node-&#62;rtbst_link[1]-&#62;rtbst_data : -1)); else
printf (">>"); putchar (')'); } void
print_whole_tree (const struct rtbst_table *tree, const char *title)
{ printf ("%s:", title); print_tree_structure (tree-&#62;rtbst_root, 0); putchar ('\n'); }
This code is included in @refalso{411

 
static int 
compare_trees (struct rtbst_node *a, struct rtbst_node *b)
{ int okay; if (a == NULL || b == NULL)
{ if (a != NULL || b != NULL)
{ printf ("a=%db=%d\n", a ? *(int *) a-&#62;rtbst_data : -1, b ? *(int *) b-&#62;rtbst_data : -1); assert (0); } return 1; } assert (a != b); if (*(int *) a-&#62;rtbst_data != *(int *) b-&#62;rtbst_data || a-&#62;rtbst_rtag != b-&#62;rtbst_rtag)
{ printf ("Copiednodesdiffer:a=%db=%da:", *(int *) a-&#62;rtbst_data, *(int *) b-&#62;rtbst_data); if (a-&#62;rtbst_rtag == RTBST_CHILD)
printf ("r"); printf ("b:"); if (b-&#62;rtbst_rtag == RTBST_CHILD)
printf ("r"); printf ("\n"); return 0; } if (a-&#62;rtbst_rtag == RTBST_THREAD) assert ((a-&#62;rtbst_link[1] == NULL) != (a-&#62;rtbst_link[1] != b-&#62;rtbst_link[1])); okay = compare_trees (a-&#62;rtbst_link[0], b-&#62;rtbst_link[0]); if (a-&#62;rtbst_rtag == RTBST_CHILD) okay &= compare_trees (a-&#62;rtbst_link[1], b-&#62;rtbst_link[1]); return okay; }
This code is included in @refalso{411

 
static void 
recurse_verify_tree (struct rtbst_node *node, int *okay, size_t *count, int min, int max)
{ int d; /* Value of this node's data. */ size_t subcount[2]; /* Number of nodes in subtrees. */ if (node == NULL)
{ *count = 0; return; } d = *(int *) node-&#62;rtbst_data; &#60;@xref{\NODE\, , Verify binary search tree ordering.&#62;,114} subcount[0] = subcount[1] = 0; recurse_verify_tree (node-&#62;rtbst_link[0], okay, &subcount[0], min, d - 1); if (node-&#62;rtbst_rtag == RTBST_CHILD) recurse_verify_tree (node-&#62;rtbst_link[1], okay, &subcount[1], d + 1, max); *count = 1 + subcount[0] + subcount[1]; }
This code is included in @refalso{411


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

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