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