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