src/avl.c

   1 /*
   2  * ANSI C Library for maintainance of AVL Balanced Trees
   3  *
   4  * ref.:
   5  *  G. M. Adelson-Velskij & E. M. Landis
   6  *  Doklady Akad. Nauk SSSR 146 (1962), 263-266
   7  *
   8  * see also:
   9  *  D. E. Knuth: The Art of Computer Programming Vol.3 (Sorting and Searching)
  10  *
  11  * (C) 2000 Daniel Nagy, Budapest University of Technology and Economics
  12  * Released under GNU General Public License (GPL) version 2
  13  *
  14  */
  15
  16 #ifdef HAVE_CONFIG_H
  17 #include <config.h>
  18 #endif
  19 #include "avl.h"
  20 #include "log.h"
  21
  22 /* Swing to the left
  23  * Warning: no balance maintainance
  24  */
  25 void avl_swl(avl** root) {
  26         avl* a = *root;
  27         avl* b = a->right;
  28         *root = b;
  29         a->right = b->left;
  30         b->left = a;
  31 }
  32
  33 /* Swing to the right
  34  * Warning: no balance maintainance
  35  */
  36 void avl_swr(avl** root) {
  37         avl* a = *root;
  38         avl* b = a->left;
  39         *root = b;
  40         a->left = b->right;
  41         b->right = a;
  42 }
  43
  44 /* Balance maintainance after especially nasty swings
  45  */
  46 void avl_nasty(avl* root) {
  47         switch (root->balance) {
  48         case -1:
  49                 root->left->balance = 0;
  50                 root->right->balance = 1;
  51                 break;
  52         case 1:
  53                 root->left->balance = -1;
  54                 root->right->balance = 0;
  55                 break;
  56         case 0:
  57                 root->left->balance = 0;
  58                 root->right->balance = 0;
  59         }
  60         root->balance = 0;
  61 }
  62
  63 /* Public methods */
  64
  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
  68  */
  69 int avl_insert(avl_tree* t, avl* a) {
  70         /* initialize */
  71         a->left = 0;
  72         a->right = 0;
  73         a->balance = 0;
  74         /* insert into an empty tree */
  75         if (!t->root) {
  76                 t->root = a;
  77                 return 1;
  78         }
  79
  80         if (t->compar(t->root, a) > 0) {
  81                 /* insert into the left subtree */
  82                 if (t->root->left) {
  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--) {
  88                                 case 1:
  89                                         return 0;
  90                                 case 0:
  91                                         return 1;
  92                                 }
  93                                 if (t->root->left->balance < 0) {
  94                                         avl_swr(&(t->root));
  95                                         t->root->balance = 0;
  96                                         t->root->right->balance = 0;
  97                                 } else {
  98                                         avl_swl(&(t->root->left));
  99                                         avl_swr(&(t->root));
 100                                         avl_nasty(t->root);
 101                                 }
 102                         } else
 103                                 t->root->left = left_subtree.root;
 104                         return 0;
 105                 } else {
 106                         t->root->left = a;
 107                         if (t->root->balance--)
 108                                 return 0;
 109                         return 1;
 110                 }
 111         } else {
 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++) {
 119                                 case -1:
 120                                         return 0;
 121                                 case 0:
 122                                         return 1;
 123                                 }
 124                                 if (t->root->right->balance > 0) {
 125                                         avl_swl(&(t->root));
 126                                         t->root->balance = 0;
 127                                         t->root->left->balance = 0;
 128                                 } else {
 129                                         avl_swr(&(t->root->right));
 130                                         avl_swl(&(t->root));
 131                                         avl_nasty(t->root);
 132                                 }
 133                         } else
 134                                 t->root->right = right_subtree.root;
 135                         return 0;
 136                 } else {
 137                         t->root->right = a;
 138                         if (t->root->balance++)
 139                                 return 0;
 140                         return 1;
 141                 }
 142         }
 143 }
 144
 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.
 149  */
 150 int avl_remove(avl_tree* t, avl* a) {
 151         int b;
 152         if (t->root == a)
 153                 return avl_removeroot(t);
 154         b = t->compar(t->root, a);
 155         if (b >= 0) {
 156                 /* remove from the left subtree */
 157                 int ch;
 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;
 163                         if (ch) {
 164                                 switch (t->root->balance++) {
 165                                 case -1:
 166                                         return -1;
 167                                 case 0:
 168                                         return 0;
 169                                 }
 170                                 switch (t->root->right->balance) {
 171                                 case 0:
 172                                         avl_swl(&(t->root));
 173                                         t->root->balance = -1;
 174                                         t->root->left->balance = 1;
 175                                         return 0;
 176                                 case 1:
 177                                         avl_swl(&(t->root));
 178                                         t->root->balance = 0;
 179                                         t->root->left->balance = 0;
 180                                         return -1;
 181                                 }
 182                                 avl_swr(&(t->root->right));
 183                                 avl_swl(&(t->root));
 184                                 avl_nasty(t->root);
 185                                 return -1;
 186                         }
 187                 }
 188         }
 189         if (b <= 0) {
 190                 /* remove from the right subtree */
 191                 int ch;
 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;
 197                         if (ch) {
 198                                 switch (t->root->balance--) {
 199                                 case 1:
 200                                         return -1;
 201                                 case 0:
 202                                         return 0;
 203                                 }
 204                                 switch (t->root->left->balance) {
 205                                 case 0:
 206                                         avl_swr(&(t->root));
 207                                         t->root->balance = 1;
 208                                         t->root->right->balance = -1;
 209                                         return 0;
 210                                 case -1:
 211                                         avl_swr(&(t->root));
 212                                         t->root->balance = 0;
 213                                         t->root->right->balance = 0;
 214                                         return -1;
 215                                 }
 216                                 avl_swl(&(t->root->left));
 217                                 avl_swr(&(t->root));
 218                                 avl_nasty(t->root);
 219                                 return -1;
 220                         }
 221                 }
 222         }
 223         return 0;
 224 }
 225
 226 /* Remove the root of the AVL tree t
 227  * Warning: dumps core if t is empty
 228  */
 229 int avl_removeroot(avl_tree* t) {
 230         int ch;
 231         avl* a;
 232         if (!t->root->left) {
 233                 if (!t->root->right) {
 234                         t->root = 0;
 235                         return -1;
 236                 }
 237                 t->root = t->root->right;
 238                 return -1;
 239         }
 240         if (!t->root->right) {
 241                 t->root = t->root->left;
 242                 return -1;
 243         }
 244         if (t->root->balance < 0) {
 245                 /* remove from the left subtree */
 246                 a = t->root->left;
 247                 while (a->right)
 248                         a = a->right;
 249         } else {
 250                 /* remove from the right subtree */
 251                 a = t->root->right;
 252                 while (a->left)
 253                         a = a->left;
 254         }
 255         ch = avl_remove(t, a);
 256         a->left = t->root->left;
 257         a->right = t->root->right;
 258         a->balance = t->root->balance;
 259         t->root = a;
 260         if (a->balance == 0)
 261                 return ch;
 262         return 0;
 263 }
 264
 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
 269  */
 270 int avl_range(avl_tree* t, avl* a, avl* b, int (*iter)(avl*), avl** ret) {
 271         int x, c = 0;
 272         if (!t->root)
 273                 return 0;
 274         x = t->compar(t->root, a);
 275         if (a != b) {
 276                 if (x < 0) {
 277                         x = t->compar(t->root, b);
 278                         if (x > 0)
 279                                 x = 0;
 280                 }
 281         }
 282         if (x >= 0) {
 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)))
 288                                 if (x > 0)
 289                                         return 0;
 290                 }
 291         }
 292         if (x == 0) {
 293                 if (!(c = iter(t->root))) {
 294                         if (ret)
 295                                 *ret = t->root;
 296                         return 0;
 297                 }
 298         }
 299         if (x <= 0) {
 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)))
 305                                 if (x < 0)
 306                                         return 0;
 307                 }
 308         }
 309         return c;
 310 }
 311
 312 void avl_init(avl_tree *t, int (*compar)(void *a, void *b)) {
 313         t->root = NULL;
 314         t->compar = compar;
 315 }
 316
 317 /* ------------------------------------------------------------------------- */
 318
 319 void avl_lock(avl_tree_lock *t) {
 320 #ifndef AVL_WITHOUT_PTHREADS
 321 #ifdef AVL_LOCK_WITH_MUTEX
 322         pthread_mutex_lock(&t->mutex);
 323 #else
 324         pthread_rwlock_wrlock(&t->rwlock);
 325 #endif
 326 #endif /* AVL_WITHOUT_PTHREADS */
 327 }
 328
 329 void avl_unlock(avl_tree_lock *t) {
 330 #ifndef AVL_WITHOUT_PTHREADS
 331 #ifdef AVL_LOCK_WITH_MUTEX
 332         pthread_mutex_unlock(&t->mutex);
 333 #else
 334         pthread_rwlock_unlock(&t->rwlock);
 335 #endif
 336 #endif /* AVL_WITHOUT_PTHREADS */
 337 }
 338
 339 /* ------------------------------------------------------------------------- */
 340
 341 void avl_init_lock(avl_tree_lock *t, int (*compar)(void *a, void *b)) {
 342         avl_init(&t->avl_tree, compar);
 343
 344 #ifndef AVL_WITHOUT_PTHREADS
 345         int lock;
 346
 347 #ifdef AVL_LOCK_WITH_MUTEX
 348         lock = pthread_mutex_init(&t->mutex, NULL);
 349 #else
 350         lock = pthread_rwlock_init(&t->rwlock, NULL);
 351 #endif
 352
 353         if(lock != 0)
 354                 fatal("Failed to initialize AVL mutex/rwlock, error: %d", lock);
 355
 356 #endif /* AVL_WITHOUT_PTHREADS */
 357 }
 358
 359 int avl_range_lock(avl_tree_lock *t, avl *a, avl *b, int (*iter)(avl *), avl **ret) {
 360         avl_lock(t);
 361         int ret2 = avl_range(&t->avl_tree, a, b, iter, ret);
 362         avl_unlock(t);
 363         return ret2;
 364 }
 365
 366 int avl_removeroot_lock(avl_tree_lock *t) {
 367         avl_lock(t);
 368         int ret = avl_removeroot(&t->avl_tree);
 369         avl_unlock(t);
 370         return ret;
 371 }
 372
 373 int avl_remove_lock(avl_tree_lock *t, avl *a) {
 374         avl_lock(t);
 375         int ret = avl_remove(&t->avl_tree, a);
 376         avl_unlock(t);
 377         return ret;
 378 }
 379
 380 int avl_insert_lock(avl_tree_lock *t, avl *a) {
 381         avl_lock(t);
 382         int ret = avl_insert(&t->avl_tree, a);
 383         avl_lock(t);
 384         return ret;
 385 }