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


GNU libavl 2.0.1

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

14.8 Testing

 
&#60;@xref{\NODE\, , License.&#62;,1}
#include &#60;assert.h&#62;
#include &#60;limits.h&#62;
#include &#60;stdio.h&#62;
#include "pbst.h"
#include "test.h"
&#60;@xref{\NODE\, , BST print function; bst =>.&#62; pbst,119}
&#60;@xref{\NODE\, , BST traverser check function; bst =>.&#62; pbst,104}
&#60;@xref{\NODE\, , Compare two PBSTs for structure and content.&#62;,516}
&#60;@xref{\NODE\, , Recursively verify PBST structure.&#62;,517}
&#60;@xref{\NODE\, , BST verify function; bst =>.&#62; pbst,109}
&#60;@xref{\NODE\, , TBST test function; tbst =>.&#62; pbst,295}
&#60;@xref{\NODE\, , BST overflow test function; bst =>.&#62; pbst,122}

 
static int 
compare_trees (struct pbst_node *a, struct pbst_node *b)
{ int okay; if (a == NULL || b == NULL)
{ assert (a == NULL && b == NULL); return 1; } if (*(int *) a-&#62;pbst_data != *(int *) b-&#62;pbst_data || ((a-&#62;pbst_link[0] != NULL) != (b-&#62;pbst_link[0] != NULL)) || ((a-&#62;pbst_link[1] != NULL) != (b-&#62;pbst_link[1] != NULL)) || ((a-&#62;pbst_parent != NULL) != (b-&#62;pbst_parent != NULL)) || (a-&#62;pbst_parent != NULL && b-&#62;pbst_parent != NULL && a-&#62;pbst_parent-&#62;pbst_data != b-&#62;pbst_parent-&#62;pbst_data))
{ printf ("Copiednodesdiffer:\n" "a:%d,parent%d,%sleftchild,%srightchild\n" "b:%d,parent%d,%sleftchild,%srightchild\n", *(int *) a-&#62;pbst_data, a-&#62;pbst_parent != NULL ? *(int *) a-&#62;pbst_parent : -1, a-&#62;pbst_link[0] != NULL ? "has" : "no", a-&#62;pbst_link[1] != NULL ? "has" : "no", *(int *) b-&#62;pbst_data, b-&#62;pbst_parent != NULL ? *(int *) b-&#62;pbst_parent : -1, b-&#62;pbst_link[0] != NULL ? "has" : "no", b-&#62;pbst_link[1] != NULL ? "has" : "no"); return 0; } okay = 1; if (a-&#62;pbst_link[0] != NULL) okay &= compare_trees (a-&#62;pbst_link[0], b-&#62;pbst_link[0]); if (a-&#62;pbst_link[1] != NULL) okay &= compare_trees (a-&#62;pbst_link[1], b-&#62;pbst_link[1]); return okay; }
This code is included in @refalso{515

 
static void 
recurse_verify_tree (struct pbst_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. */ int i; if (node == NULL)
{ *count = 0; return; } d = *(int *) node-&#62;pbst_data; &#60;@xref{\NODE\, , Verify binary search tree ordering.&#62;,114} recurse_verify_tree (node-&#62;pbst_link[0], okay, &subcount[0], min, d - 1); recurse_verify_tree (node-&#62;pbst_link[1], okay, &subcount[1], d + 1, max); *count = 1 + subcount[0] + subcount[1]; &#60;@xref{\NODE\, , Verify PBST node parent pointers.&#62;,518} }
This code is included in @refalso{515

 
for (i = 0; i < 2; i++) 
{ if (node-&#62;pbst_link[i] != NULL
&& node-&#62;pbst_link[i]-&#62;pbst_parent != node)
{ printf ("Node%dhasparent%d(shouldbe%d).\n", *(int *) node-&#62;pbst_link[i]-&#62;pbst_data, (node-&#62;pbst_link[i]-&#62;pbst_parent != NULL ? *(int *) node-&#62;pbst_link[i]-&#62;pbst_parent-&#62;pbst_data : -1), d); *okay = 0; } }
This code is included in @refalso{517


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

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