granicus.if.org Git - sudo/blob - plugins/sudoers/redblack.c

   1 /*
   2  * Copyright (c) 2004-2005, 2007, 2009-2015
   3  *      Todd C. Miller <Todd.Miller@sudo.ws>
   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  * This is an open source non-commercial project. Dear PVS-Studio, please check it.
  20  * PVS-Studio Static Code Analyzer for C, C++ and C#: http://www.viva64.com
  21  */
  22
  23 /*
  24  * Adapted from the following code written by Emin Martinian:
  25  * http://web.mit.edu/~emin/www/source_code/red_black_tree/index.html
  26  *
  27  * Copyright (c) 2001 Emin Martinian
  28  *
  29  * Redistribution and use in source and binary forms, with or without
  30  * modification, are permitted provided that neither the name of Emin
  31  * Martinian nor the names of any contributors are be used to endorse or
  32  * promote products derived from this software without specific prior
  33  * written permission.
  34  *
  35  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  36  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  37  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  38  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  39  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  40  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  41  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  42  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  43  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  44  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  45  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  46  */
  47
  48 #include <config.h>
  49
  50 #include <sys/types.h>
  51
  52 #include <stdio.h>
  53 #include <stdlib.h>
  54
  55 #include "sudoers.h"
  56 #include "redblack.h"
  57
  58 static void rbrepair(struct rbtree *, struct rbnode *);
  59 static void rotate_left(struct rbtree *, struct rbnode *);
  60 static void rotate_right(struct rbtree *, struct rbnode *);
  61 static void rbdestroy_int(struct rbtree *, struct rbnode *, void (*)(void *));
  62
  63 /*
  64  * Red-Black tree, see http://en.wikipedia.org/wiki/Red-black_tree
  65  *
  66  * A red-black tree is a binary search tree where each node has a color
  67  * attribute, the value of which is either red or black.  Essentially, it
  68  * is just a convenient way to express a 2-3-4 binary search tree where
  69  * the color indicates whether the node is part of a 3-node or a 4-node.
  70  * In addition to the ordinary requirements imposed on binary search
  71  * trees, we make the following additional requirements of any valid
  72  * red-black tree:
  73  *  1) Every node is either red or black.
  74  *  2) The root is black.
  75  *  3) All leaves are black.
  76  *  4) Both children of each red node are black.
  77  *  5) The paths from each leaf up to the root each contain the same
  78  *     number of black nodes.
  79  */
  80
  81 /*
  82  * Create a red black tree struct using the specified compare routine.
  83  * Allocates and returns the initialized (empty) tree or NULL if
  84  * memory cannot be allocated.
  85  */
  86 struct rbtree *
  87 rbcreate(int (*compar)(const void *, const void*))
  88 {
  89     struct rbtree *tree;
  90     debug_decl(rbcreate, SUDOERS_DEBUG_RBTREE)
  91
  92     if ((tree = malloc(sizeof(*tree))) == NULL) {
  93         sudo_debug_printf(SUDO_DEBUG_ERROR|SUDO_DEBUG_LINENO,
  94             "unable to allocate memory");
  95         debug_return_ptr(NULL);
  96     }
  97
  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     debug_return_ptr(tree);
 117 }
 118
 119 /*
 120  * Perform a left rotation starting at node.
 121  */
 122 static void
 123 rotate_left(struct rbtree *tree, struct rbnode *node)
 124 {
 125     struct rbnode *child;
 126     debug_decl(rotate_left, SUDOERS_DEBUG_RBTREE)
 127
 128     child = node->right;
 129     node->right = child->left;
 130
 131     if (child->left != rbnil(tree))
 132         child->left->parent = node;
 133     child->parent = node->parent;
 134
 135     if (node == node->parent->left)
 136         node->parent->left = child;
 137     else
 138         node->parent->right = child;
 139     child->left = node;
 140     node->parent = child;
 141
 142     debug_return;
 143 }
 144
 145 /*
 146  * Perform a right rotation starting at node.
 147  */
 148 static void
 149 rotate_right(struct rbtree *tree, struct rbnode *node)
 150 {
 151     struct rbnode *child;
 152     debug_decl(rotate_right, SUDOERS_DEBUG_RBTREE)
 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     debug_return;
 169 }
 170
 171 /*
 172  * Insert data pointer into a redblack tree.
 173  * Returns a 0 on success, 1 if a node matching "data" already exists
 174  * (filling in "existing" if not NULL), or -1 on malloc() failure.
 175  */
 176 int
 177 rbinsert(struct rbtree *tree, void *data, struct rbnode **existing)
 178 {
 179     struct rbnode *node = rbfirst(tree);
 180     struct rbnode *parent = rbroot(tree);
 181     int res;
 182     debug_decl(rbinsert, SUDOERS_DEBUG_RBTREE)
 183
 184     /* Find correct insertion point. */
 185     while (node != rbnil(tree)) {
 186         parent = node;
 187         if ((res = tree->compar(data, node->data)) == 0) {
 188             if (existing != NULL)
 189                 *existing = node;
 190             debug_return_int(1);
 191         }
 192         node = res < 0 ? node->left : node->right;
 193     }
 194
 195     node = malloc(sizeof(*node));
 196     if (node == NULL) {
 197         sudo_debug_printf(SUDO_DEBUG_ERROR|SUDO_DEBUG_LINENO,
 198             "unable to allocate memory");
 199         debug_return_int(-1);
 200     }
 201     node->data = data;
 202     node->left = node->right = rbnil(tree);
 203     node->parent = parent;
 204     if (parent == rbroot(tree) || tree->compar(data, parent->data) < 0)
 205         parent->left = node;
 206     else
 207         parent->right = node;
 208     node->color = red;
 209
 210     /*
 211      * If the parent node is black we are all set, if it is red we have
 212      * the following possible cases to deal with.  We iterate through
 213      * the rest of the tree to make sure none of the required properties
 214      * is violated.
 215      *
 216      *  1) The uncle is red.  We repaint both the parent and uncle black
 217      *     and repaint the grandparent node red.
 218      *
 219      *  2) The uncle is black and the new node is the right child of its
 220      *     parent, and the parent in turn is the left child of its parent.
 221      *     We do a left rotation to switch the roles of the parent and
 222      *     child, relying on further iterations to fixup the old parent.
 223      *
 224      *  3) The uncle is black and the new node is the left child of its
 225      *     parent, and the parent in turn is the left child of its parent.
 226      *     We switch the colors of the parent and grandparent and perform
 227      *     a right rotation around the grandparent.  This makes the former
 228      *     parent the parent of the new node and the former grandparent.
 229      *
 230      * Note that because we use a sentinel for the root node we never
 231      * need to worry about replacing the root.
 232      */
 233     while (node->parent->color == red) {
 234         struct rbnode *uncle;
 235         if (node->parent == node->parent->parent->left) {
 236             uncle = node->parent->parent->right;
 237             if (uncle->color == red) {
 238                 node->parent->color = black;
 239                 uncle->color = black;
 240                 node->parent->parent->color = red;
 241                 node = node->parent->parent;
 242             } else /* if (uncle->color == black) */ {
 243                 if (node == node->parent->right) {
 244                     node = node->parent;
 245                     rotate_left(tree, node);
 246                 }
 247                 node->parent->color = black;
 248                 node->parent->parent->color = red;
 249                 rotate_right(tree, node->parent->parent);
 250             }
 251         } else { /* if (node->parent == node->parent->parent->right) */
 252             uncle = node->parent->parent->left;
 253             if (uncle->color == red) {
 254                 node->parent->color = black;
 255                 uncle->color = black;
 256                 node->parent->parent->color = red;
 257                 node = node->parent->parent;
 258             } else /* if (uncle->color == black) */ {
 259                 if (node == node->parent->left) {
 260                     node = node->parent;
 261                     rotate_right(tree, node);
 262                 }
 263                 node->parent->color = black;
 264                 node->parent->parent->color = red;
 265                 rotate_left(tree, node->parent->parent);
 266             }
 267         }
 268     }
 269     rbfirst(tree)->color = black;       /* first node is always black */
 270     debug_return_int(0);
 271 }
 272
 273 /*
 274  * Look for a node matching key in tree.
 275  * Returns a pointer to the node if found, else NULL.
 276  */
 277 struct rbnode *
 278 rbfind(struct rbtree *tree, void *key)
 279 {
 280     struct rbnode *node = rbfirst(tree);
 281     int res;
 282     debug_decl(rbfind, SUDOERS_DEBUG_RBTREE)
 283
 284     while (node != rbnil(tree)) {
 285         if ((res = tree->compar(key, node->data)) == 0)
 286             debug_return_ptr(node);
 287         node = res < 0 ? node->left : node->right;
 288     }
 289     debug_return_ptr(NULL);
 290 }
 291
 292 /*
 293  * Call func() for each node, passing it the node data and a cookie;
 294  * If func() returns non-zero for a node, the traversal stops and the
 295  * error value is returned.  Returns 0 on successful traversal.
 296  */
 297 int
 298 rbapply_node(struct rbtree *tree, struct rbnode *node,
 299     int (*func)(void *, void *), void *cookie, enum rbtraversal order)
 300 {
 301     int error;
 302     debug_decl(rbapply_node, SUDOERS_DEBUG_RBTREE)
 303
 304     if (node != rbnil(tree)) {
 305         if (order == preorder)
 306             if ((error = func(node->data, cookie)) != 0)
 307                 debug_return_int(error);
 308         if ((error = rbapply_node(tree, node->left, func, cookie, order)) != 0)
 309             debug_return_int(error);
 310         if (order == inorder)
 311             if ((error = func(node->data, cookie)) != 0)
 312                 debug_return_int(error);
 313         if ((error = rbapply_node(tree, node->right, func, cookie, order)) != 0)
 314             debug_return_int(error);
 315         if (order == postorder)
 316             if ((error = func(node->data, cookie)) != 0)
 317                 debug_return_int(error);
 318     }
 319     debug_return_int(0);
 320 }
 321
 322 /*
 323  * Returns the successor of node, or nil if there is none.
 324  */
 325 static struct rbnode *
 326 rbsuccessor(struct rbtree *tree, struct rbnode *node)
 327 {
 328     struct rbnode *succ;
 329     debug_decl(rbsuccessor, SUDOERS_DEBUG_RBTREE)
 330
 331     if ((succ = node->right) != rbnil(tree)) {
 332         while (succ->left != rbnil(tree))
 333             succ = succ->left;
 334     } else {
 335         /* No right child, move up until we find it or hit the root */
 336         for (succ = node->parent; node == succ->right; succ = succ->parent)
 337             node = succ;
 338         if (succ == rbroot(tree))
 339             succ = rbnil(tree);
 340     }
 341     debug_return_ptr(succ);
 342 }
 343
 344 /*
 345  * Recursive portion of rbdestroy().
 346  */
 347 static void
 348 rbdestroy_int(struct rbtree *tree, struct rbnode *node, void (*destroy)(void *))
 349 {
 350     debug_decl(rbdestroy_int, SUDOERS_DEBUG_RBTREE)
 351     if (node != rbnil(tree)) {
 352         rbdestroy_int(tree, node->left, destroy);
 353         rbdestroy_int(tree, node->right, destroy);
 354         if (destroy != NULL)
 355             destroy(node->data);
 356         free(node);
 357     }
 358     debug_return;
 359 }
 360
 361 /*
 362  * Destroy the specified tree, calling the destructor "destroy"
 363  * for each node and then freeing the tree itself.
 364  */
 365 void
 366 rbdestroy(struct rbtree *tree, void (*destroy)(void *))
 367 {
 368     debug_decl(rbdestroy, SUDOERS_DEBUG_RBTREE)
 369     rbdestroy_int(tree, rbfirst(tree), destroy);
 370     free(tree);
 371     debug_return;
 372 }
 373
 374 /*
 375  * Delete node 'z' from the tree and return its data pointer.
 376  */
 377 void *rbdelete(struct rbtree *tree, struct rbnode *z)
 378 {
 379     struct rbnode *x, *y;
 380     void *data = z->data;
 381     debug_decl(rbdelete, SUDOERS_DEBUG_RBTREE)
 382
 383     if (z->left == rbnil(tree) || z->right == rbnil(tree))
 384         y = z;
 385     else
 386         y = rbsuccessor(tree, z);
 387     x = (y->left == rbnil(tree)) ? y->right : y->left;
 388
 389     if ((x->parent = y->parent) == rbroot(tree)) {
 390         rbfirst(tree) = x;
 391     } else {
 392         if (y == y->parent->left)
 393             y->parent->left = x;
 394         else
 395             y->parent->right = x;
 396     }
 397     if (y->color == black)
 398         rbrepair(tree, x);
 399     if (y != z) {
 400         y->left = z->left;
 401         y->right = z->right;
 402         y->parent = z->parent;
 403         y->color = z->color;
 404         z->left->parent = z->right->parent = y;
 405         if (z == z->parent->left)
 406             z->parent->left = y;
 407         else
 408             z->parent->right = y;
 409     }
 410     free(z);
 411
 412     debug_return_ptr(data);
 413 }
 414
 415 /*
 416  * Repair the tree after a node has been deleted by rotating and repainting
 417  * colors to restore the 4 properties inherent in red-black trees.
 418  */
 419 static void
 420 rbrepair(struct rbtree *tree, struct rbnode *node)
 421 {
 422     struct rbnode *sibling;
 423     debug_decl(rbrepair, SUDOERS_DEBUG_RBTREE)
 424
 425     while (node->color == black && node != rbfirst(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 = rbfirst(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 = rbfirst(tree); /* exit loop */
 473             }
 474         }
 475     }
 476     node->color = black;
 477
 478     debug_return;
 479 }