Annotation of embedaddon/sudo/plugins/sudoers/redblack.c, revision 1.1.1.2
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"
1.1.1.2 ! misho 60: #include "sudo_debug.h"
1.1 misho 61: #include "redblack.h"
62:
63: static void rbrepair(struct rbtree *, struct rbnode *);
64: static void rotate_left(struct rbtree *, struct rbnode *);
65: static void rotate_right(struct rbtree *, struct rbnode *);
66: static void _rbdestroy(struct rbtree *, struct rbnode *, 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) Every node is either red or black.
79: * 2) The root is black.
80: * 3) All leaves are black.
81: * 4) Both children of each red node are black.
82: * 5) The paths from each leaf up to the root each contain the same
83: * number of black nodes.
84: */
85:
86: /*
87: * Create a red black tree struct using the specified compare routine.
88: * Allocates and returns the initialized (empty) tree.
89: */
90: struct rbtree *
91: rbcreate(int (*compar)(const void *, const void*))
92: {
93: struct rbtree *tree;
1.1.1.2 ! misho 94: debug_decl(rbcreate, SUDO_DEBUG_RBTREE)
1.1 misho 95:
96: tree = (struct rbtree *) emalloc(sizeof(*tree));
97: tree->compar = compar;
98:
99: /*
100: * We use a self-referencing sentinel node called nil to simplify the
101: * code by avoiding the need to check for NULL pointers.
102: */
103: tree->nil.left = tree->nil.right = tree->nil.parent = &tree->nil;
104: tree->nil.color = black;
105: tree->nil.data = NULL;
106:
107: /*
108: * Similarly, the fake root node keeps us from having to worry
109: * about splitting the root.
110: */
111: tree->root.left = tree->root.right = tree->root.parent = &tree->nil;
112: tree->root.color = black;
113: tree->root.data = NULL;
114:
1.1.1.2 ! misho 115: debug_return_ptr(tree);
1.1 misho 116: }
117:
118: /*
119: * Perform a left rotation starting at node.
120: */
121: static void
122: rotate_left(struct rbtree *tree, struct rbnode *node)
123: {
124: struct rbnode *child;
1.1.1.2 ! misho 125: debug_decl(rotate_left, SUDO_DEBUG_RBTREE)
1.1 misho 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;
1.1.1.2 ! misho 140:
! 141: debug_return;
1.1 misho 142: }
143:
144: /*
145: * Perform a right rotation starting at node.
146: */
147: static void
148: rotate_right(struct rbtree *tree, struct rbnode *node)
149: {
150: struct rbnode *child;
1.1.1.2 ! misho 151: debug_decl(rotate_right, SUDO_DEBUG_RBTREE)
1.1 misho 152:
153: child = node->left;
154: node->left = child->right;
155:
156: if (child->right != rbnil(tree))
157: child->right->parent = node;
158: child->parent = node->parent;
159:
160: if (node == node->parent->left)
161: node->parent->left = child;
162: else
163: node->parent->right = child;
164: child->right = node;
165: node->parent = child;
1.1.1.2 ! misho 166:
! 167: debug_return;
1.1 misho 168: }
169:
170: /*
171: * Insert data pointer into a redblack tree.
172: * Returns a NULL pointer on success. If a node matching "data"
173: * already exists, a pointer to the existant node is returned.
174: */
175: struct rbnode *
176: rbinsert(struct rbtree *tree, void *data)
177: {
178: struct rbnode *node = rbfirst(tree);
179: struct rbnode *parent = rbroot(tree);
180: int res;
1.1.1.2 ! misho 181: debug_decl(rbinsert, SUDO_DEBUG_RBTREE)
1.1 misho 182:
183: /* Find correct insertion point. */
184: while (node != rbnil(tree)) {
185: parent = node;
186: if ((res = tree->compar(data, node->data)) == 0)
1.1.1.2 ! misho 187: debug_return_ptr(node);
1.1 misho 188: node = res < 0 ? node->left : node->right;
189: }
190:
191: node = (struct rbnode *) emalloc(sizeof(*node));
192: node->data = data;
193: node->left = node->right = rbnil(tree);
194: node->parent = parent;
195: if (parent == rbroot(tree) || tree->compar(data, parent->data) < 0)
196: parent->left = node;
197: else
198: parent->right = node;
199: node->color = red;
200:
201: /*
202: * If the parent node is black we are all set, if it is red we have
203: * the following possible cases to deal with. We iterate through
204: * the rest of the tree to make sure none of the required properties
205: * is violated.
206: *
207: * 1) The uncle is red. We repaint both the parent and uncle black
208: * and repaint the grandparent node red.
209: *
210: * 2) The uncle is black and the new node is the right child of its
211: * parent, and the parent in turn is the left child of its parent.
212: * We do a left rotation to switch the roles of the parent and
213: * child, relying on further iterations to fixup the old parent.
214: *
215: * 3) The uncle is black and the new node is the left child of its
216: * parent, and the parent in turn is the left child of its parent.
217: * We switch the colors of the parent and grandparent and perform
218: * a right rotation around the grandparent. This makes the former
219: * parent the parent of the new node and the former grandparent.
220: *
221: * Note that because we use a sentinel for the root node we never
222: * need to worry about replacing the root.
223: */
224: while (node->parent->color == red) {
225: struct rbnode *uncle;
226: if (node->parent == node->parent->parent->left) {
227: uncle = node->parent->parent->right;
228: if (uncle->color == red) {
229: node->parent->color = black;
230: uncle->color = black;
231: node->parent->parent->color = red;
232: node = node->parent->parent;
233: } else /* if (uncle->color == black) */ {
234: if (node == node->parent->right) {
235: node = node->parent;
236: rotate_left(tree, node);
237: }
238: node->parent->color = black;
239: node->parent->parent->color = red;
240: rotate_right(tree, node->parent->parent);
241: }
242: } else { /* if (node->parent == node->parent->parent->right) */
243: uncle = node->parent->parent->left;
244: if (uncle->color == red) {
245: node->parent->color = black;
246: uncle->color = black;
247: node->parent->parent->color = red;
248: node = node->parent->parent;
249: } else /* if (uncle->color == black) */ {
250: if (node == node->parent->left) {
251: node = node->parent;
252: rotate_right(tree, node);
253: }
254: node->parent->color = black;
255: node->parent->parent->color = red;
256: rotate_left(tree, node->parent->parent);
257: }
258: }
259: }
260: rbfirst(tree)->color = black; /* first node is always black */
1.1.1.2 ! misho 261: debug_return_ptr(NULL);
1.1 misho 262: }
263:
264: /*
265: * Look for a node matching key in tree.
266: * Returns a pointer to the node if found, else NULL.
267: */
268: struct rbnode *
269: rbfind(struct rbtree *tree, void *key)
270: {
271: struct rbnode *node = rbfirst(tree);
272: int res;
1.1.1.2 ! misho 273: debug_decl(rbfind, SUDO_DEBUG_RBTREE)
1.1 misho 274:
275: while (node != rbnil(tree)) {
276: if ((res = tree->compar(key, node->data)) == 0)
1.1.1.2 ! misho 277: debug_return_ptr(node);
1.1 misho 278: node = res < 0 ? node->left : node->right;
279: }
1.1.1.2 ! misho 280: debug_return_ptr(NULL);
1.1 misho 281: }
282:
283: /*
284: * Call func() for each node, passing it the node data and a cookie;
285: * If func() returns non-zero for a node, the traversal stops and the
286: * error value is returned. Returns 0 on successful traversal.
287: */
288: int
289: rbapply_node(struct rbtree *tree, struct rbnode *node,
290: int (*func)(void *, void *), void *cookie, enum rbtraversal order)
291: {
292: int error;
1.1.1.2 ! misho 293: debug_decl(rbapply_node, SUDO_DEBUG_RBTREE)
1.1 misho 294:
295: if (node != rbnil(tree)) {
296: if (order == preorder)
297: if ((error = func(node->data, cookie)) != 0)
1.1.1.2 ! misho 298: debug_return_int(error);
1.1 misho 299: if ((error = rbapply_node(tree, node->left, func, cookie, order)) != 0)
1.1.1.2 ! misho 300: debug_return_int(error);
1.1 misho 301: if (order == inorder)
302: if ((error = func(node->data, cookie)) != 0)
1.1.1.2 ! misho 303: debug_return_int(error);
1.1 misho 304: if ((error = rbapply_node(tree, node->right, func, cookie, order)) != 0)
1.1.1.2 ! misho 305: debug_return_int(error);
1.1 misho 306: if (order == postorder)
307: if ((error = func(node->data, cookie)) != 0)
1.1.1.2 ! misho 308: debug_return_int(error);
1.1 misho 309: }
1.1.1.2 ! misho 310: debug_return_int(0);
1.1 misho 311: }
312:
313: /*
314: * Returns the successor of node, or nil if there is none.
315: */
316: static struct rbnode *
317: rbsuccessor(struct rbtree *tree, struct rbnode *node)
318: {
319: struct rbnode *succ;
1.1.1.2 ! misho 320: debug_decl(rbsuccessor, SUDO_DEBUG_RBTREE)
1.1 misho 321:
322: if ((succ = node->right) != rbnil(tree)) {
323: while (succ->left != rbnil(tree))
324: succ = succ->left;
325: } else {
326: /* No right child, move up until we find it or hit the root */
327: for (succ = node->parent; node == succ->right; succ = succ->parent)
328: node = succ;
329: if (succ == rbroot(tree))
330: succ = rbnil(tree);
331: }
1.1.1.2 ! misho 332: debug_return_ptr(succ);
1.1 misho 333: }
334:
335: /*
336: * Recursive portion of rbdestroy().
337: */
338: static void
339: _rbdestroy(struct rbtree *tree, struct rbnode *node, void (*destroy)(void *))
340: {
1.1.1.2 ! misho 341: debug_decl(_rbdestroy, SUDO_DEBUG_RBTREE)
1.1 misho 342: if (node != rbnil(tree)) {
343: _rbdestroy(tree, node->left, destroy);
344: _rbdestroy(tree, node->right, destroy);
345: if (destroy != NULL)
346: destroy(node->data);
347: efree(node);
348: }
1.1.1.2 ! misho 349: debug_return;
1.1 misho 350: }
351:
352: /*
353: * Destroy the specified tree, calling the destructor destroy
354: * for each node and then freeing the tree itself.
355: */
356: void
357: rbdestroy(struct rbtree *tree, void (*destroy)(void *))
358: {
1.1.1.2 ! misho 359: debug_decl(rbdestroy, SUDO_DEBUG_RBTREE)
1.1 misho 360: _rbdestroy(tree, rbfirst(tree), destroy);
361: efree(tree);
1.1.1.2 ! misho 362: debug_return;
1.1 misho 363: }
364:
365: /*
366: * Delete node 'z' from the tree and return its data pointer.
367: */
368: void *rbdelete(struct rbtree *tree, struct rbnode *z)
369: {
370: struct rbnode *x, *y;
371: void *data = z->data;
1.1.1.2 ! misho 372: debug_decl(rbdelete, SUDO_DEBUG_RBTREE)
1.1 misho 373:
374: if (z->left == rbnil(tree) || z->right == rbnil(tree))
375: y = z;
376: else
377: y = rbsuccessor(tree, z);
378: x = (y->left == rbnil(tree)) ? y->right : y->left;
379:
380: if ((x->parent = y->parent) == rbroot(tree)) {
381: rbfirst(tree) = x;
382: } else {
383: if (y == y->parent->left)
384: y->parent->left = x;
385: else
386: y->parent->right = x;
387: }
388: if (y->color == black)
389: rbrepair(tree, x);
390: if (y != z) {
391: y->left = z->left;
392: y->right = z->right;
393: y->parent = z->parent;
394: y->color = z->color;
395: z->left->parent = z->right->parent = y;
396: if (z == z->parent->left)
397: z->parent->left = y;
398: else
399: z->parent->right = y;
400: }
401: free(z);
402:
1.1.1.2 ! misho 403: debug_return_ptr(data);
1.1 misho 404: }
405:
406: /*
407: * Repair the tree after a node has been deleted by rotating and repainting
408: * colors to restore the 4 properties inherent in red-black trees.
409: */
410: static void
411: rbrepair(struct rbtree *tree, struct rbnode *node)
412: {
413: struct rbnode *sibling;
1.1.1.2 ! misho 414: debug_decl(rbrepair, SUDO_DEBUG_RBTREE)
1.1 misho 415:
416: while (node->color == black && node != rbroot(tree)) {
417: if (node == node->parent->left) {
418: sibling = node->parent->right;
419: if (sibling->color == red) {
420: sibling->color = black;
421: node->parent->color = red;
422: rotate_left(tree, node->parent);
423: sibling = node->parent->right;
424: }
425: if (sibling->right->color == black && sibling->left->color == black) {
426: sibling->color = red;
427: node = node->parent;
428: } else {
429: if (sibling->right->color == black) {
430: sibling->left->color = black;
431: sibling->color = red;
432: rotate_right(tree, sibling);
433: sibling = node->parent->right;
434: }
435: sibling->color = node->parent->color;
436: node->parent->color = black;
437: sibling->right->color = black;
438: rotate_left(tree, node->parent);
439: node = rbroot(tree); /* exit loop */
440: }
441: } else { /* if (node == node->parent->right) */
442: sibling = node->parent->left;
443: if (sibling->color == red) {
444: sibling->color = black;
445: node->parent->color = red;
446: rotate_right(tree, node->parent);
447: sibling = node->parent->left;
448: }
449: if (sibling->right->color == black && sibling->left->color == black) {
450: sibling->color = red;
451: node = node->parent;
452: } else {
453: if (sibling->left->color == black) {
454: sibling->right->color = black;
455: sibling->color = red;
456: rotate_left(tree, sibling);
457: sibling = node->parent->left;
458: }
459: sibling->color = node->parent->color;
460: node->parent->color = black;
461: sibling->left->color = black;
462: rotate_right(tree, node->parent);
463: node = rbroot(tree); /* exit loop */
464: }
465: }
466: }
467: node->color = black;
1.1.1.2 ! misho 468:
! 469: debug_return;
1.1 misho 470: }
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