/*
 * Copyright (c) 2003, 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-bsd-tree-0.c,v 1.4 2004/12/26 04:08:53 ca Exp $")

#include "sm/assert.h"
#include "sm/heap.h"
#include "sm/test.h"
#include "sm/bsd-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, *node_P;
typedef struct t_tree t_tree_T, *t_tree_P;

RB_HEAD(t_tree, node);

struct node
{
	RB_ENTRY(node)	entry;
	uint		key;
	long		value;
	node_P		next;
};

#if 0
static int
compare(long oa, long ob)
{
	if (oa < ob)
		return -1;
	else if (oa == ob)
		return 0;
	else
		return 1;
}
#endif /* 0 */

static int
compare_nodes(node_P oa, node_P ob)
{
	long a;
	long b;

	a = oa->key;
	b = ob->key;
	if (a < b)
		return -1;
	else if (a == b)
		return 0;
	else
		return 1;
}

RB_GENERATE(t_tree, node, entry, compare_nodes)

node_P	 root;
int	 limit;
int	*hist;
long	*keys;

#define TREE_SEARCH(elm, r) (elm).key = keys[r], RB_FIND(t_tree, tree, &(elm))

#define TREE_RM(r)					\
	do 						\
	{ 						\
		node_T elm;				\
		elm.key = keys[r];			\
		RB_REMOVE(t_tree, tree, &elm);		\
	} while (0)

static int
validate_node(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->entry.rbe_left != NULL)
	{
		SM_TEST(current->entry.rbe_left->entry.rbe_parent == current);

		if (check_order)
		{
			SM_TEST(compare_nodes(current,
					current->entry.rbe_left) == 1);
		}
		left_height = validate_node(current->entry.rbe_left, count,
						check_order, check_heights);
	}

	if (current->entry.rbe_right != NULL)
	{
		SM_TEST(current->entry.rbe_right->entry.rbe_parent == current);
		if (check_order)
			SM_TEST(compare_nodes(current,
					current->entry.rbe_right) == -1);
		right_height = validate_node(current->entry.rbe_right, count,
						check_order, check_heights);
	}
	if (check_heights)
	{
		SM_TEST(abs(right_height - left_height) <= 2);
		if (abs(right_height - left_height) > 2)
		{
			fprintf(stderr, "right_height=%d, left_height=%d\n",
				right_height, left_height);
		}
	}

/*
	if (check_heights)
	{
		if (left_height >entry. right_height)
			SM_TEST(current->entry.an_balance == b_left);
		else if (right_height > left_height)
			SM_TEST(current->entry.an_balance == b_right);
		else
			SM_TEST(current->entry.an_balance == b_even);
	}
*/
	height = SM_MAX(right_height, left_height) + 1;
	return height;
}

static int
validate_tree(t_tree_T *otree, int check_order, int check_heights)
{
	t_tree_T *tree;
	node_T *current;
	int count;
	int height;

	tree = otree;
	current = tree->rbh_root;
	count = 0;
	if (current != NULL)
		height = validate_node(current, &count,
					check_order, check_heights);
	return count;
}

static int
validate_tree2(t_tree_T *tree)
{
	node_T *current;
	int count;

	current = RB_MIN(t_tree, tree);
	count = 0;
	while (current != NULL)
	{
		current = RB_NEXT(t_tree, tree, current);
		++count;
	}
	return count;
}

static int
validate_tree3(t_tree_T *tree)
{
	int i;
	long value;
	node_T *node, *next, elm;

	for (i = 0; i < limit; i++)
	{
		value = random() % limit;
#if 0
		node = TREE_SEARCH(elm, value);
#else
		(elm).key = keys[value];
		node = RB_FIND(t_tree, tree, &(elm));
#endif
		if (node == NULL)
			continue;
		while ((next = RB_NEXT(t_tree, tree, node)) != NULL)
		{
			SM_TEST(compare_nodes(node, next));
			node = next;
		}
	}
	return 0;
}

static void
validate_chain(t_tree_T *otree, int size)
{
	t_tree_T *tree;
	node_T *current;
	node_T *next;
	int count;

	tree = otree;
	current = RB_MIN(t_tree, tree);
	if (current == NULL)
	{
		SM_TEST(size == 0);
		return;
	}
	while (current->entry.rbe_left != NULL)
		current = current->entry.rbe_left;

	count = 1;
	do
	{
		next = RB_NEXT(t_tree, 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)
{
	t_tree_T tree;
	node_T *tree_node;
	node_T *node, elm, *result;
	int  i, j;
	int  size;
	int  validated_size;
	int  insertions;
	int  deletions;
	int c;

	root = NULL;
	limit = 200;
	hist = NULL;
	keys = NULL;
	while ((c = getopt(argc, argv, "s:v")) != -1)
	{
		switch (c)
		{
		  case 's':
			limit = atoi(optarg);
			if (limit <= 0)
				return 1;
			break;
		}
	}
	sm_test_begin(argc, argv, "test bsd-tree-0");
	argc -= optind;
	argv += optind;

	initstate((ulong) 0x482094872L, (char *) state, sizeof state);
	RB_INIT(&tree);
	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 < limit; i++)
	{
		for (;;)
		{
			node = malloc(sizeof(node_T));
			if (node == NULL)
				goto error;
			node->value = random() % limit;
			node->key = keys[node->value];
#if 0
			tree_node = TREE_SEARCH(elm, node->value);
#else
			elm.key = keys[node->value];
			tree_node = RB_FIND(t_tree, &tree, &elm);
#endif
			if (tree_node == NULL)
			{
				result = RB_INSERT(t_tree, &tree, node);
				SM_TEST(result == NULL);
				if (result == NULL)
				{
					size++;
					node->next = root;
					root = node;
					insertions++;
					break;
				}
				else
				{
					fprintf(stderr,
						"result=%p, node=%p, result->value=%ld, node->value=%ld\n",
						result, node, result->value,
						node->value);
					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]++;
	}
	validate_tree3(&tree);
	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 0
	sm_tree_destroy(&tree);
#endif /* 0 */
	if (keys != NULL)
		free(keys);
	if (hist != NULL)
		free(hist);
	return sm_test_end();
}