Annotation of src/usr.bin/sudo/redblack.c, Revision 1.6
1.1 millert 1: /*
1.4 millert 2: * Copyright (c) 2004-2005, 2007,2009 Todd C. Miller <Todd.Miller@courtesan.com>
1.1 millert 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: static void rbrepair __P((struct rbtree *, struct rbnode *));
61: static void rotate_left __P((struct rbtree *, struct rbnode *));
62: static void rotate_right __P((struct rbtree *, struct rbnode *));
63: static 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:
1.4 millert 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
1.1 millert 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: */
88: struct rbtree *
89: rbcreate(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: */
119: static void
120: rotate_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: */
144: static void
145: rotate_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: */
171: struct rbnode *
172: rbinsert(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: */
265: struct rbnode *
266: rbfind(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: */
286: int
287: rbapply_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: */
317: static struct rbnode *
318: rbsuccessor(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: */
340: static 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: */
359: void
360: rbdestroy(tree, destroy)
361: struct rbtree *tree;
362: void (*destroy)__P((void *));
363: {
364: _rbdestroy(tree, rbfirst(tree), destroy);
365: efree(tree);
366: }
367:
368: /*
1.2 millert 369: * Delete node 'z' from the tree and return its data pointer.
1.1 millert 370: */
1.2 millert 371: void *rbdelete(tree, z)
1.4 millert 372: struct rbtree *tree;
373: struct rbnode *z;
1.1 millert 374: {
1.2 millert 375: struct rbnode *x, *y;
376: void *data = z->data;
1.1 millert 377:
1.2 millert 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;
1.1 millert 383:
1.2 millert 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;
1.1 millert 402: else
1.2 millert 403: z->parent->right = y;
1.1 millert 404: }
1.2 millert 405: free(z);
406:
407: return (data);
1.1 millert 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: */
414: static void
415: rbrepair(tree, node)
416: struct rbtree *tree;
417: struct rbnode *node;
418: {
419: struct rbnode *sibling;
420:
1.6 ! millert 421: while (node->color == black && node != rbfirst(tree)) {
1.1 millert 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);
1.6 ! millert 444: node = rbfirst(tree); /* exit loop */
1.1 millert 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);
1.6 ! millert 468: node = rbfirst(tree); /* exit loop */
1.1 millert 469: }
470: }
471: }
1.4 millert 472: node->color = black;
1.1 millert 473: }
![[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