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