8.7 Testing [ToC] [Index]     [Skip Back]     [Prev] [Up] [Next]

The testing code harbors no surprises.

330. <tavl-test.c 330> =
<License 1>
#include <assert.h>
#include <limits.h>
#include <stdio.h>
#include "tavl.h"
#include "test.h"

<TBST print function; tbst => tavl 291>
<BST traverser check function; bst => tavl 104>
<Compare two TAVL trees for structure and content 331>
<Recursively verify TAVL tree structure 332>
<AVL tree verify function; avl => tavl 190>
<BST test function; bst => tavl 100>
<BST overflow test function; bst => tavl 122>

331. <Compare two TAVL trees for structure and content 331> =
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=%d b=%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 (" Copied nodes differ: 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 330.

332. <Recursively verify TAVL tree structure 332> =
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; <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]); <Verify AVL node balance factor; avl => tavl 189> }

This code is included in 330.

Prev: 8.6 Copying Up: 8 Threaded AVL Trees 9 Threaded Red-Black Trees Next