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 int _avl_removeroot(avl_tree* t);
26 * Warning: no balance maintainance
28 void avl_swl(avl** root) {
37 * Warning: no balance maintainance
39 void avl_swr(avl** root) {
47 /* Balance maintainance after especially nasty swings
49 void avl_nasty(avl* root) {
50 switch (root->balance) {
52 root->left->balance = 0;
53 root->right->balance = 1;
56 root->left->balance = -1;
57 root->right->balance = 0;
60 root->left->balance = 0;
61 root->right->balance = 0;
68 /* Insert element a into the AVL tree t
69 * returns 1 if the depth of the tree has grown
70 * Warning: do not insert elements already present
72 int _avl_insert(avl_tree* t, avl* a) {
77 /* insert into an empty tree */
83 if (t->compar(t->root, a) > 0) {
84 /* insert into the left subtree */
86 avl_tree left_subtree;
87 left_subtree.root = t->root->left;
88 left_subtree.compar = t->compar;
89 if (_avl_insert(&left_subtree, a)) {
90 switch (t->root->balance--) {
96 if (t->root->left->balance < 0) {
99 t->root->right->balance = 0;
101 avl_swl(&(t->root->left));
106 t->root->left = left_subtree.root;
110 if (t->root->balance--)
115 /* insert into the right subtree */
116 if (t->root->right) {
117 avl_tree right_subtree;
118 right_subtree.root = t->root->right;
119 right_subtree.compar = t->compar;
120 if (_avl_insert(&right_subtree, a)) {
121 switch (t->root->balance++) {
127 if (t->root->right->balance > 0) {
129 t->root->balance = 0;
130 t->root->left->balance = 0;
132 avl_swr(&(t->root->right));
137 t->root->right = right_subtree.root;
141 if (t->root->balance++)
147 int avl_insert(avl_tree* t, avl* a) {
148 #ifdef AVL_LOCK_WITH_MUTEX
149 pthread_mutex_lock(&t->mutex);
151 pthread_rwlock_wrlock(&t->rwlock);
154 int ret = _avl_insert(t, a);
156 #ifdef AVL_LOCK_WITH_MUTEX
157 pthread_mutex_unlock(&t->mutex);
159 pthread_rwlock_unlock(&t->rwlock);
164 /* Remove an element a from the AVL tree t
165 * returns -1 if the depth of the tree has shrunk
166 * Warning: if the element is not present in the tree,
167 * returns 0 as if it had been removed succesfully.
169 int _avl_remove(avl_tree* t, avl* a) {
172 return _avl_removeroot(t);
173 b = t->compar(t->root, a);
175 /* remove from the left subtree */
177 avl_tree left_subtree;
178 if ((left_subtree.root = t->root->left)) {
179 left_subtree.compar = t->compar;
180 ch = _avl_remove(&left_subtree, a);
181 t->root->left = left_subtree.root;
183 switch (t->root->balance++) {
189 switch (t->root->right->balance) {
192 t->root->balance = -1;
193 t->root->left->balance = 1;
197 t->root->balance = 0;
198 t->root->left->balance = 0;
201 avl_swr(&(t->root->right));
209 /* remove from the right subtree */
211 avl_tree right_subtree;
212 if ((right_subtree.root = t->root->right)) {
213 right_subtree.compar = t->compar;
214 ch = _avl_remove(&right_subtree, a);
215 t->root->right = right_subtree.root;
217 switch (t->root->balance--) {
223 switch (t->root->left->balance) {
226 t->root->balance = 1;
227 t->root->right->balance = -1;
231 t->root->balance = 0;
232 t->root->right->balance = 0;
235 avl_swl(&(t->root->left));
245 int avl_remove(avl_tree* t, avl* a) {
246 #ifdef AVL_LOCK_WITH_MUTEX
247 pthread_mutex_lock(&t->mutex);
249 pthread_rwlock_wrlock(&t->rwlock);
252 int ret = _avl_remove(t, a);
254 #ifdef AVL_LOCK_WITH_MUTEX
255 pthread_mutex_unlock(&t->mutex);
257 pthread_rwlock_unlock(&t->rwlock);
262 /* Remove the root of the AVL tree t
263 * Warning: dumps core if t is empty
265 int _avl_removeroot(avl_tree* t) {
268 if (!t->root->left) {
269 if (!t->root->right) {
273 t->root = t->root->right;
276 if (!t->root->right) {
277 t->root = t->root->left;
280 if (t->root->balance < 0) {
281 /* remove from the left subtree */
286 /* remove from the right subtree */
291 ch = _avl_remove(t, a);
292 a->left = t->root->left;
293 a->right = t->root->right;
294 a->balance = t->root->balance;
301 int avl_removeroot(avl_tree* t) {
302 #ifdef AVL_LOCK_WITH_MUTEX
303 pthread_mutex_lock(&t->mutex);
305 pthread_rwlock_wrlock(&t->rwlock);
308 int ret = _avl_removeroot(t);
310 #ifdef AVL_LOCK_WITH_MUTEX
311 pthread_mutex_unlock(&t->mutex);
313 pthread_rwlock_unlock(&t->rwlock);
318 /* Iterate through elements in t from a range between a and b (inclusive)
319 * for each element calls iter(a) until it returns 0
320 * returns the last value returned by iterator or 0 if there were no calls
321 * Warning: a<=b must hold
323 int _avl_range(avl_tree* t, avl* a, avl* b, int (*iter)(avl*), avl** ret) {
327 x = t->compar(t->root, a);
330 x = t->compar(t->root, b);
336 /* search in the left subtree */
337 avl_tree left_subtree;
338 if ((left_subtree.root = t->root->left)) {
339 left_subtree.compar = t->compar;
340 if (!(c = _avl_range(&left_subtree, a, b, iter, ret)))
346 if (!(c = iter(t->root))) {
353 /* search in the right subtree */
354 avl_tree right_subtree;
355 if ((right_subtree.root = t->root->right)) {
356 right_subtree.compar = t->compar;
357 if (!(c = _avl_range(&right_subtree, a, b, iter, ret)))
365 int avl_range(avl_tree* t, avl* a, avl* b, int (*iter)(avl*), avl** ret) {
366 #ifdef AVL_LOCK_WITH_MUTEX
367 pthread_mutex_lock(&t->mutex);
369 pthread_rwlock_wrlock(&t->rwlock);
372 int ret2 = _avl_range(t, a, b, iter, ret);
374 #ifdef AVL_LOCK_WITH_MUTEX
375 pthread_mutex_unlock(&t->mutex);
377 pthread_rwlock_unlock(&t->rwlock);
383 /* Iterate through elements in t equal to a
384 * for each element calls iter(a) until it returns 0
385 * returns the last value returned by iterator or 0 if there were no calls
387 int avl_search(avl_tree* t, avl* a, int (*iter)(avl* a), avl** ret) {
388 return avl_range(t, a, a, iter, ret);
391 void avl_init(avl_tree* t, int (*compar)(void* a, void* b)) {
396 #ifdef AVL_LOCK_WITH_MUTEX
397 lock = pthread_mutex_init(&t->mutex, NULL);
399 lock = pthread_rwlock_init(&t->rwlock, NULL);
403 fatal("Failed to initialize AVL mutex/rwlock, error: %d", lock);