src/utils_avltree.c

   1 /**
   2  * collectd - src/utils_avltree.c
   3  * Copyright (C) 2006,2007  Florian octo Forster
   4  *
   5  * This program is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License as published by the
   7  * Free Software Foundation; either version 2 of the License, or (at your
   8  * option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful, but
  11  * WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  * General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License along
  16  * with this program; if not, write to the Free Software Foundation, Inc.,
  17  * 51 Franklin St, Fifth Floor, Boston, MA  02110-1301 USA
  18  *
  19  * Authors:
  20  *   Florian octo Forster <octo at verplant.org>
  21  **/
  22 #include <stdlib.h>
  23 #include <stdio.h>
  24 #include <assert.h>
  25
  26 #include "utils_avltree.h"
  27
  28 #define BALANCE(n) ((((n)->left == NULL) ? 0 : (n)->left->height) \
  29                 - (((n)->right == NULL) ? 0 : (n)->right->height))
  30
  31 /*
  32  * private data types
  33  */
  34 struct avl_node_s
  35 {
  36         void *key;
  37         void *value;
  38
  39         int height;
  40         struct avl_node_s *left;
  41         struct avl_node_s *right;
  42         struct avl_node_s *parent;
  43 };
  44 typedef struct avl_node_s avl_node_t;
  45
  46 struct avl_tree_s
  47 {
  48         avl_node_t *root;
  49         int (*compare) (const void *, const void *);
  50 };
  51
  52 struct avl_iterator_s
  53 {
  54         avl_tree_t *tree;
  55         avl_node_t *node;
  56 };
  57
  58 /*
  59  * private functions
  60  */
  61 #if 0
  62 static void verify_tree (avl_node_t *n)
  63 {
  64         if (n == NULL)
  65                 return;
  66
  67         verify_tree (n->left);
  68         verify_tree (n->right);
  69
  70         assert ((BALANCE (n) >= -1) && (BALANCE (n) <= 1));
  71         assert ((n->parent == NULL) || (n->parent->right == n) || (n->parent->left == n));
  72 } /* void verify_tree */
  73 #else
  74 # define verify_tree(n) /**/
  75 #endif
  76
  77 static void free_node (avl_node_t *n)
  78 {
  79         if (n == NULL)
  80                 return;
  81
  82         if (n->left != NULL)
  83                 free_node (n->left);
  84         if (n->right != NULL)
  85                 free_node (n->right);
  86
  87         free (n);
  88 }
  89
  90 static int calc_height (avl_node_t *n)
  91 {
  92         int height_left;
  93         int height_right;
  94
  95         if (n == NULL)
  96                 return (0);
  97
  98         height_left  = (n->left == NULL)  ? 0 : n->left->height;
  99         height_right = (n->right == NULL) ? 0 : n->right->height;
 100
 101         return (((height_left > height_right)
 102                                 ? height_left
 103                                 : height_right) + 1);
 104 } /* int calc_height */
 105
 106 static avl_node_t *search (avl_tree_t *t, const void *key)
 107 {
 108         avl_node_t *n;
 109         int cmp;
 110
 111         n = t->root;
 112         while (n != NULL)
 113         {
 114                 cmp = t->compare (key, n->key);
 115                 if (cmp == 0)
 116                         return (n);
 117                 else if (cmp < 0)
 118                         n = n->left;
 119                 else
 120                         n = n->right;
 121         }
 122
 123         return (NULL);
 124 }
 125
 126 /*         (x)             (y)
 127  *        /   \           /   \
 128  *     (y)    /\         /\    (x)
 129  *    /   \  /_c\  ==>  / a\  /   \
 130  *   /\   /\           /____\/\   /\
 131  *  / a\ /_b\               /_b\ /_c\
 132  * /____\
 133  */
 134 static avl_node_t *rotate_right (avl_tree_t *t, avl_node_t *x)
 135 {
 136         avl_node_t *p;
 137         avl_node_t *y;
 138         avl_node_t *b;
 139
 140         p = x->parent;
 141         y = x->left;
 142         b = y->right;
 143
 144         x->left = b;
 145         if (b != NULL)
 146                 b->parent = x;
 147
 148         x->parent = y;
 149         y->right = x;
 150
 151         y->parent = p;
 152         assert ((p == NULL) || (p->left == x) || (p->right == x));
 153         if (p == NULL)
 154                 t->root = y;
 155         else if (p->left == x)
 156                 p->left = y;
 157         else
 158                 p->right = y;
 159
 160         x->height = calc_height (x);
 161         y->height = calc_height (y);
 162
 163         return (y);
 164 } /* void rotate_left */
 165
 166 /*
 167  *    (x)                   (y)
 168  *   /   \                 /   \
 169  *  /\    (y)           (x)    /\
 170  * /_a\  /   \   ==>   /   \  / c\
 171  *      /\   /\       /\   /\/____\
 172  *     /_b\ / c\     /_a\ /_b\
 173  *         /____\
 174  */
 175 static avl_node_t *rotate_left (avl_tree_t *t, avl_node_t *x)
 176 {
 177         avl_node_t *p;
 178         avl_node_t *y;
 179         avl_node_t *b;
 180
 181         p = x->parent;
 182         y = x->right;
 183         b = y->left;
 184
 185         x->right = b;
 186         if (b != NULL)
 187                 b->parent = x;
 188
 189         x->parent = y;
 190         y->left = x;
 191
 192         y->parent = p;
 193         assert ((p == NULL) || (p->left == x) || (p->right == x));
 194         if (p == NULL)
 195                 t->root = y;
 196         else if (p->left == x)
 197                 p->left = y;
 198         else
 199                 p->right = y;
 200
 201         x->height = calc_height (x);
 202         y->height = calc_height (y);
 203
 204         return (y);
 205 } /* void rotate_left */
 206
 207 static avl_node_t *rotate_left_right (avl_tree_t *t, avl_node_t *x)
 208 {
 209         rotate_left (t, x->left);
 210         return (rotate_right (t, x));
 211 } /* void rotate_left_right */
 212
 213 static avl_node_t *rotate_right_left (avl_tree_t *t, avl_node_t *x)
 214 {
 215         rotate_right (t, x->right);
 216         return (rotate_left (t, x));
 217 } /* void rotate_right_left */
 218
 219 static void rebalance (avl_tree_t *t, avl_node_t *n)
 220 {
 221         int b_top;
 222         int b_bottom;
 223
 224         while (n != NULL)
 225         {
 226                 b_top = BALANCE (n);
 227                 assert ((b_top >= -2) && (b_top <= 2));
 228
 229                 if (b_top == -2)
 230                 {
 231                         assert (n->right != NULL);
 232                         b_bottom = BALANCE (n->right);
 233                         assert ((b_bottom >= -1) || (b_bottom <= 1));
 234                         if (b_bottom == 1)
 235                                 n = rotate_right_left (t, n);
 236                         else
 237                                 n = rotate_left (t, n);
 238                 }
 239                 else if (b_top == 2)
 240                 {
 241                         assert (n->left != NULL);
 242                         b_bottom = BALANCE (n->left);
 243                         assert ((b_bottom >= -1) || (b_bottom <= 1));
 244                         if (b_bottom == -1)
 245                                 n = rotate_left_right (t, n);
 246                         else
 247                                 n = rotate_right (t, n);
 248                 }
 249                 else
 250                 {
 251                         int height = calc_height (n);
 252                         if (height == n->height)
 253                                 break;
 254                         n->height = height;
 255                 }
 256
 257                 assert (n->height == calc_height (n));
 258
 259                 n = n->parent;
 260         } /* while (n != NULL) */
 261 } /* void rebalance */
 262
 263 #if 0
 264 /* This code disabled until a need arises. */
 265 static avl_iterator_t *avl_create_iterator (avl_tree_t *t, avl_node_t *n)
 266 {
 267         avl_iterator_t *iter;
 268
 269         iter = (avl_iterator_t *) malloc (sizeof (avl_iterator_t));
 270         if (iter == NULL)
 271                 return (NULL);
 272
 273         iter->tree = t;
 274         iter->node = n;
 275
 276         return (iter);
 277 }
 278 #endif
 279
 280 static void *avl_node_next (avl_tree_t *t, avl_node_t *n)
 281 {
 282         avl_node_t *r; /* return node */
 283
 284         if (n == NULL)
 285         {
 286                 return (NULL);
 287         }
 288         else if (n->right == NULL)
 289         {
 290
 291                 r = n->parent;
 292                 while (r != NULL)
 293                 {
 294                         /* stop if a bigger node is found */
 295                         if (t->compare (n, r) < 0) /* n < r */
 296                                 break;
 297                         r = r->parent;
 298                 }
 299         }
 300         else
 301         {
 302                 r = n->right;
 303                 while (r->left != NULL)
 304                         r = r->left;
 305         }
 306
 307         return (r);
 308 }
 309
 310 static void *avl_node_prev (avl_tree_t *t, avl_node_t *n)
 311 {
 312         avl_node_t *r; /* return node */
 313
 314         if (n == NULL)
 315         {
 316                 return (NULL);
 317         }
 318         else if (n->left == NULL)
 319         {
 320
 321                 r = n->parent;
 322                 while (r != NULL)
 323                 {
 324                         /* stop if a smaller node is found */
 325                         if (t->compare (n, r) > 0) /* n > r */
 326                                 break;
 327                         r = r->parent;
 328                 }
 329         }
 330         else
 331         {
 332                 r = n->left;
 333                 while (r->right != NULL)
 334                         r = r->right;
 335         }
 336
 337         return (r);
 338 } /* void *avl_node_prev */
 339
 340 static int _remove (avl_tree_t *t, avl_node_t *n)
 341 {
 342         assert ((t != NULL) && (n != NULL));
 343
 344         if ((n->left != NULL) && (n->right != NULL))
 345         {
 346                 avl_node_t *r; /* replacement node */
 347                 if (BALANCE (n) > 0) /* left subtree is higher */
 348                 {
 349                         assert (n->left != NULL);
 350                         r = avl_node_prev (t, n);
 351
 352                 }
 353                 else /* right subtree is higher */
 354                 {
 355                         assert (n->right != NULL);
 356                         r = avl_node_next (t, n);
 357                 }
 358
 359                 assert ((r->left == NULL) || (r->right == NULL));
 360
 361                 /* copy content */
 362                 n->key   = r->key;
 363                 n->value = r->value;
 364
 365                 n = r;
 366         }
 367
 368         assert ((n->left == NULL) || (n->right == NULL));
 369
 370         if ((n->left == NULL) && (n->right == NULL))
 371         {
 372                 /* Deleting a leave is easy */
 373                 if (n->parent == NULL)
 374                 {
 375                         assert (t->root == n);
 376                         t->root = NULL;
 377                 }
 378                 else
 379                 {
 380                         assert ((n->parent->left == n)
 381                                         || (n->parent->right == n));
 382                         if (n->parent->left == n)
 383                                 n->parent->left = NULL;
 384                         else
 385                                 n->parent->right = NULL;
 386
 387                         rebalance (t, n->parent);
 388                 }
 389
 390                 free_node (n);
 391         }
 392         else if (n->left == NULL)
 393         {
 394                 assert (BALANCE (n) == -1);
 395                 assert ((n->parent == NULL) || (n->parent->left == n) || (n->parent->right == n));
 396                 if (n->parent == NULL)
 397                 {
 398                         assert (t->root == n);
 399                         t->root = n->right;
 400                 }
 401                 else if (n->parent->left == n)
 402                 {
 403                         n->parent->left = n->right;
 404                 }
 405                 else
 406                 {
 407                         n->parent->right = n->right;
 408                 }
 409                 n->right->parent = n->parent;
 410
 411                 if (n->parent != NULL)
 412                         rebalance (t, n->parent);
 413
 414                 n->right = NULL;
 415                 free_node (n);
 416         }
 417         else if (n->right == NULL)
 418         {
 419                 assert (BALANCE (n) == 1);
 420                 assert ((n->parent == NULL) || (n->parent->left == n) || (n->parent->right == n));
 421                 if (n->parent == NULL)
 422                 {
 423                         assert (t->root == n);
 424                         t->root = n->left;
 425                 }
 426                 else if (n->parent->left == n)
 427                 {
 428                         n->parent->left = n->left;
 429                 }
 430                 else
 431                 {
 432                         n->parent->right = n->left;
 433                 }
 434                 n->left->parent = n->parent;
 435
 436                 if (n->parent != NULL)
 437                         rebalance (t, n->parent);
 438
 439                 n->left = NULL;
 440                 free_node (n);
 441         }
 442         else
 443         {
 444                 assert (0);
 445         }
 446
 447         return (0);
 448 } /* void *_remove */
 449
 450 /*
 451  * public functions
 452  */
 453 avl_tree_t *avl_create (int (*compare) (const void *, const void *))
 454 {
 455         avl_tree_t *t;
 456
 457         if (compare == NULL)
 458                 return (NULL);
 459
 460         if ((t = (avl_tree_t *) malloc (sizeof (avl_tree_t))) == NULL)
 461                 return (NULL);
 462
 463         t->root = NULL;
 464         t->compare = compare;
 465
 466         return (t);
 467 }
 468
 469 void avl_destroy (avl_tree_t *t)
 470 {
 471         free_node (t->root);
 472         free (t);
 473 }
 474
 475 int avl_insert (avl_tree_t *t, void *key, void *value)
 476 {
 477         avl_node_t *new;
 478         avl_node_t *nptr;
 479         int cmp;
 480
 481         if ((new = (avl_node_t *) malloc (sizeof (avl_node_t))) == NULL)
 482                 return (-1);
 483
 484         new->key = key;
 485         new->value = value;
 486         new->height = 1;
 487         new->left = NULL;
 488         new->right = NULL;
 489
 490         if (t->root == NULL)
 491         {
 492                 new->parent = NULL;
 493                 t->root = new;
 494                 return (0);
 495         }
 496
 497         nptr = t->root;
 498         while (42)
 499         {
 500                 cmp = t->compare (nptr->key, new->key);
 501                 if (cmp == 0)
 502                 {
 503                         free_node (new);
 504                         return (-1);
 505                 }
 506                 else if (cmp < 0)
 507                 {
 508                         /* nptr < new */
 509                         if (nptr->right == NULL)
 510                         {
 511                                 nptr->right = new;
 512                                 new->parent = nptr;
 513                                 rebalance (t, nptr);
 514                                 break;
 515                         }
 516                         else
 517                         {
 518                                 nptr = nptr->right;
 519                         }
 520                 }
 521                 else /* if (cmp > 0) */
 522                 {
 523                         /* nptr > new */
 524                         if (nptr->left == NULL)
 525                         {
 526                                 nptr->left = new;
 527                                 new->parent = nptr;
 528                                 rebalance (t, nptr);
 529                                 break;
 530                         }
 531                         else
 532                         {
 533                                 nptr = nptr->left;
 534                         }
 535                 }
 536         } /* while (42) */
 537
 538         verify_tree (t->root);
 539         return (0);
 540 } /* int avl_insert */
 541
 542 int avl_remove (avl_tree_t *t, void *key, void **rkey, void **rvalue)
 543 {
 544         avl_node_t *n;
 545         int status;
 546
 547         assert (t != NULL);
 548
 549         n = search (t, key);
 550         if (n == NULL)
 551                 return (-1);
 552
 553         if (rkey != NULL)
 554                 *rkey = n->key;
 555         if (rvalue != NULL)
 556                 *rvalue = n->value;
 557
 558         status = _remove (t, n);
 559         verify_tree (t->root);
 560         return (status);
 561 } /* void *avl_remove */
 562
 563 int avl_get (avl_tree_t *t, const void *key, void **value)
 564 {
 565         avl_node_t *n;
 566
 567         assert (value != NULL);
 568
 569         n = search (t, key);
 570         if (n == NULL)
 571                 return (-1);
 572
 573         *value = n->value;
 574
 575         return (0);
 576 }
 577
 578 int avl_pick (avl_tree_t *t, void **key, void **value)
 579 {
 580         avl_node_t *n;
 581         avl_node_t *p;
 582
 583         if ((key == NULL) || (value == NULL))
 584                 return (-1);
 585         if (t->root == NULL)
 586                 return (-1);
 587
 588         n = t->root;
 589         while ((n->left != NULL) || (n->right != NULL))
 590         {
 591                 int height_left  = (n->left  == NULL) ? 0 : n->left->height;
 592                 int height_right = (n->right == NULL) ? 0 : n->right->height;
 593
 594                 if (height_left > height_right)
 595                         n = n->left;
 596                 else
 597                         n = n->right;
 598         }
 599
 600         p = n->parent;
 601         if (p == NULL)
 602                 t->root = NULL;
 603         else if (p->left == n)
 604                 p->left = NULL;
 605         else
 606                 p->right = NULL;
 607
 608         *key   = n->key;
 609         *value = n->value;
 610
 611         free_node (n);
 612         rebalance (t, p);
 613
 614         return (0);
 615 } /* int avl_pick */
 616
 617 #if 0
 618 /* This code disabled until a need arises. */
 619 avl_iterator_t *avl_get_iterator (avl_tree_t *t)
 620 {
 621         avl_node_t *n;
 622
 623         if (t == NULL)
 624                 return (NULL);
 625
 626         for (n = t->root; n != NULL; n = n->left)
 627                 if (n->left == NULL)
 628                         break;
 629
 630         return (avl_create_iterator (t, n));
 631 } /* avl_iterator_t *avl_get_iterator */
 632
 633 void *avl_iterator_next (avl_iterator_t *iter)
 634 {
 635         avl_node_t *n;
 636
 637         if ((iter == NULL) || (iter->node == NULL))
 638                 return (NULL);
 639
 640         n = avl_node_next (iter->tree, iter->node);
 641
 642         if (n == NULL)
 643                 return (NULL);
 644
 645         iter->node = n;
 646         return (n);
 647
 648 }
 649
 650 void *avl_iterator_prev (avl_iterator_t *iter)
 651 {
 652         avl_node_t *n;
 653
 654         if ((iter == NULL) || (iter->node == NULL))
 655                 return (NULL);
 656
 657         n = avl_node_prev (iter->tree, iter->node);
 658
 659         if (n == NULL)
 660                 return (NULL);
 661
 662         iter->node = n;
 663         return (n);
 664
 665 }
 666
 667 void avl_iterator_destroy (avl_iterator_t *iter)
 668 {
 669         free (iter);
 670 }
 671 #endif /* 0 */