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

   1 /*
   2  * Copyright (c) 2004-2005, 2007 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.10 2008/11/22 15:01:25 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) The root is black.
  81  *  2) All leaves are black.
  82  *  3) Both children of each red node are black.
  83  *  4) The paths from each leaf up to the root each contain the same
  84  *     number of black nodes.
  85  */
  86
  87 /*
  88  * Create a red black tree struct using the specified compare routine.
  89  * Allocates and returns the initialized (empty) tree.
  90  */
  91 struct rbtree *
  92 rbcreate(compar)
  93     int (*compar)__P((const void *, const void*));
  94 {
  95     struct rbtree *tree;
  96
  97     tree = (struct rbtree *) emalloc(sizeof(*tree));
  98     tree->compar = compar;
  99
 100     /*
 101      * We use a self-referencing sentinel node called nil to simplify the
 102      * code by avoiding the need to check for NULL pointers.
 103      */
 104     tree->nil.left = tree->nil.right = tree->nil.parent = &tree->nil;
 105     tree->nil.color = black;
 106     tree->nil.data = NULL;
 107
 108     /*
 109      * Similarly, the fake root node keeps us from having to worry
 110      * about splitting the root.
 111      */
 112     tree->root.left = tree->root.right = tree->root.parent = &tree->nil;
 113     tree->root.color = black;
 114     tree->root.data = NULL;
 115
 116     return(tree);
 117 }
 118
 119 /*
 120  * Perform a left rotation starting at node.
 121  */
 122 static void
 123 rotate_left(tree, node)
 124     struct rbtree *tree;
 125     struct rbnode *node;
 126 {
 127     struct rbnode *child;
 128
 129     child = node->right;
 130     node->right = child->left;
 131
 132     if (child->left != rbnil(tree))
 133         child->left->parent = node;
 134     child->parent = node->parent;
 135
 136     if (node == node->parent->left)
 137         node->parent->left = child;
 138     else
 139         node->parent->right = child;
 140     child->left = node;
 141     node->parent = child;
 142 }
 143
 144 /*
 145  * Perform a right rotation starting at node.
 146  */
 147 static void
 148 rotate_right(tree, node)
 149     struct rbtree *tree;
 150     struct rbnode *node;
 151 {
 152     struct rbnode *child;
 153
 154     child = node->left;
 155     node->left = child->right;
 156
 157     if (child->right != rbnil(tree))
 158         child->right->parent = node;
 159     child->parent = node->parent;
 160
 161     if (node == node->parent->left)
 162         node->parent->left = child;
 163     else
 164         node->parent->right = child;
 165     child->right = node;
 166     node->parent = child;
 167 }
 168
 169 /*
 170  * Insert data pointer into a redblack tree.
 171  * Returns a NULL pointer on success.  If a node matching "data"
 172  * already exists, a pointer to the existant node is returned.
 173  */
 174 struct rbnode *
 175 rbinsert(tree, data)
 176     struct rbtree *tree;
 177     void *data;
 178 {
 179     struct rbnode *node = rbfirst(tree);
 180     struct rbnode *parent = rbroot(tree);
 181     int res;
 182
 183     /* Find correct insertion point. */
 184     while (node != rbnil(tree)) {
 185         parent = node;
 186         if ((res = tree->compar(data, node->data)) == 0)
 187             return(node);
 188         node = res < 0 ? node->left : node->right;
 189     }
 190
 191     node = (struct rbnode *) emalloc(sizeof(*node));
 192     node->data = data;
 193     node->left = node->right = rbnil(tree);
 194     node->parent = parent;
 195     if (parent == rbroot(tree) || tree->compar(data, parent->data) < 0)
 196         parent->left = node;
 197     else
 198         parent->right = node;
 199     node->color = red;
 200
 201     /*
 202      * If the parent node is black we are all set, if it is red we have
 203      * the following possible cases to deal with.  We iterate through
 204      * the rest of the tree to make sure none of the required properties
 205      * is violated.
 206      *
 207      *  1) The uncle is red.  We repaint both the parent and uncle black
 208      *     and repaint the grandparent node red.
 209      *
 210      *  2) The uncle is black and the new node is the right child of its
 211      *     parent, and the parent in turn is the left child of its parent.
 212      *     We do a left rotation to switch the roles of the parent and
 213      *     child, relying on further iterations to fixup the old parent.
 214      *
 215      *  3) The uncle is black and the new node is the left child of its
 216      *     parent, and the parent in turn is the left child of its parent.
 217      *     We switch the colors of the parent and grandparent and perform
 218      *     a right rotation around the grandparent.  This makes the former
 219      *     parent the parent of the new node and the former grandparent.
 220      *
 221      * Note that because we use a sentinel for the root node we never
 222      * need to worry about replacing the root.
 223      */
 224     while (node->parent->color == red) {
 225         struct rbnode *uncle;
 226         if (node->parent == node->parent->parent->left) {
 227             uncle = node->parent->parent->right;
 228             if (uncle->color == red) {
 229                 node->parent->color = black;
 230                 uncle->color = black;
 231                 node->parent->parent->color = red;
 232                 node = node->parent->parent;
 233             } else /* if (uncle->color == black) */ {
 234                 if (node == node->parent->right) {
 235                     node = node->parent;
 236                     rotate_left(tree, node);
 237                 }
 238                 node->parent->color = black;
 239                 node->parent->parent->color = red;
 240                 rotate_right(tree, node->parent->parent);
 241             }
 242         } else { /* if (node->parent == node->parent->parent->right) */
 243             uncle = node->parent->parent->left;
 244             if (uncle->color == red) {
 245                 node->parent->color = black;
 246                 uncle->color = black;
 247                 node->parent->parent->color = red;
 248                 node = node->parent->parent;
 249             } else /* if (uncle->color == black) */ {
 250                 if (node == node->parent->left) {
 251                     node = node->parent;
 252                     rotate_right(tree, node);
 253                 }
 254                 node->parent->color = black;
 255                 node->parent->parent->color = red;
 256                 rotate_left(tree, node->parent->parent);
 257             }
 258         }
 259     }
 260     rbfirst(tree)->color = black;       /* first node is always black */
 261     return(NULL);
 262 }
 263
 264 /*
 265  * Look for a node matching key in tree.
 266  * Returns a pointer to the node if found, else NULL.
 267  */
 268 struct rbnode *
 269 rbfind(tree, key)
 270     struct rbtree *tree;
 271     void *key;
 272 {
 273     struct rbnode *node = rbfirst(tree);
 274     int res;
 275
 276     while (node != rbnil(tree)) {
 277         if ((res = tree->compar(key, node->data)) == 0)
 278             return(node);
 279         node = res < 0 ? node->left : node->right;
 280     }
 281     return(NULL);
 282 }
 283
 284 /*
 285  * Call func() for each node, passing it the node data and a cookie;
 286  * If func() returns non-zero for a node, the traversal stops and the
 287  * error value is returned.  Returns 0 on successful traversal.
 288  */
 289 int
 290 rbapply_node(tree, node, func, cookie, order)
 291     struct rbtree *tree;
 292     struct rbnode *node;
 293     int (*func)__P((void *, void *));
 294     void *cookie;
 295     enum rbtraversal order;
 296 {
 297     int error;
 298
 299     if (node != rbnil(tree)) {
 300         if (order == preorder)
 301             if ((error = func(node->data, cookie)) != 0)
 302                 return(error);
 303         if ((error = rbapply_node(tree, node->left, func, cookie, order)) != 0)
 304             return(error);
 305         if (order == inorder)
 306             if ((error = func(node->data, cookie)) != 0)
 307                 return(error);
 308         if ((error = rbapply_node(tree, node->right, func, cookie, order)) != 0)
 309             return(error);
 310         if (order == postorder)
 311             if ((error = func(node->data, cookie)) != 0)
 312                 return(error);
 313     }
 314     return (0);
 315 }
 316
 317 /*
 318  * Returns the successor of node, or nil if there is none.
 319  */
 320 static struct rbnode *
 321 rbsuccessor(tree, node)
 322     struct rbtree *tree;
 323     struct rbnode *node;
 324 {
 325     struct rbnode *succ;
 326
 327     if ((succ = node->right) != rbnil(tree)) {
 328         while (succ->left != rbnil(tree))
 329             succ = succ->left;
 330     } else {
 331         /* No right child, move up until we find it or hit the root */
 332         for (succ = node->parent; node == succ->right; succ = succ->parent)
 333             node = succ;
 334         if (succ == rbroot(tree))
 335             succ = rbnil(tree);
 336     }
 337     return(succ);
 338 }
 339
 340 /*
 341  * Recursive portion of rbdestroy().
 342  */
 343 static void
 344 _rbdestroy(tree, node, destroy)
 345     struct rbtree *tree;
 346     struct rbnode *node;
 347     void (*destroy)__P((void *));
 348 {
 349     if (node != rbnil(tree)) {
 350         _rbdestroy(tree, node->left, destroy);
 351         _rbdestroy(tree, node->right, destroy);
 352         if (destroy != NULL)
 353             destroy(node->data);
 354         efree(node);
 355     }
 356 }
 357
 358 /*
 359  * Destroy the specified tree, calling the destructor destroy
 360  * for each node and then freeing the tree itself.
 361  */
 362 void
 363 rbdestroy(tree, destroy)
 364     struct rbtree *tree;
 365     void (*destroy)__P((void *));
 366 {
 367     _rbdestroy(tree, rbfirst(tree), destroy);
 368     efree(tree);
 369 }
 370
 371 /*
 372  * Delete node 'z' from the tree and return its data pointer.
 373  */
 374 void *rbdelete(tree, z)
 375     struct rbtree* tree;
 376     struct rbnode* z;
 377 {
 378     struct rbnode *x, *y;
 379     void *data = z->data;
 380
 381     if (z->left == rbnil(tree) || z->right == rbnil(tree))
 382         y = z;
 383     else
 384         y = rbsuccessor(tree, z);
 385     x = (y->left == rbnil(tree)) ? y->right : y->left;
 386
 387     if ((x->parent = y->parent) == rbroot(tree)) {
 388         rbfirst(tree) = x;
 389     } else {
 390         if (y == y->parent->left)
 391             y->parent->left = x;
 392         else
 393             y->parent->right = x;
 394     }
 395     if (y->color == black)
 396         rbrepair(tree, x);
 397     if (y != z) {
 398         y->left = z->left;
 399         y->right = z->right;
 400         y->parent = z->parent;
 401         y->color = z->color;
 402         z->left->parent = z->right->parent = y;
 403         if (z == z->parent->left)
 404             z->parent->left = y;
 405         else
 406             z->parent->right = y;
 407     }
 408     free(z);
 409
 410     return (data);
 411 }
 412
 413 /*
 414  * Repair the tree after a node has been deleted by rotating and repainting
 415  * colors to restore the 4 properties inherent in red-black trees.
 416  */
 417 static void
 418 rbrepair(tree, node)
 419     struct rbtree *tree;
 420     struct rbnode *node;
 421 {
 422     struct rbnode *sibling;
 423
 424     while (node->color == black) {
 425         if (node == node->parent->left) {
 426             sibling = node->parent->right;
 427             if (sibling->color == red) {
 428                 sibling->color = black;
 429                 node->parent->color = red;
 430                 rotate_left(tree, node->parent);
 431                 sibling = node->parent->right;
 432             }
 433             if (sibling->right->color == black && sibling->left->color == black) {
 434                 sibling->color = red;
 435                 node = node->parent;
 436             } else {
 437                 if (sibling->right->color == black) {
 438                       sibling->left->color = black;
 439                       sibling->color = red;
 440                       rotate_right(tree, sibling);
 441                       sibling = node->parent->right;
 442                 }
 443                 sibling->color = node->parent->color;
 444                 node->parent->color = black;
 445                 sibling->right->color = black;
 446                 rotate_left(tree, node->parent);
 447                 break;
 448             }
 449         } else { /* if (node == node->parent->right) */
 450             sibling = node->parent->left;
 451             if (sibling->color == red) {
 452                 sibling->color = black;
 453                 node->parent->color = red;
 454                 rotate_right(tree, node->parent);
 455                 sibling = node->parent->left;
 456             }
 457             if (sibling->right->color == black && sibling->left->color == black) {
 458                 sibling->color = red;
 459                 node = node->parent;
 460             } else {
 461                 if (sibling->left->color == black) {
 462                     sibling->right->color = black;
 463                     sibling->color = red;
 464                     rotate_left(tree, sibling);
 465                     sibling = node->parent->left;
 466                 }
 467                 sibling->color = node->parent->color;
 468                 node->parent->color = black;
 469                 sibling->left->color = black;
 470                 rotate_right(tree, node->parent);
 471                 break;
 472             }
 473         }
 474     }
 475 }