1 /* ldap_avl.h - avl tree definitions */
3 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
5 * Copyright 1998-2022 The OpenLDAP Foundation.
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted only as authorized by the OpenLDAP
12 * A copy of this license is available in file LICENSE in the
13 * top-level directory of the distribution or, alternatively, at
14 * <http://www.OpenLDAP.org/license.html>.
16 /* Portions Copyright (c) 1993 Regents of the University of Michigan.
17 * All rights reserved.
19 * Redistribution and use in source and binary forms are permitted
20 * provided that this notice is preserved and that due credit is given
21 * to the University of Michigan at Ann Arbor. The name of the University
22 * may not be used to endorse or promote products derived from this
23 * software without specific prior written permission. This software
24 * is provided ``as is'' without express or implied warranty.
31 #include <ldap_cdefs.h>
34 * this structure represents a generic avl tree node.
39 typedef struct avlnode Avlnode
;
43 struct avlnode
*avl_link
[2];
48 #define avl_left avl_link[0]
49 #define avl_right avl_link[1]
50 #define avl_lbit avl_bits[0]
51 #define avl_rbit avl_bits[1]
53 typedef struct tavlnode TAvlnode
;
57 struct tavlnode
*avl_link
[2];
64 /* balance factor values */
69 #define avl_bf2str(bf) ((bf) == -1 ? "LH" : (bf) == 0 ? "EH" : (bf) == 1 ? "RH" : "(unknown)" )
76 #define ldap_avl_getone(x) ((x) == 0 ? 0 : (x)->avl_data)
77 #define ldap_avl_onenode(x) ((x) == 0 || ((x)->avl_left == 0 && (x)->avl_right == 0))
79 #endif /* AVL_INTERNALS */
81 #define ldap_avl_child(x,dir) ((x)->avl_bits[dir]) == AVL_CHILD ? \
82 (x)->avl_link[dir] : NULL
83 #define ldap_avl_lchild(x) ldap_avl_child(x,0)
84 #define ldap_avl_rchild(x) ldap_avl_child(x,1)
86 typedef int (*AVL_APPLY
) LDAP_P((void *, void*));
87 typedef int (*AVL_CMP
) LDAP_P((const void*, const void*));
88 typedef int (*AVL_DUP
) LDAP_P((void*, void*));
89 typedef void (*AVL_FREE
) LDAP_P((void*));
92 ldap_avl_free
LDAP_P(( Avlnode
*root
, AVL_FREE dfree
));
95 ldap_avl_insert
LDAP_P((Avlnode
**, void*, AVL_CMP
, AVL_DUP
));
98 ldap_avl_delete
LDAP_P((Avlnode
**, void*, AVL_CMP
));
101 ldap_avl_find
LDAP_P((Avlnode
*, const void*, AVL_CMP
));
103 LDAP_AVL_F( Avlnode
* )
104 ldap_avl_find2
LDAP_P((Avlnode
*, const void*, AVL_CMP
));
107 ldap_avl_find_lin
LDAP_P((Avlnode
*, const void*, AVL_CMP
));
109 #ifdef AVL_NONREENTRANT
111 ldap_avl_getfirst
LDAP_P((Avlnode
*));
114 ldap_avl_getnext
LDAP_P((void));
118 ldap_avl_dup_error
LDAP_P((void*, void*));
121 ldap_avl_dup_ok
LDAP_P((void*, void*));
124 ldap_avl_apply
LDAP_P((Avlnode
*, AVL_APPLY
, void*, int, int));
127 ldap_avl_prefixapply
LDAP_P((Avlnode
*, void*, AVL_CMP
, void*, AVL_CMP
, void*, int));
130 ldap_tavl_free
LDAP_P(( TAvlnode
*root
, AVL_FREE dfree
));
133 ldap_tavl_insert
LDAP_P((TAvlnode
**, void*, AVL_CMP
, AVL_DUP
));
136 ldap_tavl_delete
LDAP_P((TAvlnode
**, void*, AVL_CMP
));
139 ldap_tavl_find
LDAP_P((TAvlnode
*, const void*, AVL_CMP
));
141 LDAP_AVL_F( TAvlnode
* )
142 ldap_tavl_find2
LDAP_P((TAvlnode
*, const void*, AVL_CMP
));
144 LDAP_AVL_F( TAvlnode
* )
145 ldap_tavl_find3
LDAP_P((TAvlnode
*, const void*, AVL_CMP
, int *ret
));
147 #define TAVL_DIR_LEFT 0
148 #define TAVL_DIR_RIGHT 1
150 LDAP_AVL_F( TAvlnode
* )
151 ldap_tavl_end
LDAP_P((TAvlnode
*, int direction
));
153 LDAP_AVL_F( TAvlnode
* )
154 ldap_tavl_next
LDAP_P((TAvlnode
*, int direction
));
156 /* apply traversal types */
157 #define AVL_PREORDER 1
158 #define AVL_INORDER 2
159 #define AVL_POSTORDER 3
160 /* what apply returns if it ran out of nodes */
161 #define AVL_NOMORE (-6)