src/utils_avltree.c

   1 #include <stdlib.h>
   2 #include <assert.h>
   3
   4 #include "utils_avltree.h"
   5
   6 #define BALANCE(n) ((((n)->right == NULL) ? 0 : (n)->right->height) \
   7                                  - (((n)->left == NULL) ? 0 : (n)->left->height))
   8
   9 /*
  10  * private data types
  11  */
  12 struct avl_node_s
  13 {
  14         void *key;
  15         void *value;
  16
  17         int height;
  18         struct avl_node_s *left;
  19         struct avl_node_s *right;
  20         struct avl_node_s *parent;
  21 };
  22 typedef struct avl_node_s avl_node_t;
  23
  24 struct avl_tree_s
  25 {
  26         avl_node_t *root;
  27         int (*compare) (const void *, const void *);
  28 };
  29
  30 struct avl_iterator_s
  31 {
  32         avl_tree_t *tree;
  33         avl_node_t *node;
  34 };
  35
  36 /*
  37  * private functions
  38  */
  39 static void free_node (avl_node_t *n)
  40 {
  41         if (n == NULL)
  42                 return;
  43
  44         if (n->left != NULL)
  45                 free_node (n->left);
  46         if (n->right != NULL)
  47                 free_node (n->right);
  48
  49         free (n);
  50 }
  51
  52 static avl_node_t *search (avl_tree_t *t, const void *key)
  53 {
  54         avl_node_t *n;
  55         int cmp;
  56
  57         n = t->root;
  58         while (n != NULL)
  59         {
  60                 cmp = t->compare (key, n->key);
  61                 if (cmp == 0)
  62                         return (n);
  63                 else if (cmp < 0)
  64                         n = n->left;
  65                 else
  66                         n = n->right;
  67         }
  68
  69         return (NULL);
  70 }
  71
  72 static void rebalance (avl_tree_t *t, avl_node_t *n)
  73 {
  74         int height_left;
  75         int height_right;
  76         int height_new;
  77         int cmp;
  78
  79         while (n != NULL)
  80         {
  81                 height_left = (n->left == NULL) ? 0 : n->left->height;
  82                 height_right = (n->right == NULL) ? 0 : n->right->height;
  83
  84                 height_new = 1 + ((height_left > height_right) ? height_left : height_right);
  85
  86                 if (height_new == n->height)
  87                         break;
  88
  89                 /* FIXME */
  90                 if (n->left != NULL)
  91                 {
  92                         cmp = BALANCE(n->left);
  93                         assert ((cmp >= -1) && (cmp <= 1));
  94                 }
  95                 if (n->right != NULL)
  96                 {
  97                         cmp = BALANCE(n->right);
  98                         assert ((cmp >= -1) && (cmp <= 1));
  99                 }
 100
 101                 n->height = height_new;
 102
 103                 cmp = height_right - height_left;
 104                 if (cmp < -1)
 105                 {
 106                         avl_node_t *l;
 107                         avl_node_t *lr;
 108
 109                         l = n->left;
 110                         lr = l->right;
 111
 112                         l->right = n;
 113                         l->parent = n->parent;
 114                         n->parent = l;
 115                         n->left = lr;
 116
 117                         if (lr != NULL)
 118                                 lr->parent = n;
 119
 120                         if (l->parent == NULL)
 121                         {
 122                                 assert (t->root == n);
 123                                 t->root = l;
 124                         }
 125                         else
 126                         {
 127                                 assert ((l->parent->left == n) || (l->parent->right == n));
 128                                 if (l->parent->left == n)
 129                                         l->parent->left = l;
 130                                 else
 131                                         l->parent->right = l;
 132                         }
 133
 134                         height_left = (n->left == NULL) ? 0 : n->left->height;
 135                         height_right = (n->right == NULL) ? 0 : n->right->height;
 136                         height_new = 1 + ((height_left > height_right) ? height_left : height_right);
 137                         cmp = BALANCE(n);
 138                         assert (height_new < n->height);
 139                         assert ((cmp >= -1) || (cmp <= 1));
 140                         n->height = height_new;
 141
 142                         height_left = (l->left == NULL) ? 0 : l->left->height;
 143                         height_right = (l->right == NULL) ? 0 : l->right->height;
 144                         height_new = 1 + ((height_left > height_right) ? height_left : height_right);
 145                         cmp = BALANCE(l);
 146                         assert (height_new >= l->height);
 147                         assert ((cmp >= -1) || (cmp <= 1));
 148                         l->height = height_new;
 149
 150                         n = l->parent;
 151                 }
 152                 else if (cmp > 1)
 153                 {
 154                         avl_node_t *r;
 155                         avl_node_t *rl;
 156
 157                         r = n->right;
 158                         rl = r->left;
 159
 160                         r->left = n;
 161                         r->parent = n->parent;
 162                         n->parent = r;
 163                         n->right = rl;
 164
 165                         if (rl != NULL)
 166                                 rl->parent = n;
 167
 168                         if (r->parent == NULL)
 169                         {
 170                                 assert (t->root == n);
 171                                 t->root = r;
 172                         }
 173                         else
 174                         {
 175                                 assert ((r->parent->left == n) || (r->parent->right == n));
 176                                 if (r->parent->left == n)
 177                                         r->parent->left = r;
 178                                 else
 179                                         r->parent->right = r;
 180                         }
 181
 182                         height_left = (n->left == NULL) ? 0 : n->left->height;
 183                         height_right = (n->right == NULL) ? 0 : n->right->height;
 184                         height_new = 1 + ((height_left > height_right) ? height_left : height_right);
 185                         cmp = BALANCE(n);
 186                         assert (height_new < n->height);
 187                         assert ((cmp >= -1) || (cmp <= 1));
 188                         n->height = height_new;
 189
 190                         height_left = (r->left == NULL) ? 0 : r->left->height;
 191                         height_right = (r->right == NULL) ? 0 : r->right->height;
 192                         height_new = 1 + ((height_left > height_right) ? height_left : height_right);
 193                         cmp = BALANCE(r);
 194                         assert (height_new >= r->height);
 195                         assert ((cmp >= -1) || (cmp <= 1));
 196                         r->height = height_new;
 197
 198                         n = r->parent;
 199                 }
 200                 else
 201                 {
 202                         n = n->parent;
 203                 }
 204
 205                 assert ((n == NULL) || (n->parent == NULL)
 206                                 || (n->parent->left == n)
 207                                 || (n->parent->right == n));
 208         } /* while (n != NULL) */
 209 } /* void rebalance */
 210
 211 static avl_iterator_t *avl_create_iterator (avl_tree_t *t, avl_node_t *n)
 212 {
 213         avl_iterator_t *iter;
 214
 215         iter = (avl_iterator_t *) malloc (sizeof (avl_iterator_t));
 216         if (iter == NULL)
 217                 return (NULL);
 218
 219         iter->tree = t;
 220         iter->node = n;
 221
 222         return (iter);
 223 }
 224
 225 void *avl_node_next (avl_tree_t *t, avl_node_t *n)
 226 {
 227         avl_node_t *r; /* return node */
 228
 229         if (n == NULL)
 230         {
 231                 return (NULL);
 232         }
 233         else if (n->right == NULL)
 234         {
 235
 236                 r = n->parent;
 237                 while (r != NULL)
 238                 {
 239                         /* stop if a bigger node is found */
 240                         if (t->compare (n, r) < 0) /* n < r */
 241                                 break;
 242                         r = r->parent;
 243                 }
 244         }
 245         else
 246         {
 247                 r = n->right;
 248                 while (r->left != NULL)
 249                         r = r->left;
 250         }
 251
 252         return (r);
 253 }
 254
 255 void *avl_node_prev (avl_tree_t *t, avl_node_t *n)
 256 {
 257         avl_node_t *r; /* return node */
 258
 259         if (n == NULL)
 260         {
 261                 return (NULL);
 262         }
 263         else if (n->left == NULL)
 264         {
 265
 266                 r = n->parent;
 267                 while (r != NULL)
 268                 {
 269                         /* stop if a smaller node is found */
 270                         if (t->compare (n, r) > 0) /* n > r */
 271                                 break;
 272                         r = r->parent;
 273                 }
 274         }
 275         else
 276         {
 277                 r = n->left;
 278                 while (r->right != NULL)
 279                         r = r->right;
 280         }
 281
 282         return (r);
 283 }
 284
 285 static int _remove (avl_tree_t *t, avl_node_t *n)
 286 {
 287         assert ((t != NULL) && (n != NULL));
 288
 289         if ((n->left == NULL) && (n->right == NULL))
 290         {
 291                 /* Deleting a leave is easy */
 292                 if (n->parent == NULL)
 293                 {
 294                         assert (t->root == n);
 295                         t->root = NULL;
 296                 }
 297                 else
 298                 {
 299                         assert ((n->parent->left == n)
 300                                         || (n->parent->right == n));
 301                         if (n->parent->left == n)
 302                                 n->parent->left = NULL;
 303                         else
 304                                 n->parent->right = NULL;
 305
 306                         rebalance (t, n->parent);
 307                 }
 308
 309                 free_node (n);
 310         }
 311         else
 312         {
 313                 avl_node_t *r; /* replacement node */
 314                 if (BALANCE (n) < 0)
 315                 {
 316                         assert (n->left != NULL);
 317                         r = avl_node_prev (t, n);
 318                 }
 319                 else
 320                 {
 321                         assert (n->right != NULL);
 322                         r = avl_node_next (t, n);
 323                 }
 324                 n->key   = r->key;
 325                 n->value = r->value;
 326
 327                 _remove (t, r);
 328         }
 329
 330         return (0);
 331 } /* void *_remove */
 332
 333 /*
 334  * public functions
 335  */
 336 avl_tree_t *avl_create (int (*compare) (const void *, const void *))
 337 {
 338         avl_tree_t *t;
 339
 340         if ((t = (avl_tree_t *) malloc (sizeof (avl_tree_t))) == NULL)
 341                 return (NULL);
 342
 343         t->root = NULL;
 344         t->compare = compare;
 345
 346         return (t);
 347 }
 348
 349 void avl_destroy (avl_tree_t *t)
 350 {
 351         free_node (t->root);
 352         free (t);
 353 }
 354
 355 int avl_insert (avl_tree_t *t, void *key, void *value)
 356 {
 357         avl_node_t *new;
 358         avl_node_t *nptr;
 359         int cmp;
 360
 361         if ((new = (avl_node_t *) malloc (sizeof (avl_node_t))) == NULL)
 362                 return (-1);
 363
 364         new->key = key;
 365         new->value = value;
 366         new->height = 1;
 367         new->left = NULL;
 368         new->right = NULL;
 369
 370         if (t->root == NULL)
 371         {
 372                 new->parent = NULL;
 373                 t->root = new;
 374                 return (0);
 375         }
 376
 377         nptr = t->root;
 378         while (42)
 379         {
 380                 cmp = t->compare (nptr->key, new->key);
 381                 if (cmp == 0)
 382                 {
 383                         free_node (new);
 384                         return (-1);
 385                 }
 386                 else if (cmp < 0)
 387                 {
 388                         /* nptr < new */
 389                         if (nptr->right == NULL)
 390                         {
 391                                 nptr->right = new;
 392                                 new->parent = nptr;
 393                                 nptr = NULL;
 394                                 break;
 395                         }
 396                         else
 397                         {
 398                                 nptr = nptr->right;
 399                         }
 400                 }
 401                 else /* if (cmp > 0) */
 402                 {
 403                         /* nptr > new */
 404                         if (nptr->left == NULL)
 405                         {
 406                                 nptr->left = new;
 407                                 new->parent = nptr;
 408                                 nptr = NULL;
 409                                 break;
 410                         }
 411                         else
 412                         {
 413                                 nptr = nptr->left;
 414                         }
 415                 }
 416         } /* while (42) */
 417
 418         assert ((new->parent != NULL)
 419                         && ((new->parent->left == new)
 420                                 || (new->parent->right == new)));
 421
 422         return (0);
 423 } /* int avl_insert */
 424
 425 int avl_remove (avl_tree_t *t, void *key, void **rkey, void **rvalue)
 426 {
 427         avl_node_t *n;
 428
 429         assert (t != NULL);
 430
 431         n = search (t, key);
 432         if (n == NULL)
 433                 return (-1);
 434
 435         if (rkey != NULL)
 436                 *rkey = n->key;
 437         if (rvalue != NULL)
 438                 *rvalue = n->value;
 439
 440         return (_remove (t, n));
 441 } /* void *avl_remove */
 442
 443 int avl_get (avl_tree_t *t, const void *key, void **value)
 444 {
 445         avl_node_t *n;
 446
 447         assert (value != NULL);
 448
 449         n = search (t, key);
 450         if (n == NULL)
 451                 return (-1);
 452
 453         *value = n->value;
 454
 455         return (0);
 456 }
 457
 458 avl_iterator_t *avl_get_iterator (avl_tree_t *t)
 459 {
 460         avl_node_t *n;
 461
 462         if (t == NULL)
 463                 return (NULL);
 464
 465         for (n = t->root; n != NULL; n = n->left)
 466                 if (n->left == NULL)
 467                         break;
 468
 469         return (avl_create_iterator (t, n));
 470 } /* avl_iterator_t *avl_get_iterator */
 471
 472 void *avl_iterator_next (avl_iterator_t *iter)
 473 {
 474         avl_node_t *n;
 475
 476         if ((iter == NULL) || (iter->node == NULL))
 477                 return (NULL);
 478
 479         n = avl_node_next (iter->tree, iter->node);
 480
 481         if (n == NULL)
 482                 return (NULL);
 483
 484         iter->node = n;
 485         return (n);
 486
 487 }
 488
 489 void *avl_iterator_prev (avl_iterator_t *iter)
 490 {
 491         avl_node_t *n;
 492
 493         if ((iter == NULL) || (iter->node == NULL))
 494                 return (NULL);
 495
 496         n = avl_node_prev (iter->tree, iter->node);
 497
 498         if (n == NULL)
 499                 return (NULL);
 500
 501         iter->node = n;
 502         return (n);
 503
 504 }
 505
 506 void avl_iterator_destroy (avl_iterator_t *iter)
 507 {
 508         free (iter);
 509 }