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

#ifndef SM_AVL_H
#define SM_AVL_H 1

typedef struct avl_node	avl_node_T, *avl_node_P;
typedef struct avl_tree avl_tree_T, *avl_tree_P;

typedef int (*avl_compare_T)(avl_node_T*, avl_node_T*);

typedef signed char	sm_avl_comp_T;

struct avl_node
{
    avl_node_T *an_parent;
    avl_node_T *an_left;
    avl_node_T *an_right;
    signed char an_balance;
    char        an_root;
};

struct avl_tree
{
    avl_node_T     at_root;
    avl_compare_T  at_compare;
};

enum
{
    b_null,
    b_left,
    b_even,
    b_right
};

void		 avl_create(avl_tree_P _tree, avl_compare_T _compare);
avl_node_P	 avl_node_add(avl_tree_P _tree, avl_node_P _node);
void		 avl_node_rm(avl_tree_P _tree, avl_node_P _node);
avl_node_P	 avl_locate(avl_tree_P _tree, avl_node_P _search_node);
avl_node_P	 avl_next(avl_tree_P _tree, avl_node_P _node);

#endif /* SM_AVL_H */