50e4115b7d59c44fe444a54a8bf6454c6706015b
[openafs.git] / src / opr / rbtree.c
1 /*
2  * Copyright (c) 2008 - 2010 Jason Evans <jasone@FreeBSD.org>
3  * Copyright (c) 2011 Your File System Inc.
4  * All rights reserved.
5  *
6  * Redistribution and use in source and binary forms, with or without
7  * modification, are permitted provided that the following conditions
8  * are met:
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.
14  *
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.
25  */
26
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
32  */
33
34 #include <afsconfig.h>
35 #include <afs/param.h>
36
37 #ifdef KERNEL
38 # include "afs/sysincludes.h"
39 # include "afsincludes.h"
40 #else
41 # include <roken.h>
42 #endif
43 #include <afs/opr.h>
44
45 #include "rbtree.h"
46
47 struct {
48     struct opr_rbtree_node *left;
49     struct opr_rbtree_node *right;
50     struct opr_rbtree_node *parent;
51     int red;
52 } opr_rbtree_node;
53
54 struct {
55     struct opr_rbtree_node *root;
56 } opr_rbtree;
57
58 /* Update the parent pointers for a node which is being replaced.
59  *
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.
65  */
66
67 static_inline void
68 update_parent_ptr(struct opr_rbtree *head, struct opr_rbtree_node *old,
69                   struct opr_rbtree_node *replacement)
70 {
71     if (old->parent) {
72         if (old->parent->left == old)
73             old->parent->left = replacement;
74         else
75             old->parent->right = replacement;
76     } else
77         head->root = replacement;
78 }
79
80 void
81 opr_rbtree_init(struct opr_rbtree *head)
82 {
83     head->root = NULL;
84 }
85
86 struct opr_rbtree_node *
87 opr_rbtree_first(struct opr_rbtree *head)
88 {
89     struct opr_rbtree_node *node;
90
91     node = head->root;
92     if (node == NULL)
93         return node;
94
95     while (node->left != NULL)
96         node = node->left;
97
98     return node;
99 }
100
101 struct opr_rbtree_node *
102 opr_rbtree_last(struct opr_rbtree *head)
103 {
104     struct opr_rbtree_node *node;
105
106     node = head->root;
107
108     if (node == NULL)
109         return node;
110
111     while (node->right != NULL)
112         node = node->right;
113
114     return node;
115 }
116
117
118 struct opr_rbtree_node *
119 opr_rbtree_next(struct opr_rbtree_node *node)
120 {
121     struct opr_rbtree_node *parent;
122
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) {
126         node = node->right;
127         while (node->left != NULL)
128              node = node->left;
129
130         return node;
131     }
132
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
136      */
137     while ((parent = node->parent) != NULL && node == parent->right)
138         node = parent;
139
140     return parent;
141 }
142
143 struct opr_rbtree_node *
144 opr_rbtree_prev(struct opr_rbtree_node *node)
145 {
146     struct opr_rbtree_node *parent;
147
148     if (node->left != NULL) {
149         node = node->left;
150         while (node->right != NULL)
151             node = node->right;
152
153         return node;
154     }
155
156     /* Same ancestor logic as for 'next', but in reverse */
157     while ((parent = node->parent) != NULL && node == parent->left)
158         node = parent;
159
160     return parent;
161 }
162
163 static_inline void
164 initnode(struct opr_rbtree_node *node)
165 {
166     node->left = node->right = node->parent = NULL;
167     node->red = 1;
168 }
169
170 static_inline void
171 rotateright(struct opr_rbtree *head, struct opr_rbtree_node *node)
172 {
173     struct opr_rbtree_node *left = node->left;
174
175     node->left = left->right;
176     if (left->right)
177         left->right->parent = node;
178
179     left->right = node;
180     left->parent = node->parent;
181
182     update_parent_ptr(head, node, left);
183
184     node->parent = left;
185 }
186
187 static_inline void
188 rotateleft(struct opr_rbtree *head, struct opr_rbtree_node *node)
189 {
190     struct opr_rbtree_node *right = node->right;
191
192     node->right = right->left;
193     if (right->left)
194         right->left->parent = node;
195
196     right->left = node;
197     right->parent = node->parent;
198
199     update_parent_ptr(head, node, right);
200
201     node->parent = right;
202 }
203
204 static_inline void
205 swapnode(struct opr_rbtree_node **a, struct opr_rbtree_node **b)
206 {
207     struct opr_rbtree_node *tmp;
208
209     tmp = *a;
210     *a = *b;
211     *b = tmp;
212 }
213
214 static void
215 insert_recolour(struct opr_rbtree *head, struct opr_rbtree_node *node)
216 {
217     struct opr_rbtree_node *parent, *gramps;
218
219     while ((parent = node->parent) && parent->red) {
220         gramps = parent->parent;
221
222         if (parent == gramps->left) {
223             struct opr_rbtree_node *uncle = gramps->right;
224
225             if (uncle && uncle->red) {
226                 uncle->red = 0;
227                 parent->red = 0;
228                 gramps->red = 1;
229                 node = gramps;
230                 continue;
231             }
232
233             if (parent->right == node) {
234                 rotateleft(head, parent);
235                 swapnode(&parent, &node);
236             }
237
238             parent->red = 0;
239             gramps->red = 1;
240             rotateright(head, gramps);
241         } else {
242             struct opr_rbtree_node *uncle = gramps->left;
243
244             if (uncle && uncle->red) {
245                 uncle->red = 0;
246                 parent->red = 0;
247                 gramps->red = 1;
248                 node = gramps;
249                 continue;
250             }
251
252             if (parent->left == node) {
253                 rotateright(head, parent);
254                 swapnode(&parent, &node);
255             }
256
257             parent->red = 0;
258             gramps->red = 1;
259             rotateleft(head, gramps);
260         }
261     }
262
263     head->root->red = 0;
264 }
265
266 void
267 opr_rbtree_insert(struct opr_rbtree *head,
268                   struct opr_rbtree_node *parent,
269                   struct opr_rbtree_node **childptr,
270                   struct opr_rbtree_node *node)
271 {
272     /* Link node 'node' into the tree at position 'parent', using either the
273      * left or right pointers */
274
275     node->parent = parent;
276     node->left = node->right = NULL;
277     node->red = 1;
278     *childptr = node;
279
280     /* Rebalance the tree for the newly inserted node */
281     insert_recolour(head, node);
282 }
283
284 static void
285 remove_recolour(struct opr_rbtree *head, struct opr_rbtree_node *parent,
286                 struct opr_rbtree_node *node)
287 {
288     struct opr_rbtree_node *other;
289
290     while ((node == NULL || !node->red) && node != head->root) {
291         if (parent->left == node) {
292             other = parent->right;
293             if (other->red) {
294                 other->red = 0;
295                 parent->red = 1;
296                 rotateleft(head, parent);
297                 other = parent->right;
298             }
299             if ((other->left == NULL || !other->left->red) &&
300                 (other->right == NULL || !other->right->red)) {
301                 other->red = 1;
302                 node = parent;
303                 parent = node->parent;
304             } else {
305                 if (other->right == NULL || !other->right->red) {
306                     other->left->red = 0;
307                     other->red = 1;
308                     rotateright(head, other);
309                     other = parent->right;
310                 }
311                 other->red = parent->red;
312                 parent->red = 0;
313                 other->right->red = 0;
314                 rotateleft(head, parent);
315                 node = head->root;
316                 break;
317             }
318         } else {
319             other = parent->left;
320             if (other->red) {
321                 other->red = 0;
322                 parent->red = 1;
323                 rotateright(head, parent);
324                 other = parent->left;
325             }
326             if ((other->left == NULL || !other->left->red) &&
327                 (other->right == NULL || !other->right->red)) {
328                 other->red = 1;
329                 node = parent;
330                 parent = node->parent;
331             } else {
332                 if (other->left == NULL || !other->left->red) {
333                     other->right->red = 0;
334                     other->red = 1;
335                     rotateleft(head, other);
336                     other = parent->left;
337                 }
338                 other->red = parent->red;
339                 parent->red = 0;
340                 other->left->red = 0;
341                 rotateright(head, parent);
342                 node = head->root;
343                 break;
344             }
345         }
346     }
347     if (node)
348         node->red = 0;
349 }
350
351 void
352 opr_rbtree_remove(struct opr_rbtree *head, struct opr_rbtree_node *node)
353 {
354     struct opr_rbtree_node *child, *parent;
355     int red;
356
357
358     if (node->left == NULL && node->right == NULL) {
359         /* A node with no non-leaf children */
360         update_parent_ptr(head, node, NULL);
361
362         if (!node->red)
363             remove_recolour(head, node->parent, NULL);
364
365         return;
366     }
367
368     if (node->left != NULL && node->right != NULL) {
369         /* A node with two children.
370          *
371          * Move the next node in the tree (which will be a leaf node)
372          * onto our tree current position, then rebalance as required
373          */
374         struct opr_rbtree_node *old, *left;
375
376         old = node;
377
378         /* Set node to the next node in the tree from the current
379          * position, where the next node is the left-most leaf node
380          * in our right child */
381         node = node->right;
382         while ((left = node->left) != NULL)
383             node = left;
384
385         /* Move 'node' into the position occupied by 'old', which is being
386          * removed */
387
388         update_parent_ptr(head, old, node);
389
390         child = node->right;
391         parent = node->parent;
392         red = node->red;
393
394         /* As we're logically just copying the value, must preserve the
395          * old node's colour */
396         node->red = old->red;
397
398         /* ... and the old node's linkage */
399         if (parent == old)
400             parent = node;
401         else {
402             if (child)
403                 child->parent = parent;
404             parent->left = child;
405
406             node->right = old->right;
407             old->right->parent = node;
408         }
409
410         node->parent = old->parent;
411         node->left = old->left;
412         old->left->parent = node;
413
414         /* If the node being removed was black, then we must recolour the
415          * tree to maintain balance */
416         if (!red)
417             remove_recolour(head, parent, child);
418
419         return;
420     }
421
422     /* Only remaining option - node with a single child */
423
424     if (node->left == NULL)
425         child = node->right;
426     else {
427         opr_Assert(node->right == NULL);
428         child = node->left;
429     }
430
431     child->parent = node->parent;
432
433     update_parent_ptr(head, node, child);
434
435     if (!node->red)
436         remove_recolour(head, node->parent, child);
437 }
438
439 void
440 opr_rbtree_replace(struct opr_rbtree *head,
441                    struct opr_rbtree_node *old,
442                    struct opr_rbtree_node *replacement)
443 {
444     /* Update our parent's pointer to us */
445     update_parent_ptr(head, old, replacement);
446
447     /* And our children's pointers to us */
448     if (old->left)
449         old->left->parent = replacement;
450     if (old->right)
451         old->right->parent = replacement;
452
453     /* Copy over parent, left, right and colour */
454     *replacement = *old;
455 }