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         pthread_rwlock_wrlock(&t->rwlock);
 148         int ret = _avl_insert(t, a);
 149         pthread_rwlock_unlock(&t->rwlock);
 150         return ret;
 151 }
 152
 153 /* Remove an element a from the AVL tree t
 154  * returns -1 if the depth of the tree has shrunk
 155  * Warning: if the element is not present in the tree,
 156  *          returns 0 as if it had been removed succesfully.
 157  */
 158 int _avl_remove(avl_tree* t, avl* a) {
 159         int b;
 160         if (t->root == a)
 161                 return _avl_removeroot(t);
 162         b = t->compar(t->root, a);
 163         if (b >= 0) {
 164                 /* remove from the left subtree */
 165                 int ch;
 166                 avl_tree left_subtree;
 167                 if ((left_subtree.root = t->root->left)) {
 168                         left_subtree.compar = t->compar;
 169                         ch = _avl_remove(&left_subtree, a);
 170                         t->root->left = left_subtree.root;
 171                         if (ch) {
 172                                 switch (t->root->balance++) {
 173                                 case -1:
 174                                         return -1;
 175                                 case 0:
 176                                         return 0;
 177                                 }
 178                                 switch (t->root->right->balance) {
 179                                 case 0:
 180                                         avl_swl(&(t->root));
 181                                         t->root->balance = -1;
 182                                         t->root->left->balance = 1;
 183                                         return 0;
 184                                 case 1:
 185                                         avl_swl(&(t->root));
 186                                         t->root->balance = 0;
 187                                         t->root->left->balance = 0;
 188                                         return -1;
 189                                 }
 190                                 avl_swr(&(t->root->right));
 191                                 avl_swl(&(t->root));
 192                                 avl_nasty(t->root);
 193                                 return -1;
 194                         }
 195                 }
 196         }
 197         if (b <= 0) {
 198                 /* remove from the right subtree */
 199                 int ch;
 200                 avl_tree right_subtree;
 201                 if ((right_subtree.root = t->root->right)) {
 202                         right_subtree.compar = t->compar;
 203                         ch = _avl_remove(&right_subtree, a);
 204                         t->root->right = right_subtree.root;
 205                         if (ch) {
 206                                 switch (t->root->balance--) {
 207                                 case 1:
 208                                         return -1;
 209                                 case 0:
 210                                         return 0;
 211                                 }
 212                                 switch (t->root->left->balance) {
 213                                 case 0:
 214                                         avl_swr(&(t->root));
 215                                         t->root->balance = 1;
 216                                         t->root->right->balance = -1;
 217                                         return 0;
 218                                 case -1:
 219                                         avl_swr(&(t->root));
 220                                         t->root->balance = 0;
 221                                         t->root->right->balance = 0;
 222                                         return -1;
 223                                 }
 224                                 avl_swl(&(t->root->left));
 225                                 avl_swr(&(t->root));
 226                                 avl_nasty(t->root);
 227                                 return -1;
 228                         }
 229                 }
 230         }
 231         return 0;
 232 }
 233
 234 int avl_remove(avl_tree* t, avl* a) {
 235         pthread_rwlock_wrlock(&t->rwlock);
 236         int ret = _avl_remove(t, a);
 237         pthread_rwlock_unlock(&t->rwlock);
 238         return ret;
 239 }
 240
 241 /* Remove the root of the AVL tree t
 242  * Warning: dumps core if t is empty
 243  */
 244 int _avl_removeroot(avl_tree* t) {
 245         int ch;
 246         avl* a;
 247         if (!t->root->left) {
 248                 if (!t->root->right) {
 249                         t->root = 0;
 250                         return -1;
 251                 }
 252                 t->root = t->root->right;
 253                 return -1;
 254         }
 255         if (!t->root->right) {
 256                 t->root = t->root->left;
 257                 return -1;
 258         }
 259         if (t->root->balance < 0) {
 260                 /* remove from the left subtree */
 261                 a = t->root->left;
 262                 while (a->right)
 263                         a = a->right;
 264         } else {
 265                 /* remove from the right subtree */
 266                 a = t->root->right;
 267                 while (a->left)
 268                         a = a->left;
 269         }
 270         ch = _avl_remove(t, a);
 271         a->left = t->root->left;
 272         a->right = t->root->right;
 273         a->balance = t->root->balance;
 274         t->root = a;
 275         if (a->balance == 0)
 276                 return ch;
 277         return 0;
 278 }
 279
 280 int avl_removeroot(avl_tree* t) {
 281         pthread_rwlock_wrlock(&t->rwlock);
 282         int ret = _avl_removeroot(t);
 283         pthread_rwlock_unlock(&t->rwlock);
 284         return ret;
 285 }
 286
 287 /* Iterate through elements in t from a range between a and b (inclusive)
 288  * for each element calls iter(a) until it returns 0
 289  * returns the last value returned by iterator or 0 if there were no calls
 290  * Warning: a<=b must hold
 291  */
 292 int _avl_range(avl_tree* t, avl* a, avl* b, int (*iter)(avl* a), avl** ret) {
 293         int x, c = 0;
 294         if (!t->root)
 295                 return 0;
 296         x = t->compar(t->root, a);
 297         if (a != b) {
 298                 if (x < 0) {
 299                         x = t->compar(t->root, b);
 300                         if (x > 0)
 301                                 x = 0;
 302                 }
 303         }
 304         if (x >= 0) {
 305                 /* search in the left subtree */
 306                 avl_tree left_subtree;
 307                 if ((left_subtree.root = t->root->left)) {
 308                         left_subtree.compar = t->compar;
 309                         if (!(c = _avl_range(&left_subtree, a, b, iter, ret)))
 310                                 if (x > 0)
 311                                         return 0;
 312                 }
 313         }
 314         if (x == 0) {
 315                 if (!(c = iter(t->root))) {
 316                         if (ret)
 317                                 *ret = t->root;
 318                         return 0;
 319                 }
 320         }
 321         if (x <= 0) {
 322                 /* search in the right subtree */
 323                 avl_tree right_subtree;
 324                 if ((right_subtree.root = t->root->right)) {
 325                         right_subtree.compar = t->compar;
 326                         if (!(c = _avl_range(&right_subtree, a, b, iter, ret)))
 327                                 if (x < 0)
 328                                         return 0;
 329                 }
 330         }
 331         return c;
 332 }
 333
 334 int avl_range(avl_tree* t, avl* a, avl* b, int (*iter)(avl* a), avl** ret) {
 335         pthread_rwlock_rdlock(&t->rwlock);
 336         int ret2 = _avl_range(t, a, b, iter, ret);
 337         pthread_rwlock_unlock(&t->rwlock);
 338         return ret2;
 339 }
 340
 341 /* Iterate through elements in t equal to a
 342  * for each element calls iter(a) until it returns 0
 343  * returns the last value returned by iterator or 0 if there were no calls
 344  */
 345 int avl_search(avl_tree* t, avl* a, int (*iter)(avl* a), avl** ret) {
 346         return avl_range(t, a, a, iter, ret);
 347 }
 348
 349 void avl_init(avl_tree* t, int (*compar)(void* a, void* b)) {
 350         t->root = NULL;
 351         t->compar = compar;
 352         pthread_rwlock_init(&t->rwlock, NULL);
 353 }