]>
git.proxmox.com Git - mirror_ubuntu-artful-kernel.git/blob - lib/rbtree.c
3 (C) 1999 Andrea Arcangeli <andrea@suse.de>
4 (C) 2002 David Woodhouse <dwmw2@infradead.org>
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.
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.
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
23 #include <linux/rbtree.h>
24 #include <linux/export.h>
29 #define rb_color(r) ((r)->__rb_parent_color & 1)
30 #define rb_is_red(r) (!rb_color(r))
31 #define rb_is_black(r) rb_color(r)
32 #define rb_set_red(r) do { (r)->__rb_parent_color &= ~1; } while (0)
33 #define rb_set_black(r) do { (r)->__rb_parent_color |= 1; } while (0)
35 static inline void rb_set_parent(struct rb_node
*rb
, struct rb_node
*p
)
37 rb
->__rb_parent_color
= rb_color(rb
) | (unsigned long)p
;
39 static inline void rb_set_color(struct rb_node
*rb
, int color
)
41 rb
->__rb_parent_color
= (rb
->__rb_parent_color
& ~1) | color
;
44 static void __rb_rotate_left(struct rb_node
*node
, struct rb_root
*root
)
46 struct rb_node
*right
= node
->rb_right
;
47 struct rb_node
*parent
= rb_parent(node
);
49 if ((node
->rb_right
= right
->rb_left
))
50 rb_set_parent(right
->rb_left
, node
);
51 right
->rb_left
= node
;
53 rb_set_parent(right
, parent
);
57 if (node
== parent
->rb_left
)
58 parent
->rb_left
= right
;
60 parent
->rb_right
= right
;
63 root
->rb_node
= right
;
64 rb_set_parent(node
, right
);
67 static void __rb_rotate_right(struct rb_node
*node
, struct rb_root
*root
)
69 struct rb_node
*left
= node
->rb_left
;
70 struct rb_node
*parent
= rb_parent(node
);
72 if ((node
->rb_left
= left
->rb_right
))
73 rb_set_parent(left
->rb_right
, node
);
74 left
->rb_right
= node
;
76 rb_set_parent(left
, parent
);
80 if (node
== parent
->rb_right
)
81 parent
->rb_right
= left
;
83 parent
->rb_left
= left
;
87 rb_set_parent(node
, left
);
90 void rb_insert_color(struct rb_node
*node
, struct rb_root
*root
)
92 struct rb_node
*parent
, *gparent
;
94 while ((parent
= rb_parent(node
)) && rb_is_red(parent
))
96 gparent
= rb_parent(parent
);
98 if (parent
== gparent
->rb_left
)
101 register struct rb_node
*uncle
= gparent
->rb_right
;
102 if (uncle
&& rb_is_red(uncle
))
105 rb_set_black(parent
);
112 if (parent
->rb_right
== node
)
114 register struct rb_node
*tmp
;
115 __rb_rotate_left(parent
, root
);
121 rb_set_black(parent
);
123 __rb_rotate_right(gparent
, root
);
126 register struct rb_node
*uncle
= gparent
->rb_left
;
127 if (uncle
&& rb_is_red(uncle
))
130 rb_set_black(parent
);
137 if (parent
->rb_left
== node
)
139 register struct rb_node
*tmp
;
140 __rb_rotate_right(parent
, root
);
146 rb_set_black(parent
);
148 __rb_rotate_left(gparent
, root
);
152 rb_set_black(root
->rb_node
);
154 EXPORT_SYMBOL(rb_insert_color
);
156 static void __rb_erase_color(struct rb_node
*node
, struct rb_node
*parent
,
157 struct rb_root
*root
)
159 struct rb_node
*other
;
161 while ((!node
|| rb_is_black(node
)) && node
!= root
->rb_node
)
163 if (parent
->rb_left
== node
)
165 other
= parent
->rb_right
;
166 if (rb_is_red(other
))
170 __rb_rotate_left(parent
, root
);
171 other
= parent
->rb_right
;
173 if ((!other
->rb_left
|| rb_is_black(other
->rb_left
)) &&
174 (!other
->rb_right
|| rb_is_black(other
->rb_right
)))
178 parent
= rb_parent(node
);
182 if (!other
->rb_right
|| rb_is_black(other
->rb_right
))
184 rb_set_black(other
->rb_left
);
186 __rb_rotate_right(other
, root
);
187 other
= parent
->rb_right
;
189 rb_set_color(other
, rb_color(parent
));
190 rb_set_black(parent
);
191 rb_set_black(other
->rb_right
);
192 __rb_rotate_left(parent
, root
);
193 node
= root
->rb_node
;
199 other
= parent
->rb_left
;
200 if (rb_is_red(other
))
204 __rb_rotate_right(parent
, root
);
205 other
= parent
->rb_left
;
207 if ((!other
->rb_left
|| rb_is_black(other
->rb_left
)) &&
208 (!other
->rb_right
|| rb_is_black(other
->rb_right
)))
212 parent
= rb_parent(node
);
216 if (!other
->rb_left
|| rb_is_black(other
->rb_left
))
218 rb_set_black(other
->rb_right
);
220 __rb_rotate_left(other
, root
);
221 other
= parent
->rb_left
;
223 rb_set_color(other
, rb_color(parent
));
224 rb_set_black(parent
);
225 rb_set_black(other
->rb_left
);
226 __rb_rotate_right(parent
, root
);
227 node
= root
->rb_node
;
236 void rb_erase(struct rb_node
*node
, struct rb_root
*root
)
238 struct rb_node
*child
, *parent
;
242 child
= node
->rb_right
;
243 else if (!node
->rb_right
)
244 child
= node
->rb_left
;
247 struct rb_node
*old
= node
, *left
;
249 node
= node
->rb_right
;
250 while ((left
= node
->rb_left
) != NULL
)
253 if (rb_parent(old
)) {
254 if (rb_parent(old
)->rb_left
== old
)
255 rb_parent(old
)->rb_left
= node
;
257 rb_parent(old
)->rb_right
= node
;
259 root
->rb_node
= node
;
261 child
= node
->rb_right
;
262 parent
= rb_parent(node
);
263 color
= rb_color(node
);
269 rb_set_parent(child
, parent
);
270 parent
->rb_left
= child
;
272 node
->rb_right
= old
->rb_right
;
273 rb_set_parent(old
->rb_right
, node
);
276 node
->__rb_parent_color
= old
->__rb_parent_color
;
277 node
->rb_left
= old
->rb_left
;
278 rb_set_parent(old
->rb_left
, node
);
283 parent
= rb_parent(node
);
284 color
= rb_color(node
);
287 rb_set_parent(child
, parent
);
290 if (parent
->rb_left
== node
)
291 parent
->rb_left
= child
;
293 parent
->rb_right
= child
;
296 root
->rb_node
= child
;
299 if (color
== RB_BLACK
)
300 __rb_erase_color(child
, parent
, root
);
302 EXPORT_SYMBOL(rb_erase
);
304 static void rb_augment_path(struct rb_node
*node
, rb_augment_f func
, void *data
)
306 struct rb_node
*parent
;
310 parent
= rb_parent(node
);
314 if (node
== parent
->rb_left
&& parent
->rb_right
)
315 func(parent
->rb_right
, data
);
316 else if (parent
->rb_left
)
317 func(parent
->rb_left
, data
);
324 * after inserting @node into the tree, update the tree to account for
325 * both the new entry and any damage done by rebalance
327 void rb_augment_insert(struct rb_node
*node
, rb_augment_f func
, void *data
)
330 node
= node
->rb_left
;
331 else if (node
->rb_right
)
332 node
= node
->rb_right
;
334 rb_augment_path(node
, func
, data
);
336 EXPORT_SYMBOL(rb_augment_insert
);
339 * before removing the node, find the deepest node on the rebalance path
340 * that will still be there after @node gets removed
342 struct rb_node
*rb_augment_erase_begin(struct rb_node
*node
)
344 struct rb_node
*deepest
;
346 if (!node
->rb_right
&& !node
->rb_left
)
347 deepest
= rb_parent(node
);
348 else if (!node
->rb_right
)
349 deepest
= node
->rb_left
;
350 else if (!node
->rb_left
)
351 deepest
= node
->rb_right
;
353 deepest
= rb_next(node
);
354 if (deepest
->rb_right
)
355 deepest
= deepest
->rb_right
;
356 else if (rb_parent(deepest
) != node
)
357 deepest
= rb_parent(deepest
);
362 EXPORT_SYMBOL(rb_augment_erase_begin
);
365 * after removal, update the tree to account for the removed entry
366 * and any rebalance damage.
368 void rb_augment_erase_end(struct rb_node
*node
, rb_augment_f func
, void *data
)
371 rb_augment_path(node
, func
, data
);
373 EXPORT_SYMBOL(rb_augment_erase_end
);
376 * This function returns the first node (in sort order) of the tree.
378 struct rb_node
*rb_first(const struct rb_root
*root
)
389 EXPORT_SYMBOL(rb_first
);
391 struct rb_node
*rb_last(const struct rb_root
*root
)
402 EXPORT_SYMBOL(rb_last
);
404 struct rb_node
*rb_next(const struct rb_node
*node
)
406 struct rb_node
*parent
;
408 if (RB_EMPTY_NODE(node
))
411 /* If we have a right-hand child, go down and then left as far
413 if (node
->rb_right
) {
414 node
= node
->rb_right
;
415 while (node
->rb_left
)
417 return (struct rb_node
*)node
;
420 /* No right-hand children. Everything down and left is
421 smaller than us, so any 'next' node must be in the general
422 direction of our parent. Go up the tree; any time the
423 ancestor is a right-hand child of its parent, keep going
424 up. First time it's a left-hand child of its parent, said
425 parent is our 'next' node. */
426 while ((parent
= rb_parent(node
)) && node
== parent
->rb_right
)
431 EXPORT_SYMBOL(rb_next
);
433 struct rb_node
*rb_prev(const struct rb_node
*node
)
435 struct rb_node
*parent
;
437 if (RB_EMPTY_NODE(node
))
440 /* If we have a left-hand child, go down and then right as far
443 node
= node
->rb_left
;
444 while (node
->rb_right
)
446 return (struct rb_node
*)node
;
449 /* No left-hand children. Go up till we find an ancestor which
450 is a right-hand child of its parent */
451 while ((parent
= rb_parent(node
)) && node
== parent
->rb_left
)
456 EXPORT_SYMBOL(rb_prev
);
458 void rb_replace_node(struct rb_node
*victim
, struct rb_node
*new,
459 struct rb_root
*root
)
461 struct rb_node
*parent
= rb_parent(victim
);
463 /* Set the surrounding nodes to point to the replacement */
465 if (victim
== parent
->rb_left
)
466 parent
->rb_left
= new;
468 parent
->rb_right
= new;
473 rb_set_parent(victim
->rb_left
, new);
474 if (victim
->rb_right
)
475 rb_set_parent(victim
->rb_right
, new);
477 /* Copy the pointers/colour from the victim to the replacement */
480 EXPORT_SYMBOL(rb_replace_node
);