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


GNU libavl 2.0.1

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

6.8 Testing

Our job isn't done until we can demonstrate that our code works. We'll do this with a test program built using the framework from the previous chapter (see section 5.14 Testing). All we have to do is produce functions for AVL trees that correspond to each of those in &#60;@xref{\NODE\, , bst-test.c.&#62;,98}. This just involves making small changes to the functions used there. They are presented below without additional comment.

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

 
static int 
compare_trees (struct avl_node *a, struct avl_node *b)
{ int okay; if (a == NULL || b == NULL)
{ assert (a == NULL && b == NULL); return 1; } if (*(int *) a-&#62;avl_data != *(int *) b-&#62;avl_data || ((a-&#62;avl_link[0] != NULL) != (b-&#62;avl_link[0] != NULL)) || ((a-&#62;avl_link[1] != NULL) != (b-&#62;avl_link[1] != NULL)) || a-&#62;avl_balance != b-&#62;avl_balance)
{ printf ("Copiednodesdiffer:a=%d(bal=%d)b=%d(bal=%d)a:", *(int *) a-&#62;avl_data, a-&#62;avl_balance, *(int *) b-&#62;avl_data, b-&#62;avl_balance); if (a-&#62;avl_link[0] != NULL)
printf ("l"); if (a-&#62;avl_link[1] != NULL)
printf ("r"); printf ("b:"); if (b-&#62;avl_link[0] != NULL)
printf ("l"); if (b-&#62;avl_link[1] != NULL)
printf ("r"); printf ("\n"); return 0; } okay = 1; if (a-&#62;avl_link[0] != NULL)
okay &= compare_trees (a-&#62;avl_link[0], b-&#62;avl_link[0]); if (a-&#62;avl_link[1] != NULL)
okay &= compare_trees (a-&#62;avl_link[1], b-&#62;avl_link[1]); return okay; }
This code is included in @refalso{186

 
/* 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 *height to the tree's 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 avl_node *node, int *okay, size_t *count, int min, int max, int *height)
{ int d; /* Value of this node's data. */ size_t subcount[2]; /* Number of nodes in subtrees. */ int subheight[2]; /* Heights of subtrees. */ if (node == NULL)
{ *count = 0; *height = 0; return; } d = *(int *) node-&#62;avl_data; &#60;@xref{\NODE\, , Verify binary search tree ordering.&#62;,114} recurse_verify_tree (node-&#62;avl_link[0], okay, &subcount[0], min, d - 1, &subheight[0]); recurse_verify_tree (node-&#62;avl_link[1], okay, &subcount[1], d + 1, max, &subheight[1]); *count = 1 + subcount[0] + subcount[1]; *height = 1 + (subheight[0] > subheight[1] ? subheight[0] : subheight[1]); &#60;@xref{\NODE\, , Verify AVL node balance factor.&#62;,189} }
This code is included in @refalso{186

 
if (subheight[1] - subheight[0] != node-&#62;avl_balance) 
{ printf ("Balancefactorofnode%dis%d,butshouldbe%d.\n", d, node-&#62;avl_balance, subheight[1] - subheight[0]); *okay = 0; } else if (node-&#62;avl_balance < -1 || node-&#62;avl_balance > +1)
{ printf ("Balancefactorofnode%dis%d.\n", d, node-&#62;avl_balance); *okay = 0; }
This code is included in @refalso{188

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

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


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

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