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 rotateright(struct opr_rbtree
*head
, struct opr_rbtree_node
*node
)
165 struct opr_rbtree_node
*left
= node
->left
;
167 node
->left
= left
->right
;
169 left
->right
->parent
= node
;
172 left
->parent
= node
->parent
;
174 update_parent_ptr(head
, node
, left
);
180 rotateleft(struct opr_rbtree
*head
, struct opr_rbtree_node
*node
)
182 struct opr_rbtree_node
*right
= node
->right
;
184 node
->right
= right
->left
;
186 right
->left
->parent
= node
;
189 right
->parent
= node
->parent
;
191 update_parent_ptr(head
, node
, right
);
193 node
->parent
= right
;
197 swapnode(struct opr_rbtree_node
**a
, struct opr_rbtree_node
**b
)
199 struct opr_rbtree_node
*tmp
;
207 insert_recolour(struct opr_rbtree
*head
, struct opr_rbtree_node
*node
)
209 struct opr_rbtree_node
*parent
, *gramps
;
211 while ((parent
= node
->parent
) && parent
->red
) {
212 gramps
= parent
->parent
;
214 if (parent
== gramps
->left
) {
215 struct opr_rbtree_node
*uncle
= gramps
->right
;
217 if (uncle
&& uncle
->red
) {
225 if (parent
->right
== node
) {
226 rotateleft(head
, parent
);
227 swapnode(&parent
, &node
);
232 rotateright(head
, gramps
);
234 struct opr_rbtree_node
*uncle
= gramps
->left
;
236 if (uncle
&& uncle
->red
) {
244 if (parent
->left
== node
) {
245 rotateright(head
, parent
);
246 swapnode(&parent
, &node
);
251 rotateleft(head
, gramps
);
259 opr_rbtree_insert(struct opr_rbtree
*head
,
260 struct opr_rbtree_node
*parent
,
261 struct opr_rbtree_node
**childptr
,
262 struct opr_rbtree_node
*node
)
264 /* Link node 'node' into the tree at position 'parent', using either the
265 * left or right pointers */
267 node
->parent
= parent
;
268 node
->left
= node
->right
= NULL
;
272 /* Rebalance the tree for the newly inserted node */
273 insert_recolour(head
, node
);
277 remove_recolour(struct opr_rbtree
*head
, struct opr_rbtree_node
*parent
,
278 struct opr_rbtree_node
*node
)
280 struct opr_rbtree_node
*other
;
282 while ((node
== NULL
|| !node
->red
) && node
!= head
->root
) {
283 if (parent
->left
== node
) {
284 other
= parent
->right
;
288 rotateleft(head
, parent
);
289 other
= parent
->right
;
291 if ((other
->left
== NULL
|| !other
->left
->red
) &&
292 (other
->right
== NULL
|| !other
->right
->red
)) {
295 parent
= node
->parent
;
297 if (other
->right
== NULL
|| !other
->right
->red
) {
298 other
->left
->red
= 0;
300 rotateright(head
, other
);
301 other
= parent
->right
;
303 other
->red
= parent
->red
;
305 other
->right
->red
= 0;
306 rotateleft(head
, parent
);
311 other
= parent
->left
;
315 rotateright(head
, parent
);
316 other
= parent
->left
;
318 if ((other
->left
== NULL
|| !other
->left
->red
) &&
319 (other
->right
== NULL
|| !other
->right
->red
)) {
322 parent
= node
->parent
;
324 if (other
->left
== NULL
|| !other
->left
->red
) {
325 other
->right
->red
= 0;
327 rotateleft(head
, other
);
328 other
= parent
->left
;
330 other
->red
= parent
->red
;
332 other
->left
->red
= 0;
333 rotateright(head
, parent
);
344 opr_rbtree_remove(struct opr_rbtree
*head
, struct opr_rbtree_node
*node
)
346 struct opr_rbtree_node
*child
, *parent
;
350 if (node
->left
== NULL
&& node
->right
== NULL
) {
351 /* A node with no non-leaf children */
352 update_parent_ptr(head
, node
, NULL
);
355 remove_recolour(head
, node
->parent
, NULL
);
360 if (node
->left
!= NULL
&& node
->right
!= NULL
) {
361 /* A node with two children.
363 * Move the next node in the tree (which will be a leaf node)
364 * onto our tree current position, then rebalance as required
366 struct opr_rbtree_node
*old
, *left
;
370 /* Set node to the next node in the tree from the current
371 * position, where the next node is the left-most leaf node
372 * in our right child */
374 while ((left
= node
->left
) != NULL
)
377 /* Move 'node' into the position occupied by 'old', which is being
380 update_parent_ptr(head
, old
, node
);
383 parent
= node
->parent
;
386 /* As we're logically just copying the value, must preserve the
387 * old node's colour */
388 node
->red
= old
->red
;
390 /* ... and the old node's linkage */
395 child
->parent
= parent
;
396 parent
->left
= child
;
398 node
->right
= old
->right
;
399 old
->right
->parent
= node
;
402 node
->parent
= old
->parent
;
403 node
->left
= old
->left
;
404 old
->left
->parent
= node
;
406 /* If the node being removed was black, then we must recolour the
407 * tree to maintain balance */
409 remove_recolour(head
, parent
, child
);
414 /* Only remaining option - node with a single child */
416 if (node
->left
== NULL
)
421 child
->parent
= node
->parent
;
423 update_parent_ptr(head
, node
, child
);
426 remove_recolour(head
, node
->parent
, child
);
430 opr_rbtree_replace(struct opr_rbtree
*head
,
431 struct opr_rbtree_node
*old
,
432 struct opr_rbtree_node
*replacement
)
434 /* Update our parent's pointer to us */
435 update_parent_ptr(head
, old
, replacement
);
437 /* And our children's pointers to us */
439 old
->left
->parent
= replacement
;
441 old
->right
->parent
= replacement
;
443 /* Copy over parent, left, right and colour */