Return to redblack.c CVS log | Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / sudo / plugins / sudoers |
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: }