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"
48 struct opr_rbtree_node *left;
49 struct opr_rbtree_node *right;
50 struct opr_rbtree_node *parent;
55 struct opr_rbtree_node *root;
58 /* Update the parent pointers for a node which is being replaced.
60 * If the original node had no parent, then it was the root of the tree,
61 * and the replacement is too.
62 * Otherwise, the original node must have been either the left or right
63 * child of its parent, so update the left (or right) pointer to point
64 * to the replacement as appropriate.
68 update_parent_ptr(struct opr_rbtree *head, struct opr_rbtree_node *old,
69 struct opr_rbtree_node *replacement)
72 if (old->parent->left == old)
73 old->parent->left = replacement;
75 old->parent->right = replacement;
77 head->root = replacement;
81 opr_rbtree_init(struct opr_rbtree *head)
86 struct opr_rbtree_node *
87 opr_rbtree_first(struct opr_rbtree *head)
89 struct opr_rbtree_node *node;
95 while (node->left != NULL)
101 struct opr_rbtree_node *
102 opr_rbtree_last(struct opr_rbtree *head)
104 struct opr_rbtree_node *node;
111 while (node->right != NULL)
118 struct opr_rbtree_node *
119 opr_rbtree_next(struct opr_rbtree_node *node)
121 struct opr_rbtree_node *parent;
123 /* Where there is a right child, the next node is to the right, then
124 * left as far as we can go */
125 if (node->right != NULL) {
127 while (node->left != NULL)
133 /* If there is no right hand child, then the next node is above us.
134 * Whenever our ancestor is a right-hand child, the next node is
135 * further up. When it is a left-hand child, it is our next node
137 while ((parent = node->parent) != NULL && node == parent->right)
143 struct opr_rbtree_node *
144 opr_rbtree_prev(struct opr_rbtree_node *node)
146 struct opr_rbtree_node *parent;
148 if (node->left != NULL) {
150 while (node->right != NULL)
156 /* Same ancestor logic as for 'next', but in reverse */
157 while ((parent = node->parent) != NULL && node == parent->left)
164 rotateright(struct opr_rbtree *head, struct opr_rbtree_node *node)
166 struct opr_rbtree_node *left = node->left;
168 node->left = left->right;
170 left->right->parent = node;
173 left->parent = node->parent;
175 update_parent_ptr(head, node, left);
181 rotateleft(struct opr_rbtree *head, struct opr_rbtree_node *node)
183 struct opr_rbtree_node *right = node->right;
185 node->right = right->left;
187 right->left->parent = node;
190 right->parent = node->parent;
192 update_parent_ptr(head, node, right);
194 node->parent = right;
198 swapnode(struct opr_rbtree_node **a, struct opr_rbtree_node **b)
200 struct opr_rbtree_node *tmp;
208 insert_recolour(struct opr_rbtree *head, struct opr_rbtree_node *node)
210 struct opr_rbtree_node *parent, *gramps;
212 while ((parent = node->parent) && parent->red) {
213 gramps = parent->parent;
215 if (parent == gramps->left) {
216 struct opr_rbtree_node *uncle = gramps->right;
218 if (uncle && uncle->red) {
226 if (parent->right == node) {
227 rotateleft(head, parent);
228 swapnode(&parent, &node);
233 rotateright(head, gramps);
235 struct opr_rbtree_node *uncle = gramps->left;
237 if (uncle && uncle->red) {
245 if (parent->left == node) {
246 rotateright(head, parent);
247 swapnode(&parent, &node);
252 rotateleft(head, gramps);
260 opr_rbtree_insert(struct opr_rbtree *head,
261 struct opr_rbtree_node *parent,
262 struct opr_rbtree_node **childptr,
263 struct opr_rbtree_node *node)
265 /* Link node 'node' into the tree at position 'parent', using either the
266 * left or right pointers */
268 node->parent = parent;
269 node->left = node->right = NULL;
273 /* Rebalance the tree for the newly inserted node */
274 insert_recolour(head, node);
278 remove_recolour(struct opr_rbtree *head, struct opr_rbtree_node *parent,
279 struct opr_rbtree_node *node)
281 struct opr_rbtree_node *other;
283 while ((node == NULL || !node->red) && node != head->root) {
284 if (parent->left == node) {
285 other = parent->right;
289 rotateleft(head, parent);
290 other = parent->right;
292 if ((other->left == NULL || !other->left->red) &&
293 (other->right == NULL || !other->right->red)) {
296 parent = node->parent;
298 if (other->right == NULL || !other->right->red) {
299 other->left->red = 0;
301 rotateright(head, other);
302 other = parent->right;
304 other->red = parent->red;
306 other->right->red = 0;
307 rotateleft(head, parent);
312 other = parent->left;
316 rotateright(head, parent);
317 other = parent->left;
319 if ((other->left == NULL || !other->left->red) &&
320 (other->right == NULL || !other->right->red)) {
323 parent = node->parent;
325 if (other->left == NULL || !other->left->red) {
326 other->right->red = 0;
328 rotateleft(head, other);
329 other = parent->left;
331 other->red = parent->red;
333 other->left->red = 0;
334 rotateright(head, parent);
345 opr_rbtree_remove(struct opr_rbtree *head, struct opr_rbtree_node *node)
347 struct opr_rbtree_node *child, *parent;
351 if (node->left == NULL && node->right == NULL) {
352 /* A node with no non-leaf children */
353 update_parent_ptr(head, node, NULL);
356 remove_recolour(head, node->parent, NULL);
361 if (node->left != NULL && node->right != NULL) {
362 /* A node with two children.
364 * Move the next node in the tree (which will be a leaf node)
365 * onto our tree current position, then rebalance as required
367 struct opr_rbtree_node *old, *left;
371 /* Set node to the next node in the tree from the current
372 * position, where the next node is the left-most leaf node
373 * in our right child */
375 while ((left = node->left) != NULL)
378 /* Move 'node' into the position occupied by 'old', which is being
381 update_parent_ptr(head, old, node);
384 parent = node->parent;
387 /* As we're logically just copying the value, must preserve the
388 * old node's colour */
389 node->red = old->red;
391 /* ... and the old node's linkage */
396 child->parent = parent;
397 parent->left = child;
399 node->right = old->right;
400 old->right->parent = node;
403 node->parent = old->parent;
404 node->left = old->left;
405 old->left->parent = node;
407 /* If the node being removed was black, then we must recolour the
408 * tree to maintain balance */
410 remove_recolour(head, parent, child);
415 /* Only remaining option - node with a single child */
417 if (node->left == NULL)
420 opr_Assert(node->right == NULL);
424 child->parent = node->parent;
426 update_parent_ptr(head, node, child);
429 remove_recolour(head, node->parent, child);
433 opr_rbtree_replace(struct opr_rbtree *head,
434 struct opr_rbtree_node *old,
435 struct opr_rbtree_node *replacement)
437 /* Update our parent's pointer to us */
438 update_parent_ptr(head, old, replacement);
440 /* And our children's pointers to us */
442 old->left->parent = replacement;
444 old->right->parent = replacement;
446 /* Copy over parent, left, right and colour */