Annotation of embedaddon/sudo/plugins/sudoers/redblack.c, revision 1.1
1.1 ! misho 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 "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:
! 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(struct rbtree *tree, struct rbnode *node)
! 121: {
! 122: struct rbnode *child;
! 123:
! 124: child = node->right;
! 125: node->right = child->left;
! 126:
! 127: if (child->left != rbnil(tree))
! 128: child->left->parent = node;
! 129: child->parent = node->parent;
! 130:
! 131: if (node == node->parent->left)
! 132: node->parent->left = child;
! 133: else
! 134: node->parent->right = child;
! 135: child->left = node;
! 136: node->parent = child;
! 137: }
! 138:
! 139: /*
! 140: * Perform a right rotation starting at node.
! 141: */
! 142: static void
! 143: rotate_right(struct rbtree *tree, struct rbnode *node)
! 144: {
! 145: struct rbnode *child;
! 146:
! 147: child = node->left;
! 148: node->left = child->right;
! 149:
! 150: if (child->right != rbnil(tree))
! 151: child->right->parent = node;
! 152: child->parent = node->parent;
! 153:
! 154: if (node == node->parent->left)
! 155: node->parent->left = child;
! 156: else
! 157: node->parent->right = child;
! 158: child->right = node;
! 159: node->parent = child;
! 160: }
! 161:
! 162: /*
! 163: * Insert data pointer into a redblack tree.
! 164: * Returns a NULL pointer on success. If a node matching "data"
! 165: * already exists, a pointer to the existant node is returned.
! 166: */
! 167: struct rbnode *
! 168: rbinsert(struct rbtree *tree, void *data)
! 169: {
! 170: struct rbnode *node = rbfirst(tree);
! 171: struct rbnode *parent = rbroot(tree);
! 172: int res;
! 173:
! 174: /* Find correct insertion point. */
! 175: while (node != rbnil(tree)) {
! 176: parent = node;
! 177: if ((res = tree->compar(data, node->data)) == 0)
! 178: return node;
! 179: node = res < 0 ? node->left : node->right;
! 180: }
! 181:
! 182: node = (struct rbnode *) emalloc(sizeof(*node));
! 183: node->data = data;
! 184: node->left = node->right = rbnil(tree);
! 185: node->parent = parent;
! 186: if (parent == rbroot(tree) || tree->compar(data, parent->data) < 0)
! 187: parent->left = node;
! 188: else
! 189: parent->right = node;
! 190: node->color = red;
! 191:
! 192: /*
! 193: * If the parent node is black we are all set, if it is red we have
! 194: * the following possible cases to deal with. We iterate through
! 195: * the rest of the tree to make sure none of the required properties
! 196: * is violated.
! 197: *
! 198: * 1) The uncle is red. We repaint both the parent and uncle black
! 199: * and repaint the grandparent node red.
! 200: *
! 201: * 2) The uncle is black and the new node is the right child of its
! 202: * parent, and the parent in turn is the left child of its parent.
! 203: * We do a left rotation to switch the roles of the parent and
! 204: * child, relying on further iterations to fixup the old parent.
! 205: *
! 206: * 3) The uncle is black and the new node is the left child of its
! 207: * parent, and the parent in turn is the left child of its parent.
! 208: * We switch the colors of the parent and grandparent and perform
! 209: * a right rotation around the grandparent. This makes the former
! 210: * parent the parent of the new node and the former grandparent.
! 211: *
! 212: * Note that because we use a sentinel for the root node we never
! 213: * need to worry about replacing the root.
! 214: */
! 215: while (node->parent->color == red) {
! 216: struct rbnode *uncle;
! 217: if (node->parent == node->parent->parent->left) {
! 218: uncle = node->parent->parent->right;
! 219: if (uncle->color == red) {
! 220: node->parent->color = black;
! 221: uncle->color = black;
! 222: node->parent->parent->color = red;
! 223: node = node->parent->parent;
! 224: } else /* if (uncle->color == black) */ {
! 225: if (node == node->parent->right) {
! 226: node = node->parent;
! 227: rotate_left(tree, node);
! 228: }
! 229: node->parent->color = black;
! 230: node->parent->parent->color = red;
! 231: rotate_right(tree, node->parent->parent);
! 232: }
! 233: } else { /* if (node->parent == node->parent->parent->right) */
! 234: uncle = node->parent->parent->left;
! 235: if (uncle->color == red) {
! 236: node->parent->color = black;
! 237: uncle->color = black;
! 238: node->parent->parent->color = red;
! 239: node = node->parent->parent;
! 240: } else /* if (uncle->color == black) */ {
! 241: if (node == node->parent->left) {
! 242: node = node->parent;
! 243: rotate_right(tree, node);
! 244: }
! 245: node->parent->color = black;
! 246: node->parent->parent->color = red;
! 247: rotate_left(tree, node->parent->parent);
! 248: }
! 249: }
! 250: }
! 251: rbfirst(tree)->color = black; /* first node is always black */
! 252: return NULL;
! 253: }
! 254:
! 255: /*
! 256: * Look for a node matching key in tree.
! 257: * Returns a pointer to the node if found, else NULL.
! 258: */
! 259: struct rbnode *
! 260: rbfind(struct rbtree *tree, void *key)
! 261: {
! 262: struct rbnode *node = rbfirst(tree);
! 263: int res;
! 264:
! 265: while (node != rbnil(tree)) {
! 266: if ((res = tree->compar(key, node->data)) == 0)
! 267: return node;
! 268: node = res < 0 ? node->left : node->right;
! 269: }
! 270: return NULL;
! 271: }
! 272:
! 273: /*
! 274: * Call func() for each node, passing it the node data and a cookie;
! 275: * If func() returns non-zero for a node, the traversal stops and the
! 276: * error value is returned. Returns 0 on successful traversal.
! 277: */
! 278: int
! 279: rbapply_node(struct rbtree *tree, struct rbnode *node,
! 280: int (*func)(void *, void *), void *cookie, enum rbtraversal order)
! 281: {
! 282: int error;
! 283:
! 284: if (node != rbnil(tree)) {
! 285: if (order == preorder)
! 286: if ((error = func(node->data, cookie)) != 0)
! 287: return error;
! 288: if ((error = rbapply_node(tree, node->left, func, cookie, order)) != 0)
! 289: return error;
! 290: if (order == inorder)
! 291: if ((error = func(node->data, cookie)) != 0)
! 292: return error;
! 293: if ((error = rbapply_node(tree, node->right, func, cookie, order)) != 0)
! 294: return error;
! 295: if (order == postorder)
! 296: if ((error = func(node->data, cookie)) != 0)
! 297: return error;
! 298: }
! 299: return 0;
! 300: }
! 301:
! 302: /*
! 303: * Returns the successor of node, or nil if there is none.
! 304: */
! 305: static struct rbnode *
! 306: rbsuccessor(struct rbtree *tree, struct rbnode *node)
! 307: {
! 308: struct rbnode *succ;
! 309:
! 310: if ((succ = node->right) != rbnil(tree)) {
! 311: while (succ->left != rbnil(tree))
! 312: succ = succ->left;
! 313: } else {
! 314: /* No right child, move up until we find it or hit the root */
! 315: for (succ = node->parent; node == succ->right; succ = succ->parent)
! 316: node = succ;
! 317: if (succ == rbroot(tree))
! 318: succ = rbnil(tree);
! 319: }
! 320: return succ;
! 321: }
! 322:
! 323: /*
! 324: * Recursive portion of rbdestroy().
! 325: */
! 326: static void
! 327: _rbdestroy(struct rbtree *tree, struct rbnode *node, void (*destroy)(void *))
! 328: {
! 329: if (node != rbnil(tree)) {
! 330: _rbdestroy(tree, node->left, destroy);
! 331: _rbdestroy(tree, node->right, destroy);
! 332: if (destroy != NULL)
! 333: destroy(node->data);
! 334: efree(node);
! 335: }
! 336: }
! 337:
! 338: /*
! 339: * Destroy the specified tree, calling the destructor destroy
! 340: * for each node and then freeing the tree itself.
! 341: */
! 342: void
! 343: rbdestroy(struct rbtree *tree, void (*destroy)(void *))
! 344: {
! 345: _rbdestroy(tree, rbfirst(tree), destroy);
! 346: efree(tree);
! 347: }
! 348:
! 349: /*
! 350: * Delete node 'z' from the tree and return its data pointer.
! 351: */
! 352: void *rbdelete(struct rbtree *tree, struct rbnode *z)
! 353: {
! 354: struct rbnode *x, *y;
! 355: void *data = z->data;
! 356:
! 357: if (z->left == rbnil(tree) || z->right == rbnil(tree))
! 358: y = z;
! 359: else
! 360: y = rbsuccessor(tree, z);
! 361: x = (y->left == rbnil(tree)) ? y->right : y->left;
! 362:
! 363: if ((x->parent = y->parent) == rbroot(tree)) {
! 364: rbfirst(tree) = x;
! 365: } else {
! 366: if (y == y->parent->left)
! 367: y->parent->left = x;
! 368: else
! 369: y->parent->right = x;
! 370: }
! 371: if (y->color == black)
! 372: rbrepair(tree, x);
! 373: if (y != z) {
! 374: y->left = z->left;
! 375: y->right = z->right;
! 376: y->parent = z->parent;
! 377: y->color = z->color;
! 378: z->left->parent = z->right->parent = y;
! 379: if (z == z->parent->left)
! 380: z->parent->left = y;
! 381: else
! 382: z->parent->right = y;
! 383: }
! 384: free(z);
! 385:
! 386: return data;
! 387: }
! 388:
! 389: /*
! 390: * Repair the tree after a node has been deleted by rotating and repainting
! 391: * colors to restore the 4 properties inherent in red-black trees.
! 392: */
! 393: static void
! 394: rbrepair(struct rbtree *tree, struct rbnode *node)
! 395: {
! 396: struct rbnode *sibling;
! 397:
! 398: while (node->color == black && node != rbroot(tree)) {
! 399: if (node == node->parent->left) {
! 400: sibling = node->parent->right;
! 401: if (sibling->color == red) {
! 402: sibling->color = black;
! 403: node->parent->color = red;
! 404: rotate_left(tree, node->parent);
! 405: sibling = node->parent->right;
! 406: }
! 407: if (sibling->right->color == black && sibling->left->color == black) {
! 408: sibling->color = red;
! 409: node = node->parent;
! 410: } else {
! 411: if (sibling->right->color == black) {
! 412: sibling->left->color = black;
! 413: sibling->color = red;
! 414: rotate_right(tree, sibling);
! 415: sibling = node->parent->right;
! 416: }
! 417: sibling->color = node->parent->color;
! 418: node->parent->color = black;
! 419: sibling->right->color = black;
! 420: rotate_left(tree, node->parent);
! 421: node = rbroot(tree); /* exit loop */
! 422: }
! 423: } else { /* if (node == node->parent->right) */
! 424: sibling = node->parent->left;
! 425: if (sibling->color == red) {
! 426: sibling->color = black;
! 427: node->parent->color = red;
! 428: rotate_right(tree, node->parent);
! 429: sibling = node->parent->left;
! 430: }
! 431: if (sibling->right->color == black && sibling->left->color == black) {
! 432: sibling->color = red;
! 433: node = node->parent;
! 434: } else {
! 435: if (sibling->left->color == black) {
! 436: sibling->right->color = black;
! 437: sibling->color = red;
! 438: rotate_left(tree, sibling);
! 439: sibling = node->parent->left;
! 440: }
! 441: sibling->color = node->parent->color;
! 442: node->parent->color = black;
! 443: sibling->left->color = black;
! 444: rotate_right(tree, node->parent);
! 445: node = rbroot(tree); /* exit loop */
! 446: }
! 447: }
! 448: }
! 449: node->color = black;
! 450: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to redblack.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / sudo / plugins / sudoers