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