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 c_avl_node_s
  39 {
  40         void *key;
  41         void *value;
  42
  43         int height;
  44         struct c_avl_node_s *left;
  45         struct c_avl_node_s *right;
  46         struct c_avl_node_s *parent;
  47 };
  48 typedef struct c_avl_node_s c_avl_node_t;
  49
  50 struct c_avl_tree_s
  51 {
  52         c_avl_node_t *root;
  53         int (*compare) (const void *, const void *);
  54 };
  55
  56 struct c_avl_iterator_s
  57 {
  58         c_avl_tree_t *tree;
  59         c_avl_node_t *node;
  60 };
  61
  62 /*
  63  * private functions
  64  */
  65 #if 0
  66 static void verify_tree (c_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 (c_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 (c_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 c_avl_node_t *search (c_avl_tree_t *t, const void *key)
 111 {
 112         c_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 c_avl_node_t *rotate_right (c_avl_tree_t *t, c_avl_node_t *x)
 139 {
 140         c_avl_node_t *p;
 141         c_avl_node_t *y;
 142         c_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 c_avl_node_t *rotate_left (c_avl_tree_t *t, c_avl_node_t *x)
 180 {
 181         c_avl_node_t *p;
 182         c_avl_node_t *y;
 183         c_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 c_avl_node_t *rotate_left_right (c_avl_tree_t *t, c_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 c_avl_node_t *rotate_right_left (c_avl_tree_t *t, c_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 (c_avl_tree_t *t, c_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 c_avl_node_t *c_avl_node_next (c_avl_node_t *n)
 268 {
 269         c_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 } /* c_avl_node_t *c_avl_node_next */
 311
 312 static c_avl_node_t *c_avl_node_prev (c_avl_node_t *n)
 313 {
 314         c_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 } /* c_avl_node_t *c_avl_node_prev */
 356
 357 static int _remove (c_avl_tree_t *t, c_avl_node_t *n)
 358 {
 359         assert ((t != NULL) && (n != NULL));
 360
 361         if ((n->left != NULL) && (n->right != NULL))
 362         {
 363                 c_avl_node_t *r; /* replacement node */
 364                 if (BALANCE (n) > 0) /* left subtree is higher */
 365                 {
 366                         assert (n->left != NULL);
 367                         r = c_avl_node_prev (n);
 368
 369                 }
 370                 else /* right subtree is higher */
 371                 {
 372                         assert (n->right != NULL);
 373                         r = c_avl_node_next (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 c_avl_tree_t *c_avl_create (int (*compare) (const void *, const void *))
 471 {
 472         c_avl_tree_t *t;
 473
 474         if (compare == NULL)
 475                 return (NULL);
 476
 477         if ((t = (c_avl_tree_t *) malloc (sizeof (c_avl_tree_t))) == NULL)
 478                 return (NULL);
 479
 480         t->root = NULL;
 481         t->compare = compare;
 482
 483         return (t);
 484 }
 485
 486 void c_avl_destroy (c_avl_tree_t *t)
 487 {
 488         free_node (t->root);
 489         free (t);
 490 }
 491
 492 int c_avl_insert (c_avl_tree_t *t, void *key, void *value)
 493 {
 494         c_avl_node_t *new;
 495         c_avl_node_t *nptr;
 496         int cmp;
 497
 498         if ((new = (c_avl_node_t *) malloc (sizeof (c_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 c_avl_insert */
 558
 559 int c_avl_remove (c_avl_tree_t *t, const void *key, void **rkey, void **rvalue)
 560 {
 561         c_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 *c_avl_remove */
 579
 580 int c_avl_get (c_avl_tree_t *t, const void *key, void **value)
 581 {
 582         c_avl_node_t *n;
 583
 584         assert (t != NULL);
 585
 586         n = search (t, key);
 587         if (n == NULL)
 588                 return (-1);
 589
 590         if (value != NULL)
 591                 *value = n->value;
 592
 593         return (0);
 594 }
 595
 596 int c_avl_pick (c_avl_tree_t *t, void **key, void **value)
 597 {
 598         c_avl_node_t *n;
 599         c_avl_node_t *p;
 600
 601         if ((key == NULL) || (value == NULL))
 602                 return (-1);
 603         if (t->root == NULL)
 604                 return (-1);
 605
 606         n = t->root;
 607         while ((n->left != NULL) || (n->right != NULL))
 608         {
 609                 int height_left  = (n->left  == NULL) ? 0 : n->left->height;
 610                 int height_right = (n->right == NULL) ? 0 : n->right->height;
 611
 612                 if (height_left > height_right)
 613                         n = n->left;
 614                 else
 615                         n = n->right;
 616         }
 617
 618         p = n->parent;
 619         if (p == NULL)
 620                 t->root = NULL;
 621         else if (p->left == n)
 622                 p->left = NULL;
 623         else
 624                 p->right = NULL;
 625
 626         *key   = n->key;
 627         *value = n->value;
 628
 629         free_node (n);
 630         rebalance (t, p);
 631
 632         return (0);
 633 } /* int c_avl_pick */
 634
 635 c_avl_iterator_t *c_avl_get_iterator (c_avl_tree_t *t)
 636 {
 637         c_avl_iterator_t *iter;
 638
 639         if (t == NULL)
 640                 return (NULL);
 641
 642         iter = (c_avl_iterator_t *) malloc (sizeof (c_avl_iterator_t));
 643         if (iter == NULL)
 644                 return (NULL);
 645         memset (iter, '\0', sizeof (c_avl_iterator_t));
 646         iter->tree = t;
 647
 648         return (iter);
 649 } /* c_avl_iterator_t *c_avl_get_iterator */
 650
 651 int c_avl_iterator_next (c_avl_iterator_t *iter, void **key, void **value)
 652 {
 653         c_avl_node_t *n;
 654
 655         if ((iter == NULL) || (key == NULL) || (value == NULL))
 656                 return (-1);
 657
 658         if (iter->node == NULL)
 659         {
 660                 for (n = iter->tree->root; n != NULL; n = n->left)
 661                         if (n->left == NULL)
 662                                 break;
 663                 iter->node = n;
 664         }
 665         else
 666         {
 667                 n = c_avl_node_next (iter->node);
 668         }
 669
 670         if (n == NULL)
 671                 return (-1);
 672
 673         iter->node = n;
 674         *key = n->key;
 675         *value = n->value;
 676
 677         return (0);
 678 } /* int c_avl_iterator_next */
 679
 680 int c_avl_iterator_prev (c_avl_iterator_t *iter, void **key, void **value)
 681 {
 682         c_avl_node_t *n;
 683
 684         if ((iter == NULL) || (key == NULL) || (value == NULL))
 685                 return (-1);
 686
 687         if (iter->node == NULL)
 688         {
 689                 for (n = iter->tree->root; n != NULL; n = n->left)
 690                         if (n->right == NULL)
 691                                 break;
 692                 iter->node = n;
 693         }
 694         else
 695         {
 696                 n = c_avl_node_prev (iter->node);
 697         }
 698
 699         if (n == NULL)
 700                 return (-1);
 701
 702         iter->node = n;
 703         *key = n->key;
 704         *value = n->value;
 705
 706         return (0);
 707 } /* int c_avl_iterator_prev */
 708
 709 void c_avl_iterator_destroy (c_avl_iterator_t *iter)
 710 {
 711         free (iter);
 712 }