rbtree.c

Go to the documentation of this file.
00001 /*
00002  * rbtree.c -- generic red black tree
00003  *
00004  * Taken from Unbound, modified for ldns
00005  *
00006  * Copyright (c) 2001-2008, NLnet Labs. All rights reserved.
00007  * 
00008  * This software is open source.
00009  * 
00010  * Redistribution and use in source and binary forms, with or without
00011  * modification, are permitted provided that the following conditions
00012  * are met:
00013  * 
00014  * Redistributions of source code must retain the above copyright notice,
00015  * this list of conditions and the following disclaimer.
00016  * 
00017  * Redistributions in binary form must reproduce the above copyright notice,
00018  * this list of conditions and the following disclaimer in the documentation
00019  * and/or other materials provided with the distribution.
00020  * 
00021  * Neither the name of the NLNET LABS nor the names of its contributors may
00022  * be used to endorse or promote products derived from this software without
00023  * specific prior written permission.
00024  * 
00025  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
00026  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
00027  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
00028  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE
00029  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
00030  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
00031  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
00032  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
00033  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
00034  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
00035  * POSSIBILITY OF SUCH DAMAGE.
00036  *
00037  */
00038 
00044 #include <ldns/config.h>
00045 #include <ldns/rbtree.h>
00046 #include <ldns/util.h>
00047 #include <stdlib.h>
00048 
00050 #define BLACK   0
00051 
00052 #define RED     1
00053 
00055 ldns_rbnode_t   ldns_rbtree_null_node = {
00056         LDNS_RBTREE_NULL,       /* Parent.  */
00057         LDNS_RBTREE_NULL,       /* Left.  */
00058         LDNS_RBTREE_NULL,       /* Right.  */
00059         NULL,                   /* Key.  */
00060         NULL,               /* Data. */
00061         BLACK                /* Color.  */
00062 };
00063 
00065 static void ldns_rbtree_rotate_left(ldns_rbtree_t *rbtree, ldns_rbnode_t *node);
00067 static void ldns_rbtree_rotate_right(ldns_rbtree_t *rbtree, ldns_rbnode_t *node);
00069 static void ldns_rbtree_insert_fixup(ldns_rbtree_t *rbtree, ldns_rbnode_t *node);
00071 static void ldns_rbtree_delete_fixup(ldns_rbtree_t* rbtree, ldns_rbnode_t* child, ldns_rbnode_t* child_parent);
00072 
00073 /*
00074  * Creates a new red black tree, intializes and returns a pointer to it.
00075  *
00076  * Return NULL on failure.
00077  *
00078  */
00079 ldns_rbtree_t *
00080 ldns_rbtree_create (int (*cmpf)(const void *, const void *))
00081 {
00082         ldns_rbtree_t *rbtree;
00083 
00084         /* Allocate memory for it */
00085         rbtree = (ldns_rbtree_t *) LDNS_MALLOC(ldns_rbtree_t);
00086         if (!rbtree) {
00087                 return NULL;
00088         }
00089 
00090         /* Initialize it */
00091         ldns_rbtree_init(rbtree, cmpf);
00092 
00093         return rbtree;
00094 }
00095 
00096 void 
00097 ldns_rbtree_init(ldns_rbtree_t *rbtree, int (*cmpf)(const void *, const void *))
00098 {
00099         /* Initialize it */
00100         rbtree->root = LDNS_RBTREE_NULL;
00101         rbtree->count = 0;
00102         rbtree->cmp = cmpf;
00103 }
00104 
00105 void 
00106 ldns_rbtree_free(ldns_rbtree_t *rbtree)
00107 {
00108         LDNS_FREE(rbtree);
00109 }
00110 
00111 /*
00112  * Rotates the node to the left.
00113  *
00114  */
00115 static void
00116 ldns_rbtree_rotate_left(ldns_rbtree_t *rbtree, ldns_rbnode_t *node)
00117 {
00118         ldns_rbnode_t *right = node->right;
00119         node->right = right->left;
00120         if (right->left != LDNS_RBTREE_NULL)
00121                 right->left->parent = node;
00122 
00123         right->parent = node->parent;
00124 
00125         if (node->parent != LDNS_RBTREE_NULL) {
00126                 if (node == node->parent->left) {
00127                         node->parent->left = right;
00128                 } else  {
00129                         node->parent->right = right;
00130                 }
00131         } else {
00132                 rbtree->root = right;
00133         }
00134         right->left = node;
00135         node->parent = right;
00136 }
00137 
00138 /*
00139  * Rotates the node to the right.
00140  *
00141  */
00142 static void
00143 ldns_rbtree_rotate_right(ldns_rbtree_t *rbtree, ldns_rbnode_t *node)
00144 {
00145         ldns_rbnode_t *left = node->left;
00146         node->left = left->right;
00147         if (left->right != LDNS_RBTREE_NULL)
00148                 left->right->parent = node;
00149 
00150         left->parent = node->parent;
00151 
00152         if (node->parent != LDNS_RBTREE_NULL) {
00153                 if (node == node->parent->right) {
00154                         node->parent->right = left;
00155                 } else  {
00156                         node->parent->left = left;
00157                 }
00158         } else {
00159                 rbtree->root = left;
00160         }
00161         left->right = node;
00162         node->parent = left;
00163 }
00164 
00165 static void
00166 ldns_rbtree_insert_fixup(ldns_rbtree_t *rbtree, ldns_rbnode_t *node)
00167 {
00168         ldns_rbnode_t   *uncle;
00169 
00170         /* While not at the root and need fixing... */
00171         while (node != rbtree->root && node->parent->color == RED) {
00172                 /* If our parent is left child of our grandparent... */
00173                 if (node->parent == node->parent->parent->left) {
00174                         uncle = node->parent->parent->right;
00175 
00176                         /* If our uncle is red... */
00177                         if (uncle->color == RED) {
00178                                 /* Paint the parent and the uncle black... */
00179                                 node->parent->color = BLACK;
00180                                 uncle->color = BLACK;
00181 
00182                                 /* And the grandparent red... */
00183                                 node->parent->parent->color = RED;
00184 
00185                                 /* And continue fixing the grandparent */
00186                                 node = node->parent->parent;
00187                         } else {                                /* Our uncle is black... */
00188                                 /* Are we the right child? */
00189                                 if (node == node->parent->right) {
00190                                         node = node->parent;
00191                                         ldns_rbtree_rotate_left(rbtree, node);
00192                                 }
00193                                 /* Now we're the left child, repaint and rotate... */
00194                                 node->parent->color = BLACK;
00195                                 node->parent->parent->color = RED;
00196                                 ldns_rbtree_rotate_right(rbtree, node->parent->parent);
00197                         }
00198                 } else {
00199                         uncle = node->parent->parent->left;
00200 
00201                         /* If our uncle is red... */
00202                         if (uncle->color == RED) {
00203                                 /* Paint the parent and the uncle black... */
00204                                 node->parent->color = BLACK;
00205                                 uncle->color = BLACK;
00206 
00207                                 /* And the grandparent red... */
00208                                 node->parent->parent->color = RED;
00209 
00210                                 /* And continue fixing the grandparent */
00211                                 node = node->parent->parent;
00212                         } else {                                /* Our uncle is black... */
00213                                 /* Are we the right child? */
00214                                 if (node == node->parent->left) {
00215                                         node = node->parent;
00216                                         ldns_rbtree_rotate_right(rbtree, node);
00217                                 }
00218                                 /* Now we're the right child, repaint and rotate... */
00219                                 node->parent->color = BLACK;
00220                                 node->parent->parent->color = RED;
00221                                 ldns_rbtree_rotate_left(rbtree, node->parent->parent);
00222                         }
00223                 }
00224         }
00225         rbtree->root->color = BLACK;
00226 }
00227 
00228 void
00229 ldns_rbtree_insert_vref(ldns_rbnode_t *data, void *rbtree)
00230 {
00231         (void) ldns_rbtree_insert((ldns_rbtree_t *) rbtree,
00232                                                  data);
00233 }
00234 
00235 /*
00236  * Inserts a node into a red black tree.
00237  *
00238  * Returns NULL on failure or the pointer to the newly added node
00239  * otherwise.
00240  */
00241 ldns_rbnode_t *
00242 ldns_rbtree_insert (ldns_rbtree_t *rbtree, ldns_rbnode_t *data)
00243 {
00244         /* XXX Not necessary, but keeps compiler quiet... */
00245         int r = 0;
00246 
00247         /* We start at the root of the tree */
00248         ldns_rbnode_t   *node = rbtree->root;
00249         ldns_rbnode_t   *parent = LDNS_RBTREE_NULL;
00250 
00251         /* Lets find the new parent... */
00252         while (node != LDNS_RBTREE_NULL) {
00253                 /* Compare two keys, do we have a duplicate? */
00254                 if ((r = rbtree->cmp(data->key, node->key)) == 0) {
00255                         return NULL;
00256                 }
00257                 parent = node;
00258 
00259                 if (r < 0) {
00260                         node = node->left;
00261                 } else {
00262                         node = node->right;
00263                 }
00264         }
00265 
00266         /* Initialize the new node */
00267         data->parent = parent;
00268         data->left = data->right = LDNS_RBTREE_NULL;
00269         data->color = RED;
00270         rbtree->count++;
00271 
00272         /* Insert it into the tree... */
00273         if (parent != LDNS_RBTREE_NULL) {
00274                 if (r < 0) {
00275                         parent->left = data;
00276                 } else {
00277                         parent->right = data;
00278                 }
00279         } else {
00280                 rbtree->root = data;
00281         }
00282 
00283         /* Fix up the red-black properties... */
00284         ldns_rbtree_insert_fixup(rbtree, data);
00285 
00286         return data;
00287 }
00288 
00289 /*
00290  * Searches the red black tree, returns the data if key is found or NULL otherwise.
00291  *
00292  */
00293 ldns_rbnode_t *
00294 ldns_rbtree_search (ldns_rbtree_t *rbtree, const void *key)
00295 {
00296         ldns_rbnode_t *node;
00297 
00298         if (ldns_rbtree_find_less_equal(rbtree, key, &node)) {
00299                 return node;
00300         } else {
00301                 return NULL;
00302         }
00303 }
00304 
00306 static void swap_int8(uint8_t* x, uint8_t* y) 
00307 { 
00308         uint8_t t = *x; *x = *y; *y = t; 
00309 }
00310 
00312 static void swap_np(ldns_rbnode_t** x, ldns_rbnode_t** y) 
00313 {
00314         ldns_rbnode_t* t = *x; *x = *y; *y = t; 
00315 }
00316 
00318 static void change_parent_ptr(ldns_rbtree_t* rbtree, ldns_rbnode_t* parent, ldns_rbnode_t* old, ldns_rbnode_t* new)
00319 {
00320         if(parent == LDNS_RBTREE_NULL)
00321         {
00322                 if(rbtree->root == old) rbtree->root = new;
00323                 return;
00324         }
00325         if(parent->left == old) parent->left = new;
00326         if(parent->right == old) parent->right = new;
00327 }
00329 static void change_child_ptr(ldns_rbnode_t* child, ldns_rbnode_t* old, ldns_rbnode_t* new)
00330 {
00331         if(child == LDNS_RBTREE_NULL) return;
00332         if(child->parent == old) child->parent = new;
00333 }
00334 
00335 ldns_rbnode_t* 
00336 ldns_rbtree_delete(ldns_rbtree_t *rbtree, const void *key)
00337 {
00338         ldns_rbnode_t *to_delete;
00339         ldns_rbnode_t *child;
00340         if((to_delete = ldns_rbtree_search(rbtree, key)) == 0) return 0;
00341         rbtree->count--;
00342 
00343         /* make sure we have at most one non-leaf child */
00344         if(to_delete->left != LDNS_RBTREE_NULL &&
00345            to_delete->right != LDNS_RBTREE_NULL)
00346         {
00347                 /* swap with smallest from right subtree (or largest from left) */
00348                 ldns_rbnode_t *smright = to_delete->right;
00349                 while(smright->left != LDNS_RBTREE_NULL)
00350                         smright = smright->left;
00351                 /* swap the smright and to_delete elements in the tree,
00352                  * but the ldns_rbnode_t is first part of user data struct
00353                  * so cannot just swap the keys and data pointers. Instead
00354                  * readjust the pointers left,right,parent */
00355 
00356                 /* swap colors - colors are tied to the position in the tree */
00357                 swap_int8(&to_delete->color, &smright->color);
00358 
00359                 /* swap child pointers in parents of smright/to_delete */
00360                 change_parent_ptr(rbtree, to_delete->parent, to_delete, smright);
00361                 if(to_delete->right != smright)
00362                         change_parent_ptr(rbtree, smright->parent, smright, to_delete);
00363 
00364                 /* swap parent pointers in children of smright/to_delete */
00365                 change_child_ptr(smright->left, smright, to_delete);
00366                 change_child_ptr(smright->left, smright, to_delete);
00367                 change_child_ptr(smright->right, smright, to_delete);
00368                 change_child_ptr(smright->right, smright, to_delete);
00369                 change_child_ptr(to_delete->left, to_delete, smright);
00370                 if(to_delete->right != smright)
00371                         change_child_ptr(to_delete->right, to_delete, smright);
00372                 if(to_delete->right == smright)
00373                 {
00374                         /* set up so after swap they work */
00375                         to_delete->right = to_delete;
00376                         smright->parent = smright;
00377                 }
00378 
00379                 /* swap pointers in to_delete/smright nodes */
00380                 swap_np(&to_delete->parent, &smright->parent);
00381                 swap_np(&to_delete->left, &smright->left);
00382                 swap_np(&to_delete->right, &smright->right);
00383 
00384                 /* now delete to_delete (which is at the location where the smright previously was) */
00385         }
00386 
00387         if(to_delete->left != LDNS_RBTREE_NULL) child = to_delete->left;
00388         else child = to_delete->right;
00389 
00390         /* unlink to_delete from the tree, replace to_delete with child */
00391         change_parent_ptr(rbtree, to_delete->parent, to_delete, child);
00392         change_child_ptr(child, to_delete, to_delete->parent);
00393 
00394         if(to_delete->color == RED)
00395         {
00396                 /* if node is red then the child (black) can be swapped in */
00397         }
00398         else if(child->color == RED)
00399         {
00400                 /* change child to BLACK, removing a RED node is no problem */
00401                 if(child!=LDNS_RBTREE_NULL) child->color = BLACK;
00402         }
00403         else ldns_rbtree_delete_fixup(rbtree, child, to_delete->parent);
00404 
00405         /* unlink completely */
00406         to_delete->parent = LDNS_RBTREE_NULL;
00407         to_delete->left = LDNS_RBTREE_NULL;
00408         to_delete->right = LDNS_RBTREE_NULL;
00409         to_delete->color = BLACK;
00410         return to_delete;
00411 }
00412 
00413 static void ldns_rbtree_delete_fixup(ldns_rbtree_t* rbtree, ldns_rbnode_t* child, ldns_rbnode_t* child_parent)
00414 {
00415         ldns_rbnode_t* sibling;
00416         int go_up = 1;
00417 
00418         /* determine sibling to the node that is one-black short */
00419         if(child_parent->right == child) sibling = child_parent->left;
00420         else sibling = child_parent->right;
00421 
00422         while(go_up)
00423         {
00424                 if(child_parent == LDNS_RBTREE_NULL)
00425                 {
00426                         /* removed parent==black from root, every path, so ok */
00427                         return;
00428                 }
00429 
00430                 if(sibling->color == RED)
00431                 {       /* rotate to get a black sibling */
00432                         child_parent->color = RED;
00433                         sibling->color = BLACK;
00434                         if(child_parent->right == child)
00435                                 ldns_rbtree_rotate_right(rbtree, child_parent);
00436                         else    ldns_rbtree_rotate_left(rbtree, child_parent);
00437                         /* new sibling after rotation */
00438                         if(child_parent->right == child) sibling = child_parent->left;
00439                         else sibling = child_parent->right;
00440                 }
00441 
00442                 if(child_parent->color == BLACK 
00443                         && sibling->color == BLACK
00444                         && sibling->left->color == BLACK
00445                         && sibling->right->color == BLACK)
00446                 {       /* fixup local with recolor of sibling */
00447                         if(sibling != LDNS_RBTREE_NULL)
00448                                 sibling->color = RED;
00449 
00450                         child = child_parent;
00451                         child_parent = child_parent->parent;
00452                         /* prepare to go up, new sibling */
00453                         if(child_parent->right == child) sibling = child_parent->left;
00454                         else sibling = child_parent->right;
00455                 }
00456                 else go_up = 0;
00457         }
00458 
00459         if(child_parent->color == RED
00460                 && sibling->color == BLACK
00461                 && sibling->left->color == BLACK
00462                 && sibling->right->color == BLACK) 
00463         {
00464                 /* move red to sibling to rebalance */
00465                 if(sibling != LDNS_RBTREE_NULL)
00466                         sibling->color = RED;
00467                 child_parent->color = BLACK;
00468                 return;
00469         }
00470 
00471         /* get a new sibling, by rotating at sibling. See which child
00472            of sibling is red */
00473         if(child_parent->right == child
00474                 && sibling->color == BLACK
00475                 && sibling->right->color == RED
00476                 && sibling->left->color == BLACK)
00477         {
00478                 sibling->color = RED;
00479                 sibling->right->color = BLACK;
00480                 ldns_rbtree_rotate_left(rbtree, sibling);
00481                 /* new sibling after rotation */
00482                 if(child_parent->right == child) sibling = child_parent->left;
00483                 else sibling = child_parent->right;
00484         }
00485         else if(child_parent->left == child
00486                 && sibling->color == BLACK
00487                 && sibling->left->color == RED
00488                 && sibling->right->color == BLACK)
00489         {
00490                 sibling->color = RED;
00491                 sibling->left->color = BLACK;
00492                 ldns_rbtree_rotate_right(rbtree, sibling);
00493                 /* new sibling after rotation */
00494                 if(child_parent->right == child) sibling = child_parent->left;
00495                 else sibling = child_parent->right;
00496         }
00497 
00498         /* now we have a black sibling with a red child. rotate and exchange colors. */
00499         sibling->color = child_parent->color;
00500         child_parent->color = BLACK;
00501         if(child_parent->right == child)
00502         {
00503                 sibling->left->color = BLACK;
00504                 ldns_rbtree_rotate_right(rbtree, child_parent);
00505         }
00506         else
00507         {
00508                 sibling->right->color = BLACK;
00509                 ldns_rbtree_rotate_left(rbtree, child_parent);
00510         }
00511 }
00512 
00513 int
00514 ldns_rbtree_find_less_equal(ldns_rbtree_t *rbtree, const void *key, ldns_rbnode_t **result)
00515 {
00516         int r;
00517         ldns_rbnode_t *node;
00518 
00519         /* We start at root... */
00520         node = rbtree->root;
00521 
00522         *result = NULL;
00523 
00524         /* While there are children... */
00525         while (node != LDNS_RBTREE_NULL) {
00526                 r = rbtree->cmp(key, node->key);
00527                 if (r == 0) {
00528                         /* Exact match */
00529                         *result = node;
00530                         return 1;
00531                 } 
00532                 if (r < 0) {
00533                         node = node->left;
00534                 } else {
00535                         /* Temporary match */
00536                         *result = node;
00537                         node = node->right;
00538                 }
00539         }
00540         return 0;
00541 }
00542 
00543 /*
00544  * Finds the first element in the red black tree
00545  *
00546  */
00547 ldns_rbnode_t *
00548 ldns_rbtree_first (ldns_rbtree_t *rbtree)
00549 {
00550         ldns_rbnode_t *node = rbtree->root;
00551 
00552         if (rbtree->root != LDNS_RBTREE_NULL) {
00553                 for (node = rbtree->root; node->left != LDNS_RBTREE_NULL; node = node->left);
00554         }
00555         return node;
00556 }
00557 
00558 ldns_rbnode_t *
00559 ldns_rbtree_last (ldns_rbtree_t *rbtree)
00560 {
00561         ldns_rbnode_t *node = rbtree->root;
00562 
00563         if (rbtree->root != LDNS_RBTREE_NULL) {
00564                 for (node = rbtree->root; node->right != LDNS_RBTREE_NULL; node = node->right);
00565         }
00566         return node;
00567 }
00568 
00569 /*
00570  * Returns the next node...
00571  *
00572  */
00573 ldns_rbnode_t *
00574 ldns_rbtree_next (ldns_rbnode_t *node)
00575 {
00576         ldns_rbnode_t *parent;
00577 
00578         if (node->right != LDNS_RBTREE_NULL) {
00579                 /* One right, then keep on going left... */
00580                 for (node = node->right;
00581                         node->left != LDNS_RBTREE_NULL;
00582                         node = node->left);
00583         } else {
00584                 parent = node->parent;
00585                 while (parent != LDNS_RBTREE_NULL && node == parent->right) {
00586                         node = parent;
00587                         parent = parent->parent;
00588                 }
00589                 node = parent;
00590         }
00591         return node;
00592 }
00593 
00594 ldns_rbnode_t *
00595 ldns_rbtree_previous(ldns_rbnode_t *node)
00596 {
00597         ldns_rbnode_t *parent;
00598 
00599         if (node->left != LDNS_RBTREE_NULL) {
00600                 /* One left, then keep on going right... */
00601                 for (node = node->left;
00602                         node->right != LDNS_RBTREE_NULL;
00603                         node = node->right);
00604         } else {
00605                 parent = node->parent;
00606                 while (parent != LDNS_RBTREE_NULL && node == parent->left) {
00607                         node = parent;
00608                         parent = parent->parent;
00609                 }
00610                 node = parent;
00611         }
00612         return node;
00613 }
00614 
00619 ldns_rbtree_t *
00620 ldns_rbtree_split(ldns_rbtree_t *tree,
00621                            size_t elements)
00622 {
00623         ldns_rbtree_t *new_tree;
00624         ldns_rbnode_t *cur_node;
00625         ldns_rbnode_t *move_node;
00626         size_t count = 0;
00627 
00628         new_tree = ldns_rbtree_create(tree->cmp);
00629 
00630         cur_node = ldns_rbtree_first(tree);
00631         while (count < elements && cur_node != LDNS_RBTREE_NULL) {
00632                 move_node = ldns_rbtree_delete(tree, cur_node->key);
00633                 (void)ldns_rbtree_insert(new_tree, move_node);
00634                 cur_node = ldns_rbtree_first(tree);
00635                 count++;
00636         }
00637 
00638         return new_tree;
00639 }
00640 
00641 /*
00642  * add all node from the second tree to the first (removing them from the
00643  * second), and fix up nsec(3)s if present
00644  */
00645 void
00646 ldns_rbtree_join(ldns_rbtree_t *tree1, ldns_rbtree_t *tree2)
00647 {
00648         ldns_traverse_postorder(tree2, ldns_rbtree_insert_vref, tree1);
00649 }
00650 
00652 static void 
00653 traverse_post(void (*func)(ldns_rbnode_t*, void*), void* arg, 
00654         ldns_rbnode_t* node)
00655 {
00656         if(!node || node == LDNS_RBTREE_NULL)
00657                 return;
00658         /* recurse */
00659         traverse_post(func, arg, node->left);
00660         traverse_post(func, arg, node->right);
00661         /* call user func */
00662         (*func)(node, arg);
00663 }
00664 
00665 void 
00666 ldns_traverse_postorder(ldns_rbtree_t* tree, 
00667         void (*func)(ldns_rbnode_t*, void*), void* arg)
00668 {
00669         traverse_post(func, arg, tree->root);
00670 }

Generated on Wed Dec 19 16:56:42 2012 for ldns by  doxygen 1.4.7