2 * Copyright (c) 2004-2005, 2007,2009 Todd C. Miller <Todd.Miller@courtesan.com>
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.
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.
18 * Adapted from the following code written by Emin Martinian:
19 * http://web.mit.edu/~emin/www/source_code/red_black_tree/index.html
21 * Copyright (c) 2001 Emin Martinian
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
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.
44 #include <sys/types.h>
45 #include <sys/param.h>
55 #endif /* STDC_HEADERS */
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 *,
67 * Red-Black tree, see http://en.wikipedia.org/wiki/Red-black_tree
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
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
81 * number of black nodes.
85 * Create a red black tree struct using the specified compare routine.
86 * Allocates and returns the initialized (empty) tree.
90 int (*compar)__P((const void *, const void*));
94 tree = (struct rbtree *) emalloc(sizeof(*tree));
95 tree->compar = compar;
98 * We use a self-referencing sentinel node called nil to simplify the
99 * code by avoiding the need to check for NULL pointers.
101 tree->nil.left = tree->nil.right = tree->nil.parent = &tree->nil;
102 tree->nil.color = black;
103 tree->nil.data = NULL;
106 * Similarly, the fake root node keeps us from having to worry
107 * about splitting the root.
109 tree->root.left = tree->root.right = tree->root.parent = &tree->nil;
110 tree->root.color = black;
111 tree->root.data = NULL;
117 * Perform a left rotation starting at node.
120 rotate_left(tree, node)
124 struct rbnode *child;
127 node->right = child->left;
129 if (child->left != rbnil(tree))
130 child->left->parent = node;
131 child->parent = node->parent;
133 if (node == node->parent->left)
134 node->parent->left = child;
136 node->parent->right = child;
138 node->parent = child;
142 * Perform a right rotation starting at node.
145 rotate_right(tree, node)
149 struct rbnode *child;
152 node->left = child->right;
154 if (child->right != rbnil(tree))
155 child->right->parent = node;
156 child->parent = node->parent;
158 if (node == node->parent->left)
159 node->parent->left = child;
161 node->parent->right = child;
163 node->parent = child;
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.
176 struct rbnode *node = rbfirst(tree);
177 struct rbnode *parent = rbroot(tree);
180 /* Find correct insertion point. */
181 while (node != rbnil(tree)) {
183 if ((res = tree->compar(data, node->data)) == 0)
185 node = res < 0 ? node->left : node->right;
188 node = (struct rbnode *) emalloc(sizeof(*node));
190 node->left = node->right = rbnil(tree);
191 node->parent = parent;
192 if (parent == rbroot(tree) || tree->compar(data, parent->data) < 0)
195 parent->right = node;
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
204 * 1) The uncle is red. We repaint both the parent and uncle black
205 * and repaint the grandparent node red.
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.
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.
218 * Note that because we use a sentinel for the root node we never
219 * need to worry about replacing the root.
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) {
233 rotate_left(tree, node);
235 node->parent->color = black;
236 node->parent->parent->color = red;
237 rotate_right(tree, node->parent->parent);
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) {
249 rotate_right(tree, node);
251 node->parent->color = black;
252 node->parent->parent->color = red;
253 rotate_left(tree, node->parent->parent);
257 rbfirst(tree)->color = black; /* first node is always black */
262 * Look for a node matching key in tree.
263 * Returns a pointer to the node if found, else NULL.
270 struct rbnode *node = rbfirst(tree);
273 while (node != rbnil(tree)) {
274 if ((res = tree->compar(key, node->data)) == 0)
276 node = res < 0 ? node->left : node->right;
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.
287 rbapply_node(tree, node, func, cookie, order)
290 int (*func)__P((void *, void *));
292 enum rbtraversal order;
296 if (node != rbnil(tree)) {
297 if (order == preorder)
298 if ((error = func(node->data, cookie)) != 0)
300 if ((error = rbapply_node(tree, node->left, func, cookie, order)) != 0)
302 if (order == inorder)
303 if ((error = func(node->data, cookie)) != 0)
305 if ((error = rbapply_node(tree, node->right, func, cookie, order)) != 0)
307 if (order == postorder)
308 if ((error = func(node->data, cookie)) != 0)
315 * Returns the successor of node, or nil if there is none.
317 static struct rbnode *
318 rbsuccessor(tree, node)
324 if ((succ = node->right) != rbnil(tree)) {
325 while (succ->left != rbnil(tree))
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)
331 if (succ == rbroot(tree))
338 * Recursive portion of rbdestroy().
341 _rbdestroy(tree, node, destroy)
344 void (*destroy)__P((void *));
346 if (node != rbnil(tree)) {
347 _rbdestroy(tree, node->left, destroy);
348 _rbdestroy(tree, node->right, destroy);
356 * Destroy the specified tree, calling the destructor destroy
357 * for each node and then freeing the tree itself.
360 rbdestroy(tree, destroy)
362 void (*destroy)__P((void *));
364 _rbdestroy(tree, rbfirst(tree), destroy);
369 * Delete node 'z' from the tree and return its data pointer.
371 void *rbdelete(tree, z)
375 struct rbnode *x, *y;
376 void *data = z->data;
378 if (z->left == rbnil(tree) || z->right == rbnil(tree))
381 y = rbsuccessor(tree, z);
382 x = (y->left == rbnil(tree)) ? y->right : y->left;
384 if ((x->parent = y->parent) == rbroot(tree)) {
387 if (y == y->parent->left)
390 y->parent->right = x;
392 if (y->color == black)
397 y->parent = z->parent;
399 z->left->parent = z->right->parent = y;
400 if (z == z->parent->left)
403 z->parent->right = y;
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.
419 struct rbnode *sibling;
421 while (node->color == black && node != rbroot(tree)) {
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;
430 if (sibling->right->color == black && sibling->left->color == black) {
431 sibling->color = red;
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;
440 sibling->color = node->parent->color;
441 node->parent->color = black;
442 sibling->right->color = black;
443 rotate_left(tree, node->parent);
444 node = rbroot(tree); /* exit loop */
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;
454 if (sibling->right->color == black && sibling->left->color == black) {
455 sibling->color = red;
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;
464 sibling->color = node->parent->color;
465 node->parent->color = black;
466 sibling->left->color = black;
467 rotate_right(tree, node->parent);
468 node = rbroot(tree); /* exit loop */