/*
* Copyright (c) 2002-2004 Sendmail, Inc. and its suppliers.
* All rights reserved.
*
* By using this file, you agree to the terms and conditions set
* forth in the LICENSE file which can be found at the top level of
* the sendmail distribution.
*/
#include "sm/generic.h"
SM_RCSID("@(#)$Id: t-tree-2.c,v 1.6 2004/12/26 04:08:53 ca Exp $")
#include "sm/assert.h"
#include "sm/heap.h"
#include "sm/test.h"
#include "sm/tree.h"
#include <stdio.h>
uint state[] =
{
0x934a0b83,
0x589ce730,
0x938cde01,
0x20992cea,
0x49120598,
0xc492ce22,
0x092c98ef,
0x68013da8,
0x34927491,
0x78934289,
0xc8734ea8,
0x2390437c,
0x8c09a24f,
0x494710ee,
0x94892188,
0x94810cbf
};
typedef struct node node_T;
struct node
{
sm_tree_node_P tree_node;
long value;
node_T *next;
};
static int
compare(sm_tree_key_T oa, sm_tree_key_T ob, uint len)
{
long *a;
long *b;
a = (long *) oa;
b = (long *) ob;
if (*a < *b)
return -1;
else if (*a == *b)
return 0;
else
return 1;
}
static int
compare_nodes(sm_tree_node_P oa, sm_tree_node_P ob)
{
return compare(oa->sm_tree_key, ob->sm_tree_key, sizeof(long));
}
node_T *root;
int limit;
int *hist;
long *keys;
int run_length;
#define TREE_INS(x, y) \
do { \
result = sm_tree_add(tree, (sm_tree_key_T) &keys[x], sizeof(long *), (void *) &keys[y]); \
SM_TEST(result >= 0); \
if (result < 0) \
{ \
fprintf(stderr, "sm_tree_add failed\n"); \
exit(1); \
} \
} while (0)
#define TREE_SEARCH(r) sm_tree_lookup(tree, (sm_tree_key_T) &keys[r], sizeof(long *))
#define TREE_RM(r) sm_tree_rm(tree, (sm_tree_key_T) &keys[r], sizeof(long *))
static int
validate_node(sm_tree_node_T *current, int *count, int check_order, int check_heights)
{
int left_height;
int right_height;
int height;
right_height = 0;
left_height = 0;
if (count != NULL)
(*count)++;
if (current->sm_tree_left != NULL)
{
SM_TEST(current->sm_tree_left->sm_tree_parent == current);
if (check_order)
{
SM_TEST(compare_nodes(current,
current->sm_tree_left) == 1);
}
left_height = validate_node(current->sm_tree_left, count,
check_order, check_heights);
}
if (current->sm_tree_right != NULL)
{
SM_TEST(current->sm_tree_right->sm_tree_parent == current);
if (check_order)
SM_TEST(compare_nodes(current,
current->sm_tree_right) == -1);
right_height = validate_node(current->sm_tree_right, count,
check_order, check_heights);
}
if (check_heights)
SM_TEST(abs(right_height - left_height) <= 1);
/*
if (check_heights)
{
if (left_height > right_height)
SM_TEST(current->an_balance == b_left);
else if (right_height > left_height)
SM_TEST(current->an_balance == b_right);
else
SM_TEST(current->an_balance == b_even);
}
*/
height = SM_MAX(right_height, left_height) + 1;
return height;
}
static int
validate_tree(sm_tree_T *otree, int check_order, int check_heights)
{
sm_tree_T *tree;
sm_tree_node_T *current;
int count;
int height;
tree = otree;
current = tree->sm_tree_root;
count = 0;
if (current != NULL)
height = validate_node(current, &count,
check_order, check_heights);
return count;
}
static int
validate_tree2(sm_tree_T *tree)
{
sm_tree_node_T *current;
int count;
current = sm_tree_first(tree);
count = 0;
while (current != NULL)
{
current = sm_tree_next(tree, current);
++count;
}
return count;
}
static void
validate_chain(sm_tree_T *otree, int size)
{
sm_tree_T *tree;
sm_tree_node_T *current;
sm_tree_node_T *next;
int count;
tree = otree;
current = sm_tree_first(tree);
if (current == NULL)
{
SM_TEST(size == 0);
return;
}
while (current->sm_tree_left != NULL)
current = current->sm_tree_left;
count = 1;
do
{
next = sm_tree_next(otree, current);
if (next != NULL)
{
count++;
/*
SM_TEST(((node_T*) next)->value >
((node_T*) current)->value);
*/
SM_TEST(compare_nodes(next, current) == 1);
}
current = next;
} while (next != NULL);
SM_TEST(count == size);
return;
}
int
main(int argc, char* *argv)
{
sm_tree_T *tree;
sm_tree_node_T *tree_node;
node_T *node;
node_T *prev;
int i, j, result;
long target;
int size;
int validated_size;
int insertions;
int deletions;
root = NULL;
limit = 200;
hist = NULL;
keys = NULL;
run_length = 10000;
sm_test_begin(argc, argv, "test sm_tree");
if (argc == 2)
run_length = atoi(argv [1]);
if (run_length <= 0)
{
fprintf(stderr, "Usage: %s <run length>\n", argv[0]);
exit(1);
}
initstate((ulong) 0x482094872L, (char *) state, sizeof state);
tree = sm_tree_create(NULL, 0, compare);
SM_TEST(tree != NULL);
hist = malloc(sizeof(*hist) * (limit + 1));
SM_TEST(hist != NULL);
if (hist == NULL)
goto error;
keys = malloc(sizeof(*keys) * (limit + 1));
SM_TEST(keys != NULL);
if (keys == NULL)
goto error;
size = 0;
insertions = 0;
deletions = 0;
for (i = 0; i <= limit; i++)
{
hist[i] = 0;
again:
keys[i] = random();
for (j = 0; j < i; j++)
{
if (keys[i] == keys[j])
goto again;
}
}
for (i = 0; i < run_length; i++)
{
if (size >= limit || ((random () & 1) && size > 0))
{
target = random() & 0xfffffff;
target %= size;
node = root;
prev = NULL;
while (target > 0)
{
prev = node;
node = node->next;
target--;
}
if (prev == NULL)
root = node->next;
else
prev->next = node->next;
node->next = NULL;
TREE_RM(node->value);
deletions++;
size--;
free(node);
}
else
{
node = malloc(sizeof(node_T));
SM_TEST(node != NULL);
if (node == NULL)
goto error;
node->value = random() % limit;
tree_node = TREE_SEARCH(node->value);
if (tree_node == NULL)
{
TREE_INS(node->value, node->value);
SM_TEST(result >= 0);
if (result >= 0)
{
size++;
node->next = root;
root = node;
insertions++;
}
else
free(node);
}
else
free(node);
}
validated_size = validate_tree(tree, true, true);
SM_TEST(validated_size == size);
if (validated_size != size)
{
SmTestVerbose = 1;
SM_TEST(validated_size == validate_tree2(tree));
}
validate_chain(tree, size);
if (SmTestVerbose && (i % 1000 == 0))
printf("Interation %d, size %d (%d i, %d d)\n",
i, size, insertions, deletions);
SM_TEST(size <= limit);
hist[size]++;
}
if (SmTestVerbose)
{
printf("%-6.6s %-8.8s\n", " Size", " Count");
for (i = 0; i <= limit; i++)
printf("%6d %8d\n", i, hist [i]);
}
error:
if (tree != NULL)
sm_tree_destroy(tree);
if (keys != NULL)
free(keys);
if (hist != NULL)
free(hist);
return sm_test_end();
}
syntax highlighted by Code2HTML, v. 0.9.1