/*
 * Copyright (c) 2002, 2004, 2005 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: tree2.c,v 1.10 2005/07/12 23:23:38 ca Exp $")

#include "sm/error.h"
#include "sm/assert.h"
#include "sm/tree.h"

/*
**  XXX need to assign proper error module, look for sm_error_gen()
*/

/* local functions */
static void	 sm_tree_rotate_left(sm_tree_node_P *);
static void	 sm_tree_rotate_right(sm_tree_node_P *);

/*
**  SM_TREE_ROTATE_LEFT -- rotate tree left
**
**	Parameters:
**		n -- node to rotate
**
**	Returns:
**		nothing.
*/

static void
sm_tree_rotate_left(sm_tree_node_P *n)
{
	sm_tree_node_P q, p;

	SM_REQUIRE(n != NULL);
	SM_REQUIRE(*n != NULL);
#if SM_TREE_STAT
	++sm_tree_rotates;
#endif /* SM_TREE_STAT */
	q = *n;
	p = (*n)->sm_tree_parent;
	(*n)->sm_tree_parent = (*n)->sm_tree_right;
	*n = (*n)->sm_tree_right;
	(*n)->sm_tree_parent = p;
	q->sm_tree_right = (*n)->sm_tree_left;
	if (q->sm_tree_right != NULL)
		q->sm_tree_right->sm_tree_parent = q;
	(*n)->sm_tree_left = q;
	q->sm_tree_balance--;
	if ((*n)->sm_tree_balance > 0)
		q->sm_tree_balance -= (*n)->sm_tree_balance;
	(*n)->sm_tree_balance--;
	if (q->sm_tree_balance < 0)
		(*n)->sm_tree_balance += q->sm_tree_balance;
}

/*
**  SM_TREE_ROTATE_RIGHT -- rotate tree right
**
**	Parameters:
**		n -- node to rotate
**
**	Returns:
**		nothing.
*/

static void
sm_tree_rotate_right(sm_tree_node_P *n)
{
	sm_tree_node_P q, p;

	SM_REQUIRE(n != NULL);
	SM_REQUIRE(*n != NULL);
#if SM_TREE_STAT
	++sm_tree_rotates;
#endif /* SM_TREE_STAT */
	q = *n;
	p = (*n)->sm_tree_parent;
	(*n)->sm_tree_parent = (*n)->sm_tree_left;
	*n = (*n)->sm_tree_left;
	(*n)->sm_tree_parent = p;
	q->sm_tree_left = (*n)->sm_tree_right;
	if (q->sm_tree_left != NULL)
		q->sm_tree_left->sm_tree_parent = q;
	(*n)->sm_tree_right = q;
	q->sm_tree_balance++;
	if ((*n)->sm_tree_balance < 0)
		q->sm_tree_balance -= (*n)->sm_tree_balance;
	(*n)->sm_tree_balance++;
	if (q->sm_tree_balance > 0)
		(*n)->sm_tree_balance += q->sm_tree_balance;
}

/*
**  SM_TREE_INSERT2 -- insert a new node into a tree or overwrite the
**	data in an existing node
**
**	Parameters:
**		tree -- tree
**		n -- initial node
**		p -- should be NULL initially (used for recursion)
**		key -- key for insertion
**		len -- len of key
**		data -- data to insert
**
**	Returns:
**		>=0 on success (difference in height)
**		< 0 error code
*/

int
sm_tree_insert2(sm_tree_P tree, sm_tree_node_P *n, sm_tree_node_P p, sm_tree_key_T key, uint len, sm_tree_data_T data)
{
	int done;
	int cmp;

	SM_REQUIRE(n != NULL);
	done = 0;
	if (*n == NULL)
	{
		sm_ret_T ret;

		ret = sm_tree_node_alloc(tree, n, key, len, data);
		if (sm_is_err(ret))
			return ret;
		(*n)->sm_tree_parent = p;
		done = 1;
	}
	else
	{
		cmp = tree->sm_tree_compare(key, (*n)->sm_tree_key, len);
		if (cmp > 0)
		{
			if (sm_tree_insert2(tree, &(*n)->sm_tree_right, *n,
					key, len, data) > 0)
			{
				(*n)->sm_tree_balance++;
				if ((*n)->sm_tree_balance == 1)
					done = 1;
				else if ((*n)->sm_tree_balance == 2)
				{
					if ((*n)->sm_tree_right->sm_tree_balance
					    == -1)
						sm_tree_rotate_right(&(*n)->sm_tree_right);
					sm_tree_rotate_left(n);
				}
			}
		}
		else if (cmp < 0)
		{
			if (sm_tree_insert2(tree, &(*n)->sm_tree_left, *n,
					key, len, data) > 0)
			{
				(*n)->sm_tree_balance--;
				if ((*n)->sm_tree_balance == -1)
					done = 1;
				else if ((*n)->sm_tree_balance == -2)
				{
					if ((*n)->sm_tree_left->sm_tree_balance
					    == 1)
						sm_tree_rotate_left(&(*n)->sm_tree_left);
					sm_tree_rotate_right(n);
				}
			}
		}
		else
		{
			/* found key: overwrite data */
			sm_tree_assign_data((*n)->sm_tree_data, data);
		}
	}
	return done;
}

