2 * ANSI C Library for maintainance of AVL Balanced Trees
5 * G. M. Adelson-Velskij & E. M. Landis
6 * Doklady Akad. Nauk SSSR 146 (1962), 263-266
9 * D. E. Knuth: The Art of Computer Programming Vol.3 (Sorting and Searching)
11 * (C) 2000 Daniel Nagy, Budapest University of Technology and Economics
12 * Released under GNU General Public License (GPL) version 2
23 * Warning: no balance maintainance
25 void avl_swl(avl** root) {
34 * Warning: no balance maintainance
36 void avl_swr(avl** root) {
44 /* Balance maintainance after especially nasty swings
46 void avl_nasty(avl* root) {
47 switch (root->balance) {
49 root->left->balance = 0;
50 root->right->balance = 1;
53 root->left->balance = -1;
54 root->right->balance = 0;
57 root->left->balance = 0;
58 root->right->balance = 0;
65 /* Insert element a into the AVL tree t
66 * returns 1 if the depth of the tree has grown
67 * Warning: do not insert elements already present
69 int avl_insert(avl_tree* t, avl* a) {
74 /* insert into an empty tree */
80 if (t->compar(t->root, a) > 0) {
81 /* insert into the left subtree */
83 avl_tree left_subtree;
84 left_subtree.root = t->root->left;
85 left_subtree.compar = t->compar;
86 if (avl_insert(&left_subtree, a)) {
87 switch (t->root->balance--) {
93 if (t->root->left->balance < 0) {
96 t->root->right->balance = 0;
98 avl_swl(&(t->root->left));
103 t->root->left = left_subtree.root;
107 if (t->root->balance--)
112 /* insert into the right subtree */
113 if (t->root->right) {
114 avl_tree right_subtree;
115 right_subtree.root = t->root->right;
116 right_subtree.compar = t->compar;
117 if (avl_insert(&right_subtree, a)) {
118 switch (t->root->balance++) {
124 if (t->root->right->balance > 0) {
126 t->root->balance = 0;
127 t->root->left->balance = 0;
129 avl_swr(&(t->root->right));
134 t->root->right = right_subtree.root;
138 if (t->root->balance++)
145 /* Remove an element a from the AVL tree t
146 * returns -1 if the depth of the tree has shrunk
147 * Warning: if the element is not present in the tree,
148 * returns 0 as if it had been removed succesfully.
150 int avl_remove(avl_tree* t, avl* a) {
153 return avl_removeroot(t);
154 b = t->compar(t->root, a);
156 /* remove from the left subtree */
158 avl_tree left_subtree;
159 if ((left_subtree.root = t->root->left)) {
160 left_subtree.compar = t->compar;
161 ch = avl_remove(&left_subtree, a);
162 t->root->left = left_subtree.root;
164 switch (t->root->balance++) {
170 switch (t->root->right->balance) {
173 t->root->balance = -1;
174 t->root->left->balance = 1;
178 t->root->balance = 0;
179 t->root->left->balance = 0;
182 avl_swr(&(t->root->right));
190 /* remove from the right subtree */
192 avl_tree right_subtree;
193 if ((right_subtree.root = t->root->right)) {
194 right_subtree.compar = t->compar;
195 ch = avl_remove(&right_subtree, a);
196 t->root->right = right_subtree.root;
198 switch (t->root->balance--) {
204 switch (t->root->left->balance) {
207 t->root->balance = 1;
208 t->root->right->balance = -1;
212 t->root->balance = 0;
213 t->root->right->balance = 0;
216 avl_swl(&(t->root->left));
226 /* Remove the root of the AVL tree t
227 * Warning: dumps core if t is empty
229 int avl_removeroot(avl_tree* t) {
232 if (!t->root->left) {
233 if (!t->root->right) {
237 t->root = t->root->right;
240 if (!t->root->right) {
241 t->root = t->root->left;
244 if (t->root->balance < 0) {
245 /* remove from the left subtree */
250 /* remove from the right subtree */
255 ch = avl_remove(t, a);
256 a->left = t->root->left;
257 a->right = t->root->right;
258 a->balance = t->root->balance;
265 /* Iterate through elements in t from a range between a and b (inclusive)
266 * for each element calls iter(a) until it returns 0
267 * returns the last value returned by iterator or 0 if there were no calls
268 * Warning: a<=b must hold
270 int avl_range(avl_tree* t, avl* a, avl* b, int (*iter)(avl*), avl** ret) {
274 x = t->compar(t->root, a);
277 x = t->compar(t->root, b);
283 /* search in the left subtree */
284 avl_tree left_subtree;
285 if ((left_subtree.root = t->root->left)) {
286 left_subtree.compar = t->compar;
287 if (!(c = avl_range(&left_subtree, a, b, iter, ret)))
293 if (!(c = iter(t->root))) {
300 /* search in the right subtree */
301 avl_tree right_subtree;
302 if ((right_subtree.root = t->root->right)) {
303 right_subtree.compar = t->compar;
304 if (!(c = avl_range(&right_subtree, a, b, iter, ret)))
312 /* high performance searching - by ktsaou */
313 avl *avl_search(avl_tree *t, avl *a) {
317 int x = t->compar(root, a);
335 void avl_init(avl_tree *t, int (*compar)(void *a, void *b)) {
340 /* ------------------------------------------------------------------------- */
342 void avl_read_lock(avl_tree_lock *t) {
343 #ifndef AVL_WITHOUT_PTHREADS
344 #ifdef AVL_LOCK_WITH_MUTEX
345 pthread_mutex_lock(&t->mutex);
347 pthread_rwlock_rdlock(&t->rwlock);
349 #endif /* AVL_WITHOUT_PTHREADS */
352 void avl_write_lock(avl_tree_lock *t) {
353 #ifndef AVL_WITHOUT_PTHREADS
354 #ifdef AVL_LOCK_WITH_MUTEX
355 pthread_mutex_lock(&t->mutex);
357 pthread_rwlock_wrlock(&t->rwlock);
359 #endif /* AVL_WITHOUT_PTHREADS */
362 void avl_unlock(avl_tree_lock *t) {
363 #ifndef AVL_WITHOUT_PTHREADS
364 #ifdef AVL_LOCK_WITH_MUTEX
365 pthread_mutex_unlock(&t->mutex);
367 pthread_rwlock_unlock(&t->rwlock);
369 #endif /* AVL_WITHOUT_PTHREADS */
372 /* ------------------------------------------------------------------------- */
374 void avl_init_lock(avl_tree_lock *t, int (*compar)(void *a, void *b)) {
375 avl_init(&t->avl_tree, compar);
377 #ifndef AVL_WITHOUT_PTHREADS
380 #ifdef AVL_LOCK_WITH_MUTEX
381 lock = pthread_mutex_init(&t->mutex, NULL);
383 lock = pthread_rwlock_init(&t->rwlock, NULL);
387 fatal("Failed to initialize AVL mutex/rwlock, error: %d", lock);
389 #endif /* AVL_WITHOUT_PTHREADS */
392 avl *avl_search_lock(avl_tree_lock *t, avl *a) {
394 avl *ret = avl_search(&t->avl_tree, a);
399 int avl_range_lock(avl_tree_lock *t, avl *a, avl *b, int (*iter)(avl *), avl **ret) {
401 int ret2 = avl_range(&t->avl_tree, a, b, iter, ret);
406 int avl_removeroot_lock(avl_tree_lock *t) {
408 int ret = avl_removeroot(&t->avl_tree);
413 int avl_remove_lock(avl_tree_lock *t, avl *a) {
415 int ret = avl_remove(&t->avl_tree, a);
420 int avl_insert_lock(avl_tree_lock *t, avl *a) {
422 int ret = avl_insert(&t->avl_tree, a);