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

There's nothing new or interesting in the test code.

413. <rtbst-test.c 413> =
<Program License 2>
#include <assert.h>
#include <limits.h>
#include <stdio.h>
#include "rtbst.h"
#include "test.h"

<RTBST print function 414>
<BST traverser check function; bst => rtbst 105>
<Compare two RTBSTs for structure and content 415>
<Recursively verify RTBST structure 416>
<BST verify function; bst => rtbst 110>
<TBST test function; tbst => rtbst 297>
<BST overflow test function; bst => rtbst 123>

414. <RTBST print function 414> =
void 
print_tree_structure (struct rtbst_node *node, int level)
{ if (level > 16)
    { printf ("[...]"); return; } if (node == NULL)
    { printf ("<nil>"); return; } printf ("%d(", node->rtbst_data ? *(int *) node->rtbst_data : -1); if (node->rtbst_link[0] != NULL) print_tree_structure (node->rtbst_link[0], level + 1); fputs (", ", stdout); if (node->rtbst_rtag == RTBST_CHILD)
    { if (node->rtbst_link[1] == node) printf ("loop"); else
        print_tree_structure (node->rtbst_link[1], level + 1); } else if (node->rtbst_link[1] != NULL)
    printf (">%d",
            (node->rtbst_link[1]->rtbst_data ? *(int *) node->rtbst_link[1]->rtbst_data : -1)); else
    printf (">>"); putchar (')'); } void
print_whole_tree (const struct rtbst_table *tree, const char *title)
{ printf ("%s: ", title); print_tree_structure (tree->rtbst_root, 0); putchar ('\n'); }

This code is included in 413, 451, and 484.

415. <Compare two RTBSTs for structure and content 415> =
static int 
compare_trees (struct rtbst_node *a, struct rtbst_node *b)
{ int okay; if (a == NULL || b == NULL)
    { if (a != NULL || b != NULL)
        { printf (" a=%d b=%d\n", a ? *(int *) a->rtbst_data : -1, b ? *(int *) b->rtbst_data : -1); assert (0); } return 1; } assert (a != b); if (*(int *) a->rtbst_data != *(int *) b->rtbst_data || a->rtbst_rtag != b->rtbst_rtag)
    { printf (" Copied nodes differ: a=%d b=%d a:", *(int *) a->rtbst_data, *(int *) b->rtbst_data); if (a->rtbst_rtag == RTBST_CHILD)
        printf ("r"); printf (" b:"); if (b->rtbst_rtag == RTBST_CHILD)
        printf ("r"); printf ("\n"); return 0; } if (a->rtbst_rtag == RTBST_THREAD) assert ((a->rtbst_link[1] == NULL) != (a->rtbst_link[1] != b->rtbst_link[1])); okay = compare_trees (a->rtbst_link[0], b->rtbst_link[0]); if (a->rtbst_rtag == RTBST_CHILD) okay &= compare_trees (a->rtbst_link[1], b->rtbst_link[1]); return okay; }

This code is included in 413.

416. <Recursively verify RTBST structure 416> =
static void 
recurse_verify_tree (struct rtbst_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->rtbst_data; <Verify binary search tree ordering 115> subcount[0] = subcount[1] = 0; recurse_verify_tree (node->rtbst_link[0], okay, &subcount[0], min, d - 1); if (node->rtbst_rtag == RTBST_CHILD) recurse_verify_tree (node->rtbst_link[1], okay, &subcount[1], d + 1, max); *count = 1 + subcount[0] + subcount[1]; }

This code is included in 413.

Prev: 10.9 Balance Up: 10 Right-Threaded Binary Search Trees 11 Right-Threaded AVL Trees Next