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