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