-
Notifications
You must be signed in to change notification settings - Fork 27
/
Copy pathavl.h
152 lines (111 loc) · 3.26 KB
/
avl.h
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
/* $ReOpenLDAP$ */
/* Copyright 1992-2018 ReOpenLDAP AUTHORS: please see AUTHORS file.
* All rights reserved.
*
* This file is part of ReOpenLDAP.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted only as authorized by the OpenLDAP
* Public License.
*
* A copy of this license is available in the file LICENSE in the
* top-level directory of the distribution or, alternatively, at
* <http://www.OpenLDAP.org/license.html>.
*/
#ifndef _AVL
#define _AVL
#include <ldap_cdefs.h>
/*
* this structure represents a generic avl tree node.
*/
LDAP_BEGIN_DECL
typedef struct avlnode Avlnode;
struct avlnode {
void *avl_data;
struct avlnode *avl_link[2];
char avl_bits[2];
signed char avl_bf;
};
#define avl_left avl_link[0]
#define avl_right avl_link[1]
#define avl_lbit avl_bits[0]
#define avl_rbit avl_bits[1]
typedef struct tavlnode TAvlnode;
struct tavlnode {
void *avl_data;
struct tavlnode *avl_link[2];
char avl_bits[2];
signed char avl_bf;
};
#ifdef AVL_INTERNAL
/* balance factor values */
#define LH (-1)
#define EH 0
#define RH 1
#define avl_bf2str(bf) ((bf) == -1 ? "LH" : (bf) == 0 ? "EH" : (bf) == 1 ? "RH" : "(unknown)")
/* thread bits */
#define AVL_CHILD 0
#define AVL_THREAD 1
/* avl routines */
#define avl_getone(x) ((x) == 0 ? 0 : (x)->avl_data)
#define avl_onenode(x) ((x) == 0 || ((x)->avl_left == 0 && (x)->avl_right == 0))
#endif /* AVL_INTERNALS */
#define avl_child(x, dir) ((x)->avl_bits[dir]) == AVL_CHILD ? (x)->avl_link[dir] : NULL
#define avl_lchild(x) avl_child(x, 0)
#define avl_rchild(x) avl_child(x, 1)
typedef int (*AVL_APPLY)(void *, void *);
typedef int (*AVL_CMP)(const void *, const void *);
typedef int (*AVL_DUP)(void *, void *);
typedef void (*AVL_FREE)(void *);
LDAP_AVL_F(int)
avl_free(Avlnode *root, AVL_FREE dfree);
LDAP_AVL_F(int)
avl_insert(Avlnode **, void *, AVL_CMP, AVL_DUP);
LDAP_AVL_F(void *)
avl_delete(Avlnode **, void *, AVL_CMP);
LDAP_AVL_F(void *)
avl_find(Avlnode *, const void *, AVL_CMP);
LDAP_AVL_F(Avlnode *)
avl_find2(Avlnode *, const void *, AVL_CMP);
LDAP_AVL_F(void *)
avl_find_lin(Avlnode *, const void *, AVL_CMP);
#ifdef AVL_NONREENTRANT
LDAP_AVL_F(void *)
avl_getfirst(Avlnode *);
LDAP_AVL_F(void *)
avl_getnext(void);
#endif
LDAP_AVL_F(int)
avl_dup_error(void *, void *);
LDAP_AVL_F(int)
avl_dup_ok(void *, void *);
LDAP_AVL_F(int)
avl_apply(Avlnode *, AVL_APPLY, void *, int, int);
LDAP_AVL_F(int)
avl_prefixapply(Avlnode *, void *, AVL_CMP, void *, AVL_CMP, void *, int);
LDAP_AVL_F(int)
tavl_free(TAvlnode *root, AVL_FREE dfree);
LDAP_AVL_F(int)
tavl_insert(TAvlnode **, void *, AVL_CMP, AVL_DUP);
LDAP_AVL_F(void *)
tavl_delete(TAvlnode **, void *, AVL_CMP);
LDAP_AVL_F(void *)
tavl_find(TAvlnode *, const void *, AVL_CMP);
LDAP_AVL_F(TAvlnode *)
tavl_find2(TAvlnode *, const void *, AVL_CMP);
LDAP_AVL_F(TAvlnode *)
tavl_find3(TAvlnode *, const void *, AVL_CMP, int *ret);
#define TAVL_DIR_LEFT 0
#define TAVL_DIR_RIGHT 1
LDAP_AVL_F(TAvlnode *)
tavl_end(TAvlnode *, int direction);
LDAP_AVL_F(TAvlnode *)
tavl_next(TAvlnode *, int direction);
/* apply traversal types */
#define AVL_PREORDER 1
#define AVL_INORDER 2
#define AVL_POSTORDER 3
/* what apply returns if it ran out of nodes */
#define AVL_NOMORE (-6)
LDAP_END_DECL
#endif /* _AVL */