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