src/utils_avltree.c

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