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 /* Private methods */
  23 int _avl_removeroot(avl_tree* t);
  24
  25 /* Swing to the left
  26  * Warning: no balance maintainance
  27  */
  28 void avl_swl(avl** root) {
  29         avl* a = *root;
  30         avl* b = a->right;
  31         *root = b;
  32         a->right = b->left;
  33         b->left = a;
  34 }
  35
  36 /* Swing to the right
  37  * Warning: no balance maintainance
  38  */
  39 void avl_swr(avl** root) {
  40         avl* a = *root;
  41         avl* b = a->left;
  42         *root = b;
  43         a->left = b->right;
  44         b->right = a;
  45 }
  46
  47 /* Balance maintainance after especially nasty swings
  48  */
  49 void avl_nasty(avl* root) {
  50         switch (root->balance) {
  51         case -1:
  52                 root->left->balance = 0;
  53                 root->right->balance = 1;
  54                 break;
  55         case 1:
  56                 root->left->balance = -1;
  57                 root->right->balance = 0;
  58                 break;
  59         case 0:
  60                 root->left->balance = 0;
  61                 root->right->balance = 0;
  62         }
  63         root->balance = 0;
  64 }
  65
  66 /* Public methods */
  67
  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
  71  */
  72 int _avl_insert(avl_tree* t, avl* a) {
  73         /* initialize */
  74         a->left = 0;
  75         a->right = 0;
  76         a->balance = 0;
  77         /* insert into an empty tree */
  78         if (!t->root) {
  79                 t->root = a;
  80                 return 1;
  81         }
  82
  83         if (t->compar(t->root, a) > 0) {
  84                 /* insert into the left subtree */
  85                 if (t->root->left) {
  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--) {
  91                                 case 1:
  92                                         return 0;
  93                                 case 0:
  94                                         return 1;
  95                                 }
  96                                 if (t->root->left->balance < 0) {
  97                                         avl_swr(&(t->root));
  98                                         t->root->balance = 0;
  99                                         t->root->right->balance = 0;
 100                                 } else {
 101                                         avl_swl(&(t->root->left));
 102                                         avl_swr(&(t->root));
 103                                         avl_nasty(t->root);
 104                                 }
 105                         } else
 106                                 t->root->left = left_subtree.root;
 107                         return 0;
 108                 } else {
 109                         t->root->left = a;
 110                         if (t->root->balance--)
 111                                 return 0;
 112                         return 1;
 113                 }
 114         } else {
 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++) {
 122                                 case -1:
 123                                         return 0;
 124                                 case 0:
 125                                         return 1;
 126                                 }
 127                                 if (t->root->right->balance > 0) {
 128                                         avl_swl(&(t->root));
 129                                         t->root->balance = 0;
 130                                         t->root->left->balance = 0;
 131                                 } else {
 132                                         avl_swr(&(t->root->right));
 133                                         avl_swl(&(t->root));
 134                                         avl_nasty(t->root);
 135                                 }
 136                         } else
 137                                 t->root->right = right_subtree.root;
 138                         return 0;
 139                 } else {
 140                         t->root->right = a;
 141                         if (t->root->balance++)
 142                                 return 0;
 143                         return 1;
 144                 }
 145         }
 146 }
 147 int avl_insert(avl_tree* t, avl* a) {
 148 #ifndef AVL_WITHOUT_PTHREADS
 149 #ifdef AVL_LOCK_WITH_MUTEX
 150         pthread_mutex_lock(&t->mutex);
 151 #else
 152         pthread_rwlock_wrlock(&t->rwlock);
 153 #endif
 154 #endif /* AVL_WITHOUT_PTHREADS */
 155
 156         int ret = _avl_insert(t, a);
 157
 158 #ifndef AVL_WITHOUT_PTHREADS
 159 #ifdef AVL_LOCK_WITH_MUTEX
 160         pthread_mutex_unlock(&t->mutex);
 161 #else
 162         pthread_rwlock_unlock(&t->rwlock);
 163 #endif
 164 #endif /* AVL_WITHOUT_PTHREADS */
 165         return ret;
 166 }
 167
 168 /* Remove an element a from the AVL tree t
 169  * returns -1 if the depth of the tree has shrunk
 170  * Warning: if the element is not present in the tree,
 171  *          returns 0 as if it had been removed succesfully.
 172  */
 173 int _avl_remove(avl_tree* t, avl* a) {
 174         int b;
 175         if (t->root == a)
 176                 return _avl_removeroot(t);
 177         b = t->compar(t->root, a);
 178         if (b >= 0) {
 179                 /* remove from the left subtree */
 180                 int ch;
 181                 avl_tree left_subtree;
 182                 if ((left_subtree.root = t->root->left)) {
 183                         left_subtree.compar = t->compar;
 184                         ch = _avl_remove(&left_subtree, a);
 185                         t->root->left = left_subtree.root;
 186                         if (ch) {
 187                                 switch (t->root->balance++) {
 188                                 case -1:
 189                                         return -1;
 190                                 case 0:
 191                                         return 0;
 192                                 }
 193                                 switch (t->root->right->balance) {
 194                                 case 0:
 195                                         avl_swl(&(t->root));
 196                                         t->root->balance = -1;
 197                                         t->root->left->balance = 1;
 198                                         return 0;
 199                                 case 1:
 200                                         avl_swl(&(t->root));
 201                                         t->root->balance = 0;
 202                                         t->root->left->balance = 0;
 203                                         return -1;
 204                                 }
 205                                 avl_swr(&(t->root->right));
 206                                 avl_swl(&(t->root));
 207                                 avl_nasty(t->root);
 208                                 return -1;
 209                         }
 210                 }
 211         }
 212         if (b <= 0) {
 213                 /* remove from the right subtree */
 214                 int ch;
 215                 avl_tree right_subtree;
 216                 if ((right_subtree.root = t->root->right)) {
 217                         right_subtree.compar = t->compar;
 218                         ch = _avl_remove(&right_subtree, a);
 219                         t->root->right = right_subtree.root;
 220                         if (ch) {
 221                                 switch (t->root->balance--) {
 222                                 case 1:
 223                                         return -1;
 224                                 case 0:
 225                                         return 0;
 226                                 }
 227                                 switch (t->root->left->balance) {
 228                                 case 0:
 229                                         avl_swr(&(t->root));
 230                                         t->root->balance = 1;
 231                                         t->root->right->balance = -1;
 232                                         return 0;
 233                                 case -1:
 234                                         avl_swr(&(t->root));
 235                                         t->root->balance = 0;
 236                                         t->root->right->balance = 0;
 237                                         return -1;
 238                                 }
 239                                 avl_swl(&(t->root->left));
 240                                 avl_swr(&(t->root));
 241                                 avl_nasty(t->root);
 242                                 return -1;
 243                         }
 244                 }
 245         }
 246         return 0;
 247 }
 248
 249 int avl_remove(avl_tree* t, avl* a) {
 250 #ifndef AVL_WITHOUT_PTHREADS
 251 #ifdef AVL_LOCK_WITH_MUTEX
 252         pthread_mutex_lock(&t->mutex);
 253 #else
 254         pthread_rwlock_wrlock(&t->rwlock);
 255 #endif
 256 #endif /* AVL_WITHOUT_PTHREADS */
 257
 258         int ret = _avl_remove(t, a);
 259
 260 #ifndef AVL_WITHOUT_PTHREADS
 261 #ifdef AVL_LOCK_WITH_MUTEX
 262         pthread_mutex_unlock(&t->mutex);
 263 #else
 264         pthread_rwlock_unlock(&t->rwlock);
 265 #endif
 266 #endif /* AVL_WITHOUT_PTHREADS */
 267         return ret;
 268 }
 269
 270 /* Remove the root of the AVL tree t
 271  * Warning: dumps core if t is empty
 272  */
 273 int _avl_removeroot(avl_tree* t) {
 274         int ch;
 275         avl* a;
 276         if (!t->root->left) {
 277                 if (!t->root->right) {
 278                         t->root = 0;
 279                         return -1;
 280                 }
 281                 t->root = t->root->right;
 282                 return -1;
 283         }
 284         if (!t->root->right) {
 285                 t->root = t->root->left;
 286                 return -1;
 287         }
 288         if (t->root->balance < 0) {
 289                 /* remove from the left subtree */
 290                 a = t->root->left;
 291                 while (a->right)
 292                         a = a->right;
 293         } else {
 294                 /* remove from the right subtree */
 295                 a = t->root->right;
 296                 while (a->left)
 297                         a = a->left;
 298         }
 299         ch = _avl_remove(t, a);
 300         a->left = t->root->left;
 301         a->right = t->root->right;
 302         a->balance = t->root->balance;
 303         t->root = a;
 304         if (a->balance == 0)
 305                 return ch;
 306         return 0;
 307 }
 308
 309 int avl_removeroot(avl_tree* t) {
 310 #ifndef AVL_WITHOUT_PTHREADS
 311 #ifdef AVL_LOCK_WITH_MUTEX
 312         pthread_mutex_lock(&t->mutex);
 313 #else
 314         pthread_rwlock_wrlock(&t->rwlock);
 315 #endif
 316 #endif /* AVL_WITHOUT_PTHREADS */
 317
 318         int ret = _avl_removeroot(t);
 319
 320 #ifndef AVL_WITHOUT_PTHREADS
 321 #ifdef AVL_LOCK_WITH_MUTEX
 322         pthread_mutex_unlock(&t->mutex);
 323 #else
 324         pthread_rwlock_unlock(&t->rwlock);
 325 #endif
 326 #endif /* AVL_WITHOUT_PTHREADS */
 327         return ret;
 328 }
 329
 330 /* Iterate through elements in t from a range between a and b (inclusive)
 331  * for each element calls iter(a) until it returns 0
 332  * returns the last value returned by iterator or 0 if there were no calls
 333  * Warning: a<=b must hold
 334  */
 335 int _avl_range(avl_tree* t, avl* a, avl* b, int (*iter)(avl*), avl** ret) {
 336         int x, c = 0;
 337         if (!t->root)
 338                 return 0;
 339         x = t->compar(t->root, a);
 340         if (a != b) {
 341                 if (x < 0) {
 342                         x = t->compar(t->root, b);
 343                         if (x > 0)
 344                                 x = 0;
 345                 }
 346         }
 347         if (x >= 0) {
 348                 /* search in the left subtree */
 349                 avl_tree left_subtree;
 350                 if ((left_subtree.root = t->root->left)) {
 351                         left_subtree.compar = t->compar;
 352                         if (!(c = _avl_range(&left_subtree, a, b, iter, ret)))
 353                                 if (x > 0)
 354                                         return 0;
 355                 }
 356         }
 357         if (x == 0) {
 358                 if (!(c = iter(t->root))) {
 359                         if (ret)
 360                                 *ret = t->root;
 361                         return 0;
 362                 }
 363         }
 364         if (x <= 0) {
 365                 /* search in the right subtree */
 366                 avl_tree right_subtree;
 367                 if ((right_subtree.root = t->root->right)) {
 368                         right_subtree.compar = t->compar;
 369                         if (!(c = _avl_range(&right_subtree, a, b, iter, ret)))
 370                                 if (x < 0)
 371                                         return 0;
 372                 }
 373         }
 374         return c;
 375 }
 376
 377 int avl_range(avl_tree* t, avl* a, avl* b, int (*iter)(avl*), avl** ret) {
 378 #ifndef AVL_WITHOUT_PTHREADS
 379 #ifdef AVL_LOCK_WITH_MUTEX
 380         pthread_mutex_lock(&t->mutex);
 381 #else
 382         pthread_rwlock_wrlock(&t->rwlock);
 383 #endif
 384 #endif /* AVL_WITHOUT_PTHREADS */
 385
 386         int ret2 = _avl_range(t, a, b, iter, ret);
 387
 388 #ifndef AVL_WITHOUT_PTHREADS
 389 #ifdef AVL_LOCK_WITH_MUTEX
 390         pthread_mutex_unlock(&t->mutex);
 391 #else
 392         pthread_rwlock_unlock(&t->rwlock);
 393 #endif
 394 #endif /* AVL_WITHOUT_PTHREADS */
 395
 396         return ret2;
 397 }
 398
 399 /* Iterate through elements in t equal to a
 400  * for each element calls iter(a) until it returns 0
 401  * returns the last value returned by iterator or 0 if there were no calls
 402  */
 403 int avl_search(avl_tree* t, avl* a, int (*iter)(avl* a), avl** ret) {
 404         return avl_range(t, a, a, iter, ret);
 405 }
 406
 407 void avl_init(avl_tree* t, int (*compar)(void* a, void* b)) {
 408         t->root = NULL;
 409         t->compar = compar;
 410
 411 #ifndef AVL_WITHOUT_PTHREADS
 412         int lock;
 413
 414 #ifdef AVL_LOCK_WITH_MUTEX
 415         lock = pthread_mutex_init(&t->mutex, NULL);
 416 #else
 417         lock = pthread_rwlock_init(&t->rwlock, NULL);
 418 #endif
 419
 420         if(lock != 0)
 421                 fatal("Failed to initialize AVL mutex/rwlock, error: %d", lock);
 422
 423 #endif /* AVL_WITHOUT_PTHREADS */
 424
 425 }