contrib/unbound/util/rbtree.c

   1 /*
   2  * rbtree.c -- generic red black tree
   3  *
   4  * Copyright (c) 2001-2007, NLnet Labs. All rights reserved.
   5  *
   6  * This software is open source.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  *
  12  * Redistributions of source code must retain the above copyright notice,
  13  * this list of conditions and the following disclaimer.
  14  *
  15  * Redistributions in binary form must reproduce the above copyright notice,
  16  * this list of conditions and the following disclaimer in the documentation
  17  * and/or other materials provided with the distribution.
  18  *
  19  * Neither the name of the NLNET LABS nor the names of its contributors may
  20  * be used to endorse or promote products derived from this software without
  21  * specific prior written permission.
  22  *
  23  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  24  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  25  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  26  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  27  * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  28  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
  29  * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  30  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
  31  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
  32  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  33  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  34  *
  35  */
  36
  37 /**
  38  * \file
  39  * Implementation of a redblack tree.
  40  */
  41
  42 #include "config.h"
  43 #include "log.h"
  44 #include "fptr_wlist.h"
  45 #include "util/rbtree.h"
  46
  47 /** Node colour black */
  48 #define BLACK   0
  49 /** Node colour red */
  50 #define RED     1
  51
  52 /** the NULL node, global alloc */
  53 rbnode_type     rbtree_null_node = {
  54         RBTREE_NULL,            /* Parent.  */
  55         RBTREE_NULL,            /* Left.  */
  56         RBTREE_NULL,            /* Right.  */
  57         NULL,                   /* Key.  */
  58         BLACK                   /* Color.  */
  59 };
  60
  61 /** rotate subtree left (to preserve redblack property) */
  62 static void rbtree_rotate_left(rbtree_type *rbtree, rbnode_type *node);
  63 /** rotate subtree right (to preserve redblack property) */
  64 static void rbtree_rotate_right(rbtree_type *rbtree, rbnode_type *node);
  65 /** Fixup node colours when insert happened */
  66 static void rbtree_insert_fixup(rbtree_type *rbtree, rbnode_type *node);
  67 /** Fixup node colours when delete happened */
  68 static void rbtree_delete_fixup(rbtree_type* rbtree, rbnode_type* child,
  69         rbnode_type* child_parent);
  70
  71 /*
  72  * Creates a new red black tree, initializes and returns a pointer to it.
  73  *
  74  * Return NULL on failure.
  75  *
  76  */
  77 rbtree_type *
  78 rbtree_create (int (*cmpf)(const void *, const void *))
  79 {
  80         rbtree_type *rbtree;
  81
  82         /* Allocate memory for it */
  83         rbtree = (rbtree_type *) malloc(sizeof(rbtree_type));
  84         if (!rbtree) {
  85                 return NULL;
  86         }
  87
  88         /* Initialize it */
  89         rbtree_init(rbtree, cmpf);
  90
  91         return rbtree;
  92 }
  93
  94 void
  95 rbtree_init(rbtree_type *rbtree, int (*cmpf)(const void *, const void *))
  96 {
  97         /* Initialize it */
  98         rbtree->root = RBTREE_NULL;
  99         rbtree->count = 0;
 100         rbtree->cmp = cmpf;
 101 }
 102
 103 /*
 104  * Rotates the node to the left.
 105  *
 106  */
 107 static void
 108 rbtree_rotate_left(rbtree_type *rbtree, rbnode_type *node)
 109 {
 110         rbnode_type *right = node->right;
 111         node->right = right->left;
 112         if (right->left != RBTREE_NULL)
 113                 right->left->parent = node;
 114
 115         right->parent = node->parent;
 116
 117         if (node->parent != RBTREE_NULL) {
 118                 if (node == node->parent->left) {
 119                         node->parent->left = right;
 120                 } else  {
 121                         node->parent->right = right;
 122                 }
 123         } else {
 124                 rbtree->root = right;
 125         }
 126         right->left = node;
 127         node->parent = right;
 128 }
 129
 130 /*
 131  * Rotates the node to the right.
 132  *
 133  */
 134 static void
 135 rbtree_rotate_right(rbtree_type *rbtree, rbnode_type *node)
 136 {
 137         rbnode_type *left = node->left;
 138         node->left = left->right;
 139         if (left->right != RBTREE_NULL)
 140                 left->right->parent = node;
 141
 142         left->parent = node->parent;
 143
 144         if (node->parent != RBTREE_NULL) {
 145                 if (node == node->parent->right) {
 146                         node->parent->right = left;
 147                 } else  {
 148                         node->parent->left = left;
 149                 }
 150         } else {
 151                 rbtree->root = left;
 152         }
 153         left->right = node;
 154         node->parent = left;
 155 }
 156
 157 static void
 158 rbtree_insert_fixup(rbtree_type *rbtree, rbnode_type *node)
 159 {
 160         rbnode_type     *uncle;
 161
 162         /* While not at the root and need fixing... */
 163         while (node != rbtree->root && node->parent->color == RED) {
 164                 /* If our parent is left child of our grandparent... */
 165                 if (node->parent == node->parent->parent->left) {
 166                         uncle = node->parent->parent->right;
 167
 168                         /* If our uncle is red... */
 169                         if (uncle->color == RED) {
 170                                 /* Paint the parent and the uncle black... */
 171                                 node->parent->color = BLACK;
 172                                 uncle->color = BLACK;
 173
 174                                 /* And the grandparent red... */
 175                                 node->parent->parent->color = RED;
 176
 177                                 /* And continue fixing the grandparent */
 178                                 node = node->parent->parent;
 179                         } else {                                /* Our uncle is black... */
 180                                 /* Are we the right child? */
 181                                 if (node == node->parent->right) {
 182                                         node = node->parent;
 183                                         rbtree_rotate_left(rbtree, node);
 184                                 }
 185                                 /* Now we're the left child, repaint and rotate... */
 186                                 node->parent->color = BLACK;
 187                                 node->parent->parent->color = RED;
 188                                 rbtree_rotate_right(rbtree, node->parent->parent);
 189                         }
 190                 } else {
 191                         uncle = node->parent->parent->left;
 192
 193                         /* If our uncle is red... */
 194                         if (uncle->color == RED) {
 195                                 /* Paint the parent and the uncle black... */
 196                                 node->parent->color = BLACK;
 197                                 uncle->color = BLACK;
 198
 199                                 /* And the grandparent red... */
 200                                 node->parent->parent->color = RED;
 201
 202                                 /* And continue fixing the grandparent */
 203                                 node = node->parent->parent;
 204                         } else {                                /* Our uncle is black... */
 205                                 /* Are we the right child? */
 206                                 if (node == node->parent->left) {
 207                                         node = node->parent;
 208                                         rbtree_rotate_right(rbtree, node);
 209                                 }
 210                                 /* Now we're the right child, repaint and rotate... */
 211                                 node->parent->color = BLACK;
 212                                 node->parent->parent->color = RED;
 213                                 rbtree_rotate_left(rbtree, node->parent->parent);
 214                         }
 215                 }
 216         }
 217         rbtree->root->color = BLACK;
 218 }
 219
 220
 221 /*
 222  * Inserts a node into a red black tree.
 223  *
 224  * Returns NULL on failure or the pointer to the newly added node
 225  * otherwise.
 226  */
 227 rbnode_type *
 228 rbtree_insert (rbtree_type *rbtree, rbnode_type *data)
 229 {
 230         /* XXX Not necessary, but keeps compiler quiet... */
 231         int r = 0;
 232
 233         /* We start at the root of the tree */
 234         rbnode_type     *node = rbtree->root;
 235         rbnode_type     *parent = RBTREE_NULL;
 236
 237         fptr_ok(fptr_whitelist_rbtree_cmp(rbtree->cmp));
 238         /* Lets find the new parent... */
 239         while (node != RBTREE_NULL) {
 240                 /* Compare two keys, do we have a duplicate? */
 241                 if ((r = rbtree->cmp(data->key, node->key)) == 0) {
 242                         return NULL;
 243                 }
 244                 parent = node;
 245
 246                 if (r < 0) {
 247                         node = node->left;
 248                 } else {
 249                         node = node->right;
 250                 }
 251         }
 252
 253         /* Initialize the new node */
 254         data->parent = parent;
 255         data->left = data->right = RBTREE_NULL;
 256         data->color = RED;
 257         rbtree->count++;
 258
 259         /* Insert it into the tree... */
 260         if (parent != RBTREE_NULL) {
 261                 if (r < 0) {
 262                         parent->left = data;
 263                 } else {
 264                         parent->right = data;
 265                 }
 266         } else {
 267                 rbtree->root = data;
 268         }
 269
 270         /* Fix up the red-black properties... */
 271         rbtree_insert_fixup(rbtree, data);
 272
 273         return data;
 274 }
 275
 276 /*
 277  * Searches the red black tree, returns the data if key is found or NULL otherwise.
 278  *
 279  */
 280 rbnode_type *
 281 rbtree_search (rbtree_type *rbtree, const void *key)
 282 {
 283         rbnode_type *node;
 284
 285         if (rbtree_find_less_equal(rbtree, key, &node)) {
 286                 return node;
 287         } else {
 288                 return NULL;
 289         }
 290 }
 291
 292 /** helpers for delete: swap node colours */
 293 static void swap_int8(uint8_t* x, uint8_t* y)
 294 {
 295         uint8_t t = *x; *x = *y; *y = t;
 296 }
 297
 298 /** helpers for delete: swap node pointers */
 299 static void swap_np(rbnode_type** x, rbnode_type** y)
 300 {
 301         rbnode_type* t = *x; *x = *y; *y = t;
 302 }
 303
 304 /** Update parent pointers of child trees of 'parent' */
 305 static void change_parent_ptr(rbtree_type* rbtree, rbnode_type* parent,
 306         rbnode_type* old, rbnode_type* new)
 307 {
 308         if(parent == RBTREE_NULL)
 309         {
 310                 log_assert(rbtree->root == old);
 311                 if(rbtree->root == old) rbtree->root = new;
 312                 return;
 313         }
 314         log_assert(parent->left == old || parent->right == old
 315                 || parent->left == new || parent->right == new);
 316         if(parent->left == old) parent->left = new;
 317         if(parent->right == old) parent->right = new;
 318 }
 319 /** Update parent pointer of a node 'child' */
 320 static void change_child_ptr(rbnode_type* child, rbnode_type* old,
 321         rbnode_type* new)
 322 {
 323         if(child == RBTREE_NULL) return;
 324         log_assert(child->parent == old || child->parent == new);
 325         if(child->parent == old) child->parent = new;
 326 }
 327
 328 rbnode_type*
 329 rbtree_delete(rbtree_type *rbtree, const void *key)
 330 {
 331         rbnode_type *to_delete;
 332         rbnode_type *child;
 333         if((to_delete = rbtree_search(rbtree, key)) == 0) return 0;
 334         rbtree->count--;
 335
 336         /* make sure we have at most one non-leaf child */
 337         if(to_delete->left != RBTREE_NULL && to_delete->right != RBTREE_NULL)
 338         {
 339                 /* swap with smallest from right subtree (or largest from left) */
 340                 rbnode_type *smright = to_delete->right;
 341                 while(smright->left != RBTREE_NULL)
 342                         smright = smright->left;
 343                 /* swap the smright and to_delete elements in the tree,
 344                  * but the rbnode_type is first part of user data struct
 345                  * so cannot just swap the keys and data pointers. Instead
 346                  * readjust the pointers left,right,parent */
 347
 348                 /* swap colors - colors are tied to the position in the tree */
 349                 swap_int8(&to_delete->color, &smright->color);
 350
 351                 /* swap child pointers in parents of smright/to_delete */
 352                 change_parent_ptr(rbtree, to_delete->parent, to_delete, smright);
 353                 if(to_delete->right != smright)
 354                         change_parent_ptr(rbtree, smright->parent, smright, to_delete);
 355
 356                 /* swap parent pointers in children of smright/to_delete */
 357                 change_child_ptr(smright->left, smright, to_delete);
 358                 change_child_ptr(smright->left, smright, to_delete);
 359                 change_child_ptr(smright->right, smright, to_delete);
 360                 change_child_ptr(smright->right, smright, to_delete);
 361                 change_child_ptr(to_delete->left, to_delete, smright);
 362                 if(to_delete->right != smright)
 363                         change_child_ptr(to_delete->right, to_delete, smright);
 364                 if(to_delete->right == smright)
 365                 {
 366                         /* set up so after swap they work */
 367                         to_delete->right = to_delete;
 368                         smright->parent = smright;
 369                 }
 370
 371                 /* swap pointers in to_delete/smright nodes */
 372                 swap_np(&to_delete->parent, &smright->parent);
 373                 swap_np(&to_delete->left, &smright->left);
 374                 swap_np(&to_delete->right, &smright->right);
 375
 376                 /* now delete to_delete (which is at the location where the smright previously was) */
 377         }
 378         log_assert(to_delete->left == RBTREE_NULL || to_delete->right == RBTREE_NULL);
 379
 380         if(to_delete->left != RBTREE_NULL) child = to_delete->left;
 381         else child = to_delete->right;
 382
 383         /* unlink to_delete from the tree, replace to_delete with child */
 384         change_parent_ptr(rbtree, to_delete->parent, to_delete, child);
 385         change_child_ptr(child, to_delete, to_delete->parent);
 386
 387         if(to_delete->color == RED)
 388         {
 389                 /* if node is red then the child (black) can be swapped in */
 390         }
 391         else if(child->color == RED)
 392         {
 393                 /* change child to BLACK, removing a RED node is no problem */
 394                 if(child!=RBTREE_NULL) child->color = BLACK;
 395         }
 396         else rbtree_delete_fixup(rbtree, child, to_delete->parent);
 397
 398         /* unlink completely */
 399         to_delete->parent = RBTREE_NULL;
 400         to_delete->left = RBTREE_NULL;
 401         to_delete->right = RBTREE_NULL;
 402         to_delete->color = BLACK;
 403         return to_delete;
 404 }
 405
 406 static void rbtree_delete_fixup(rbtree_type* rbtree, rbnode_type* child,
 407         rbnode_type* child_parent)
 408 {
 409         rbnode_type* sibling;
 410         int go_up = 1;
 411
 412         /* determine sibling to the node that is one-black short */
 413         if(child_parent->right == child) sibling = child_parent->left;
 414         else sibling = child_parent->right;
 415
 416         while(go_up)
 417         {
 418                 if(child_parent == RBTREE_NULL)
 419                 {
 420                         /* removed parent==black from root, every path, so ok */
 421                         return;
 422                 }
 423
 424                 if(sibling->color == RED)
 425                 {       /* rotate to get a black sibling */
 426                         child_parent->color = RED;
 427                         sibling->color = BLACK;
 428                         if(child_parent->right == child)
 429                                 rbtree_rotate_right(rbtree, child_parent);
 430                         else    rbtree_rotate_left(rbtree, child_parent);
 431                         /* new sibling after rotation */
 432                         if(child_parent->right == child) sibling = child_parent->left;
 433                         else sibling = child_parent->right;
 434                 }
 435
 436                 if(child_parent->color == BLACK
 437                         && sibling->color == BLACK
 438                         && sibling->left->color == BLACK
 439                         && sibling->right->color == BLACK)
 440                 {       /* fixup local with recolor of sibling */
 441                         if(sibling != RBTREE_NULL)
 442                                 sibling->color = RED;
 443
 444                         child = child_parent;
 445                         child_parent = child_parent->parent;
 446                         /* prepare to go up, new sibling */
 447                         if(child_parent->right == child) sibling = child_parent->left;
 448                         else sibling = child_parent->right;
 449                 }
 450                 else go_up = 0;
 451         }
 452
 453         if(child_parent->color == RED
 454                 && sibling->color == BLACK
 455                 && sibling->left->color == BLACK
 456                 && sibling->right->color == BLACK)
 457         {
 458                 /* move red to sibling to rebalance */
 459                 if(sibling != RBTREE_NULL)
 460                         sibling->color = RED;
 461                 child_parent->color = BLACK;
 462                 return;
 463         }
 464         log_assert(sibling != RBTREE_NULL);
 465
 466         /* get a new sibling, by rotating at sibling. See which child
 467            of sibling is red */
 468         if(child_parent->right == child
 469                 && sibling->color == BLACK
 470                 && sibling->right->color == RED
 471                 && sibling->left->color == BLACK)
 472         {
 473                 sibling->color = RED;
 474                 sibling->right->color = BLACK;
 475                 rbtree_rotate_left(rbtree, sibling);
 476                 /* new sibling after rotation */
 477                 if(child_parent->right == child) sibling = child_parent->left;
 478                 else sibling = child_parent->right;
 479         }
 480         else if(child_parent->left == child
 481                 && sibling->color == BLACK
 482                 && sibling->left->color == RED
 483                 && sibling->right->color == BLACK)
 484         {
 485                 sibling->color = RED;
 486                 sibling->left->color = BLACK;
 487                 rbtree_rotate_right(rbtree, sibling);
 488                 /* new sibling after rotation */
 489                 if(child_parent->right == child) sibling = child_parent->left;
 490                 else sibling = child_parent->right;
 491         }
 492
 493         /* now we have a black sibling with a red child. rotate and exchange colors. */
 494         sibling->color = child_parent->color;
 495         child_parent->color = BLACK;
 496         if(child_parent->right == child)
 497         {
 498                 log_assert(sibling->left->color == RED);
 499                 sibling->left->color = BLACK;
 500                 rbtree_rotate_right(rbtree, child_parent);
 501         }
 502         else
 503         {
 504                 log_assert(sibling->right->color == RED);
 505                 sibling->right->color = BLACK;
 506                 rbtree_rotate_left(rbtree, child_parent);
 507         }
 508 }
 509
 510 int
 511 rbtree_find_less_equal(rbtree_type *rbtree, const void *key,
 512         rbnode_type **result)
 513 {
 514         int r;
 515         rbnode_type *node;
 516
 517         log_assert(result);
 518
 519         /* We start at root... */
 520         node = rbtree->root;
 521
 522         *result = NULL;
 523         fptr_ok(fptr_whitelist_rbtree_cmp(rbtree->cmp));
 524
 525         /* While there are children... */
 526         while (node != RBTREE_NULL) {
 527                 r = rbtree->cmp(key, node->key);
 528                 if (r == 0) {
 529                         /* Exact match */
 530                         *result = node;
 531                         return 1;
 532                 }
 533                 if (r < 0) {
 534                         node = node->left;
 535                 } else {
 536                         /* Temporary match */
 537                         *result = node;
 538                         node = node->right;
 539                 }
 540         }
 541         return 0;
 542 }
 543
 544 /*
 545  * Finds the first element in the red black tree
 546  *
 547  */
 548 rbnode_type *
 549 rbtree_first (rbtree_type *rbtree)
 550 {
 551         rbnode_type *node;
 552
 553         for (node = rbtree->root; node->left != RBTREE_NULL; node = node->left);
 554         return node;
 555 }
 556
 557 rbnode_type *
 558 rbtree_last (rbtree_type *rbtree)
 559 {
 560         rbnode_type *node;
 561
 562         for (node = rbtree->root; node->right != RBTREE_NULL; node = node->right);
 563         return node;
 564 }
 565
 566 /*
 567  * Returns the next node...
 568  *
 569  */
 570 rbnode_type *
 571 rbtree_next (rbnode_type *node)
 572 {
 573         rbnode_type *parent;
 574
 575         if (node->right != RBTREE_NULL) {
 576                 /* One right, then keep on going left... */
 577                 for (node = node->right; node->left != RBTREE_NULL; node = node->left);
 578         } else {
 579                 parent = node->parent;
 580                 while (parent != RBTREE_NULL && node == parent->right) {
 581                         node = parent;
 582                         parent = parent->parent;
 583                 }
 584                 node = parent;
 585         }
 586         return node;
 587 }
 588
 589 rbnode_type *
 590 rbtree_previous(rbnode_type *node)
 591 {
 592         rbnode_type *parent;
 593
 594         if (node->left != RBTREE_NULL) {
 595                 /* One left, then keep on going right... */
 596                 for (node = node->left; node->right != RBTREE_NULL; node = node->right);
 597         } else {
 598                 parent = node->parent;
 599                 while (parent != RBTREE_NULL && node == parent->left) {
 600                         node = parent;
 601                         parent = parent->parent;
 602                 }
 603                 node = parent;
 604         }
 605         return node;
 606 }
 607
 608 /** recursive descent traverse */
 609 static void
 610 traverse_post(void (*func)(rbnode_type*, void*), void* arg, rbnode_type* node)
 611 {
 612         if(!node || node == RBTREE_NULL)
 613                 return;
 614         /* recurse */
 615         traverse_post(func, arg, node->left);
 616         traverse_post(func, arg, node->right);
 617         /* call user func */
 618         (*func)(node, arg);
 619 }
 620
 621 void
 622 traverse_postorder(rbtree_type* tree, void (*func)(rbnode_type*, void*),
 623         void* arg)
 624 {
 625         traverse_post(func, arg, tree->root);
 626 }