/*
 * 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();
}