1 /* ----------------------------------------------------------------------
2  * avl_tree.h
3  *
4  *	Declarations for AVL style balanced tree support.
5  *
6  *	Copyright (c) 2003-2009, PostgreSQL Global Development Group
7  *	Author: Jan Wieck, Afilias USA INC.
8  *
9  *
10  * ----------------------------------------------------------------------
11  */
12 
13 #ifndef _AVL_TREE_H_INCLUDED_
14 #define _AVL_TREE_H_INCLUDED_
15 
16 /* ----
17  * Callback function type declarations
18  * ----
19  */
20 typedef int (AVLcompfunc) (void *, void *);
21 typedef void (AVLfreefunc) (void *);
22 
23 
24 /* ----
25  * Data structures
26  * ----
27  */
28 typedef struct AVLnode_s
29 {
30 	struct AVLnode_s *lnode,
31 			   *rnode;
32 	int			ldepth,
33 				rdepth;
34 	void	   *cdata;
35 	int			deleted;
36 }	AVLnode;
37 
38 typedef struct AVLtree_s
39 {
40 	AVLnode    *root;
41 	AVLcompfunc *compfunc;
42 	AVLfreefunc *freefunc;
43 }	AVLtree;
44 
45 /* ----
46  * Macros
47  * ----
48  */
49 #define		AVL_DATA(n)		(n)->cdata
50 #define		AVL_SETDATA(n,p) ((n)->cdata = (p))
51 #define		AVL_MAXDEPTH(n) (((n)->ldepth > (n)->rdepth) ? (n)->ldepth : (n)->rdepth)
52 #define		AVL_BALANCE(n)	((n)->rdepth - (n)->ldepth)
53 
54 #define		AVL_INITIALIZER(cmp,free) {NULL, (cmp), (free)}
55 
56 
57 /* ----
58  * Public functions
59  * ----
60  */
61 void avl_init(AVLtree * tree, AVLcompfunc * compfunc,
62 		 AVLfreefunc * freefunc);
63 void		avl_reset(AVLtree * tree);
64 AVLnode    *avl_insert(AVLtree * tree, void *cdata);
65 AVLnode    *avl_lookup(AVLtree * tree, void *cdata);
66 int			avl_delete(AVLtree * tree, void *cdata);
67 
68 #endif   /* _AVL_TREE_H_INCLUDED_ */
69