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