osl.c: Fix assertion in create_table_index().
[osl.git] / rbtree.c
1 /*
2   Red Black Trees
3   (C) 1999  Andrea Arcangeli <andrea@suse.de>
4   (C) 2002  David Woodhouse <dwmw2@infradead.org>
5   (C) 2007  Andre Noll <maan@tuebingen.mpg.de>
6   
7   This program is free software; you can redistribute it and/or modify
8   it under the terms of the GNU General Public License as published by
9   the Free Software Foundation; either version 2 of the License, or
10   (at your option) any later version.
11
12   This program is distributed in the hope that it will be useful,
13   but WITHOUT ANY WARRANTY; without even the implied warranty of
14   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15   GNU General Public License for more details.
16
17   You should have received a copy of the GNU General Public License
18   along with this program; if not, write to the Free Software
19   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
20
21   linux/lib/rbtree.c
22 */
23
24 /** \file rbtree.c Red-black tree implementation. */
25
26 #include "stddef.h"
27 #include "rbtree.h"
28
29 static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
30 {
31         struct rb_node *right = node->rb_right;
32         struct rb_node *parent = rb_parent(node);
33
34         if ((node->rb_right = right->rb_left))
35                 rb_set_parent(right->rb_left, node);
36         right->rb_left = node;
37
38         rb_set_parent(right, parent);
39
40         if (parent)
41         {
42                 if (node == parent->rb_left)
43                         parent->rb_left = right;
44                 else
45                         parent->rb_right = right;
46         }
47         else
48                 root->rb_node = right;
49         rb_set_parent(node, right);
50         right->size = node->size;
51         node->size = 1;
52         if (node->rb_right)
53                 node->size += node->rb_right->size;
54         if (node->rb_left)
55                 node->size += node->rb_left->size;
56 }
57
58 static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
59 {
60         struct rb_node *left = node->rb_left;
61         struct rb_node *parent = rb_parent(node);
62
63         if ((node->rb_left = left->rb_right))
64                 rb_set_parent(left->rb_right, node);
65         left->rb_right = node;
66
67         rb_set_parent(left, parent);
68
69         if (parent)
70         {
71                 if (node == parent->rb_right)
72                         parent->rb_right = left;
73                 else
74                         parent->rb_left = left;
75         }
76         else
77                 root->rb_node = left;
78         rb_set_parent(node, left);
79         left->size = node->size;
80         node->size = 1;
81         if (node->rb_right)
82                 node->size += node->rb_right->size;
83         if (node->rb_left)
84                 node->size += node->rb_left->size;
85 }
86
87 void rb_insert_color(struct rb_node *node, struct rb_root *root)
88 {
89         struct rb_node *parent, *gparent;
90
91         while ((parent = rb_parent(node)) && rb_is_red(parent))
92         {
93                 gparent = rb_parent(parent);
94
95                 if (parent == gparent->rb_left)
96                 {
97                         {
98                                 register struct rb_node *uncle = gparent->rb_right;
99                                 if (uncle && rb_is_red(uncle))
100                                 {
101                                         rb_set_black(uncle);
102                                         rb_set_black(parent);
103                                         rb_set_red(gparent);
104                                         node = gparent;
105                                         continue;
106                                 }
107                         }
108
109                         if (parent->rb_right == node)
110                         {
111                                 register struct rb_node *tmp;
112                                 __rb_rotate_left(parent, root);
113                                 tmp = parent;
114                                 parent = node;
115                                 node = tmp;
116                         }
117
118                         rb_set_black(parent);
119                         rb_set_red(gparent);
120                         __rb_rotate_right(gparent, root);
121                 } else {
122                         {
123                                 register struct rb_node *uncle = gparent->rb_left;
124                                 if (uncle && rb_is_red(uncle))
125                                 {
126                                         rb_set_black(uncle);
127                                         rb_set_black(parent);
128                                         rb_set_red(gparent);
129                                         node = gparent;
130                                         continue;
131                                 }
132                         }
133
134                         if (parent->rb_left == node)
135                         {
136                                 register struct rb_node *tmp;
137                                 __rb_rotate_right(parent, root);
138                                 tmp = parent;
139                                 parent = node;
140                                 node = tmp;
141                         }
142
143                         rb_set_black(parent);
144                         rb_set_red(gparent);
145                         __rb_rotate_left(gparent, root);
146                 }
147         }
148
149         rb_set_black(root->rb_node);
150 }
151
152 static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
153                              struct rb_root *root)
154 {
155         struct rb_node *other;
156
157         while ((!node || rb_is_black(node)) && node != root->rb_node)
158         {
159                 if (parent->rb_left == node)
160                 {
161                         other = parent->rb_right;
162                         if (rb_is_red(other))
163                         {
164                                 rb_set_black(other);
165                                 rb_set_red(parent);
166                                 __rb_rotate_left(parent, root);
167                                 other = parent->rb_right;
168                         }
169                         if ((!other->rb_left || rb_is_black(other->rb_left)) &&
170                             (!other->rb_right || rb_is_black(other->rb_right)))
171                         {
172                                 rb_set_red(other);
173                                 node = parent;
174                                 parent = rb_parent(node);
175                         }
176                         else
177                         {
178                                 if (!other->rb_right || rb_is_black(other->rb_right))
179                                 {
180                                         struct rb_node *o_left;
181                                         if ((o_left = other->rb_left))
182                                                 rb_set_black(o_left);
183                                         rb_set_red(other);
184                                         __rb_rotate_right(other, root);
185                                         other = parent->rb_right;
186                                 }
187                                 rb_set_color(other, rb_color(parent));
188                                 rb_set_black(parent);
189                                 if (other->rb_right)
190                                         rb_set_black(other->rb_right);
191                                 __rb_rotate_left(parent, root);
192                                 node = root->rb_node;
193                                 break;
194                         }
195                 }
196                 else
197                 {
198                         other = parent->rb_left;
199                         if (rb_is_red(other))
200                         {
201                                 rb_set_black(other);
202                                 rb_set_red(parent);
203                                 __rb_rotate_right(parent, root);
204                                 other = parent->rb_left;
205                         }
206                         if ((!other->rb_left || rb_is_black(other->rb_left)) &&
207                             (!other->rb_right || rb_is_black(other->rb_right)))
208                         {
209                                 rb_set_red(other);
210                                 node = parent;
211                                 parent = rb_parent(node);
212                         }
213                         else
214                         {
215                                 if (!other->rb_left || rb_is_black(other->rb_left))
216                                 {
217                                         register struct rb_node *o_right;
218                                         if ((o_right = other->rb_right))
219                                                 rb_set_black(o_right);
220                                         rb_set_red(other);
221                                         __rb_rotate_left(other, root);
222                                         other = parent->rb_left;
223                                 }
224                                 rb_set_color(other, rb_color(parent));
225                                 rb_set_black(parent);
226                                 if (other->rb_left)
227                                         rb_set_black(other->rb_left);
228                                 __rb_rotate_right(parent, root);
229                                 node = root->rb_node;
230                                 break;
231                         }
232                 }
233         }
234         if (node)
235                 rb_set_black(node);
236 }
237
238 void rb_erase(struct rb_node *node, struct rb_root *root)
239 {
240         struct rb_node *child, *parent;
241         int color;
242
243         if (!node->rb_left)
244                 child = node->rb_right;
245         else if (!node->rb_right)
246                 child = node->rb_left;
247         else
248         {
249                 struct rb_node *old = node, *left;
250
251                 node = node->rb_right;
252                 while ((left = node->rb_left) != NULL)
253                         node = left;
254                 child = node->rb_right;
255                 parent = rb_parent(node);
256                 color = rb_color(node);
257
258                 if (child)
259                         rb_set_parent(child, parent);
260                 if (parent == old) {
261                         parent->rb_right = child;
262                         parent = node;
263                 } else
264                         parent->rb_left = child;
265
266                 node->rb_parent_color = old->rb_parent_color;
267                 node->rb_right = old->rb_right;
268                 node->rb_left = old->rb_left;
269                 node->size = old->size;
270
271                 if (rb_parent(old))
272                 {
273                         if (rb_parent(old)->rb_left == old)
274                                 rb_parent(old)->rb_left = node;
275                         else
276                                 rb_parent(old)->rb_right = node;
277                 } else
278                         root->rb_node = node;
279
280                 rb_set_parent(old->rb_left, node);
281                 if (old->rb_right)
282                         rb_set_parent(old->rb_right, node);
283                 goto color;
284         }
285
286         parent = rb_parent(node);
287         color = rb_color(node);
288
289         if (child)
290                 rb_set_parent(child, parent);
291         if (parent)
292         {
293                 if (parent->rb_left == node)
294                         parent->rb_left = child;
295                 else
296                         parent->rb_right = child;
297         }
298         else
299                 root->rb_node = child;
300
301  color:
302         if (color == RB_BLACK)
303                 __rb_erase_color(child, parent, root);
304 }
305
306 /*
307  * This function returns the first node (in sort order) of the tree.
308  */
309 struct rb_node *rb_first(const struct rb_root *root)
310 {
311         struct rb_node  *n;
312
313         n = root->rb_node;
314         if (!n)
315                 return NULL;
316         while (n->rb_left)
317                 n = n->rb_left;
318         return n;
319 }
320
321 struct rb_node *rb_last(const struct rb_root *root)
322 {
323         struct rb_node  *n;
324
325         n = root->rb_node;
326         if (!n)
327                 return NULL;
328         while (n->rb_right)
329                 n = n->rb_right;
330         return n;
331 }
332
333 struct rb_node *rb_next(const struct rb_node *node)
334 {
335         struct rb_node *parent;
336
337         if (rb_parent(node) == node)
338                 return NULL;
339
340         /* If we have a right-hand child, go down and then left as far
341            as we can. */
342         if (node->rb_right) {
343                 node = node->rb_right; 
344                 while (node->rb_left)
345                         node=node->rb_left;
346                 return (struct rb_node *)node;
347         }
348
349         /* No right-hand children.  Everything down and left is
350            smaller than us, so any 'next' node must be in the general
351            direction of our parent. Go up the tree; any time the
352            ancestor is a right-hand child of its parent, keep going
353            up. First time it's a left-hand child of its parent, said
354            parent is our 'next' node. */
355         while ((parent = rb_parent(node)) && node == parent->rb_right)
356                 node = parent;
357
358         return parent;
359 }
360
361 struct rb_node *rb_prev(const struct rb_node *node)
362 {
363         struct rb_node *parent;
364
365         if (rb_parent(node) == node)
366                 return NULL;
367
368         /* If we have a left-hand child, go down and then right as far
369            as we can. */
370         if (node->rb_left) {
371                 node = node->rb_left; 
372                 while (node->rb_right)
373                         node=node->rb_right;
374                 return (struct rb_node *)node;
375         }
376
377         /* No left-hand children. Go up till we find an ancestor which
378            is a right-hand child of its parent */
379         while ((parent = rb_parent(node)) && node == parent->rb_left)
380                 node = parent;
381
382         return parent;
383 }
384
385 /**
386  * Get the n-th node (in sort order) of the tree.
387  *
388  * \param node The root of the subtree to consider.
389  * \param n The order statistic to compute.
390  *
391  * \return Pointer to the \a n th greatest node on success, \p NULL on errors.
392  */
393 struct rb_node *rb_nth(const struct rb_node *node, unsigned n)
394 {
395         unsigned size = 1;
396
397         if (!node)
398                 return NULL;
399         if (node->rb_left)
400                 size += node->rb_left->size;
401         if (n == size)
402                 return (struct rb_node *)node;
403         if (n < size)
404                 return rb_nth(node->rb_left, n);
405         return rb_nth(node->rb_right, n - size);
406 }
407
408 /**
409  * Get the rank of a node in O(log n) time.
410  *
411  * \param node The node to get the rank of.
412  * \param rank Result pointer.
413  *
414  * \return Positive on success, -1 on errors.
415  */
416 int rb_rank(const struct rb_node *node, unsigned *rank)
417 {
418         *rank = 1;
419         struct rb_node *parent;
420
421         if (!node)
422                 return -1;
423         if (node->rb_left)
424                 *rank += node->rb_left->size;
425         while ((parent = rb_parent(node))) {
426                 if (node == parent->rb_right) {
427                         (*rank)++;
428                         if (parent->rb_left)
429                                 *rank += parent->rb_left->size;
430                 }
431                 node = parent;
432         }
433         return 1;
434 }