GNU libavl 2.0.1

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

search

	Buy GNU books!

GNU libavl 2.0.1

[ < ]

[ > ]

[ << ]

[ Up ]

[ >> ]

[Top]

[Contents]

[Index]

[ ? ]

8.12 Testing

There's little new in the testing code. We do add an test for tbst_balance(), because none of the existing tests exercise it. This test doesn't check that tbst_balance() actually balances the tree, it just verifies that afterwards the tree contains the items it should, so to be certain that balancing is correct, turn up the verbosity and look at the trees printed.

Function print_tree_structure() prints thread node numbers preceded by `>', with null threads indicated by `>>'. This notation is compatible with the plain text output format of the texitree program used to draw the binary trees in this book. (It will cause errors for PostScript output because it omits node names.)

<@xref{\NODE\, , License.>,1} #include <assert.h> #include <limits.h> #include <stdio.h> #include "tbst.h" #include "test.h" <@xref{\NODE\, , TBST print function.>,291} <@xref{\NODE\, , BST traverser check function; bst =>.> tbst,104} <@xref{\NODE\, , Compare two TBSTs for structure and content.>,292} <@xref{\NODE\, , Recursively verify TBST structure.>,293} <@xref{\NODE\, , TBST verify function.>,294} <@xref{\NODE\, , TBST test function.>,295} <@xref{\NODE\, , BST overflow test function; bst =>.> tbst,122}

void
print_tree_structure (struct tbst_node *node, int level)
{ int i; if (level > 16)
{ printf ("[...]"); return; } if (node == NULL)
{ printf ("<nil>"); return; } printf ("%d(", node->tbst_data ? *(int *) node->tbst_data : -1); for (i = 0; i <= 1; i++)
{ if (node->tbst_tag[i] == TBST_CHILD)
{ if (node->tbst_link[i] == node)
printf ("loop"); else
print_tree_structure (node->tbst_link[i], level + 1); } else if (node->tbst_link[i] != NULL) printf (">%d",
(node->tbst_link[i]->tbst_data ? *(int *) node->tbst_link[i]->tbst_data : -1)); else
printf (">>"); if (i == 0)
fputs (",", stdout); } putchar (')'); } void
print_whole_tree (const struct tbst_table *tree, const char *title)
{ printf ("%s:", title); print_tree_structure (tree->tbst_root, 0); putchar ('\n'); }
This code is included in @refalso{290

static int
compare_trees (struct tbst_node *a, struct tbst_node *b)
{ int okay; if (a == NULL || b == NULL)
{ if (a != NULL || b != NULL)
{ printf ("a=%db=%d\n", a ? *(int *) a->tbst_data : -1,
b ? *(int *) b->tbst_data : -1); assert (0); } return 1; } assert (a != b); if (*(int *) a->tbst_data != *(int *) b->tbst_data || a->tbst_tag[0] != b->tbst_tag[0]
|| a->tbst_tag[1] != b->tbst_tag[1])
{ printf ("Copiednodesdiffer:a=%db=%da:", *(int *) a->tbst_data, *(int *) b->tbst_data); if (a->tbst_tag[0] == TBST_CHILD)
printf ("l"); if (a->tbst_tag[1] == TBST_CHILD)
printf ("r"); printf ("b:"); if (b->tbst_tag[0] == TBST_CHILD)
printf ("l"); if (b->tbst_tag[1] == TBST_CHILD)
printf ("r"); printf ("\n"); return 0; } if (a->tbst_tag[0] == TBST_THREAD) assert ((a->tbst_link[0] == NULL) != (a->tbst_link[0] != b->tbst_link[0])); if (a->tbst_tag[1] == TBST_THREAD) assert ((a->tbst_link[1] == NULL) != (a->tbst_link[1] != b->tbst_link[1])); okay = 1; if (a->tbst_tag[0] == TBST_CHILD) okay &= compare_trees (a->tbst_link[0], b->tbst_link[0]); if (a->tbst_tag[1] == TBST_CHILD) okay &= compare_trees (a->tbst_link[1], b->tbst_link[1]); return okay; }
This code is included in @refalso{290

static void
recurse_verify_tree (struct tbst_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->tbst_data; <@xref{\NODE\, , Verify binary search tree ordering.>,114} subcount[0] = subcount[1] = 0; if (node->tbst_tag[0] == TBST_CHILD) recurse_verify_tree (node->tbst_link[0], okay, &subcount[0], min, d - 1); if (node->tbst_tag[1] == TBST_CHILD) recurse_verify_tree (node->tbst_link[1], okay, &subcount[1], d + 1, max); *count = 1 + subcount[0] + subcount[1]; }
This code is included in @refalso{290

static int
verify_tree (struct tbst_table *tree, int array[], size_t n)
{ int okay = 1; <@xref{\NODE\, , Check tree.>->bst_count is correct; bst => tbst,110} if (okay)
{
<@xref{\NODE\, , Check BST structure; bst =>.> tbst,111}
} if (okay)
{
<@xref{\NODE\, , Check that the tree contains all the elements it should; bst =>.> tbst,115}
} if (okay)
{
<@xref{\NODE\, , Check that forward traversal works; bst =>.> tbst,116}
} if (okay)
{
<@xref{\NODE\, , Check that backward traversal works; bst =>.> tbst,117}
} if (okay)
{
<@xref{\NODE\, , Check that traversal from the null element works; bst =>.> tbst,118}
} return okay; }
This code is included in @refalso{290

int
test_correctness (struct libavl_allocator *allocator, int insert[], int delete[], int n, int verbosity)
{ struct tbst_table *tree; int okay = 1; int i; <@xref{\NODE\, , Test creating a BST and inserting into it; bst =>.> tbst,102} <@xref{\NODE\, , Test BST traversal during modifications; bst =>.> tbst,103} <@xref{\NODE\, , Test deleting nodes from the BST and making copies of it; bst =>.> tbst,105} <@xref{\NODE\, , Test destroying the tree; bst =>.> tbst,108} <@xref{\NODE\, , Test TBST balancing.>,296} return okay; }
This code is included in @refalso{290

/* Test tbst_balance(). */ if (verbosity >= 2)
printf ("Testingbalancing...\n"); tree = tbst_create (compare_ints, NULL, allocator); if (tree == NULL)
{ if (verbosity >= 0)
printf ("Outofmemorycreatingtree.\n"); return 1; } for (i = 0; i < n; i++)
{ void **p = tbst_probe (tree, &insert[i]); if (p == NULL)
{ if (verbosity >= 0)
printf ("Outofmemoryininsertion.\n"); tbst_destroy (tree, NULL); return 1; } if (*p != &insert[i])
printf ("Duplicateitemintree!\n"); } if (verbosity >= 4)
print_whole_tree (tree, "Pre-balance"); tbst_balance (tree); if (verbosity >= 4)
print_whole_tree (tree, "Post-balance"); if (!verify_tree (tree, insert, n)) return 0; tbst_destroy (tree, NULL);
This code is included in @refalso{295