2 * Copyright (c) 2008 - 2010 Jason Evans <jasone@FreeBSD.org>
3 * Copyright (c) 2011 Your File System Inc.
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR `AS IS'' AND ANY EXPRESS OR
16 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
17 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
18 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
19 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
20 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
21 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
22 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
24 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 /* Left-leaning rbtree implementation. Originally derived from the FreeBSD
28 * CPP macro definitions by Jason Evans, but extensively modified to
29 * *) Be function, rather than macro based
30 * *) Use parent pointers, rather than calling an embeded comparison fn
31 * *) Use 'NULL' to represent empty nodes, rather than a magic pointer
34 #include <afsconfig.h>
35 #include <afs/param.h>
38 # include "afs/sysincludes.h"
39 # include "afsincludes.h"
47 struct opr_rbtree_node *left;
48 struct opr_rbtree_node *right;
49 struct opr_rbtree_node *parent;
54 struct opr_rbtree_node *root;
57 /* Update the parent pointers for a node which is being replaced.
59 * If the original node had no parent, then it was the root of the tree,
60 * and the replacement is too.
61 * Otherwise, the original node must have been either the left or right
62 * child of its parent, so update the left (or right) pointer to point
63 * to the replacement as appropriate.
67 update_parent_ptr(struct opr_rbtree *head, struct opr_rbtree_node *old,
68 struct opr_rbtree_node *replacement)
71 if (old->parent->left == old)
72 old->parent->left = replacement;
74 old->parent->right = replacement;
76 head->root = replacement;
80 opr_rbtree_init(struct opr_rbtree *head)
85 struct opr_rbtree_node *
86 opr_rbtree_first(struct opr_rbtree *head)
88 struct opr_rbtree_node *node;
94 while (node->left != NULL)
100 struct opr_rbtree_node *
101 opr_rbtree_last(struct opr_rbtree *head)
103 struct opr_rbtree_node *node;
110 while (node->right != NULL)
117 struct opr_rbtree_node *
118 opr_rbtree_next(struct opr_rbtree_node *node)
120 struct opr_rbtree_node *parent;
122 /* Where there is a right child, the next node is to the right, then
123 * left as far as we can go */
124 if (node->right != NULL) {
126 while (node->left != NULL)
132 /* If there is no right hand child, then the next node is above us.
133 * Whenever our ancestor is a right-hand child, the next node is
134 * further up. When it is a left-hand child, it is our next node
136 while ((parent = node->parent) != NULL && node == parent->right)
142 struct opr_rbtree_node *
143 opr_rbtree_prev(struct opr_rbtree_node *node)
145 struct opr_rbtree_node *parent;
147 if (node->left != NULL) {
149 while (node->right != NULL)
155 /* Same ancestor logic as for 'next', but in reverse */
156 while ((parent = node->parent) != NULL && node == parent->left)
163 initnode(struct opr_rbtree_node *node)
165 node->left = node->right = node->parent = NULL;
170 rotateright(struct opr_rbtree *head, struct opr_rbtree_node *node)
172 struct opr_rbtree_node *left = node->left;
174 node->left = left->right;
176 left->right->parent = node;
179 left->parent = node->parent;
181 update_parent_ptr(head, node, left);
187 rotateleft(struct opr_rbtree *head, struct opr_rbtree_node *node)
189 struct opr_rbtree_node *right = node->right;
191 node->right = right->left;
193 right->left->parent = node;
196 right->parent = node->parent;
198 update_parent_ptr(head, node, right);
200 node->parent = right;
204 swapnode(struct opr_rbtree_node **a, struct opr_rbtree_node **b)
206 struct opr_rbtree_node *tmp;
214 insert_recolour(struct opr_rbtree *head, struct opr_rbtree_node *node)
216 struct opr_rbtree_node *parent, *gramps;
218 while ((parent = node->parent) && parent->red) {
219 gramps = parent->parent;
221 if (parent == gramps->left) {
222 struct opr_rbtree_node *uncle = gramps->right;
224 if (uncle && uncle->red) {
232 if (parent->right == node) {
233 rotateleft(head, parent);
234 swapnode(&parent, &node);
239 rotateright(head, gramps);
241 struct opr_rbtree_node *uncle = gramps->left;
243 if (uncle && uncle->red) {
251 if (parent->left == node) {
252 rotateright(head, parent);
253 swapnode(&parent, &node);
258 rotateleft(head, gramps);
266 opr_rbtree_insert(struct opr_rbtree *head,
267 struct opr_rbtree_node *parent,
268 struct opr_rbtree_node **childptr,
269 struct opr_rbtree_node *node)
271 /* Link node 'node' into the tree at position 'parent', using either the
272 * left or right pointers */
274 node->parent = parent;
275 node->left = node->right = NULL;
279 /* Rebalance the tree for the newly inserted node */
280 insert_recolour(head, node);
284 remove_recolour(struct opr_rbtree *head, struct opr_rbtree_node *parent,
285 struct opr_rbtree_node *node)
287 struct opr_rbtree_node *other;
289 while ((node == NULL || !node->red) && node != head->root) {
290 if (parent->left == node) {
291 other = parent->right;
295 rotateleft(head, parent);
296 other = parent->right;
298 if ((other->left == NULL || !other->left->red) &&
299 (other->right == NULL || !other->right->red)) {
302 parent = node->parent;
304 if (other->right == NULL || !other->right->red) {
305 other->left->red = 0;
307 rotateright(head, other);
308 other = parent->right;
310 other->red = parent->red;
312 other->right->red = 0;
313 rotateleft(head, parent);
318 other = parent->left;
322 rotateright(head, parent);
323 other = parent->left;
325 if ((other->left == NULL || !other->left->red) &&
326 (other->right == NULL || !other->right->red)) {
329 parent = node->parent;
331 if (other->left == NULL || !other->left->red) {
332 other->right->red = 0;
334 rotateleft(head, other);
335 other = parent->left;
337 other->red = parent->red;
339 other->left->red = 0;
340 rotateright(head, parent);
351 opr_rbtree_remove(struct opr_rbtree *head, struct opr_rbtree_node *node)
353 struct opr_rbtree_node *child, *parent;
357 if (node->left == NULL && node->right == NULL) {
358 /* A node with no non-leaf children */
359 update_parent_ptr(head, node, NULL);
362 remove_recolour(head, node->parent, NULL);
367 if (node->left != NULL && node->right != NULL) {
368 /* A node with two children.
370 * Move the next node in the tree (which will be a leaf node)
371 * onto our tree current position, then rebalance as required
373 struct opr_rbtree_node *old, *left;
377 /* Set node to the next node in the tree from the current
378 * position, where the next node is the left-most leaf node
379 * in our right child */
381 while ((left = node->left) != NULL)
384 /* Move 'node' into the position occupied by 'old', which is being
387 update_parent_ptr(head, old, node);
390 parent = node->parent;
393 /* As we're logically just copying the value, must preserve the
394 * old node's colour */
395 node->red = old->red;
397 /* ... and the old node's linkage */
402 child->parent = parent;
403 parent->left = child;
405 node->right = old->right;
406 old->right->parent = node;
409 node->parent = old->parent;
410 node->left = old->left;
411 old->left->parent = node;
413 /* If the node being removed was black, then we must recolour the
414 * tree to maintain balance */
416 remove_recolour(head, parent, child);
421 /* Only remaining option - node with a single child */
423 if (node->left == NULL)
425 else if (node->right == NULL)
428 child->parent = node->parent;
430 update_parent_ptr(head, node, child);
433 remove_recolour(head, node->parent, child);
437 opr_rbtree_replace(struct opr_rbtree *head,
438 struct opr_rbtree_node *old,
439 struct opr_rbtree_node *replacement)
441 /* Update our parent's pointer to us */
442 update_parent_ptr(head, old, replacement);
444 /* And our children's pointers to us */
446 old->left->parent = replacement;
448 old->right->parent = replacement;
450 /* Copy over parent, left, right and colour */