/*
 * Copyright (c) 2002 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-fn.c,v 1.5 2002/10/17 22:33:10 ca Exp $")

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

/*
**  SM_TREE_FIRST -- return first (leftmost) node in a tree
**
**	Parameters:
**		tree -- tree
**
**	Returns:
**		first node (NULL if n is NULL)
*/

sm_tree_node_P
sm_tree_first(sm_tree_P tree)
{
	sm_tree_node_P node;

	SM_REQUIRE(tree != NULL);
	node = tree->sm_tree_root;
	if (node == NULL)
		return NULL;
	while (node->sm_tree_parent != NULL)
		node = node->sm_tree_parent;
	while (node->sm_tree_left != NULL)
		node = node->sm_tree_left;
	return node;
}

/*
**  SM_TREE_NEXT -- return next node in a tree
**
**	Parameters:
**		tree -- tree
**		node -- current node
**
**	Returns:
**		next node (NULL if node is NULL)
*/

sm_tree_node_P
sm_tree_next(sm_tree_P tree, sm_tree_node_P node)
{
	SM_REQUIRE(tree != NULL);
	if (node == NULL)
		return NULL;
	if (node->sm_tree_right != NULL)
	{
		node = node->sm_tree_right;
		while (node->sm_tree_left != NULL)
			node = node->sm_tree_left;
	}
	else
	{
		if (node->sm_tree_parent != NULL &&
		    (node == node->sm_tree_parent->sm_tree_left))
			node = node->sm_tree_parent;
		else
		{
			while (node->sm_tree_parent != NULL &&
			       (node == node->sm_tree_parent->sm_tree_right))
				node = node->sm_tree_parent;
			node = node->sm_tree_parent;
		}
	}
	return node;
}