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 <stdlib.h>
00047 
00049 #define BLACK   0
00050 
00051 #define RED     1
00052 
00054 ldns_rbnode_t   ldns_rbtree_null_node = {
00055         LDNS_RBTREE_NULL,       /* Parent.  */
00056         LDNS_RBTREE_NULL,       /* Left.  */
00057         LDNS_RBTREE_NULL,       /* Right.  */
00058         NULL,                   /* Key.  */
00059         NULL,               /* Data. */
00060         BLACK                /* Color.  */
00061 };
00062 
00064 static void ldns_rbtree_rotate_left(ldns_rbtree_t *rbtree, ldns_rbnode_t *node);
00066 static void ldns_rbtree_rotate_right(ldns_rbtree_t *rbtree, ldns_rbnode_t *node);
00068 static void ldns_rbtree_insert_fixup(ldns_rbtree_t *rbtree, ldns_rbnode_t *node);
00070 static void ldns_rbtree_delete_fixup(ldns_rbtree_t* rbtree, ldns_rbnode_t* child, ldns_rbnode_t* child_parent);
00071 
00072 /*
00073  * Creates a new red black tree, intializes and returns a pointer to it.
00074  *
00075  * Return NULL on failure.
00076  *
00077  */
00078 ldns_rbtree_t *
00079 ldns_rbtree_create (int (*cmpf)(const void *, const void *))
00080 {
00081         ldns_rbtree_t *rbtree;
00082 
00083         /* Allocate memory for it */
00084         rbtree = (ldns_rbtree_t *) malloc(sizeof(ldns_rbtree_t));
00085         if (!rbtree) {
00086                 return NULL;
00087         }
00088 
00089         /* Initialize it */
00090         ldns_rbtree_init(rbtree, cmpf);
00091 
00092         return rbtree;
00093 }
00094 
00095 void 
00096 ldns_rbtree_init(ldns_rbtree_t *rbtree, int (*cmpf)(const void *, const void *))
00097 {
00098         /* Initialize it */
00099         rbtree->root = LDNS_RBTREE_NULL;
00100         rbtree->count = 0;
00101         rbtree->cmp = cmpf;
00102 }
00103 
00104 void 
00105 ldns_rbtree_free(ldns_rbtree_t *rbtree)
00106 {
00107         free(rbtree);
00108 }
00109 
00110 /*
00111  * Rotates the node to the left.
00112  *
00113  */
00114 static void
00115 ldns_rbtree_rotate_left(ldns_rbtree_t *rbtree, ldns_rbnode_t *node)
00116 {
00117         ldns_rbnode_t *right = node->right;
00118         node->right = right->left;
00119         if (right->left != LDNS_RBTREE_NULL)
00120                 right->left->parent = node;
00121 
00122         right->parent = node->parent;
00123 
00124         if (node->parent != LDNS_RBTREE_NULL) {
00125                 if (node == node->parent->left) {
00126                         node->parent->left = right;
00127                 } else  {
00128                         node->parent->right = right;
00129                 }
00130         } else {
00131                 rbtree->root = right;
00132         }
00133         right->left = node;
00134         node->parent = right;
00135 }
00136 
00137 /*
00138  * Rotates the node to the right.
00139  *
00140  */
00141 static void
00142 ldns_rbtree_rotate_right(ldns_rbtree_t *rbtree, ldns_rbnode_t *node)
00143 {
00144         ldns_rbnode_t *left = node->left;
00145         node->left = left->right;
00146         if (left->right != LDNS_RBTREE_NULL)
00147                 left->right->parent = node;
00148 
00149         left->parent = node->parent;
00150 
00151         if (node->parent != LDNS_RBTREE_NULL) {
00152                 if (node == node->parent->right) {
00153                         node->parent->right = left;
00154                 } else  {
00155                         node->parent->left = left;
00156                 }
00157         } else {
00158                 rbtree->root = left;
00159         }
00160         left->right = node;
00161         node->parent = left;
00162 }
00163 
00164 static void
00165 ldns_rbtree_insert_fixup(ldns_rbtree_t *rbtree, ldns_rbnode_t *node)
00166 {
00167         ldns_rbnode_t   *uncle;
00168 
00169         /* While not at the root and need fixing... */
00170         while (node != rbtree->root && node->parent->color == RED) {
00171                 /* If our parent is left child of our grandparent... */
00172                 if (node->parent == node->parent->parent->left) {
00173                         uncle = node->parent->parent->right;
00174 
00175                         /* If our uncle is red... */
00176                         if (uncle->color == RED) {
00177                                 /* Paint the parent and the uncle black... */
00178                                 node->parent->color = BLACK;
00179                                 uncle->color = BLACK;
00180 
00181                                 /* And the grandparent red... */
00182                                 node->parent->parent->color = RED;
00183 
00184                                 /* And continue fixing the grandparent */
00185                                 node = node->parent->parent;
00186                         } else {                                /* Our uncle is black... */
00187                                 /* Are we the right child? */
00188                                 if (node == node->parent->right) {
00189                                         node = node->parent;
00190                                         ldns_rbtree_rotate_left(rbtree, node);
00191                                 }
00192                                 /* Now we're the left child, repaint and rotate... */
00193                                 node->parent->color = BLACK;
00194                                 node->parent->parent->color = RED;
00195                                 ldns_rbtree_rotate_right(rbtree, node->parent->parent);
00196                         }
00197                 } else {
00198                         uncle = node->parent->parent->left;
00199 
00200                         /* If our uncle is red... */
00201                         if (uncle->color == RED) {
00202                                 /* Paint the parent and the uncle black... */
00203                                 node->parent->color = BLACK;
00204                                 uncle->color = BLACK;
00205 
00206                                 /* And the grandparent red... */
00207                                 node->parent->parent->color = RED;
00208 
00209                                 /* And continue fixing the grandparent */
00210                                 node = node->parent->parent;
00211                         } else {                                /* Our uncle is black... */
00212                                 /* Are we the right child? */
00213                                 if (node == node->parent->left) {
00214                                         node = node->parent;
00215                                         ldns_rbtree_rotate_right(rbtree, node);
00216                                 }
00217                                 /* Now we're the right child, repaint and rotate... */
00218                                 node->parent->color = BLACK;
00219                                 node->parent->parent->color = RED;
00220                                 ldns_rbtree_rotate_left(rbtree, node->parent->parent);
00221                         }
00222                 }
00223         }
00224         rbtree->root->color = BLACK;
00225 }
00226 
00227 void
00228 ldns_rbtree_insert_vref(ldns_rbnode_t *data, void *rbtree)
00229 {
00230         (void) ldns_rbtree_insert((ldns_rbtree_t *) rbtree,
00231                                                  data);
00232 }
00233 
00234 /*
00235  * Inserts a node into a red black tree.
00236  *
00237  * Returns NULL on failure or the pointer to the newly added node
00238  * otherwise.
00239  */
00240 ldns_rbnode_t *
00241 ldns_rbtree_insert (ldns_rbtree_t *rbtree, ldns_rbnode_t *data)
00242 {
00243         /* XXX Not necessary, but keeps compiler quiet... */
00244         int r = 0;
00245 
00246         /* We start at the root of the tree */
00247         ldns_rbnode_t   *node = rbtree->root;
00248         ldns_rbnode_t   *parent = LDNS_RBTREE_NULL;
00249 
00250         /* Lets find the new parent... */
00251         while (node != LDNS_RBTREE_NULL) {
00252                 /* Compare two keys, do we have a duplicate? */
00253                 if ((r = rbtree->cmp(data->key, node->key)) == 0) {
00254                         return NULL;
00255                 }
00256                 parent = node;
00257 
00258                 if (r < 0) {
00259                         node = node->left;
00260                 } else {
00261                         node = node->right;
00262                 }
00263         }
00264 
00265         /* Initialize the new node */
00266         data->parent = parent;
00267         data->left = data->right = LDNS_RBTREE_NULL;
00268         data->color = RED;
00269         rbtree->count++;
00270 
00271         /* Insert it into the tree... */
00272         if (parent != LDNS_RBTREE_NULL) {
00273                 if (r < 0) {
00274                         parent->left = data;
00275                 } else {
00276                         parent->right = data;
00277                 }
00278         } else {
00279                 rbtree->root = data;
00280         }
00281 
00282         /* Fix up the red-black properties... */
00283         ldns_rbtree_insert_fixup(rbtree, data);
00284 
00285         return data;
00286 }
00287 
00288 /*
00289  * Searches the red black tree, returns the data if key is found or NULL otherwise.
00290  *
00291  */
00292 ldns_rbnode_t *
00293 ldns_rbtree_search (ldns_rbtree_t *rbtree, const void *key)
00294 {
00295         ldns_rbnode_t *node;
00296 
00297         if (ldns_rbtree_find_less_equal(rbtree, key, &node)) {
00298                 return node;
00299         } else {
00300                 return NULL;
00301         }
00302 }
00303 
00305 static void swap_int8(uint8_t* x, uint8_t* y) 
00306 { 
00307         uint8_t t = *x; *x = *y; *y = t; 
00308 }
00309 
00311 static void swap_np(ldns_rbnode_t** x, ldns_rbnode_t** y) 
00312 {
00313         ldns_rbnode_t* t = *x; *x = *y; *y = t; 
00314 }
00315 
00317 static void change_parent_ptr(ldns_rbtree_t* rbtree, ldns_rbnode_t* parent, ldns_rbnode_t* old, ldns_rbnode_t* new)
00318 {
00319         if(parent == LDNS_RBTREE_NULL)
00320         {
00321                 if(rbtree->root == old) rbtree->root = new;
00322                 return;
00323         }
00324         if(parent->left == old) parent->left = new;
00325         if(parent->right == old) parent->right = new;
00326 }
00328 static void change_child_ptr(ldns_rbnode_t* child, ldns_rbnode_t* old, ldns_rbnode_t* new)
00329 {
00330         if(child == LDNS_RBTREE_NULL) return;
00331         if(child->parent == old) child->parent = new;
00332 }
00333 
00334 ldns_rbnode_t* 
00335 ldns_rbtree_delete(ldns_rbtree_t *rbtree, const void *key)
00336 {
00337         ldns_rbnode_t *to_delete;
00338         ldns_rbnode_t *child;
00339         if((to_delete = ldns_rbtree_search(rbtree, key)) == 0) return 0;
00340         rbtree->count--;
00341 
00342         /* make sure we have at most one non-leaf child */
00343         if(to_delete->left != LDNS_RBTREE_NULL &&
00344            to_delete->right != LDNS_RBTREE_NULL)
00345         {
00346                 /* swap with smallest from right subtree (or largest from left) */
00347                 ldns_rbnode_t *smright = to_delete->right;
00348                 while(smright->left != LDNS_RBTREE_NULL)
00349                         smright = smright->left;
00350                 /* swap the smright and to_delete elements in the tree,
00351                  * but the ldns_rbnode_t is first part of user data struct
00352                  * so cannot just swap the keys and data pointers. Instead
00353                  * readjust the pointers left,right,parent */
00354 
00355                 /* swap colors - colors are tied to the position in the tree */
00356                 swap_int8(&to_delete->color, &smright->color);
00357 
00358                 /* swap child pointers in parents of smright/to_delete */
00359                 change_parent_ptr(rbtree, to_delete->parent, to_delete, smright);
00360                 if(to_delete->right != smright)
00361                         change_parent_ptr(rbtree, smright->parent, smright, to_delete);
00362 
00363                 /* swap parent pointers in children of smright/to_delete */
00364                 change_child_ptr(smright->left, smright, to_delete);
00365                 change_child_ptr(smright->left, smright, to_delete);
00366                 change_child_ptr(smright->right, smright, to_delete);
00367                 change_child_ptr(smright->right, smright, to_delete);
00368                 change_child_ptr(to_delete->left, to_delete, smright);
00369                 if(to_delete->right != smright)
00370                         change_child_ptr(to_delete->right, to_delete, smright);
00371                 if(to_delete->right == smright)
00372                 {
00373                         /* set up so after swap they work */
00374                         to_delete->right = to_delete;
00375                         smright->parent = smright;
00376                 }
00377 
00378                 /* swap pointers in to_delete/smright nodes */
00379                 swap_np(&to_delete->parent, &smright->parent);
00380                 swap_np(&to_delete->left, &smright->left);
00381                 swap_np(&to_delete->right, &smright->right);
00382 
00383                 /* now delete to_delete (which is at the location where the smright previously was) */
00384         }
00385 
00386         if(to_delete->left != LDNS_RBTREE_NULL) child = to_delete->left;
00387         else child = to_delete->right;
00388 
00389         /* unlink to_delete from the tree, replace to_delete with child */
00390         change_parent_ptr(rbtree, to_delete->parent, to_delete, child);
00391         change_child_ptr(child, to_delete, to_delete->parent);
00392 
00393         if(to_delete->color == RED)
00394         {
00395                 /* if node is red then the child (black) can be swapped in */
00396         }
00397         else if(child->color == RED)
00398         {
00399                 /* change child to BLACK, removing a RED node is no problem */
00400                 if(child!=LDNS_RBTREE_NULL) child->color = BLACK;
00401         }
00402         else ldns_rbtree_delete_fixup(rbtree, child, to_delete->parent);
00403 
00404         /* unlink completely */
00405         to_delete->parent = LDNS_RBTREE_NULL;
00406         to_delete->left = LDNS_RBTREE_NULL;
00407         to_delete->right = LDNS_RBTREE_NULL;
00408         to_delete->color = BLACK;
00409         return to_delete;
00410 }
00411 
00412 static void ldns_rbtree_delete_fixup(ldns_rbtree_t* rbtree, ldns_rbnode_t* child, ldns_rbnode_t* child_parent)
00413 {
00414         ldns_rbnode_t* sibling;
00415         int go_up = 1;
00416 
00417         /* determine sibling to the node that is one-black short */
00418         if(child_parent->right == child) sibling = child_parent->left;
00419         else sibling = child_parent->right;
00420 
00421         while(go_up)
00422         {
00423                 if(child_parent == LDNS_RBTREE_NULL)
00424                 {
00425                         /* removed parent==black from root, every path, so ok */
00426                         return;
00427                 }
00428 
00429                 if(sibling->color == RED)
00430                 {       /* rotate to get a black sibling */
00431                         child_parent->color = RED;
00432                         sibling->color = BLACK;
00433                         if(child_parent->right == child)
00434                                 ldns_rbtree_rotate_right(rbtree, child_parent);
00435                         else    ldns_rbtree_rotate_left(rbtree, child_parent);
00436                         /* new sibling after rotation */
00437                         if(child_parent->right == child) sibling = child_parent->left;
00438                         else sibling = child_parent->right;
00439                 }
00440 
00441                 if(child_parent->color == BLACK 
00442                         && sibling->color == BLACK
00443                         && sibling->left->color == BLACK
00444                         && sibling->right->color == BLACK)
00445                 {       /* fixup local with recolor of sibling */
00446                         if(sibling != LDNS_RBTREE_NULL)
00447                                 sibling->color = RED;
00448 
00449                         child = child_parent;
00450                         child_parent = child_parent->parent;
00451                         /* prepare to go up, new sibling */
00452                         if(child_parent->right == child) sibling = child_parent->left;
00453                         else sibling = child_parent->right;
00454                 }
00455                 else go_up = 0;
00456         }
00457 
00458         if(child_parent->color == RED
00459                 && sibling->color == BLACK
00460                 && sibling->left->color == BLACK
00461                 && sibling->right->color == BLACK) 
00462         {
00463                 /* move red to sibling to rebalance */
00464                 if(sibling != LDNS_RBTREE_NULL)
00465                         sibling->color = RED;
00466                 child_parent->color = BLACK;
00467                 return;
00468         }
00469 
00470         /* get a new sibling, by rotating at sibling. See which child
00471            of sibling is red */
00472         if(child_parent->right == child
00473                 && sibling->color == BLACK
00474                 && sibling->right->color == RED
00475                 && sibling->left->color == BLACK)
00476         {
00477                 sibling->color = RED;
00478                 sibling->right->color = BLACK;
00479                 ldns_rbtree_rotate_left(rbtree, sibling);
00480                 /* new sibling after rotation */
00481                 if(child_parent->right == child) sibling = child_parent->left;
00482                 else sibling = child_parent->right;
00483         }
00484         else if(child_parent->left == child
00485                 && sibling->color == BLACK
00486                 && sibling->left->color == RED
00487                 && sibling->right->color == BLACK)
00488         {
00489                 sibling->color = RED;
00490                 sibling->left->color = BLACK;
00491                 ldns_rbtree_rotate_right(rbtree, sibling);
00492                 /* new sibling after rotation */
00493                 if(child_parent->right == child) sibling = child_parent->left;
00494                 else sibling = child_parent->right;
00495         }
00496 
00497         /* now we have a black sibling with a red child. rotate and exchange colors. */
00498         sibling->color = child_parent->color;
00499         child_parent->color = BLACK;
00500         if(child_parent->right == child)
00501         {
00502                 sibling->left->color = BLACK;
00503                 ldns_rbtree_rotate_right(rbtree, child_parent);
00504         }
00505         else
00506         {
00507                 sibling->right->color = BLACK;
00508                 ldns_rbtree_rotate_left(rbtree, child_parent);
00509         }
00510 }
00511 
00512 int
00513 ldns_rbtree_find_less_equal(ldns_rbtree_t *rbtree, const void *key, ldns_rbnode_t **result)
00514 {
00515         int r;
00516         ldns_rbnode_t *node;
00517 
00518         /* We start at root... */
00519         node = rbtree->root;
00520 
00521         *result = NULL;
00522 
00523         /* While there are children... */
00524         while (node != LDNS_RBTREE_NULL) {
00525                 r = rbtree->cmp(key, node->key);
00526                 if (r == 0) {
00527                         /* Exact match */
00528                         *result = node;
00529                         return 1;
00530                 } 
00531                 if (r < 0) {
00532                         node = node->left;
00533                 } else {
00534                         /* Temporary match */
00535                         *result = node;
00536                         node = node->right;
00537                 }
00538         }
00539         return 0;
00540 }
00541 
00542 /*
00543  * Finds the first element in the red black tree
00544  *
00545  */
00546 ldns_rbnode_t *
00547 ldns_rbtree_first (ldns_rbtree_t *rbtree)
00548 {
00549         ldns_rbnode_t *node = rbtree->root;
00550 
00551         if (rbtree->root != LDNS_RBTREE_NULL) {
00552                 for (node = rbtree->root; node->left != LDNS_RBTREE_NULL; node = node->left);
00553         }
00554         return node;
00555 }
00556 
00557 ldns_rbnode_t *
00558 ldns_rbtree_last (ldns_rbtree_t *rbtree)
00559 {
00560         ldns_rbnode_t *node = rbtree->root;
00561 
00562         if (rbtree->root != LDNS_RBTREE_NULL) {
00563                 for (node = rbtree->root; node->right != LDNS_RBTREE_NULL; node = node->right);
00564         }
00565         return node;
00566 }
00567 
00568 /*
00569  * Returns the next node...
00570  *
00571  */
00572 ldns_rbnode_t *
00573 ldns_rbtree_next (ldns_rbnode_t *node)
00574 {
00575         ldns_rbnode_t *parent;
00576 
00577         if (node->right != LDNS_RBTREE_NULL) {
00578                 /* One right, then keep on going left... */
00579                 for (node = node->right;
00580                         node->left != LDNS_RBTREE_NULL;
00581                         node = node->left);
00582         } else {
00583                 parent = node->parent;
00584                 while (parent != LDNS_RBTREE_NULL && node == parent->right) {
00585                         node = parent;
00586                         parent = parent->parent;
00587                 }
00588                 node = parent;
00589         }
00590         return node;
00591 }
00592 
00593 ldns_rbnode_t *
00594 ldns_rbtree_previous(ldns_rbnode_t *node)
00595 {
00596         ldns_rbnode_t *parent;
00597 
00598         if (node->left != LDNS_RBTREE_NULL) {
00599                 /* One left, then keep on going right... */
00600                 for (node = node->left;
00601                         node->right != LDNS_RBTREE_NULL;
00602                         node = node->right);
00603         } else {
00604                 parent = node->parent;
00605                 while (parent != LDNS_RBTREE_NULL && node == parent->left) {
00606                         node = parent;
00607                         parent = parent->parent;
00608                 }
00609                 node = parent;
00610         }
00611         return node;
00612 }
00613 
00618 ldns_rbtree_t *
00619 ldns_rbtree_split(ldns_rbtree_t *tree,
00620                            size_t elements)
00621 {
00622         ldns_rbtree_t *new_tree;
00623         ldns_rbnode_t *cur_node;
00624         ldns_rbnode_t *move_node;
00625         size_t count = 0;
00626 
00627         new_tree = ldns_rbtree_create(tree->cmp);
00628 
00629         cur_node = ldns_rbtree_first(tree);
00630         while (count < elements && cur_node != LDNS_RBTREE_NULL) {
00631                 move_node = ldns_rbtree_delete(tree, cur_node->key);
00632                 (void)ldns_rbtree_insert(new_tree, move_node);
00633                 cur_node = ldns_rbtree_first(tree);
00634                 count++;
00635         }
00636 
00637         return new_tree;
00638 }
00639 
00640 /*
00641  * add all node from the second tree to the first (removing them from the
00642  * second), and fix up nsec(3)s if present
00643  */
00644 void
00645 ldns_rbtree_join(ldns_rbtree_t *tree1, ldns_rbtree_t *tree2)
00646 {
00647         ldns_traverse_postorder(tree2, ldns_rbtree_insert_vref, tree1);
00648 }
00649 
00651 static void 
00652 traverse_post(void (*func)(ldns_rbnode_t*, void*), void* arg, 
00653         ldns_rbnode_t* node)
00654 {
00655         if(!node || node == LDNS_RBTREE_NULL)
00656                 return;
00657         /* recurse */
00658         traverse_post(func, arg, node->left);
00659         traverse_post(func, arg, node->right);
00660         /* call user func */
00661         (*func)(node, arg);
00662 }
00663 
00664 void 
00665 ldns_traverse_postorder(ldns_rbtree_t* tree, 
00666         void (*func)(ldns_rbnode_t*, void*), void* arg)
00667 {
00668         traverse_post(func, arg, tree->root);
00669 }