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