/*
 * 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-0.c,v 1.12 2005/06/16 20:36:49 ca Exp $")

#include <stdio.h>

#include "sm/tree.h"
#include "sm/test.h"

static int
sm_tree_key_compare(sm_tree_key_T k1, sm_tree_key_T k2, uint len)
{
	return (*(int *)k1) - (*(int *)k2);
}

#define TINS(x)	SM_TEST(sm_tree_add(tree, (const char *) &x, sizeof(int *), (void *) &x) >= 0)
#define TREE_SEARCH(r) sm_tree_lookup(tree, (sm_tree_key_T) &keys[r], sizeof(int *))
#define TREE_RM(r) sm_tree_rm(tree, (sm_tree_key_T) &keys[r], sizeof(int *))

#define L_START	10
#define L_OFF	10
#define L_END	200
#define L_ENTRIES ((L_END - L_START) / L_OFF + 1)

#define FOR(r)	for (r = L_START; r < L_END; r += L_OFF)

#define KEY_TEST(key, i)	\
	SM_TEST((void *) (key) == (void *) &keys[i])
#define NODE_TEST(i)	\
	SM_TEST(hn != NULL && \
		(void *) (hn->sm_tree_key) == (void *) (&keys[i]) && \
		(void *) (hn->sm_tree_data) == (void *) &keys[i])

static void
test2(void)
{
	int r, h, i;
	sm_tree_P tree;
	sm_tree_node_P tn;
	sm_tree_node_P hn;
	int keys[L_END];

	FOR(r)
	{
		keys[r] = r;
	}
	tree = sm_tree_create(NULL, 0, sm_tree_key_compare);
	SM_TEST(tree != NULL);
	tn = NULL;
	FOR(r)
	{
		TINS(keys[r]);
	}
	FOR(r)
	{
		hn = TREE_SEARCH(r);
		NODE_TEST(r);
	}
	FOR(r)
	{
		h = TREE_RM(r);
		hn = TREE_SEARCH(r);
		SM_TEST(hn == NULL);
		for (i = r + L_OFF; i < L_END; i += L_OFF)
		{
			hn = TREE_SEARCH(i);
			NODE_TEST(i);
		}
	}
	tn = NULL;
	FOR(r)
	{
		TINS(keys[r]);
	}
	FOR(r)
	{
		hn = TREE_SEARCH(r);
		NODE_TEST(r);
	}
	for (r = L_END - L_OFF; r >= L_START; r -= L_OFF)
	{
		hn = TREE_SEARCH(r);
		NODE_TEST(r);
		h = TREE_RM(r);
		hn = TREE_SEARCH(r);
		SM_TEST(hn == NULL);
		for (i = r - L_OFF; i >= L_START; i -= L_OFF)
		{
			hn = TREE_SEARCH(i);
			NODE_TEST(i);
		}
	}
	sm_tree_destroy(tree);
}

static void
test(void)
{
	int r;
	sm_tree_P tree;
	sm_tree_node_P tn;
	sm_tree_node_P hn;
	int keys[5];

	tree = sm_tree_create(NULL, 0, sm_tree_key_compare);
	SM_TEST(tree != NULL);
	keys[0] = 10;
	keys[1] = 5;
	keys[2] = 50;
	TINS(keys[0]);
	tn = tree->sm_tree_root;
	SM_TEST(tn->sm_tree_parent == NULL);
	SM_TEST(tn->sm_tree_left == NULL);
	SM_TEST(tn->sm_tree_right == NULL);
	KEY_TEST(tn->sm_tree_key, 0);
	TINS(keys[1]);
	SM_TEST(tn->sm_tree_parent == NULL);
	SM_TEST(tn->sm_tree_left != NULL);
	KEY_TEST(tn->sm_tree_left->sm_tree_key, 1);
	SM_TEST(tn->sm_tree_right == NULL);
	TINS(keys[2]);
	SM_TEST(tn->sm_tree_parent == NULL);
	SM_TEST(tn->sm_tree_left != NULL);
	SM_TEST(tn->sm_tree_right != NULL);
	KEY_TEST(tn->sm_tree_right->sm_tree_key, 2);

	hn = sm_tree_first(tree);
	NODE_TEST(1);
	hn = sm_tree_next(tree, hn);
	NODE_TEST(0);
	hn = sm_tree_next(tree, hn);
	NODE_TEST(2);

	hn = TREE_SEARCH(0);
	NODE_TEST(0);
	hn = TREE_SEARCH(1);
	NODE_TEST(1);
	hn = TREE_SEARCH(2);
	NODE_TEST(2);

	SM_TEST(tree->sm_tree_used == 3);
	r = TREE_RM(0);
	hn = TREE_SEARCH(0);
	SM_TEST(hn == NULL);
	SM_TEST(tree->sm_tree_used == 2);
	hn = TREE_SEARCH(1);
	NODE_TEST(1);
	hn = TREE_SEARCH(2);
	NODE_TEST(2);

	r = TREE_RM(0);
	SM_TEST(r == 0);	/* XXX not found? */
	SM_TEST(tree->sm_tree_used == 2);

	r = TREE_RM(2);
	SM_TEST(tree->sm_tree_used == 1);
	hn = TREE_SEARCH(2);
	SM_TEST(hn == NULL);
	hn = TREE_SEARCH(1);
	NODE_TEST(1);

	r = TREE_RM(1);
	SM_TEST(tree->sm_tree_used == 0);
	SM_TEST(r != -1);
	hn = TREE_SEARCH(1);
	SM_TEST(hn == NULL);
	sm_tree_destroy(tree);
}


int
main(int argc, char *argv[])
{
	sm_test_begin(argc, argv, "test tree 0");
	test();
	test2();
	return sm_test_end();
}