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
25 static void __rb_rotate_left(struct rb_node
*node
, struct rb_root
*root
)
27 struct rb_node
*right
= node
->rb_right
;
28 struct rb_node
*parent
= rb_parent(node
);
30 if ((node
->rb_right
= right
->rb_left
))
31 rb_set_parent(right
->rb_left
, node
);
32 right
->rb_left
= node
;
34 rb_set_parent(right
, parent
);
38 if (node
== parent
->rb_left
)
39 parent
->rb_left
= right
;
41 parent
->rb_right
= right
;
44 root
->rb_node
= right
;
45 rb_set_parent(node
, right
);
48 static void __rb_rotate_right(struct rb_node
*node
, struct rb_root
*root
)
50 struct rb_node
*left
= node
->rb_left
;
51 struct rb_node
*parent
= rb_parent(node
);
53 if ((node
->rb_left
= left
->rb_right
))
54 rb_set_parent(left
->rb_right
, node
);
55 left
->rb_right
= node
;
57 rb_set_parent(left
, parent
);
61 if (node
== parent
->rb_right
)
62 parent
->rb_right
= left
;
64 parent
->rb_left
= left
;
68 rb_set_parent(node
, left
);
71 void rb_insert_color(struct rb_node
*node
, struct rb_root
*root
)
73 struct rb_node
*parent
, *gparent
;
75 while ((parent
= rb_parent(node
)) && rb_is_red(parent
))
77 gparent
= rb_parent(parent
);
79 if (parent
== gparent
->rb_left
)
82 struct rb_node
*uncle
= gparent
->rb_right
;
83 if (uncle
&& rb_is_red(uncle
))
93 if (parent
->rb_right
== node
)
96 __rb_rotate_left(parent
, root
);
102 rb_set_black(parent
);
104 __rb_rotate_right(gparent
, root
);
107 struct rb_node
*uncle
= gparent
->rb_left
;
108 if (uncle
&& rb_is_red(uncle
))
111 rb_set_black(parent
);
118 if (parent
->rb_left
== node
)
121 __rb_rotate_right(parent
, root
);
127 rb_set_black(parent
);
129 __rb_rotate_left(gparent
, root
);
133 rb_set_black(root
->rb_node
);
136 static void __rb_erase_color(struct rb_node
*node
, struct rb_node
*parent
,
137 struct rb_root
*root
)
139 struct rb_node
*other
;
141 while ((!node
|| rb_is_black(node
)) && node
!= root
->rb_node
)
143 if (parent
->rb_left
== node
)
145 other
= parent
->rb_right
;
146 if (rb_is_red(other
))
150 __rb_rotate_left(parent
, root
);
151 other
= parent
->rb_right
;
153 if ((!other
->rb_left
|| rb_is_black(other
->rb_left
)) &&
154 (!other
->rb_right
|| rb_is_black(other
->rb_right
)))
158 parent
= rb_parent(node
);
162 if (!other
->rb_right
|| rb_is_black(other
->rb_right
))
164 rb_set_black(other
->rb_left
);
166 __rb_rotate_right(other
, root
);
167 other
= parent
->rb_right
;
169 rb_set_color(other
, rb_color(parent
));
170 rb_set_black(parent
);
171 rb_set_black(other
->rb_right
);
172 __rb_rotate_left(parent
, root
);
173 node
= root
->rb_node
;
179 other
= parent
->rb_left
;
180 if (rb_is_red(other
))
184 __rb_rotate_right(parent
, root
);
185 other
= parent
->rb_left
;
187 if ((!other
->rb_left
|| rb_is_black(other
->rb_left
)) &&
188 (!other
->rb_right
|| rb_is_black(other
->rb_right
)))
192 parent
= rb_parent(node
);
196 if (!other
->rb_left
|| rb_is_black(other
->rb_left
))
198 rb_set_black(other
->rb_right
);
200 __rb_rotate_left(other
, root
);
201 other
= parent
->rb_left
;
203 rb_set_color(other
, rb_color(parent
));
204 rb_set_black(parent
);
205 rb_set_black(other
->rb_left
);
206 __rb_rotate_right(parent
, root
);
207 node
= root
->rb_node
;
216 void rb_erase(struct rb_node
*node
, struct rb_root
*root
)
218 struct rb_node
*child
, *parent
;
222 child
= node
->rb_right
;
223 else if (!node
->rb_right
)
224 child
= node
->rb_left
;
227 struct rb_node
*old
= node
, *left
;
229 node
= node
->rb_right
;
230 while ((left
= node
->rb_left
) != NULL
)
233 if (rb_parent(old
)) {
234 if (rb_parent(old
)->rb_left
== old
)
235 rb_parent(old
)->rb_left
= node
;
237 rb_parent(old
)->rb_right
= node
;
239 root
->rb_node
= node
;
241 child
= node
->rb_right
;
242 parent
= rb_parent(node
);
243 color
= rb_color(node
);
249 rb_set_parent(child
, parent
);
250 parent
->rb_left
= child
;
252 node
->rb_right
= old
->rb_right
;
253 rb_set_parent(old
->rb_right
, node
);
256 node
->rb_parent_color
= old
->rb_parent_color
;
257 node
->rb_left
= old
->rb_left
;
258 rb_set_parent(old
->rb_left
, node
);
263 parent
= rb_parent(node
);
264 color
= rb_color(node
);
267 rb_set_parent(child
, parent
);
270 if (parent
->rb_left
== node
)
271 parent
->rb_left
= child
;
273 parent
->rb_right
= child
;
276 root
->rb_node
= child
;
279 if (color
== RB_BLACK
)
280 __rb_erase_color(child
, parent
, root
);
283 static void rb_augment_path(struct rb_node
*node
, rb_augment_f func
, void *data
)
285 struct rb_node
*parent
;
289 parent
= rb_parent(node
);
293 if (node
== parent
->rb_left
&& parent
->rb_right
)
294 func(parent
->rb_right
, data
);
295 else if (parent
->rb_left
)
296 func(parent
->rb_left
, data
);
303 * after inserting @node into the tree, update the tree to account for
304 * both the new entry and any damage done by rebalance
306 void rb_augment_insert(struct rb_node
*node
, rb_augment_f func
, void *data
)
309 node
= node
->rb_left
;
310 else if (node
->rb_right
)
311 node
= node
->rb_right
;
313 rb_augment_path(node
, func
, data
);
317 * before removing the node, find the deepest node on the rebalance path
318 * that will still be there after @node gets removed
320 struct rb_node
*rb_augment_erase_begin(struct rb_node
*node
)
322 struct rb_node
*deepest
;
324 if (!node
->rb_right
&& !node
->rb_left
)
325 deepest
= rb_parent(node
);
326 else if (!node
->rb_right
)
327 deepest
= node
->rb_left
;
328 else if (!node
->rb_left
)
329 deepest
= node
->rb_right
;
331 deepest
= rb_next(node
);
332 if (deepest
->rb_right
)
333 deepest
= deepest
->rb_right
;
334 else if (rb_parent(deepest
) != node
)
335 deepest
= rb_parent(deepest
);
342 * after removal, update the tree to account for the removed entry
343 * and any rebalance damage.
345 void rb_augment_erase_end(struct rb_node
*node
, rb_augment_f func
, void *data
)
348 rb_augment_path(node
, func
, data
);
352 * This function returns the first node (in sort order) of the tree.
354 struct rb_node
*rb_first(const struct rb_root
*root
)
366 struct rb_node
*rb_last(const struct rb_root
*root
)
378 struct rb_node
*rb_next(const struct rb_node
*node
)
380 struct rb_node
*parent
;
382 if (rb_parent(node
) == node
)
385 /* If we have a right-hand child, go down and then left as far
387 if (node
->rb_right
) {
388 node
= node
->rb_right
;
389 while (node
->rb_left
)
391 return (struct rb_node
*)node
;
394 /* No right-hand children. Everything down and left is
395 smaller than us, so any 'next' node must be in the general
396 direction of our parent. Go up the tree; any time the
397 ancestor is a right-hand child of its parent, keep going
398 up. First time it's a left-hand child of its parent, said
399 parent is our 'next' node. */
400 while ((parent
= rb_parent(node
)) && node
== parent
->rb_right
)
406 struct rb_node
*rb_prev(const struct rb_node
*node
)
408 struct rb_node
*parent
;
410 if (rb_parent(node
) == node
)
413 /* If we have a left-hand child, go down and then right as far
416 node
= node
->rb_left
;
417 while (node
->rb_right
)
419 return (struct rb_node
*)node
;
422 /* No left-hand children. Go up till we find an ancestor which
423 is a right-hand child of its parent */
424 while ((parent
= rb_parent(node
)) && node
== parent
->rb_left
)
430 void rb_replace_node(struct rb_node
*victim
, struct rb_node
*new,
431 struct rb_root
*root
)
433 struct rb_node
*parent
= rb_parent(victim
);
435 /* Set the surrounding nodes to point to the replacement */
437 if (victim
== parent
->rb_left
)
438 parent
->rb_left
= new;
440 parent
->rb_right
= new;
445 rb_set_parent(victim
->rb_left
, new);
446 if (victim
->rb_right
)
447 rb_set_parent(victim
->rb_right
, new);
449 /* Copy the pointers/colour from the victim to the replacement */