opr: removed the unused static_inline initnode
[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 rotateright(struct opr_rbtree *head, struct opr_rbtree_node *node)
165 {
166     struct opr_rbtree_node *left = node->left;
167
168     node->left = left->right;
169     if (left->right)
170         left->right->parent = node;
171
172     left->right = node;
173     left->parent = node->parent;
174
175     update_parent_ptr(head, node, left);
176
177     node->parent = left;
178 }
179
180 static_inline void
181 rotateleft(struct opr_rbtree *head, struct opr_rbtree_node *node)
182 {
183     struct opr_rbtree_node *right = node->right;
184
185     node->right = right->left;
186     if (right->left)
187         right->left->parent = node;
188
189     right->left = node;
190     right->parent = node->parent;
191
192     update_parent_ptr(head, node, right);
193
194     node->parent = right;
195 }
196
197 static_inline void
198 swapnode(struct opr_rbtree_node **a, struct opr_rbtree_node **b)
199 {
200     struct opr_rbtree_node *tmp;
201
202     tmp = *a;
203     *a = *b;
204     *b = tmp;
205 }
206
207 static void
208 insert_recolour(struct opr_rbtree *head, struct opr_rbtree_node *node)
209 {
210     struct opr_rbtree_node *parent, *gramps;
211
212     while ((parent = node->parent) && parent->red) {
213         gramps = parent->parent;
214
215         if (parent == gramps->left) {
216             struct opr_rbtree_node *uncle = gramps->right;
217
218             if (uncle && uncle->red) {
219                 uncle->red = 0;
220                 parent->red = 0;
221                 gramps->red = 1;
222                 node = gramps;
223                 continue;
224             }
225
226             if (parent->right == node) {
227                 rotateleft(head, parent);
228                 swapnode(&parent, &node);
229             }
230
231             parent->red = 0;
232             gramps->red = 1;
233             rotateright(head, gramps);
234         } else {
235             struct opr_rbtree_node *uncle = gramps->left;
236
237             if (uncle && uncle->red) {
238                 uncle->red = 0;
239                 parent->red = 0;
240                 gramps->red = 1;
241                 node = gramps;
242                 continue;
243             }
244
245             if (parent->left == node) {
246                 rotateright(head, parent);
247                 swapnode(&parent, &node);
248             }
249
250             parent->red = 0;
251             gramps->red = 1;
252             rotateleft(head, gramps);
253         }
254     }
255
256     head->root->red = 0;
257 }
258
259 void
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)
264 {
265     /* Link node 'node' into the tree at position 'parent', using either the
266      * left or right pointers */
267
268     node->parent = parent;
269     node->left = node->right = NULL;
270     node->red = 1;
271     *childptr = node;
272
273     /* Rebalance the tree for the newly inserted node */
274     insert_recolour(head, node);
275 }
276
277 static void
278 remove_recolour(struct opr_rbtree *head, struct opr_rbtree_node *parent,
279                 struct opr_rbtree_node *node)
280 {
281     struct opr_rbtree_node *other;
282
283     while ((node == NULL || !node->red) && node != head->root) {
284         if (parent->left == node) {
285             other = parent->right;
286             if (other->red) {
287                 other->red = 0;
288                 parent->red = 1;
289                 rotateleft(head, parent);
290                 other = parent->right;
291             }
292             if ((other->left == NULL || !other->left->red) &&
293                 (other->right == NULL || !other->right->red)) {
294                 other->red = 1;
295                 node = parent;
296                 parent = node->parent;
297             } else {
298                 if (other->right == NULL || !other->right->red) {
299                     other->left->red = 0;
300                     other->red = 1;
301                     rotateright(head, other);
302                     other = parent->right;
303                 }
304                 other->red = parent->red;
305                 parent->red = 0;
306                 other->right->red = 0;
307                 rotateleft(head, parent);
308                 node = head->root;
309                 break;
310             }
311         } else {
312             other = parent->left;
313             if (other->red) {
314                 other->red = 0;
315                 parent->red = 1;
316                 rotateright(head, parent);
317                 other = parent->left;
318             }
319             if ((other->left == NULL || !other->left->red) &&
320                 (other->right == NULL || !other->right->red)) {
321                 other->red = 1;
322                 node = parent;
323                 parent = node->parent;
324             } else {
325                 if (other->left == NULL || !other->left->red) {
326                     other->right->red = 0;
327                     other->red = 1;
328                     rotateleft(head, other);
329                     other = parent->left;
330                 }
331                 other->red = parent->red;
332                 parent->red = 0;
333                 other->left->red = 0;
334                 rotateright(head, parent);
335                 node = head->root;
336                 break;
337             }
338         }
339     }
340     if (node)
341         node->red = 0;
342 }
343
344 void
345 opr_rbtree_remove(struct opr_rbtree *head, struct opr_rbtree_node *node)
346 {
347     struct opr_rbtree_node *child, *parent;
348     int red;
349
350
351     if (node->left == NULL && node->right == NULL) {
352         /* A node with no non-leaf children */
353         update_parent_ptr(head, node, NULL);
354
355         if (!node->red)
356             remove_recolour(head, node->parent, NULL);
357
358         return;
359     }
360
361     if (node->left != NULL && node->right != NULL) {
362         /* A node with two children.
363          *
364          * Move the next node in the tree (which will be a leaf node)
365          * onto our tree current position, then rebalance as required
366          */
367         struct opr_rbtree_node *old, *left;
368
369         old = node;
370
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 */
374         node = node->right;
375         while ((left = node->left) != NULL)
376             node = left;
377
378         /* Move 'node' into the position occupied by 'old', which is being
379          * removed */
380
381         update_parent_ptr(head, old, node);
382
383         child = node->right;
384         parent = node->parent;
385         red = node->red;
386
387         /* As we're logically just copying the value, must preserve the
388          * old node's colour */
389         node->red = old->red;
390
391         /* ... and the old node's linkage */
392         if (parent == old)
393             parent = node;
394         else {
395             if (child)
396                 child->parent = parent;
397             parent->left = child;
398
399             node->right = old->right;
400             old->right->parent = node;
401         }
402
403         node->parent = old->parent;
404         node->left = old->left;
405         old->left->parent = node;
406
407         /* If the node being removed was black, then we must recolour the
408          * tree to maintain balance */
409         if (!red)
410             remove_recolour(head, parent, child);
411
412         return;
413     }
414
415     /* Only remaining option - node with a single child */
416
417     if (node->left == NULL)
418         child = node->right;
419     else {
420         opr_Assert(node->right == NULL);
421         child = node->left;
422     }
423
424     child->parent = node->parent;
425
426     update_parent_ptr(head, node, child);
427
428     if (!node->red)
429         remove_recolour(head, node->parent, child);
430 }
431
432 void
433 opr_rbtree_replace(struct opr_rbtree *head,
434                    struct opr_rbtree_node *old,
435                    struct opr_rbtree_node *replacement)
436 {
437     /* Update our parent's pointer to us */
438     update_parent_ptr(head, old, replacement);
439
440     /* And our children's pointers to us */
441     if (old->left)
442         old->left->parent = replacement;
443     if (old->right)
444         old->right->parent = replacement;
445
446     /* Copy over parent, left, right and colour */
447     *replacement = *old;
448 }