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 1
  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_left (t, n);
 236                         else
 237                                 n = rotate_right_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                 /* Deleting a leave is easy */
 344                 if (n->parent == NULL)
 345                 {
 346                         assert (t->root == n);
 347                         t->root = NULL;
 348                 }
 349                 else
 350                 {
 351                         assert ((n->parent->left == n)
 352                                         || (n->parent->right == n));
 353                         if (n->parent->left == n)
 354                                 n->parent->left = NULL;
 355                         else
 356                                 n->parent->right = NULL;
 357
 358                         rebalance (t, n->parent);
 359                 }
 360
 361                 free_node (n);
 362         }
 363         else
 364         {
 365                 avl_node_t *r; /* replacement node */
 366                 if (BALANCE (n) > 0)
 367                 {
 368                         assert (n->left != NULL);
 369                         r = avl_node_prev (t, n);
 370                 }
 371                 else
 372                 {
 373                         assert (n->right != NULL);
 374                         r = avl_node_next (t, n);
 375                 }
 376
 377                 /* copy content */
 378                 n->key   = r->key;
 379                 n->value = r->value;
 380
 381                 _remove (t, r);
 382         }
 383
 384         return (0);
 385 } /* void *_remove */
 386
 387 /*
 388  * public functions
 389  */
 390 avl_tree_t *avl_create (int (*compare) (const void *, const void *))
 391 {
 392         avl_tree_t *t;
 393
 394         if ((t = (avl_tree_t *) malloc (sizeof (avl_tree_t))) == NULL)
 395                 return (NULL);
 396
 397         t->root = NULL;
 398         t->compare = compare;
 399
 400         return (t);
 401 }
 402
 403 void avl_destroy (avl_tree_t *t)
 404 {
 405         free_node (t->root);
 406         free (t);
 407 }
 408
 409 int avl_insert (avl_tree_t *t, void *key, void *value)
 410 {
 411         avl_node_t *new;
 412         avl_node_t *nptr;
 413         int cmp;
 414
 415         if ((new = (avl_node_t *) malloc (sizeof (avl_node_t))) == NULL)
 416                 return (-1);
 417
 418         new->key = key;
 419         new->value = value;
 420         new->height = 1;
 421         new->left = NULL;
 422         new->right = NULL;
 423
 424         if (t->root == NULL)
 425         {
 426                 new->parent = NULL;
 427                 t->root = new;
 428                 return (0);
 429         }
 430
 431         nptr = t->root;
 432         while (42)
 433         {
 434                 cmp = t->compare (nptr->key, new->key);
 435                 if (cmp == 0)
 436                 {
 437                         free_node (new);
 438                         return (-1);
 439                 }
 440                 else if (cmp < 0)
 441                 {
 442                         /* nptr < new */
 443                         if (nptr->right == NULL)
 444                         {
 445                                 nptr->right = new;
 446                                 new->parent = nptr;
 447                                 rebalance (t, nptr);
 448                                 break;
 449                         }
 450                         else
 451                         {
 452                                 nptr = nptr->right;
 453                         }
 454                 }
 455                 else /* if (cmp > 0) */
 456                 {
 457                         /* nptr > new */
 458                         if (nptr->left == NULL)
 459                         {
 460                                 nptr->left = new;
 461                                 new->parent = nptr;
 462                                 rebalance (t, nptr);
 463                                 break;
 464                         }
 465                         else
 466                         {
 467                                 nptr = nptr->left;
 468                         }
 469                 }
 470         } /* while (42) */
 471
 472         verify_tree (t->root);
 473         return (0);
 474 } /* int avl_insert */
 475
 476 int avl_remove (avl_tree_t *t, void *key, void **rkey, void **rvalue)
 477 {
 478         avl_node_t *n;
 479         int status;
 480
 481         assert (t != NULL);
 482
 483         n = search (t, key);
 484         if (n == NULL)
 485                 return (-1);
 486
 487         if (rkey != NULL)
 488                 *rkey = n->key;
 489         if (rvalue != NULL)
 490                 *rvalue = n->value;
 491
 492         status = _remove (t, n);
 493         verify_tree (t->root);
 494         return (status);
 495 } /* void *avl_remove */
 496
 497 int avl_get (avl_tree_t *t, const void *key, void **value)
 498 {
 499         avl_node_t *n;
 500
 501         assert (value != NULL);
 502
 503         n = search (t, key);
 504         if (n == NULL)
 505                 return (-1);
 506
 507         *value = n->value;
 508
 509         return (0);
 510 }
 511
 512 avl_iterator_t *avl_get_iterator (avl_tree_t *t)
 513 {
 514         avl_node_t *n;
 515
 516         if (t == NULL)
 517                 return (NULL);
 518
 519         for (n = t->root; n != NULL; n = n->left)
 520                 if (n->left == NULL)
 521                         break;
 522
 523         return (avl_create_iterator (t, n));
 524 } /* avl_iterator_t *avl_get_iterator */
 525
 526 void *avl_iterator_next (avl_iterator_t *iter)
 527 {
 528         avl_node_t *n;
 529
 530         if ((iter == NULL) || (iter->node == NULL))
 531                 return (NULL);
 532
 533         n = avl_node_next (iter->tree, iter->node);
 534
 535         if (n == NULL)
 536                 return (NULL);
 537
 538         iter->node = n;
 539         return (n);
 540
 541 }
 542
 543 void *avl_iterator_prev (avl_iterator_t *iter)
 544 {
 545         avl_node_t *n;
 546
 547         if ((iter == NULL) || (iter->node == NULL))
 548                 return (NULL);
 549
 550         n = avl_node_prev (iter->tree, iter->node);
 551
 552         if (n == NULL)
 553                 return (NULL);
 554
 555         iter->node = n;
 556         return (n);
 557
 558 }
 559
 560 void avl_iterator_destroy (avl_iterator_t *iter)
 561 {
 562         free (iter);
 563 }