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

search

	Buy GNU books!

GNU libavl 2.0.1

9.7 Testing

The testing code harbors no surprises.

<@xref{\NODE\, , License.>,1} #include <assert.h> #include <limits.h> #include <stdio.h> #include "tavl.h" #include "test.h" <@xref{\NODE\, , TBST print function; tbst =>.> tavl,291} <@xref{\NODE\, , BST traverser check function; bst =>.> tavl,104} <@xref{\NODE\, , Compare two TAVL trees for structure and content.>,331} <@xref{\NODE\, , Recursively verify TAVL tree structure.>,332} <@xref{\NODE\, , AVL tree verify function; avl =>.> tavl,190} <@xref{\NODE\, , BST test function; bst =>.> tavl,100} <@xref{\NODE\, , BST overflow test function; bst =>.> tavl,122}

static int compare_trees (struct tavl_node *a, struct tavl_node *b) { int okay; if (a == NULL || b == NULL) { if (a != NULL || b != NULL) { printf ("a=%db=%d\n", a ? *(int *) a->tavl_data : -1, b ? *(int *) b->tavl_data : -1); assert (0); } return 1; } assert (a != b); if (*(int *) a->tavl_data != *(int *) b->tavl_data || a->tavl_tag[0] != b->tavl_tag[0] || a->tavl_tag[1] != b->tavl_tag[1] || a->tavl_balance != b->tavl_balance) { printf ("Copiednodesdiffer:a=%d(bal=%d)b=%d(bal=%d)a:", *(int *) a->tavl_data, a->tavl_balance, *(int *) b->tavl_data, b->tavl_balance); if (a->tavl_tag[0] == TAVL_CHILD) printf ("l"); if (a->tavl_tag[1] == TAVL_CHILD) printf ("r"); printf ("b:"); if (b->tavl_tag[0] == TAVL_CHILD) printf ("l"); if (b->tavl_tag[1] == TAVL_CHILD) printf ("r"); printf ("\n"); return 0; } if (a->tavl_tag[0] == TAVL_THREAD) assert ((a->tavl_link[0] == NULL) != (a->tavl_link[0] != b->tavl_link[0])); if (a->tavl_tag[1] == TAVL_THREAD) assert ((a->tavl_link[1] == NULL) != (a->tavl_link[1] != b->tavl_link[1])); okay = 1; if (a->tavl_tag[0] == TAVL_CHILD) okay &= compare_trees (a->tavl_link[0], b->tavl_link[0]); if (a->tavl_tag[1] == TAVL_CHILD) okay &= compare_trees (a->tavl_link[1], b->tavl_link[1]); return okay; }

This code is included in @refalso{330

static void recurse_verify_tree (struct tavl_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->tavl_data; <@xref{\NODE\, , Verify binary search tree ordering.>,114} subcount[0] = subcount[1] = 0; subheight[0] = subheight[1] = 0; if (node->tavl_tag[0] == TAVL_CHILD) recurse_verify_tree (node->tavl_link[0], okay, &subcount[0], min, d - 1, &subheight[0]); if (node->tavl_tag[1] == TAVL_CHILD) recurse_verify_tree (node->tavl_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]); <@xref{\NODE\, , Verify AVL node balance factor; avl =>.> tavl,189} }

This code is included in @refalso{330