/*
 * 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: tree.c,v 1.12 2005/07/12 23:23:38 ca Exp $")

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

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

/*
**  SM_TREE_CREATE -- create a new tree
**
**	Parameters:
**		rpool -- rpool
**		limit -- maximum number of entries
**		tree_compare -- function to compare keys
**
**	Returns:
**		tree (NULL on failure)
*/

sm_tree_P
sm_tree_create(sm_rpool_P rpool, uint limit, sm_tree_compare_T tree_compare)
{
	sm_tree_P tree;

	SM_REQUIRE(tree_compare != NULL);
	tree = (sm_tree_P) sm_rpool_zalloc(rpool, sizeof(*tree));
	if (tree == NULL)
		return NULL;
	tree->sm_tree_root = NULL;
	tree->sm_tree_rpool = rpool;
	tree->sm_tree_compare = tree_compare;
	tree->sm_tree_limit = limit;
	return tree;
}

/*
**  SM_TREE_NODE_ALLOC -- allocate a new node
**
**	Parameters:
**		tree -- tree
**		n -- node to allocate (return value)
**		key -- key for insertion
**		len -- len of key
**		data -- data to insert
**
**	Returns:
**		==0 on success
**		< 0 error code
*/

sm_ret_T
sm_tree_node_alloc(sm_tree_P tree, sm_tree_node_P *n, sm_tree_key_T key, uint len, sm_tree_data_T data)
{
	SM_REQUIRE(n != NULL);
	*n = (sm_tree_node_P) sm_rpool_malloc(tree->sm_tree_rpool, sizeof(**n));
	if (*n == NULL)
		return sm_error_gen(0, SM_ERR_TEMP, ENOMEM);
	sm_tree_assign_key((*n)->sm_tree_key, key);
	(*n)->sm_tree_key_len = len;
	sm_tree_assign_data((*n)->sm_tree_data, data);
	(*n)->sm_tree_balance = 0;
	(*n)->sm_tree_parent = (*n)->sm_tree_left = (*n)->sm_tree_right = NULL;
	return SM_SUCCESS;
}

/*
**  SM_TREE_NODE_FREE -- free a new node
**
**	Parameters:
**		tree -- tree
**		n -- node to free
**
**	Returns:
**		==0 on success
**		< 0 error code
*/

sm_ret_T
sm_tree_node_free(sm_tree_P tree, sm_tree_node_P n)
{
	if (n == NULL)
		return SM_SUCCESS;
	SM_REQUIRE(tree != NULL);
#if PURIFY
	if (n->sm_tree_parent != NULL)
	{
		if (n == n->sm_tree_parent->sm_tree_left)
			n->sm_tree_parent->sm_tree_left = NULL;
		else if (n == n->sm_tree_parent->sm_tree_right)
			n->sm_tree_parent->sm_tree_right = NULL;
	}
#endif /* PURIFY */
	sm_rpool_free(tree->sm_tree_rpool, n);
	return SM_SUCCESS;
}


/*
**  SM_TREE_ADD -- add a new node into a tree
**
**	Parameters:
**		tree -- tree
**		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_add(sm_tree_P tree, sm_tree_key_T key, uint len, sm_tree_data_T data)
{
	SM_REQUIRE(tree != NULL);

	/* XXX this doesn't work if we only want to overwrite a node */
	if (tree->sm_tree_limit > 0 &&
	    tree->sm_tree_limit >= tree->sm_tree_used)
		return sm_error_gen(0, SM_ERR_TEMP, E2BIG);
	++tree->sm_tree_used;
	if (tree->sm_tree_root == NULL)
		return sm_tree_node_alloc(tree, &(tree->sm_tree_root),
					key, len, data);
	return sm_tree_insert2(tree, &(tree->sm_tree_root), NULL,
				key, len, data);
}

/*
**  SM_TREE_RM -- remove a node from a tree
**
**	Parameters:
**		tree -- tree
**		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_rm(sm_tree_P tree, sm_tree_key_T key, uint len)
{
	SM_REQUIRE(tree != NULL);
	if (tree->sm_tree_root == NULL)
		return -1;
	return sm_tree_remove2(tree, &(tree->sm_tree_root), NULL, key, len);
}