www.delorie.com/gnu/docs/avl/libavl_271.html

search

	Buy GNU books!

GNU libavl 2.0.1

16.5 Testing

No comment is necessary.

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

static int compare_trees (struct prb_node *a, struct prb_node *b) { int okay; if (a == NULL || b == NULL) { assert (a == NULL && b == NULL); return 1; } if (*(int *) a->prb_data != *(int *) b->prb_data || ((a->prb_link[0] != NULL) != (b->prb_link[0] != NULL)) || ((a->prb_link[1] != NULL) != (b->prb_link[1] != NULL)) || a->prb_color != b->prb_color) { printf ("Copiednodesdiffer:a=%d%cb=%d%ca:", *(int *) a->prb_data, a->prb_color == PRB_RED ? 'r' : 'b', *(int *) b->prb_data, b->prb_color == PRB_RED ? 'r' : 'b'); if (a->prb_link[0] != NULL) printf ("l"); if (a->prb_link[1] != NULL) printf ("r"); printf ("b:"); if (b->prb_link[0] != NULL) printf ("l"); if (b->prb_link[1] != NULL) printf ("r"); printf ("\n"); return 0; } okay = 1; if (a->prb_link[0] != NULL) okay &= compare_trees (a->prb_link[0], b->prb_link[0]); if (a->prb_link[1] != NULL) okay &= compare_trees (a->prb_link[1], b->prb_link[1]); return okay; }

This code is included in @refalso{583

/* 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 prb_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. */ int i; if (node == NULL) { *count = 0; *bh = 0; return; } d = *(int *) node->prb_data; <@xref{\NODE\, , Verify binary search tree ordering.>,114} recurse_verify_tree (node->prb_link[0], okay, &subcount[0], min, d - 1, &subbh[0]); recurse_verify_tree (node->prb_link[1], okay, &subcount[1], d + 1, max, &subbh[1]); *count = 1 + subcount[0] + subcount[1]; *bh = (node->prb_color == PRB_BLACK) + subbh[0]; <@xref{\NODE\, , Verify RB node color; rb =>.> prb,241} <@xref{\NODE\, , Verify RB node rule 1 compliance; rb =>.> prb,242} <@xref{\NODE\, , Verify RB node rule 2 compliance; rb =>.> prb,243} <@xref{\NODE\, , Verify PBST node parent pointers; pbst =>.> prb,518} }

This code is included in @refalso{583