Annotation of src/usr.bin/sudo/redblack.c, Revision 1.1
1.1 ! millert 1: /*
! 2: * Copyright (c) 2004-2005, 2007 Todd C. Miller <Todd.Miller@courtesan.com>
! 3: *
! 4: * Permission to use, copy, modify, and distribute this software for any
! 5: * purpose with or without fee is hereby granted, provided that the above
! 6: * copyright notice and this permission notice appear in all copies.
! 7: *
! 8: * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
! 9: * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
! 10: * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
! 11: * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
! 12: * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
! 13: * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
! 14: * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
! 15: */
! 16:
! 17: /*
! 18: * Adapted from the following code written by Emin Martinian:
! 19: * http://web.mit.edu/~emin/www/source_code/red_black_tree/index.html
! 20: *
! 21: * Redistribution and use in source and binary forms, with or without
! 22: * modification, are permitted provided that neither the name of Emin
! 23: * Martinian nor the names of any contributors are be used to endorse or
! 24: * promote products derived from this software without specific prior
! 25: * written permission.
! 26: *
! 27: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
! 28: * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
! 29: * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
! 30: * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
! 31: * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
! 32: * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
! 33: * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
! 34: * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
! 35: * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
! 36: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
! 37: * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
! 38: */
! 39:
! 40: #include <config.h>
! 41:
! 42: #include <sys/types.h>
! 43: #include <sys/param.h>
! 44:
! 45: #include <stdio.h>
! 46: #ifdef STDC_HEADERS
! 47: # include <stdlib.h>
! 48: # include <stddef.h>
! 49: #else
! 50: # ifdef HAVE_STDLIB_H
! 51: # include <stdlib.h>
! 52: # endif
! 53: #endif /* STDC_HEADERS */
! 54:
! 55: #include "sudo.h"
! 56: #include "redblack.h"
! 57:
! 58: #ifndef lint
! 59: __unused static const char rcsid[] = "$Sudo: redblack.c,v 1.8 2008/11/09 14:13:12 millert Exp $";
! 60: #endif /* lint */
! 61:
! 62: static void rbrepair __P((struct rbtree *, struct rbnode *));
! 63: static void rotate_left __P((struct rbtree *, struct rbnode *));
! 64: static void rotate_right __P((struct rbtree *, struct rbnode *));
! 65: static void _rbdestroy __P((struct rbtree *, struct rbnode *,
! 66: 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) The root is black.
! 79: * 2) All leaves are black.
! 80: * 3) Both children of each red node are black.
! 81: * 4) 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(compar)
! 91: int (*compar)__P((const void *, const void*));
! 92: {
! 93: struct rbtree *tree;
! 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: return(tree);
! 115: }
! 116:
! 117: /*
! 118: * Perform a left rotation starting at node.
! 119: */
! 120: static void
! 121: rotate_left(tree, node)
! 122: struct rbtree *tree;
! 123: struct rbnode *node;
! 124: {
! 125: struct rbnode *child;
! 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:
! 142: /*
! 143: * Perform a right rotation starting at node.
! 144: */
! 145: static void
! 146: rotate_right(tree, node)
! 147: struct rbtree *tree;
! 148: struct rbnode *node;
! 149: {
! 150: struct rbnode *child;
! 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:
! 167: /*
! 168: * Insert data pointer into a redblack tree.
! 169: * Returns a NULL pointer on success. If a node matching "data"
! 170: * already exists, a pointer to the existant node is returned.
! 171: */
! 172: struct rbnode *
! 173: rbinsert(tree, data)
! 174: struct rbtree *tree;
! 175: void *data;
! 176: {
! 177: struct rbnode *node = rbfirst(tree);
! 178: struct rbnode *parent = rbroot(tree);
! 179: int res;
! 180:
! 181: /* Find correct insertion point. */
! 182: while (node != rbnil(tree)) {
! 183: parent = node;
! 184: if ((res = tree->compar(data, node->data)) == 0)
! 185: return(node);
! 186: node = res < 0 ? node->left : node->right;
! 187: }
! 188:
! 189: node = (struct rbnode *) emalloc(sizeof(*node));
! 190: node->data = data;
! 191: node->left = node->right = rbnil(tree);
! 192: node->parent = parent;
! 193: if (parent == rbroot(tree) || tree->compar(data, parent->data) < 0)
! 194: parent->left = node;
! 195: else
! 196: parent->right = node;
! 197: node->color = red;
! 198:
! 199: /*
! 200: * If the parent node is black we are all set, if it is red we have
! 201: * the following possible cases to deal with. We iterate through
! 202: * the rest of the tree to make sure none of the required properties
! 203: * is violated.
! 204: *
! 205: * 1) The uncle is red. We repaint both the parent and uncle black
! 206: * and repaint the grandparent node red.
! 207: *
! 208: * 2) The uncle is black and the new node is the right child of its
! 209: * parent, and the parent in turn is the left child of its parent.
! 210: * We do a left rotation to switch the roles of the parent and
! 211: * child, relying on further iterations to fixup the old parent.
! 212: *
! 213: * 3) The uncle is black and the new node is the left child of its
! 214: * parent, and the parent in turn is the left child of its parent.
! 215: * We switch the colors of the parent and grandparent and perform
! 216: * a right rotation around the grandparent. This makes the former
! 217: * parent the parent of the new node and the former grandparent.
! 218: *
! 219: * Note that because we use a sentinel for the root node we never
! 220: * need to worry about replacing the root.
! 221: */
! 222: while (node->parent->color == red) {
! 223: struct rbnode *uncle;
! 224: if (node->parent == node->parent->parent->left) {
! 225: uncle = node->parent->parent->right;
! 226: if (uncle->color == red) {
! 227: node->parent->color = black;
! 228: uncle->color = black;
! 229: node->parent->parent->color = red;
! 230: node = node->parent->parent;
! 231: } else /* if (uncle->color == black) */ {
! 232: if (node == node->parent->right) {
! 233: node = node->parent;
! 234: rotate_left(tree, node);
! 235: }
! 236: node->parent->color = black;
! 237: node->parent->parent->color = red;
! 238: rotate_right(tree, node->parent->parent);
! 239: }
! 240: } else { /* if (node->parent == node->parent->parent->right) */
! 241: uncle = node->parent->parent->left;
! 242: if (uncle->color == red) {
! 243: node->parent->color = black;
! 244: uncle->color = black;
! 245: node->parent->parent->color = red;
! 246: node = node->parent->parent;
! 247: } else /* if (uncle->color == black) */ {
! 248: if (node == node->parent->left) {
! 249: node = node->parent;
! 250: rotate_right(tree, node);
! 251: }
! 252: node->parent->color = black;
! 253: node->parent->parent->color = red;
! 254: rotate_left(tree, node->parent->parent);
! 255: }
! 256: }
! 257: }
! 258: rbfirst(tree)->color = black; /* first node is always black */
! 259: return(NULL);
! 260: }
! 261:
! 262: /*
! 263: * Look for a node matching key in tree.
! 264: * Returns a pointer to the node if found, else NULL.
! 265: */
! 266: struct rbnode *
! 267: rbfind(tree, key)
! 268: struct rbtree *tree;
! 269: void *key;
! 270: {
! 271: struct rbnode *node = rbfirst(tree);
! 272: int res;
! 273:
! 274: while (node != rbnil(tree)) {
! 275: if ((res = tree->compar(key, node->data)) == 0)
! 276: return(node);
! 277: node = res < 0 ? node->left : node->right;
! 278: }
! 279: return(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(tree, node, func, cookie, order)
! 289: struct rbtree *tree;
! 290: struct rbnode *node;
! 291: int (*func)__P((void *, void *));
! 292: void *cookie;
! 293: enum rbtraversal order;
! 294: {
! 295: int error;
! 296:
! 297: if (node != rbnil(tree)) {
! 298: if (order == preorder)
! 299: if ((error = func(node->data, cookie)) != 0)
! 300: return(error);
! 301: if ((error = rbapply_node(tree, node->left, func, cookie, order)) != 0)
! 302: return(error);
! 303: if (order == inorder)
! 304: if ((error = func(node->data, cookie)) != 0)
! 305: return(error);
! 306: if ((error = rbapply_node(tree, node->right, func, cookie, order)) != 0)
! 307: return(error);
! 308: if (order == postorder)
! 309: if ((error = func(node->data, cookie)) != 0)
! 310: return(error);
! 311: }
! 312: return (0);
! 313: }
! 314:
! 315: /*
! 316: * Returns the successor of node, or nil if there is none.
! 317: */
! 318: static struct rbnode *
! 319: rbsuccessor(tree, node)
! 320: struct rbtree *tree;
! 321: struct rbnode *node;
! 322: {
! 323: struct rbnode *succ;
! 324:
! 325: if ((succ = node->right) != rbnil(tree)) {
! 326: while (succ->left != rbnil(tree))
! 327: succ = succ->left;
! 328: } else {
! 329: /* No right child, move up until we find it or hit the root */
! 330: for (succ = node->parent; node == succ->right; succ = succ->parent)
! 331: node = succ;
! 332: if (succ == rbroot(tree))
! 333: succ = rbnil(tree);
! 334: }
! 335: return(succ);
! 336: }
! 337:
! 338: /*
! 339: * Recursive portion of rbdestroy().
! 340: */
! 341: static void
! 342: _rbdestroy(tree, node, destroy)
! 343: struct rbtree *tree;
! 344: struct rbnode *node;
! 345: void (*destroy)__P((void *));
! 346: {
! 347: if (node != rbnil(tree)) {
! 348: _rbdestroy(tree, node->left, destroy);
! 349: _rbdestroy(tree, node->right, destroy);
! 350: if (destroy != NULL)
! 351: destroy(node->data);
! 352: efree(node);
! 353: }
! 354: }
! 355:
! 356: /*
! 357: * Destroy the specified tree, calling the destructor destroy
! 358: * for each node and then freeing the tree itself.
! 359: */
! 360: void
! 361: rbdestroy(tree, destroy)
! 362: struct rbtree *tree;
! 363: void (*destroy)__P((void *));
! 364: {
! 365: _rbdestroy(tree, rbfirst(tree), destroy);
! 366: efree(tree);
! 367: }
! 368:
! 369: /*
! 370: * Delete victim from tree and return its data pointer.
! 371: */
! 372: void *
! 373: rbdelete(tree, victim)
! 374: struct rbtree *tree;
! 375: struct rbnode *victim;
! 376: {
! 377: struct rbnode *pred, *succ;
! 378: void *data;
! 379:
! 380: if (victim->left != rbnil(tree) && victim->right != rbnil(tree)) {
! 381: succ = rbsuccessor(tree, victim);
! 382: pred = succ->left == rbnil(tree) ? succ->right : succ->left;
! 383: if (succ->parent == rbroot(tree)) {
! 384: pred->parent = rbroot(tree);
! 385: rbfirst(tree) = pred;
! 386: } else {
! 387: if (succ == succ->parent->left)
! 388: succ->parent->left = pred;
! 389: else
! 390: succ->parent->right = pred;
! 391: }
! 392: if ((succ->color == black))
! 393: rbrepair(tree, pred);
! 394:
! 395: succ->left = victim->left;
! 396: succ->right = victim->right;
! 397: succ->parent = victim->parent;
! 398: succ->color = victim->color;
! 399: victim->left->parent = victim->right->parent = succ;
! 400: if (victim == victim->parent->left)
! 401: victim->parent->left = succ;
! 402: else
! 403: victim->parent->right = succ;
! 404: data = victim->data;
! 405: efree(victim);
! 406: } else {
! 407: pred = victim->left == rbnil(tree) ? victim->right : victim->left;
! 408: if (victim->parent == rbroot(tree)) {
! 409: pred->parent = rbroot(tree);
! 410: rbfirst(tree) = pred;
! 411: } else {
! 412: if (victim == victim->parent->left)
! 413: victim->parent->left = pred;
! 414: else
! 415: victim->parent->right = pred;
! 416: }
! 417: if (victim->color == black)
! 418: rbrepair(tree, pred);
! 419: data = victim->data;
! 420: efree(victim);
! 421: }
! 422: return(data);
! 423: }
! 424:
! 425: /*
! 426: * Repair the tree after a node has been deleted by rotating and repainting
! 427: * colors to restore the 4 properties inherent in red-black trees.
! 428: */
! 429: static void
! 430: rbrepair(tree, node)
! 431: struct rbtree *tree;
! 432: struct rbnode *node;
! 433: {
! 434: struct rbnode *sibling;
! 435:
! 436: while (node->color == black && node != rbfirst(tree)) {
! 437: if (node == node->parent->left) {
! 438: sibling = node->parent->right;
! 439: if (sibling->color == red) {
! 440: sibling->color = black;
! 441: node->parent->color = red;
! 442: rotate_left(tree, node->parent);
! 443: sibling = node->parent->right;
! 444: }
! 445: if (sibling->right->color == black && sibling->left->color == black) {
! 446: sibling->color = red;
! 447: node = node->parent;
! 448: } else {
! 449: if (sibling->right->color == black) {
! 450: sibling->left->color = black;
! 451: sibling->color = red;
! 452: rotate_right(tree, sibling);
! 453: sibling = node->parent->right;
! 454: }
! 455: sibling->color = node->parent->color;
! 456: node->parent->color = black;
! 457: sibling->right->color = black;
! 458: rotate_left(tree, node->parent);
! 459: return; /* XXX */
! 460: }
! 461: } else { /* if (node == node->parent->right) */
! 462: sibling = node->parent->left;
! 463: if (sibling->color == red) {
! 464: sibling->color = black;
! 465: node->parent->color = red;
! 466: rotate_right(tree, node->parent);
! 467: sibling = node->parent->left;
! 468: }
! 469: if (sibling->right->color == black && sibling->left->color == black) {
! 470: sibling->color = red;
! 471: node = node->parent;
! 472: } else {
! 473: if (sibling->left->color == black) {
! 474: sibling->right->color = black;
! 475: sibling->color = red;
! 476: rotate_left(tree, sibling);
! 477: sibling = node->parent->left;
! 478: }
! 479: sibling->color = node->parent->color;
! 480: node->parent->color = black;
! 481: sibling->left->color = black;
! 482: rotate_right(tree, node->parent);
! 483: return; /* XXX */
! 484: }
! 485: }
! 486: }
! 487: node->color = black;
! 488: }
![[BACK]](/icons/back.gif){kind=icon}
Return to redblack.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / src / usr.bin / sudo