/*
 * 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.
 *
 *	$Id: tree.h,v 1.17 2005/06/16 00:09:35 ca Exp $
 */

#ifndef SM_TREE_H
#define SM_TREE_H 1

#include "sm/generic.h"
#include "sm/error.h"
#include "sm/rpool.h"

/*
**  Balanced tree data structure
*/

/* default data types, can be overridden */
#ifndef Tree_Key
# define Tree_Key const char *
#endif
#ifndef Tree_Data
# define Tree_Data void *
#endif

typedef Tree_Data		sm_tree_data_T;
typedef Tree_Key		sm_tree_key_T;

typedef int	 (*sm_tree_compare_T)(sm_tree_key_T, sm_tree_key_T, uint);

typedef struct sm_tree_node_S	sm_tree_node_T, *sm_tree_node_P;
struct sm_tree_node_S
{
	sm_tree_node_P	 sm_tree_parent;
	sm_tree_node_P	 sm_tree_left;
	sm_tree_node_P	 sm_tree_right;
	int		 sm_tree_balance;
	sm_tree_key_T	 sm_tree_key;
	uint		 sm_tree_key_len;
	sm_tree_data_T	 sm_tree_data;
};

typedef struct sm_tree	sm_tree_T, *sm_tree_P;
struct sm_tree
{
	sm_tree_node_P		 sm_tree_root;
	sm_tree_compare_T	 sm_tree_compare;
	sm_rpool_P		 sm_tree_rpool;
	uint			 sm_tree_limit;	/* max # of entries */
	uint			 sm_tree_used;	/* current # of entries */
#if SM_TREE_STAT
	unsigned long		 sm_tree_rotates;
#endif
};

typedef sm_ret_T (*sm_tree_walk_F)(sm_tree_P, sm_tree_node_P, void *);

/*
**  Implementation note:
**  if we want to limit the size of the tree, then we may also want to
**  reuse nodes: we can put them into a list in the tree structure,
**  and get them from there if we need to allocate one.
**  We could also create a fixed size tree with an array of nodes
**  that are "just" properly linked (in that case, the pointers could
**  be "reduced" to indices, but that's probably not worth the extra
**  coding effort).
*/

/*
**  this function must be provided externally, results:
**	== 0: keys are identical
**	< 0: first key less than second key
**	> 0: first key greather than second key
**  the function must implement a transitive relation.
*/

/* internal */
int	sm_tree_insert2(sm_tree_P _tree, sm_tree_node_P *_node, sm_tree_node_P _recn, sm_tree_key_T _key, uint _len, sm_tree_data_T _data);
int	sm_tree_remove2(sm_tree_P _tree, sm_tree_node_P *_node, sm_tree_node_P, sm_tree_key_T _key, uint _len);

/* available functions */

sm_tree_P	 sm_tree_create(sm_rpool_P _rpool, uint _limit, sm_tree_compare_T _tree_compare);
sm_ret_T	 sm_tree_destroy(sm_tree_P _tree);
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_ret_T	 sm_tree_node_free(sm_tree_P _tree, sm_tree_node_P _n);
int		 sm_tree_add(sm_tree_P _tree, sm_tree_key_T _key, uint _len, sm_tree_data_T _data);
int		 sm_tree_rm(sm_tree_P _tree, sm_tree_key_T _key, uint _len);
sm_tree_node_P	 sm_tree_first(sm_tree_P _tree);
sm_tree_node_P	 sm_tree_next(sm_tree_P _tree, sm_tree_node_P _node);
sm_tree_node_P	 sm_tree_lookup(sm_tree_P _tree, sm_tree_key_T _key, uint _len);
uint		 sm_tree_depth(sm_tree_node_P);

sm_ret_T		 sm_tree_walk(sm_tree_P _tree, sm_tree_walk_F _fct, void *_ctx);

#define sm_tree_assign_key(dst, src)	(dst) = (src)
#define sm_tree_assign_data(dst, src)	(dst) = (src)

#endif /* SM_TREE_H */