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