Annotation of src/usr.bin/sudo/redblack.c, Revision 1.3
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: *
1.2 millert 21: * Copyright (c) 2001 Emin Martinian
22: *
1.1 millert 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:
60: #ifndef lint
1.3 ! millert 61: __unused static const char rcsid[] = "$Sudo: redblack.c,v 1.11 2009/06/26 20:40:17 millert Exp $";
1.1 millert 62: #endif /* lint */
63:
64: static void rbrepair __P((struct rbtree *, struct rbnode *));
65: static void rotate_left __P((struct rbtree *, struct rbnode *));
66: static void rotate_right __P((struct rbtree *, struct rbnode *));
67: static void _rbdestroy __P((struct rbtree *, struct rbnode *,
68: void (*)(void *)));
69:
70: /*
71: * Red-Black tree, see http://en.wikipedia.org/wiki/Red-black_tree
72: *
73: * A red-black tree is a binary search tree where each node has a color
74: * attribute, the value of which is either red or black. Essentially, it
75: * is just a convenient way to express a 2-3-4 binary search tree where
76: * the color indicates whether the node is part of a 3-node or a 4-node.
77: * In addition to the ordinary requirements imposed on binary search
78: * trees, we make the following additional requirements of any valid
79: * red-black tree:
80: * 1) The root is black.
81: * 2) All leaves are black.
82: * 3) Both children of each red node are black.
83: * 4) The paths from each leaf up to the root each contain the same
84: * number of black nodes.
85: */
86:
87: /*
88: * Create a red black tree struct using the specified compare routine.
89: * Allocates and returns the initialized (empty) tree.
90: */
91: struct rbtree *
92: rbcreate(compar)
93: int (*compar)__P((const void *, const void*));
94: {
95: struct rbtree *tree;
96:
97: tree = (struct rbtree *) emalloc(sizeof(*tree));
98: tree->compar = compar;
99:
100: /*
101: * We use a self-referencing sentinel node called nil to simplify the
102: * code by avoiding the need to check for NULL pointers.
103: */
104: tree->nil.left = tree->nil.right = tree->nil.parent = &tree->nil;
105: tree->nil.color = black;
106: tree->nil.data = NULL;
107:
108: /*
109: * Similarly, the fake root node keeps us from having to worry
110: * about splitting the root.
111: */
112: tree->root.left = tree->root.right = tree->root.parent = &tree->nil;
113: tree->root.color = black;
114: tree->root.data = NULL;
115:
116: return(tree);
117: }
118:
119: /*
120: * Perform a left rotation starting at node.
121: */
122: static void
123: rotate_left(tree, node)
124: struct rbtree *tree;
125: struct rbnode *node;
126: {
127: struct rbnode *child;
128:
129: child = node->right;
130: node->right = child->left;
131:
132: if (child->left != rbnil(tree))
133: child->left->parent = node;
134: child->parent = node->parent;
135:
136: if (node == node->parent->left)
137: node->parent->left = child;
138: else
139: node->parent->right = child;
140: child->left = node;
141: node->parent = child;
142: }
143:
144: /*
145: * Perform a right rotation starting at node.
146: */
147: static void
148: rotate_right(tree, node)
149: struct rbtree *tree;
150: struct rbnode *node;
151: {
152: struct rbnode *child;
153:
154: child = node->left;
155: node->left = child->right;
156:
157: if (child->right != rbnil(tree))
158: child->right->parent = node;
159: child->parent = node->parent;
160:
161: if (node == node->parent->left)
162: node->parent->left = child;
163: else
164: node->parent->right = child;
165: child->right = node;
166: node->parent = child;
167: }
168:
169: /*
170: * Insert data pointer into a redblack tree.
171: * Returns a NULL pointer on success. If a node matching "data"
172: * already exists, a pointer to the existant node is returned.
173: */
174: struct rbnode *
175: rbinsert(tree, data)
176: struct rbtree *tree;
177: void *data;
178: {
179: struct rbnode *node = rbfirst(tree);
180: struct rbnode *parent = rbroot(tree);
181: int res;
182:
183: /* Find correct insertion point. */
184: while (node != rbnil(tree)) {
185: parent = node;
186: if ((res = tree->compar(data, node->data)) == 0)
187: return(node);
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 */
261: return(NULL);
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(tree, key)
270: struct rbtree *tree;
271: void *key;
272: {
273: struct rbnode *node = rbfirst(tree);
274: int res;
275:
276: while (node != rbnil(tree)) {
277: if ((res = tree->compar(key, node->data)) == 0)
278: return(node);
279: node = res < 0 ? node->left : node->right;
280: }
281: return(NULL);
282: }
283:
284: /*
285: * Call func() for each node, passing it the node data and a cookie;
286: * If func() returns non-zero for a node, the traversal stops and the
287: * error value is returned. Returns 0 on successful traversal.
288: */
289: int
290: rbapply_node(tree, node, func, cookie, order)
291: struct rbtree *tree;
292: struct rbnode *node;
293: int (*func)__P((void *, void *));
294: void *cookie;
295: enum rbtraversal order;
296: {
297: int error;
298:
299: if (node != rbnil(tree)) {
300: if (order == preorder)
301: if ((error = func(node->data, cookie)) != 0)
302: return(error);
303: if ((error = rbapply_node(tree, node->left, func, cookie, order)) != 0)
304: return(error);
305: if (order == inorder)
306: if ((error = func(node->data, cookie)) != 0)
307: return(error);
308: if ((error = rbapply_node(tree, node->right, func, cookie, order)) != 0)
309: return(error);
310: if (order == postorder)
311: if ((error = func(node->data, cookie)) != 0)
312: return(error);
313: }
314: return (0);
315: }
316:
317: /*
318: * Returns the successor of node, or nil if there is none.
319: */
320: static struct rbnode *
321: rbsuccessor(tree, node)
322: struct rbtree *tree;
323: struct rbnode *node;
324: {
325: struct rbnode *succ;
326:
327: if ((succ = node->right) != rbnil(tree)) {
328: while (succ->left != rbnil(tree))
329: succ = succ->left;
330: } else {
331: /* No right child, move up until we find it or hit the root */
332: for (succ = node->parent; node == succ->right; succ = succ->parent)
333: node = succ;
334: if (succ == rbroot(tree))
335: succ = rbnil(tree);
336: }
337: return(succ);
338: }
339:
340: /*
341: * Recursive portion of rbdestroy().
342: */
343: static void
344: _rbdestroy(tree, node, destroy)
345: struct rbtree *tree;
346: struct rbnode *node;
347: void (*destroy)__P((void *));
348: {
349: if (node != rbnil(tree)) {
350: _rbdestroy(tree, node->left, destroy);
351: _rbdestroy(tree, node->right, destroy);
352: if (destroy != NULL)
353: destroy(node->data);
354: efree(node);
355: }
356: }
357:
358: /*
359: * Destroy the specified tree, calling the destructor destroy
360: * for each node and then freeing the tree itself.
361: */
362: void
363: rbdestroy(tree, destroy)
364: struct rbtree *tree;
365: void (*destroy)__P((void *));
366: {
367: _rbdestroy(tree, rbfirst(tree), destroy);
368: efree(tree);
369: }
370:
371: /*
1.2 millert 372: * Delete node 'z' from the tree and return its data pointer.
1.1 millert 373: */
1.2 millert 374: void *rbdelete(tree, z)
375: struct rbtree* tree;
376: struct rbnode* z;
1.1 millert 377: {
1.2 millert 378: struct rbnode *x, *y;
379: void *data = z->data;
1.1 millert 380:
1.2 millert 381: if (z->left == rbnil(tree) || z->right == rbnil(tree))
382: y = z;
383: else
384: y = rbsuccessor(tree, z);
385: x = (y->left == rbnil(tree)) ? y->right : y->left;
1.1 millert 386:
1.2 millert 387: if ((x->parent = y->parent) == rbroot(tree)) {
388: rbfirst(tree) = x;
389: } else {
390: if (y == y->parent->left)
391: y->parent->left = x;
392: else
393: y->parent->right = x;
394: }
395: if (y->color == black)
396: rbrepair(tree, x);
397: if (y != z) {
398: y->left = z->left;
399: y->right = z->right;
400: y->parent = z->parent;
401: y->color = z->color;
402: z->left->parent = z->right->parent = y;
403: if (z == z->parent->left)
404: z->parent->left = y;
1.1 millert 405: else
1.2 millert 406: z->parent->right = y;
1.1 millert 407: }
1.2 millert 408: free(z);
409:
410: return (data);
1.1 millert 411: }
412:
413: /*
414: * Repair the tree after a node has been deleted by rotating and repainting
415: * colors to restore the 4 properties inherent in red-black trees.
416: */
417: static void
418: rbrepair(tree, node)
419: struct rbtree *tree;
420: struct rbnode *node;
421: {
422: struct rbnode *sibling;
423:
1.3 ! millert 424: while (node->color == black && node != rbroot(tree)) {
1.1 millert 425: if (node == node->parent->left) {
426: sibling = node->parent->right;
427: if (sibling->color == red) {
428: sibling->color = black;
429: node->parent->color = red;
430: rotate_left(tree, node->parent);
431: sibling = node->parent->right;
432: }
433: if (sibling->right->color == black && sibling->left->color == black) {
434: sibling->color = red;
435: node = node->parent;
436: } else {
437: if (sibling->right->color == black) {
438: sibling->left->color = black;
439: sibling->color = red;
440: rotate_right(tree, sibling);
441: sibling = node->parent->right;
442: }
443: sibling->color = node->parent->color;
444: node->parent->color = black;
445: sibling->right->color = black;
446: rotate_left(tree, node->parent);
1.2 millert 447: break;
1.1 millert 448: }
449: } else { /* if (node == node->parent->right) */
450: sibling = node->parent->left;
451: if (sibling->color == red) {
452: sibling->color = black;
453: node->parent->color = red;
454: rotate_right(tree, node->parent);
455: sibling = node->parent->left;
456: }
457: if (sibling->right->color == black && sibling->left->color == black) {
458: sibling->color = red;
459: node = node->parent;
460: } else {
461: if (sibling->left->color == black) {
462: sibling->right->color = black;
463: sibling->color = red;
464: rotate_left(tree, sibling);
465: sibling = node->parent->left;
466: }
467: sibling->color = node->parent->color;
468: node->parent->color = black;
469: sibling->left->color = black;
470: rotate_right(tree, node->parent);
1.2 millert 471: break;
1.1 millert 472: }
473: }
474: }
475: }
![[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