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

   1 /*
   2  * Copyright (c) 2004-2005, 2007, 2009-2011
   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 #include <sys/param.h>
  47
  48 #include <stdio.h>
  49 #ifdef STDC_HEADERS
  50 # include <stdlib.h>
  51 # include <stddef.h>
  52 #else
  53 # ifdef HAVE_STDLIB_H
  54 #  include <stdlib.h>
  55 # endif
  56 #endif /* STDC_HEADERS */
  57
  58 #include "missing.h"
  59 #include "alloc.h"
  60 #include "sudo_debug.h"
  61 #include "redblack.h"
  62
  63 static void rbrepair(struct rbtree *, struct rbnode *);
  64 static void rotate_left(struct rbtree *, struct rbnode *);
  65 static void rotate_right(struct rbtree *, struct rbnode *);
  66 static void _rbdestroy(struct rbtree *, struct rbnode *, void (*)(void *));
  67
  68 /*
  69  * Red-Black tree, see http://en.wikipedia.org/wiki/Red-black_tree
  70  *
  71  * A red-black tree is a binary search tree where each node has a color
  72  * attribute, the value of which is either red or black.  Essentially, it
  73  * is just a convenient way to express a 2-3-4 binary search tree where
  74  * the color indicates whether the node is part of a 3-node or a 4-node.
  75  * In addition to the ordinary requirements imposed on binary search
  76  * trees, we make the following additional requirements of any valid
  77  * red-black tree:
  78  *  1) Every node is either red or black.
  79  *  2) The root is black.
  80  *  3) All leaves are black.
  81  *  4) Both children of each red node are black.
  82  *  5) The paths from each leaf up to the root each contain the same
  83  *     number of black nodes.
  84  */
  85
  86 /*
  87  * Create a red black tree struct using the specified compare routine.
  88  * Allocates and returns the initialized (empty) tree.
  89  */
  90 struct rbtree *
  91 rbcreate(int (*compar)(const void *, const void*))
  92 {
  93     struct rbtree *tree;
  94     debug_decl(rbcreate, SUDO_DEBUG_RBTREE)
  95
  96     tree = (struct rbtree *) emalloc(sizeof(*tree));
  97     tree->compar = compar;
  98
  99     /*
 100      * We use a self-referencing sentinel node called nil to simplify the
 101      * code by avoiding the need to check for NULL pointers.
 102      */
 103     tree->nil.left = tree->nil.right = tree->nil.parent = &tree->nil;
 104     tree->nil.color = black;
 105     tree->nil.data = NULL;
 106
 107     /*
 108      * Similarly, the fake root node keeps us from having to worry
 109      * about splitting the root.
 110      */
 111     tree->root.left = tree->root.right = tree->root.parent = &tree->nil;
 112     tree->root.color = black;
 113     tree->root.data = NULL;
 114
 115     debug_return_ptr(tree);
 116 }
 117
 118 /*
 119  * Perform a left rotation starting at node.
 120  */
 121 static void
 122 rotate_left(struct rbtree *tree, struct rbnode *node)
 123 {
 124     struct rbnode *child;
 125     debug_decl(rotate_left, SUDO_DEBUG_RBTREE)
 126
 127     child = node->right;
 128     node->right = child->left;
 129
 130     if (child->left != rbnil(tree))
 131         child->left->parent = node;
 132     child->parent = node->parent;
 133
 134     if (node == node->parent->left)
 135         node->parent->left = child;
 136     else
 137         node->parent->right = child;
 138     child->left = node;
 139     node->parent = child;
 140
 141     debug_return;
 142 }
 143
 144 /*
 145  * Perform a right rotation starting at node.
 146  */
 147 static void
 148 rotate_right(struct rbtree *tree, struct rbnode *node)
 149 {
 150     struct rbnode *child;
 151     debug_decl(rotate_right, SUDO_DEBUG_RBTREE)
 152
 153     child = node->left;
 154     node->left = child->right;
 155
 156     if (child->right != rbnil(tree))
 157         child->right->parent = node;
 158     child->parent = node->parent;
 159
 160     if (node == node->parent->left)
 161         node->parent->left = child;
 162     else
 163         node->parent->right = child;
 164     child->right = node;
 165     node->parent = child;
 166
 167     debug_return;
 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(struct rbtree *tree, void *data)
 177 {
 178     struct rbnode *node = rbfirst(tree);
 179     struct rbnode *parent = rbroot(tree);
 180     int res;
 181     debug_decl(rbinsert, SUDO_DEBUG_RBTREE)
 182
 183     /* Find correct insertion point. */
 184     while (node != rbnil(tree)) {
 185         parent = node;
 186         if ((res = tree->compar(data, node->data)) == 0)
 187             debug_return_ptr(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     debug_return_ptr(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(struct rbtree *tree, void *key)
 270 {
 271     struct rbnode *node = rbfirst(tree);
 272     int res;
 273     debug_decl(rbfind, SUDO_DEBUG_RBTREE)
 274
 275     while (node != rbnil(tree)) {
 276         if ((res = tree->compar(key, node->data)) == 0)
 277             debug_return_ptr(node);
 278         node = res < 0 ? node->left : node->right;
 279     }
 280     debug_return_ptr(NULL);
 281 }
 282
 283 /*
 284  * Call func() for each node, passing it the node data and a cookie;
 285  * If func() returns non-zero for a node, the traversal stops and the
 286  * error value is returned.  Returns 0 on successful traversal.
 287  */
 288 int
 289 rbapply_node(struct rbtree *tree, struct rbnode *node,
 290     int (*func)(void *, void *), void *cookie, enum rbtraversal order)
 291 {
 292     int error;
 293     debug_decl(rbapply_node, SUDO_DEBUG_RBTREE)
 294
 295     if (node != rbnil(tree)) {
 296         if (order == preorder)
 297             if ((error = func(node->data, cookie)) != 0)
 298                 debug_return_int(error);
 299         if ((error = rbapply_node(tree, node->left, func, cookie, order)) != 0)
 300             debug_return_int(error);
 301         if (order == inorder)
 302             if ((error = func(node->data, cookie)) != 0)
 303                 debug_return_int(error);
 304         if ((error = rbapply_node(tree, node->right, func, cookie, order)) != 0)
 305             debug_return_int(error);
 306         if (order == postorder)
 307             if ((error = func(node->data, cookie)) != 0)
 308                 debug_return_int(error);
 309     }
 310     debug_return_int(0);
 311 }
 312
 313 /*
 314  * Returns the successor of node, or nil if there is none.
 315  */
 316 static struct rbnode *
 317 rbsuccessor(struct rbtree *tree, struct rbnode *node)
 318 {
 319     struct rbnode *succ;
 320     debug_decl(rbsuccessor, SUDO_DEBUG_RBTREE)
 321
 322     if ((succ = node->right) != rbnil(tree)) {
 323         while (succ->left != rbnil(tree))
 324             succ = succ->left;
 325     } else {
 326         /* No right child, move up until we find it or hit the root */
 327         for (succ = node->parent; node == succ->right; succ = succ->parent)
 328             node = succ;
 329         if (succ == rbroot(tree))
 330             succ = rbnil(tree);
 331     }
 332     debug_return_ptr(succ);
 333 }
 334
 335 /*
 336  * Recursive portion of rbdestroy().
 337  */
 338 static void
 339 _rbdestroy(struct rbtree *tree, struct rbnode *node, void (*destroy)(void *))
 340 {
 341     debug_decl(_rbdestroy, SUDO_DEBUG_RBTREE)
 342     if (node != rbnil(tree)) {
 343         _rbdestroy(tree, node->left, destroy);
 344         _rbdestroy(tree, node->right, destroy);
 345         if (destroy != NULL)
 346             destroy(node->data);
 347         efree(node);
 348     }
 349     debug_return;
 350 }
 351
 352 /*
 353  * Destroy the specified tree, calling the destructor destroy
 354  * for each node and then freeing the tree itself.
 355  */
 356 void
 357 rbdestroy(struct rbtree *tree, void (*destroy)(void *))
 358 {
 359     debug_decl(rbdestroy, SUDO_DEBUG_RBTREE)
 360     _rbdestroy(tree, rbfirst(tree), destroy);
 361     efree(tree);
 362     debug_return;
 363 }
 364
 365 /*
 366  * Delete node 'z' from the tree and return its data pointer.
 367  */
 368 void *rbdelete(struct rbtree *tree, struct rbnode *z)
 369 {
 370     struct rbnode *x, *y;
 371     void *data = z->data;
 372     debug_decl(rbdelete, SUDO_DEBUG_RBTREE)
 373
 374     if (z->left == rbnil(tree) || z->right == rbnil(tree))
 375         y = z;
 376     else
 377         y = rbsuccessor(tree, z);
 378     x = (y->left == rbnil(tree)) ? y->right : y->left;
 379
 380     if ((x->parent = y->parent) == rbroot(tree)) {
 381         rbfirst(tree) = x;
 382     } else {
 383         if (y == y->parent->left)
 384             y->parent->left = x;
 385         else
 386             y->parent->right = x;
 387     }
 388     if (y->color == black)
 389         rbrepair(tree, x);
 390     if (y != z) {
 391         y->left = z->left;
 392         y->right = z->right;
 393         y->parent = z->parent;
 394         y->color = z->color;
 395         z->left->parent = z->right->parent = y;
 396         if (z == z->parent->left)
 397             z->parent->left = y;
 398         else
 399             z->parent->right = y;
 400     }
 401     free(z);
 402
 403     debug_return_ptr(data);
 404 }
 405
 406 /*
 407  * Repair the tree after a node has been deleted by rotating and repainting
 408  * colors to restore the 4 properties inherent in red-black trees.
 409  */
 410 static void
 411 rbrepair(struct rbtree *tree, struct rbnode *node)
 412 {
 413     struct rbnode *sibling;
 414     debug_decl(rbrepair, SUDO_DEBUG_RBTREE)
 415
 416     while (node->color == black && node != rbfirst(tree)) {
 417         if (node == node->parent->left) {
 418             sibling = node->parent->right;
 419             if (sibling->color == red) {
 420                 sibling->color = black;
 421                 node->parent->color = red;
 422                 rotate_left(tree, node->parent);
 423                 sibling = node->parent->right;
 424             }
 425             if (sibling->right->color == black && sibling->left->color == black) {
 426                 sibling->color = red;
 427                 node = node->parent;
 428             } else {
 429                 if (sibling->right->color == black) {
 430                       sibling->left->color = black;
 431                       sibling->color = red;
 432                       rotate_right(tree, sibling);
 433                       sibling = node->parent->right;
 434                 }
 435                 sibling->color = node->parent->color;
 436                 node->parent->color = black;
 437                 sibling->right->color = black;
 438                 rotate_left(tree, node->parent);
 439                 node = rbfirst(tree); /* exit loop */
 440             }
 441         } else { /* if (node == node->parent->right) */
 442             sibling = node->parent->left;
 443             if (sibling->color == red) {
 444                 sibling->color = black;
 445                 node->parent->color = red;
 446                 rotate_right(tree, node->parent);
 447                 sibling = node->parent->left;
 448             }
 449             if (sibling->right->color == black && sibling->left->color == black) {
 450                 sibling->color = red;
 451                 node = node->parent;
 452             } else {
 453                 if (sibling->left->color == black) {
 454                     sibling->right->color = black;
 455                     sibling->color = red;
 456                     rotate_left(tree, sibling);
 457                     sibling = node->parent->left;
 458                 }
 459                 sibling->color = node->parent->color;
 460                 node->parent->color = black;
 461                 sibling->left->color = black;
 462                 rotate_right(tree, node->parent);
 463                 node = rbfirst(tree); /* exit loop */
 464             }
 465         }
 466     }
 467     node->color = black;
 468
 469     debug_return;
 470 }