Annotation of embedaddon/sudo/plugins/sudoers/redblack.c, revision 1.1.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