git.gag.com Git - debian/sudo/blob - redblack.c

   1 /*
   2  * Copyright (c) 2004-2005, 2007,2009 Todd C. Miller <Todd.Miller@courtesan.com>
   3  *
   4  * Permission to use, copy, modify, and distribute this software for any
   5  * purpose with or without fee is hereby granted, provided that the above
   6  * copyright notice and this permission notice appear in all copies.
   7  *
   8  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
   9  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  10  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  11  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  12  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  13  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  14  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  15  */
  16
  17 /*
  18  * Adapted from the following code written by Emin Martinian:
  19  * http://web.mit.edu/~emin/www/source_code/red_black_tree/index.html
  20  *
  21  * Copyright (c) 2001 Emin Martinian
  22  *
  23  * Redistribution and use in source and binary forms, with or without
  24  * modification, are permitted provided that neither the name of Emin
  25  * Martinian nor the names of any contributors are be used to endorse or
  26  * promote products derived from this software without specific prior
  27  * written permission.
  28  *
  29  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  30  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  31  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  32  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  33  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  34  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  35  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  36  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  37  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  38  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  39  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  40  */
  41
  42 #include <config.h>
  43
  44 #include <sys/types.h>
  45 #include <sys/param.h>
  46
  47 #include <stdio.h>
  48 #ifdef STDC_HEADERS
  49 # include <stdlib.h>
  50 # include <stddef.h>
  51 #else
  52 # ifdef HAVE_STDLIB_H
  53 #  include <stdlib.h>
  54 # endif
  55 #endif /* STDC_HEADERS */
  56
  57 #include "sudo.h"
  58 #include "redblack.h"
  59
  60 #ifndef lint
  61 __unused static const char rcsid[] = "$Sudo: redblack.c,v 1.12 2009/06/29 13:36:20 millert Exp $";
  62 #endif /* lint */
  63
  64 static void rbrepair            __P((struct rbtree *, struct rbnode *));
  65 static void rotate_left         __P((struct rbtree *, struct rbnode *));
  66 static void rotate_right        __P((struct rbtree *, struct rbnode *));
  67 static void _rbdestroy          __P((struct rbtree *, struct rbnode *,
  68                                     void (*)(void *)));
  69
  70 /*
  71  * Red-Black tree, see http://en.wikipedia.org/wiki/Red-black_tree
  72  *
  73  * A red-black tree is a binary search tree where each node has a color
  74  * attribute, the value of which is either red or black.  Essentially, it
  75  * is just a convenient way to express a 2-3-4 binary search tree where
  76  * the color indicates whether the node is part of a 3-node or a 4-node.
  77  * In addition to the ordinary requirements imposed on binary search
  78  * trees, we make the following additional requirements of any valid
  79  * red-black tree:
  80  *  1) Every node is either red or black.
  81  *  2) The root is black.
  82  *  3) All leaves are black.
  83  *  4) Both children of each red node are black.
  84  *  5) The paths from each leaf up to the root each contain the same
  85  *     number of black nodes.
  86  */
  87
  88 /*
  89  * Create a red black tree struct using the specified compare routine.
  90  * Allocates and returns the initialized (empty) tree.
  91  */
  92 struct rbtree *
  93 rbcreate(compar)
  94     int (*compar)__P((const void *, const void*));
  95 {
  96     struct rbtree *tree;
  97
  98     tree = (struct rbtree *) emalloc(sizeof(*tree));
  99     tree->compar = compar;
 100
 101     /*
 102      * We use a self-referencing sentinel node called nil to simplify the
 103      * code by avoiding the need to check for NULL pointers.
 104      */
 105     tree->nil.left = tree->nil.right = tree->nil.parent = &tree->nil;
 106     tree->nil.color = black;
 107     tree->nil.data = NULL;
 108
 109     /*
 110      * Similarly, the fake root node keeps us from having to worry
 111      * about splitting the root.
 112      */
 113     tree->root.left = tree->root.right = tree->root.parent = &tree->nil;
 114     tree->root.color = black;
 115     tree->root.data = NULL;
 116
 117     return(tree);
 118 }
 119
 120 /*
 121  * Perform a left rotation starting at node.
 122  */
 123 static void
 124 rotate_left(tree, node)
 125     struct rbtree *tree;
 126     struct rbnode *node;
 127 {
 128     struct rbnode *child;
 129
 130     child = node->right;
 131     node->right = child->left;
 132
 133     if (child->left != rbnil(tree))
 134         child->left->parent = node;
 135     child->parent = node->parent;
 136
 137     if (node == node->parent->left)
 138         node->parent->left = child;
 139     else
 140         node->parent->right = child;
 141     child->left = node;
 142     node->parent = child;
 143 }
 144
 145 /*
 146  * Perform a right rotation starting at node.
 147  */
 148 static void
 149 rotate_right(tree, node)
 150     struct rbtree *tree;
 151     struct rbnode *node;
 152 {
 153     struct rbnode *child;
 154
 155     child = node->left;
 156     node->left = child->right;
 157
 158     if (child->right != rbnil(tree))
 159         child->right->parent = node;
 160     child->parent = node->parent;
 161
 162     if (node == node->parent->left)
 163         node->parent->left = child;
 164     else
 165         node->parent->right = child;
 166     child->right = node;
 167     node->parent = child;
 168 }
 169
 170 /*
 171  * Insert data pointer into a redblack tree.
 172  * Returns a NULL pointer on success.  If a node matching "data"
 173  * already exists, a pointer to the existant node is returned.
 174  */
 175 struct rbnode *
 176 rbinsert(tree, data)
 177     struct rbtree *tree;
 178     void *data;
 179 {
 180     struct rbnode *node = rbfirst(tree);
 181     struct rbnode *parent = rbroot(tree);
 182     int res;
 183
 184     /* Find correct insertion point. */
 185     while (node != rbnil(tree)) {
 186         parent = node;
 187         if ((res = tree->compar(data, node->data)) == 0)
 188             return(node);
 189         node = res < 0 ? node->left : node->right;
 190     }
 191
 192     node = (struct rbnode *) emalloc(sizeof(*node));
 193     node->data = data;
 194     node->left = node->right = rbnil(tree);
 195     node->parent = parent;
 196     if (parent == rbroot(tree) || tree->compar(data, parent->data) < 0)
 197         parent->left = node;
 198     else
 199         parent->right = node;
 200     node->color = red;
 201
 202     /*
 203      * If the parent node is black we are all set, if it is red we have
 204      * the following possible cases to deal with.  We iterate through
 205      * the rest of the tree to make sure none of the required properties
 206      * is violated.
 207      *
 208      *  1) The uncle is red.  We repaint both the parent and uncle black
 209      *     and repaint the grandparent node red.
 210      *
 211      *  2) The uncle is black and the new node is the right child of its
 212      *     parent, and the parent in turn is the left child of its parent.
 213      *     We do a left rotation to switch the roles of the parent and
 214      *     child, relying on further iterations to fixup the old parent.
 215      *
 216      *  3) The uncle is black and the new node is the left child of its
 217      *     parent, and the parent in turn is the left child of its parent.
 218      *     We switch the colors of the parent and grandparent and perform
 219      *     a right rotation around the grandparent.  This makes the former
 220      *     parent the parent of the new node and the former grandparent.
 221      *
 222      * Note that because we use a sentinel for the root node we never
 223      * need to worry about replacing the root.
 224      */
 225     while (node->parent->color == red) {
 226         struct rbnode *uncle;
 227         if (node->parent == node->parent->parent->left) {
 228             uncle = node->parent->parent->right;
 229             if (uncle->color == red) {
 230                 node->parent->color = black;
 231                 uncle->color = black;
 232                 node->parent->parent->color = red;
 233                 node = node->parent->parent;
 234             } else /* if (uncle->color == black) */ {
 235                 if (node == node->parent->right) {
 236                     node = node->parent;
 237                     rotate_left(tree, node);
 238                 }
 239                 node->parent->color = black;
 240                 node->parent->parent->color = red;
 241                 rotate_right(tree, node->parent->parent);
 242             }
 243         } else { /* if (node->parent == node->parent->parent->right) */
 244             uncle = node->parent->parent->left;
 245             if (uncle->color == red) {
 246                 node->parent->color = black;
 247                 uncle->color = black;
 248                 node->parent->parent->color = red;
 249                 node = node->parent->parent;
 250             } else /* if (uncle->color == black) */ {
 251                 if (node == node->parent->left) {
 252                     node = node->parent;
 253                     rotate_right(tree, node);
 254                 }
 255                 node->parent->color = black;
 256                 node->parent->parent->color = red;
 257                 rotate_left(tree, node->parent->parent);
 258             }
 259         }
 260     }
 261     rbfirst(tree)->color = black;       /* first node is always black */
 262     return(NULL);
 263 }
 264
 265 /*
 266  * Look for a node matching key in tree.
 267  * Returns a pointer to the node if found, else NULL.
 268  */
 269 struct rbnode *
 270 rbfind(tree, key)
 271     struct rbtree *tree;
 272     void *key;
 273 {
 274     struct rbnode *node = rbfirst(tree);
 275     int res;
 276
 277     while (node != rbnil(tree)) {
 278         if ((res = tree->compar(key, node->data)) == 0)
 279             return(node);
 280         node = res < 0 ? node->left : node->right;
 281     }
 282     return(NULL);
 283 }
 284
 285 /*
 286  * Call func() for each node, passing it the node data and a cookie;
 287  * If func() returns non-zero for a node, the traversal stops and the
 288  * error value is returned.  Returns 0 on successful traversal.
 289  */
 290 int
 291 rbapply_node(tree, node, func, cookie, order)
 292     struct rbtree *tree;
 293     struct rbnode *node;
 294     int (*func)__P((void *, void *));
 295     void *cookie;
 296     enum rbtraversal order;
 297 {
 298     int error;
 299
 300     if (node != rbnil(tree)) {
 301         if (order == preorder)
 302             if ((error = func(node->data, cookie)) != 0)
 303                 return(error);
 304         if ((error = rbapply_node(tree, node->left, func, cookie, order)) != 0)
 305             return(error);
 306         if (order == inorder)
 307             if ((error = func(node->data, cookie)) != 0)
 308                 return(error);
 309         if ((error = rbapply_node(tree, node->right, func, cookie, order)) != 0)
 310             return(error);
 311         if (order == postorder)
 312             if ((error = func(node->data, cookie)) != 0)
 313                 return(error);
 314     }
 315     return (0);
 316 }
 317
 318 /*
 319  * Returns the successor of node, or nil if there is none.
 320  */
 321 static struct rbnode *
 322 rbsuccessor(tree, node)
 323     struct rbtree *tree;
 324     struct rbnode *node;
 325 {
 326     struct rbnode *succ;
 327
 328     if ((succ = node->right) != rbnil(tree)) {
 329         while (succ->left != rbnil(tree))
 330             succ = succ->left;
 331     } else {
 332         /* No right child, move up until we find it or hit the root */
 333         for (succ = node->parent; node == succ->right; succ = succ->parent)
 334             node = succ;
 335         if (succ == rbroot(tree))
 336             succ = rbnil(tree);
 337     }
 338     return(succ);
 339 }
 340
 341 /*
 342  * Recursive portion of rbdestroy().
 343  */
 344 static void
 345 _rbdestroy(tree, node, destroy)
 346     struct rbtree *tree;
 347     struct rbnode *node;
 348     void (*destroy)__P((void *));
 349 {
 350     if (node != rbnil(tree)) {
 351         _rbdestroy(tree, node->left, destroy);
 352         _rbdestroy(tree, node->right, destroy);
 353         if (destroy != NULL)
 354             destroy(node->data);
 355         efree(node);
 356     }
 357 }
 358
 359 /*
 360  * Destroy the specified tree, calling the destructor destroy
 361  * for each node and then freeing the tree itself.
 362  */
 363 void
 364 rbdestroy(tree, destroy)
 365     struct rbtree *tree;
 366     void (*destroy)__P((void *));
 367 {
 368     _rbdestroy(tree, rbfirst(tree), destroy);
 369     efree(tree);
 370 }
 371
 372 /*
 373  * Delete node 'z' from the tree and return its data pointer.
 374  */
 375 void *rbdelete(tree, z)
 376     struct rbtree *tree;
 377     struct rbnode *z;
 378 {
 379     struct rbnode *x, *y;
 380     void *data = z->data;
 381
 382     if (z->left == rbnil(tree) || z->right == rbnil(tree))
 383         y = z;
 384     else
 385         y = rbsuccessor(tree, z);
 386     x = (y->left == rbnil(tree)) ? y->right : y->left;
 387
 388     if ((x->parent = y->parent) == rbroot(tree)) {
 389         rbfirst(tree) = x;
 390     } else {
 391         if (y == y->parent->left)
 392             y->parent->left = x;
 393         else
 394             y->parent->right = x;
 395     }
 396     if (y->color == black)
 397         rbrepair(tree, x);
 398     if (y != z) {
 399         y->left = z->left;
 400         y->right = z->right;
 401         y->parent = z->parent;
 402         y->color = z->color;
 403         z->left->parent = z->right->parent = y;
 404         if (z == z->parent->left)
 405             z->parent->left = y;
 406         else
 407             z->parent->right = y;
 408     }
 409     free(z);
 410
 411     return (data);
 412 }
 413
 414 /*
 415  * Repair the tree after a node has been deleted by rotating and repainting
 416  * colors to restore the 4 properties inherent in red-black trees.
 417  */
 418 static void
 419 rbrepair(tree, node)
 420     struct rbtree *tree;
 421     struct rbnode *node;
 422 {
 423     struct rbnode *sibling;
 424
 425     while (node->color == black && node != rbroot(tree)) {
 426         if (node == node->parent->left) {
 427             sibling = node->parent->right;
 428             if (sibling->color == red) {
 429                 sibling->color = black;
 430                 node->parent->color = red;
 431                 rotate_left(tree, node->parent);
 432                 sibling = node->parent->right;
 433             }
 434             if (sibling->right->color == black && sibling->left->color == black) {
 435                 sibling->color = red;
 436                 node = node->parent;
 437             } else {
 438                 if (sibling->right->color == black) {
 439                       sibling->left->color = black;
 440                       sibling->color = red;
 441                       rotate_right(tree, sibling);
 442                       sibling = node->parent->right;
 443                 }
 444                 sibling->color = node->parent->color;
 445                 node->parent->color = black;
 446                 sibling->right->color = black;
 447                 rotate_left(tree, node->parent);
 448                 node = rbroot(tree); /* exit loop */
 449             }
 450         } else { /* if (node == node->parent->right) */
 451             sibling = node->parent->left;
 452             if (sibling->color == red) {
 453                 sibling->color = black;
 454                 node->parent->color = red;
 455                 rotate_right(tree, node->parent);
 456                 sibling = node->parent->left;
 457             }
 458             if (sibling->right->color == black && sibling->left->color == black) {
 459                 sibling->color = red;
 460                 node = node->parent;
 461             } else {
 462                 if (sibling->left->color == black) {
 463                     sibling->right->color = black;
 464                     sibling->color = red;
 465                     rotate_left(tree, sibling);
 466                     sibling = node->parent->left;
 467                 }
 468                 sibling->color = node->parent->color;
 469                 node->parent->color = black;
 470                 sibling->left->color = black;
 471                 rotate_right(tree, node->parent);
 472                 node = rbroot(tree); /* exit loop */
 473             }
 474         }
 475     }
 476     node->color = black;
 477 }