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