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

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