/*
**  SM_TREE_REMOVE2 -- remove a node from a tree
**
**	Parameters:
**		tree -- tree
**		n -- initial node
**		p -- should be NULL initially (used for recursion)
**		key -- key of node to remove
**		len -- len of key
**
**	Returns:
**		>=0: node removed
**			0: no rebalancing necessary
**			1: rebalancing might be necessary
**		-1: node not found
*/

int
sm_tree_remove2(sm_tree_P tree, sm_tree_node_P *n, sm_tree_node_P p, sm_tree_key_T key, uint len)
{
	int done;
	int c;

	SM_REQUIRE(n != NULL);
	if (*n == NULL)
		return -1;
	done = 0;
	c = tree->sm_tree_compare(key, (*n)->sm_tree_key, len);
	if (c < 0)
	{
		if (sm_tree_remove2(tree, &(*n)->sm_tree_left, *n, key, len)
			> 0)
		{
			(*n)->sm_tree_balance++;
			if ((*n)->sm_tree_balance == 0)
				done = 1;
			else if ((*n)->sm_tree_balance == 2)
			{
				if ((*n)->sm_tree_right->sm_tree_balance == -1)
					sm_tree_rotate_right(&(*n)->sm_tree_right);
				sm_tree_rotate_left(n);
				if ((*n)->sm_tree_balance == 0)
					done = 1;
			}
		}
	}
	else if (c > 0)
	{
		if (sm_tree_remove2(tree, &(*n)->sm_tree_right, *n, key, len)
			> 0)
		{
			(*n)->sm_tree_balance--;
			if ((*n)->sm_tree_balance == 0)
				done = 1;
			else if ((*n)->sm_tree_balance == -2)
			{
				if ((*n)->sm_tree_left->sm_tree_balance == 1)
					sm_tree_rotate_left(&(*n)->sm_tree_left);
				sm_tree_rotate_right(n);
				if ((*n)->sm_tree_balance == 0)
					done = 1;
			}
		}
	}
	else
	{
		/* found, now remove it properly */
		if ((*n)->sm_tree_right == NULL)
		{
			sm_tree_node_P n0;

			n0 = *n;
			*n = (*n)->sm_tree_left;
			if (*n != NULL)
				(*n)->sm_tree_parent = p;
			sm_tree_node_free(tree, n0);
			done = 1;
			SM_ASSERT(tree->sm_tree_used > 0);
			--tree->sm_tree_used;
		}
		else if ((*n)->sm_tree_left == NULL)
		{
			sm_tree_node_P n0;

			n0 = *n;
			*n = (*n)->sm_tree_right;
			if (*n != NULL)
				(*n)->sm_tree_parent = p;
			sm_tree_node_free(tree, n0);
			done = 1;
			SM_ASSERT(tree->sm_tree_used > 0);
			--tree->sm_tree_used;
		}
		else
		{
			sm_tree_node_P *qq;

			qq = &(*n)->sm_tree_left;
			while ((*qq)->sm_tree_right != NULL)
				qq = &(*qq)->sm_tree_right;
			sm_tree_assign_key((*n)->sm_tree_key,
					(*qq)->sm_tree_key);
			sm_tree_assign_key((*qq)->sm_tree_key, key);
			sm_tree_assign_data((*n)->sm_tree_data,
					(*qq)->sm_tree_data);
			if (sm_tree_remove2(tree, &(*n)->sm_tree_left, *n, key,
				len) > 0)
			{
				(*n)->sm_tree_balance++;
				if ((*n)->sm_tree_balance == 0)
					done = 1;
				else if ((*n)->sm_tree_balance == 2)
				{
					if ((*n)->sm_tree_right->sm_tree_balance == -1)
						sm_tree_rotate_right(&(*n)->sm_tree_right);
					sm_tree_rotate_left(n);
					if ((*n)->sm_tree_balance == 0)
						done = 1;
				}
			}
		}
	}
	return done;
}