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

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