// Abstract AVL Tree Generic C Package Test Suite.
// This code is in the public domain.
// Version: 1.5 Author: Walt Karas
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
// Mask of highest bit in an unsigned int.
const unsigned HIGH_BIT = (~(((unsigned) (~ 0)) >> 1));
void bail(const char *note)
{
printf("%s\n", note);
exit(1);
}
#define AVL_UNIQUE(X) X ## _x
#define AVL_READ_ERRORS_HAPPEN
#define AVL_READ_ERROR (0)
// Handles are indexes into the "arr" array. If a handle has been
// "accessed", it has its high bit set. (The handle has to have been
// accessed in order to alter the node's values, or compare its key.)
#define AVL_HANDLE unsigned
#define AVL_KEY int
#define AVL_SIZE unsigned
// Node array and "shadow" node array.
struct
{
signed char bf;
int val;
unsigned gt, lt;
}
arr[401], arr2[400];
#define AVL_BUILD_ITER_TYPE unsigned *
#define AVL_MAX_DEPTH 33
#include "cavl_if.h"
avl_x tree;
typedef iter_x iter;
// Verifies that a tree is a valid AVL Balanced Binary Search Tree.
// Returns depth. Don't use on an empty tree.
int verify_tree(unsigned subroot = tree.root & ~HIGH_BIT)
{
int l_depth, g_depth;
unsigned h;
if (arr[subroot].lt == ~0)
l_depth = 0;
else
{
h = arr[subroot].lt & ~HIGH_BIT;
if (arr[subroot].val <= arr[h].val)
{
printf("not less: %u %d %d %d\n",
subroot, arr[subroot].val, h, arr[h].val);
bail("verify_tree");
}
l_depth = verify_tree(h);
}
if (arr[subroot].gt == ~0)
g_depth = 0;
else
{
h = arr[subroot].gt & ~HIGH_BIT;
if (arr[subroot].val >= arr[h].val)
{
printf("not greater: %u %d %d %d\n",
subroot, arr[subroot].val, h, arr[h].val);
bail("verify_tree");
}
g_depth = verify_tree(h);
}
if (arr[subroot].bf != (g_depth - l_depth))
{
printf("bad bf: n=%u bf=%d gd=%d ld=%d\n",
subroot, arr[subroot].bf, g_depth, l_depth);
bail("verify_tree");
}
return((g_depth > l_depth ? g_depth : l_depth) + 1);
}
void check_empty(void)
{
if (tree.root != ~0)
bail("not empty");
}
void insert(unsigned h)
{
unsigned rh = insert_x(&tree, h | HIGH_BIT);
if (rh == ~0)
bail("insert null");
rh &= ~HIGH_BIT;
if (arr[h].val != arr[rh].val)
{
printf("bad - %u %u\n", h, rh);
bail("insert");
}
}
void remove(int k, bool should_be_null = false)
{
unsigned rh = remove_x(&tree, k);
if (rh == ~0)
{
if (!should_be_null)
{
printf("null key=%d\n", k);
bail("remove");
}
}
else
{
if (should_be_null)
{
printf("not null key=%d rh=%u\n", k, rh);
bail("remove");
}
rh &= ~HIGH_BIT;
if (arr[rh].val != k)
{
printf("wrong key=%d rh=%u [rh].val=%d\n", k, rh, arr[rh].val);
bail("remove");
}
// Mark balance factor of node to indicate it's not in the tree.
arr[rh].bf = 123;
}
}
unsigned max_elems;
// Prior to starting a test, mark all the nodes to be used in the test
// with a bad balance factor. This makes it easy to tell which nodes
// are in the tree and which aren't.
void mark_bf(void)
{
unsigned i = max_elems;
while (i)
{
i--;
arr[i].bf = 123;
}
}
void search_test(int key, avl_search_type st, unsigned rh)
{
if (search_x(&tree, key, st) != (rh | HIGH_BIT))
{
printf("%d %x %u\n", key, (unsigned) st, rh);
bail("search_test");
}
iter it;
start_iter_x(&tree, &it, key, st);
if (get_iter_x(&it) != (rh | HIGH_BIT))
{
printf("%d %x %x %x\n", key, (unsigned) st, rh, get_iter_x(&it));
bail("search_test - iter");
}
if ((st == AVL_EQUAL) && (rh != ~0))
{
unsigned h = get_iter_x(&it);
iter it2 = it;
incr_iter_x(&it);
decr_iter_x(&it2);
if (get_iter_x(&it) != search_x(&tree, key, AVL_GREATER))
{
printf("%d %x %x %x\n", key, (unsigned) st, h, get_iter_x(&it));
bail("search_test - iter ++");
}
if (get_iter_x(&it2) != search_x(&tree, key, AVL_LESS))
{
printf("%d %x %x %x\n", key, (unsigned) st, h, get_iter_x(&it2));
bail("search_test - iter --");
}
}
return;
}
void search_test(unsigned h)
{
if (arr[h].bf == 123)
{
search_test(2 * h, AVL_EQUAL, ~0);
// Test subst function.
arr[400].val = 2 * h;
if (subst_x(&tree, 400 | HIGH_BIT) != ~0)
{
printf("max_elems=%u h=%x\n", max_elems, h);
bail("subst not there");
}
}
else
{
search_test(2 * h, AVL_EQUAL, h);
search_test(2 * h, AVL_LESS_EQUAL, h);
search_test(2 * h, AVL_GREATER_EQUAL, h);
search_test(2 * h + 1, AVL_EQUAL, ~0);
search_test(2 * h + 1, AVL_LESS, h);
search_test(2 * h + 1, AVL_LESS_EQUAL, h);
search_test(2 * h - 1, AVL_EQUAL, ~0);
search_test(2 * h - 1, AVL_GREATER, h);
search_test(2 * h - 1, AVL_GREATER_EQUAL, h);
// Test subst function.
arr[400].val = 2 * h - 1;
if (subst_x(&tree, 400 | HIGH_BIT) != ~0)
{
printf("max_elems=%u h=%x\n", max_elems, h);
bail("subst low");
}
arr[400].val = 2 * h;
if (subst_x(&tree, 400 | HIGH_BIT) != (h | HIGH_BIT))
{
printf("max_elems=%u h=%x\n", max_elems, h);
bail("subst in");
}
verify_tree();
if (subst_x(&tree, h | HIGH_BIT) != (400 | HIGH_BIT))
{
printf("max_elems=%u h=%x\n", max_elems, h);
bail("subst out");
}
arr[400].val = 2 * h + 1;
if (subst_x(&tree, 400 | HIGH_BIT) != ~0)
{
printf("max_elems=%u h=%x\n", max_elems, h);
bail("subst high");
}
}
}
void search_all(void)
{
unsigned h = max_elems, min = ~0, max = ~0;
while (h)
{
h--;
search_test(h);
if (arr[h].bf != 123)
{
if (max == ~0)
max = h;
min = h;
}
}
h = search_least_x(&tree);
if (h != (min | HIGH_BIT))
{
printf("%x %x\n", h, min);
bail("search_all least");
}
h = search_greatest_x(&tree);
if (h != (max | HIGH_BIT))
{
printf("%x %x\n", h, max);
bail("search_all greatest");
}
iter it;
init_iter_x(&it);
if (get_iter_x(&it) != ~0)
bail("search_all least - init iter");
// Test forward iteration through entire tree.
start_iter_least_x(&tree, &it);
if (get_iter_x(&it) != (min | HIGH_BIT))
{
printf("%x %x\n", h, min);
bail("search_all least - iter");
}
while (get_iter_x(&it) != (max | HIGH_BIT))
{
h = get_iter_x(&it);
incr_iter_x(&it);
if (get_iter_x(&it) != search_x(&tree, 2 * h, AVL_GREATER))
{
printf("%x %x\n", h, get_iter_x(&it));
bail("search_all increment - iter");
}
}
incr_iter_x(&it);
if (get_iter_x(&it) != ~0)
bail("search_all increment - end");
// Test backward iteration through entire tree.
start_iter_greatest_x(&tree, &it);
if (get_iter_x(&it) != (max | HIGH_BIT))
{
printf("%x %x\n", h, max);
bail("search_all greatest - iter");
}
while (get_iter_x(&it) != (min | HIGH_BIT))
{
h = get_iter_x(&it);
decr_iter_x(&it);
if (get_iter_x(&it) != search_x(&tree, 2 * h, AVL_LESS))
{
printf("%x %x\n", h, get_iter_x(&it));
bail("search_all increment - iter");
}
}
decr_iter_x(&it);
if (get_iter_x(&it) != ~0)
bail("search_all increment - end");
}
void dump(unsigned subroot, unsigned depth)
{
if (arr[subroot].lt != ~0)
dump(arr[subroot].lt, depth + 1);
printf("%u(%u, %d) ", subroot, depth, arr[subroot].bf);
if (arr[subroot].gt != ~0)
dump(arr[subroot].gt, depth + 1);
}
void dump(void)
{
if (tree.root != ~0)
dump(tree.root & ~HIGH_BIT, 0);
putchar('\n');
}
// Create a tree with the nodes whose handles go from 0 to max_elems - 1.
// Insert step and remove step parameters must be relatively prime to
// max_elems.
void big_test(unsigned in_step, unsigned rm_step)
{
unsigned in = 0, rm = 0;
printf("inserting\n");
do
{
insert(in);
verify_tree();
in += in_step;
in %= max_elems;
}
while (in != 0);
search_all();
printf("removing\n");
for ( ; ; )
{
remove(rm * 2);
rm += rm_step;
rm %= max_elems;
if (rm == 0)
break;
verify_tree();
}
check_empty();
}
// Iterate through all the possible topologies of AVL trees with a
// certain depth. The trees are created in the "shadow" node array,
// then copied into the main node array.
class possible_trees
{
private:
// 1-base depth.
unsigned depth_;
// Subtree description structure. size is number of nodes in subtree.
struct sub { unsigned root, size; };
sub t;
// Create "first" subtree of a given depth with the node whose unsigned
// is "start" as the node with the minimum key in the tree. balance
// factors of nodes with children are all -1 in the first subtree.
sub first(unsigned start, unsigned depth)
{
sub s;
if (depth == 0)
{
s.size = 0;
s.root = ~0;
}
else if (depth == 1)
{
arr2[start].bf = 0;
arr2[start].lt = ~0;
arr2[start].gt = ~0;
s.size = 1;
s.root = start;
}
else
{
s = first(start, depth - 1);
start += s.size;
arr2[start].bf = -1;
arr2[start].lt = s.root;
sub s2 = first(start + 1, depth - 2);
arr2[start].gt = s2.root;
s.root = start;
s.size += s2.size + 1;
}
return(s);
}
// If there is no "next" subtree, returns a subtree description with
// a size of zero.
sub next(unsigned start, unsigned subroot, unsigned depth)
{
sub s;
if (depth < 2)
// For a subtree of depth 1 (1 node), the first topology is the
// only topology, so no next.
s.size = 0;
else
{
// Get next greater subtree.
s = next(subroot + 1, arr2[subroot].gt,
depth - (arr2[subroot].bf == -1 ? 2 : 1));
if (s.size != 0)
{
arr2[subroot].gt = s.root;
s.size += subroot - start + 1;
s.root = subroot;
}
else
{
// No next greater subtree. Get next less subtree, and
// start over with first greater subtree.
int bf = arr2[subroot].bf;
s = next(start, arr2[subroot].lt, depth - (bf == 1 ? 2 : 1));
if (s.size == 0)
{
// No next less subtree.
if (bf == 1)
// No next balance factor.
return(s);
// Go to next balance factor, then start iteration
// all over with first less and first greater subtrees.
bf++;
s = first(start, depth - (bf == 1 ? 2 : 1));
}
start += s.size;
arr2[start].lt = s.root;
s.root = start;
sub s2 = first(s.root + 1, depth - (bf == -1 ? 2 : 1));
arr2[s.root].gt = s2.root;
arr2[s.root].bf = bf;
s.size += s2.size + 1;
}
}
return(s);
}
void dump(unsigned subroot, unsigned depth)
{
if (arr2[subroot].lt != ~0)
dump(arr2[subroot].lt, depth + 1);
printf("%u(%u, %d) ", subroot, depth, arr2[subroot].bf);
if (arr2[subroot].gt != ~0)
dump(arr2[subroot].gt, depth + 1);
}
public:
// Copy from shadow node array to main node array and set tree root.
void place(void)
{
memcpy(arr, arr2, t.size * sizeof(arr[0]));
tree.root = t.root | HIGH_BIT;
}
void first(unsigned d) { depth_ = d; t = first(0, depth_); }
bool next(void)
{
if (t.size == 0)
bail("possible_trees::next");
t = next(0, t.root, depth_);
return(t.size > 0);
}
void dump(void) { dump(t.root, 0); putchar('\n'); }
possible_trees(void) { t.size = 0; }
};
possible_trees pt;
// Tests for each tree in the iteration.
void one_tree(void)
{
pt.place();
unsigned h = search_least_x(&tree);
while (h != ~0)
{
arr[400].val = 2 * h - 1;
insert(400);
verify_tree();
pt.place();
arr[400].val = 2 * h + 1;
insert(400);
verify_tree();
pt.place();
remove(2 * h);
verify_tree();
pt.place();
h = search_x(&tree, 2 * h, AVL_GREATER);
}
}
void all_trees(unsigned depth)
{
pt.first(depth);
do
one_tree();
while (pt.next());
}
// Array of handles in order by node key.
unsigned h_arr[400];
// Test the build member function template by building tress with from 1
// to 400 nodes.
void build_test(void)
{
unsigned i;
build_x(&tree, h_arr, 0);
check_empty();
for (i = 0; i < 400; i++)
{
h_arr[i] = i | HIGH_BIT;
build_x(&tree, h_arr, i + 1);
verify_tree();
}
}
int main()
{
unsigned i;
init_x(&tree);
for (i = 0; i < 400; i++)
arr2[i].val = i * 2;
memcpy(arr, arr2, sizeof(arr));
max_elems = 3;
mark_bf();
printf("0 nodes\n");
check_empty();
search_all();
printf("1 node\n");
insert(1);
insert(1);
verify_tree();
search_all();
remove(2);
remove(2, true);
check_empty();
printf("2 nodes less slant\n");
insert(2);
insert(2);
insert(1);
insert(1);
verify_tree();
search_all();
remove(2);
remove(2, true);
insert(1);
verify_tree();
remove(4);
remove(4, true);
verify_tree();
remove(2);
check_empty();
printf("2 nodes greater slant\n");
insert(1);
insert(1);
insert(2);
insert(2);
verify_tree();
search_all();
remove(4);
remove(4, true);
insert(2);
verify_tree();
remove(2);
remove(2, true);
verify_tree();
remove(4);
check_empty();
max_elems = 400;
printf("%u nodes\n", max_elems);
mark_bf();
big_test(3, 7);
big_test(13, 7);
printf("all trees depth 3\n");
all_trees(3);
printf("all trees depth 4\n");
all_trees(4);
printf("all trees depth 5\n");
all_trees(5);
printf("build test\n");
build_test();
printf("SUCCESS!\n");
return(0);
}
#define AVL_NULL (~0)
static unsigned AVL_GET_LESS(unsigned h, bool access)
{
if (!(h & HIGH_BIT))
bail("get_less");
unsigned child = arr[h & ~HIGH_BIT].lt;
if (access)
child |= HIGH_BIT;
return(child);
}
static void set_less(unsigned h, unsigned lh)
{
if (!(h & HIGH_BIT))
{
printf("%x %x\n", h, lh);
bail("set_less");
}
if (lh != ~0)
lh &= ~HIGH_BIT;
arr[h & ~HIGH_BIT].lt = lh;
}
#define AVL_SET_LESS(H, LH) set_less((H), (LH));
static unsigned AVL_GET_GREATER(unsigned h, bool access)
{
if (!(h & HIGH_BIT))
bail("get_greater");
unsigned child = arr[h & ~HIGH_BIT].gt;
if (access)
child |= HIGH_BIT;
return(child);
}
static void set_greater(unsigned h, unsigned gh)
{
if (!(h & HIGH_BIT))
bail("set_greater");
if (gh != ~0)
gh &= ~HIGH_BIT;
arr[h & ~HIGH_BIT].gt = gh;
}
#define AVL_SET_GREATER(H, LH) set_greater((H), (LH));
static int AVL_GET_BALANCE_FACTOR(unsigned h)
{
if (!(h & HIGH_BIT))
bail("get_balance_factor");
return(arr[h & ~HIGH_BIT].bf);
}
static void set_balance_factor(unsigned h, int bf)
{
if (!(h & HIGH_BIT))
bail("set_balance_factor");
arr[h & ~HIGH_BIT].bf = bf;
}
#define AVL_SET_BALANCE_FACTOR(H, BF) set_balance_factor((H), (BF));
static int AVL_COMPARE_KEY_NODE(int k, unsigned h)
{
if (!(h & HIGH_BIT))
bail("compare_key_node");
return(k - arr[h & ~HIGH_BIT].val);
}
static int AVL_COMPARE_NODE_NODE(unsigned h1, unsigned h2)
{
if (!(h1 & HIGH_BIT))
bail("compare_node_node - h1");
if (!(h2 & HIGH_BIT))
bail("compare_node_node - h2");
return(arr[h1 & ~HIGH_BIT].val - arr[h2 & ~HIGH_BIT].val);
}
#define AVL_BUILD_ITER_VAL(I) (*I)
#define AVL_BUILD_ITER_INCR(I) (I)++;
#undef AVL_IMPL_MASK
#define AVL_IMPL_MASK AVL_IMPL_INIT
#define AVL_NO_TREE_USE
#include "cavl_impl.h"
#undef AVL_IMPL_MASK
#define AVL_IMPL_MASK AVL_IMPL_IS_EMPTY
#include "cavl_impl.h"
#undef AVL_IMPL_MASK
#define AVL_IMPL_MASK AVL_IMPL_INSERT
#include "cavl_impl.h"
#undef AVL_IMPL_MASK
#define AVL_IMPL_MASK AVL_IMPL_SEARCH
#include "cavl_impl.h"
#undef AVL_IMPL_MASK
#define AVL_IMPL_MASK AVL_IMPL_SEARCH_LEAST
#include "cavl_impl.h"
#undef AVL_IMPL_MASK
#define AVL_IMPL_MASK AVL_IMPL_SEARCH_GREATEST
#include "cavl_impl.h"
#undef AVL_IMPL_MASK
#define AVL_IMPL_MASK AVL_IMPL_REMOVE
#include "cavl_impl.h"
#undef AVL_IMPL_MASK
#define AVL_IMPL_MASK AVL_IMPL_BUILD
#include "cavl_impl.h"
#undef AVL_IMPL_MASK
#define AVL_IMPL_MASK AVL_IMPL_START_ITER
#include "cavl_impl.h"
#undef AVL_IMPL_MASK
#define AVL_IMPL_MASK AVL_IMPL_START_ITER_LEAST
#include "cavl_impl.h"
#undef AVL_IMPL_MASK
#define AVL_IMPL_MASK AVL_IMPL_START_ITER_GREATEST
#include "cavl_impl.h"
#undef AVL_IMPL_MASK
#define AVL_IMPL_MASK AVL_IMPL_GET_ITER
#include "cavl_impl.h"
#undef AVL_IMPL_MASK
#define AVL_IMPL_MASK AVL_IMPL_INCR_ITER
#include "cavl_impl.h"
#undef AVL_IMPL_MASK
#define AVL_IMPL_MASK AVL_IMPL_DECR_ITER
#include "cavl_impl.h"
#undef AVL_IMPL_MASK
#define AVL_IMPL_MASK AVL_IMPL_INIT_ITER
#include "cavl_impl.h"
#undef AVL_IMPL_MASK
#define AVL_IMPL_MASK AVL_IMPL_SUBST
#include "cavl_impl.h"
(
geocities.com/wkaras)