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