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