src/daemon/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         assert (x != NULL);
 150         assert (x->left != NULL);
 151
 152         p = x->parent;
 153         y = x->left;
 154         b = y->right;
 155
 156         x->left = b;
 157         if (b != NULL)
 158                 b->parent = x;
 159
 160         x->parent = y;
 161         y->right = x;
 162
 163         y->parent = p;
 164         assert ((p == NULL) || (p->left == x) || (p->right == x));
 165         if (p == NULL)
 166                 t->root = y;
 167         else if (p->left == x)
 168                 p->left = y;
 169         else
 170                 p->right = y;
 171
 172         x->height = calc_height (x);
 173         y->height = calc_height (y);
 174
 175         return (y);
 176 } /* void rotate_right */
 177
 178 /*
 179  *    (x)                   (y)
 180  *   /   \                 /   \
 181  *  /\    (y)           (x)    /\
 182  * /_a\  /   \   ==>   /   \  / c\
 183  *      /\   /\       /\   /\/____\
 184  *     /_b\ / c\     /_a\ /_b\
 185  *         /____\
 186  */
 187 static c_avl_node_t *rotate_left (c_avl_tree_t *t, c_avl_node_t *x)
 188 {
 189         c_avl_node_t *p;
 190         c_avl_node_t *y;
 191         c_avl_node_t *b;
 192
 193         assert (x != NULL);
 194         assert (x->right != NULL);
 195
 196         p = x->parent;
 197         y = x->right;
 198         b = y->left;
 199
 200         x->right = b;
 201         if (b != NULL)
 202                 b->parent = x;
 203
 204         x->parent = y;
 205         y->left = x;
 206
 207         y->parent = p;
 208         assert ((p == NULL) || (p->left == x) || (p->right == x));
 209         if (p == NULL)
 210                 t->root = y;
 211         else if (p->left == x)
 212                 p->left = y;
 213         else
 214                 p->right = y;
 215
 216         x->height = calc_height (x);
 217         y->height = calc_height (y);
 218
 219         return (y);
 220 } /* void rotate_left */
 221
 222 static c_avl_node_t *rotate_left_right (c_avl_tree_t *t, c_avl_node_t *x)
 223 {
 224         rotate_left (t, x->left);
 225         return (rotate_right (t, x));
 226 } /* void rotate_left_right */
 227
 228 static c_avl_node_t *rotate_right_left (c_avl_tree_t *t, c_avl_node_t *x)
 229 {
 230         rotate_right (t, x->right);
 231         return (rotate_left (t, x));
 232 } /* void rotate_right_left */
 233
 234 static void rebalance (c_avl_tree_t *t, c_avl_node_t *n)
 235 {
 236         int b_top;
 237         int b_bottom;
 238
 239         while (n != NULL)
 240         {
 241                 b_top = BALANCE (n);
 242                 assert ((b_top >= -2) && (b_top <= 2));
 243
 244                 if (b_top == -2)
 245                 {
 246                         assert (n->right != NULL);
 247                         b_bottom = BALANCE (n->right);
 248                         assert ((b_bottom >= -1) || (b_bottom <= 1));
 249                         if (b_bottom == 1)
 250                                 n = rotate_right_left (t, n);
 251                         else
 252                                 n = rotate_left (t, n);
 253                 }
 254                 else if (b_top == 2)
 255                 {
 256                         assert (n->left != NULL);
 257                         b_bottom = BALANCE (n->left);
 258                         assert ((b_bottom >= -1) || (b_bottom <= 1));
 259                         if (b_bottom == -1)
 260                                 n = rotate_left_right (t, n);
 261                         else
 262                                 n = rotate_right (t, n);
 263                 }
 264                 else
 265                 {
 266                         int height = calc_height (n);
 267                         if (height == n->height)
 268                                 break;
 269                         n->height = height;
 270                 }
 271
 272                 assert (n->height == calc_height (n));
 273
 274                 n = n->parent;
 275         } /* while (n != NULL) */
 276 } /* void rebalance */
 277
 278 static c_avl_node_t *c_avl_node_next (c_avl_node_t *n)
 279 {
 280         c_avl_node_t *r; /* return node */
 281
 282         if (n == NULL)
 283         {
 284                 return (NULL);
 285         }
 286
 287         /* If we can't descent any further, we have to backtrack to the first
 288          * parent that's bigger than we, i. e. who's _left_ child we are. */
 289         if (n->right == NULL)
 290         {
 291                 r = n->parent;
 292                 while ((r != NULL) && (r->parent != NULL))
 293                 {
 294                         if (r->left == n)
 295                                 break;
 296                         n = r;
 297                         r = n->parent;
 298                 }
 299
 300                 /* n->right == NULL && r == NULL => t is root and has no next
 301                  * r->left != n => r->right = n => r->parent == NULL */
 302                 if ((r == NULL) || (r->left != n))
 303                 {
 304                         assert ((r == NULL) || (r->parent == NULL));
 305                         return (NULL);
 306                 }
 307                 else
 308                 {
 309                         assert (r->left == n);
 310                         return (r);
 311                 }
 312         }
 313         else
 314         {
 315                 r = n->right;
 316                 while (r->left != NULL)
 317                         r = r->left;
 318         }
 319
 320         return (r);
 321 } /* c_avl_node_t *c_avl_node_next */
 322
 323 static c_avl_node_t *c_avl_node_prev (c_avl_node_t *n)
 324 {
 325         c_avl_node_t *r; /* return node */
 326
 327         if (n == NULL)
 328         {
 329                 return (NULL);
 330         }
 331
 332         /* If we can't descent any further, we have to backtrack to the first
 333          * parent that's smaller than we, i. e. who's _right_ child we are. */
 334         if (n->left == NULL)
 335         {
 336                 r = n->parent;
 337                 while ((r != NULL) && (r->parent != NULL))
 338                 {
 339                         if (r->right == n)
 340                                 break;
 341                         n = r;
 342                         r = n->parent;
 343                 }
 344
 345                 /* n->left == NULL && r == NULL => t is root and has no next
 346                  * r->right != n => r->left = n => r->parent == NULL */
 347                 if ((r == NULL) || (r->right != n))
 348                 {
 349                         assert ((r == NULL) || (r->parent == NULL));
 350                         return (NULL);
 351                 }
 352                 else
 353                 {
 354                         assert (r->right == n);
 355                         return (r);
 356                 }
 357         }
 358         else
 359         {
 360                 r = n->left;
 361                 while (r->right != NULL)
 362                         r = r->right;
 363         }
 364
 365         return (r);
 366 } /* c_avl_node_t *c_avl_node_prev */
 367
 368 static int _remove (c_avl_tree_t *t, c_avl_node_t *n)
 369 {
 370         assert ((t != NULL) && (n != NULL));
 371
 372         if ((n->left != NULL) && (n->right != NULL))
 373         {
 374                 c_avl_node_t *r; /* replacement node */
 375                 if (BALANCE (n) > 0) /* left subtree is higher */
 376                 {
 377                         assert (n->left != NULL);
 378                         r = c_avl_node_prev (n);
 379
 380                 }
 381                 else /* right subtree is higher */
 382                 {
 383                         assert (n->right != NULL);
 384                         r = c_avl_node_next (n);
 385                 }
 386
 387                 assert ((r->left == NULL) || (r->right == NULL));
 388
 389                 /* copy content */
 390                 n->key   = r->key;
 391                 n->value = r->value;
 392
 393                 n = r;
 394         }
 395
 396         assert ((n->left == NULL) || (n->right == NULL));
 397
 398         if ((n->left == NULL) && (n->right == NULL))
 399         {
 400                 /* Deleting a leave is easy */
 401                 if (n->parent == NULL)
 402                 {
 403                         assert (t->root == n);
 404                         t->root = NULL;
 405                 }
 406                 else
 407                 {
 408                         assert ((n->parent->left == n)
 409                                         || (n->parent->right == n));
 410                         if (n->parent->left == n)
 411                                 n->parent->left = NULL;
 412                         else
 413                                 n->parent->right = NULL;
 414
 415                         rebalance (t, n->parent);
 416                 }
 417
 418                 free_node (n);
 419         }
 420         else if (n->left == NULL)
 421         {
 422                 assert (BALANCE (n) == -1);
 423                 assert ((n->parent == NULL) || (n->parent->left == n) || (n->parent->right == n));
 424                 if (n->parent == NULL)
 425                 {
 426                         assert (t->root == n);
 427                         t->root = n->right;
 428                 }
 429                 else if (n->parent->left == n)
 430                 {
 431                         n->parent->left = n->right;
 432                 }
 433                 else
 434                 {
 435                         n->parent->right = n->right;
 436                 }
 437                 n->right->parent = n->parent;
 438
 439                 if (n->parent != NULL)
 440                         rebalance (t, n->parent);
 441
 442                 n->right = NULL;
 443                 free_node (n);
 444         }
 445         else if (n->right == NULL)
 446         {
 447                 assert (BALANCE (n) == 1);
 448                 assert ((n->parent == NULL) || (n->parent->left == n) || (n->parent->right == n));
 449                 if (n->parent == NULL)
 450                 {
 451                         assert (t->root == n);
 452                         t->root = n->left;
 453                 }
 454                 else if (n->parent->left == n)
 455                 {
 456                         n->parent->left = n->left;
 457                 }
 458                 else
 459                 {
 460                         n->parent->right = n->left;
 461                 }
 462                 n->left->parent = n->parent;
 463
 464                 if (n->parent != NULL)
 465                         rebalance (t, n->parent);
 466
 467                 n->left = NULL;
 468                 free_node (n);
 469         }
 470         else
 471         {
 472                 assert (0);
 473         }
 474
 475         return (0);
 476 } /* void *_remove */
 477
 478 /*
 479  * public functions
 480  */
 481 c_avl_tree_t *c_avl_create (int (*compare) (const void *, const void *))
 482 {
 483         c_avl_tree_t *t;
 484
 485         if (compare == NULL)
 486                 return (NULL);
 487
 488         if ((t = (c_avl_tree_t *) malloc (sizeof (c_avl_tree_t))) == NULL)
 489                 return (NULL);
 490
 491         t->root = NULL;
 492         t->compare = compare;
 493         t->size = 0;
 494
 495         return (t);
 496 }
 497
 498 void c_avl_destroy (c_avl_tree_t *t)
 499 {
 500         if (t == NULL)
 501                 return;
 502         free_node (t->root);
 503         free (t);
 504 }
 505
 506 int c_avl_insert (c_avl_tree_t *t, void *key, void *value)
 507 {
 508         c_avl_node_t *new;
 509         c_avl_node_t *nptr;
 510         int cmp;
 511
 512         if ((new = (c_avl_node_t *) malloc (sizeof (c_avl_node_t))) == NULL)
 513                 return (-1);
 514
 515         new->key = key;
 516         new->value = value;
 517         new->height = 1;
 518         new->left = NULL;
 519         new->right = NULL;
 520
 521         if (t->root == NULL)
 522         {
 523                 new->parent = NULL;
 524                 t->root = new;
 525                 t->size = 1;
 526                 return (0);
 527         }
 528
 529         nptr = t->root;
 530         while (42)
 531         {
 532                 cmp = t->compare (nptr->key, new->key);
 533                 if (cmp == 0)
 534                 {
 535                         free_node (new);
 536                         return (1);
 537                 }
 538                 else if (cmp < 0)
 539                 {
 540                         /* nptr < new */
 541                         if (nptr->right == NULL)
 542                         {
 543                                 nptr->right = new;
 544                                 new->parent = nptr;
 545                                 rebalance (t, nptr);
 546                                 break;
 547                         }
 548                         else
 549                         {
 550                                 nptr = nptr->right;
 551                         }
 552                 }
 553                 else /* if (cmp > 0) */
 554                 {
 555                         /* nptr > new */
 556                         if (nptr->left == NULL)
 557                         {
 558                                 nptr->left = new;
 559                                 new->parent = nptr;
 560                                 rebalance (t, nptr);
 561                                 break;
 562                         }
 563                         else
 564                         {
 565                                 nptr = nptr->left;
 566                         }
 567                 }
 568         } /* while (42) */
 569
 570         verify_tree (t->root);
 571         ++t->size;
 572         return (0);
 573 } /* int c_avl_insert */
 574
 575 int c_avl_remove (c_avl_tree_t *t, const void *key, void **rkey, void **rvalue)
 576 {
 577         c_avl_node_t *n;
 578         int status;
 579
 580         assert (t != NULL);
 581
 582         n = search (t, key);
 583         if (n == NULL)
 584                 return (-1);
 585
 586         if (rkey != NULL)
 587                 *rkey = n->key;
 588         if (rvalue != NULL)
 589                 *rvalue = n->value;
 590
 591         status = _remove (t, n);
 592         verify_tree (t->root);
 593         --t->size;
 594         return (status);
 595 } /* void *c_avl_remove */
 596
 597 int c_avl_get (c_avl_tree_t *t, const void *key, void **value)
 598 {
 599         c_avl_node_t *n;
 600
 601         assert (t != NULL);
 602
 603         n = search (t, key);
 604         if (n == NULL)
 605                 return (-1);
 606
 607         if (value != NULL)
 608                 *value = n->value;
 609
 610         return (0);
 611 }
 612
 613 int c_avl_pick (c_avl_tree_t *t, void **key, void **value)
 614 {
 615         c_avl_node_t *n;
 616         c_avl_node_t *p;
 617
 618         if ((key == NULL) || (value == NULL))
 619                 return (-1);
 620         if (t->root == NULL)
 621                 return (-1);
 622
 623         n = t->root;
 624         while ((n->left != NULL) || (n->right != NULL))
 625         {
 626                 if (n->left == NULL)
 627                 {
 628                         n = n->right;
 629                         continue;
 630                 }
 631                 else if (n->right == NULL)
 632                 {
 633                         n = n->left;
 634                         continue;
 635                 }
 636
 637                 if (n->left->height > n->right->height)
 638                         n = n->left;
 639                 else
 640                         n = n->right;
 641         }
 642
 643         p = n->parent;
 644         if (p == NULL)
 645                 t->root = NULL;
 646         else if (p->left == n)
 647                 p->left = NULL;
 648         else
 649                 p->right = NULL;
 650
 651         *key   = n->key;
 652         *value = n->value;
 653
 654         free_node (n);
 655         --t->size;
 656         rebalance (t, p);
 657
 658         return (0);
 659 } /* int c_avl_pick */
 660
 661 c_avl_iterator_t *c_avl_get_iterator (c_avl_tree_t *t)
 662 {
 663         c_avl_iterator_t *iter;
 664
 665         if (t == NULL)
 666                 return (NULL);
 667
 668         iter = (c_avl_iterator_t *) malloc (sizeof (c_avl_iterator_t));
 669         if (iter == NULL)
 670                 return (NULL);
 671         memset (iter, '\0', sizeof (c_avl_iterator_t));
 672         iter->tree = t;
 673
 674         return (iter);
 675 } /* c_avl_iterator_t *c_avl_get_iterator */
 676
 677 int c_avl_iterator_next (c_avl_iterator_t *iter, void **key, void **value)
 678 {
 679         c_avl_node_t *n;
 680
 681         if ((iter == NULL) || (key == NULL) || (value == NULL))
 682                 return (-1);
 683
 684         if (iter->node == NULL)
 685         {
 686                 for (n = iter->tree->root; n != NULL; n = n->left)
 687                         if (n->left == NULL)
 688                                 break;
 689                 iter->node = n;
 690         }
 691         else
 692         {
 693                 n = c_avl_node_next (iter->node);
 694         }
 695
 696         if (n == NULL)
 697                 return (-1);
 698
 699         iter->node = n;
 700         *key = n->key;
 701         *value = n->value;
 702
 703         return (0);
 704 } /* int c_avl_iterator_next */
 705
 706 int c_avl_iterator_prev (c_avl_iterator_t *iter, void **key, void **value)
 707 {
 708         c_avl_node_t *n;
 709
 710         if ((iter == NULL) || (key == NULL) || (value == NULL))
 711                 return (-1);
 712
 713         if (iter->node == NULL)
 714         {
 715                 for (n = iter->tree->root; n != NULL; n = n->left)
 716                         if (n->right == NULL)
 717                                 break;
 718                 iter->node = n;
 719         }
 720         else
 721         {
 722                 n = c_avl_node_prev (iter->node);
 723         }
 724
 725         if (n == NULL)
 726                 return (-1);
 727
 728         iter->node = n;
 729         *key = n->key;
 730         *value = n->value;
 731
 732         return (0);
 733 } /* int c_avl_iterator_prev */
 734
 735 void c_avl_iterator_destroy (c_avl_iterator_t *iter)
 736 {
 737         free (iter);
 738 }
 739
 740 int c_avl_size (c_avl_tree_t *t)
 741 {
 742         if (t == NULL)
 743                 return (0);
 744         return (t->size);
 745 }