3 (C) 1999 Andrea Arcangeli <andrea@suse.de>
4 (C) 2002 David Woodhouse <dwmw2@infradead.org>
5 (C) 2007 Andre Noll <maan@systemlinux.org>
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.
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.
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
27 static void __rb_rotate_left(struct rb_node
*node
, struct rb_root
*root
)
29 struct rb_node
*right
= node
->rb_right
;
30 struct rb_node
*parent
= rb_parent(node
);
32 if ((node
->rb_right
= right
->rb_left
))
33 rb_set_parent(right
->rb_left
, node
);
34 right
->rb_left
= node
;
36 rb_set_parent(right
, parent
);
40 if (node
== parent
->rb_left
)
41 parent
->rb_left
= right
;
43 parent
->rb_right
= right
;
46 root
->rb_node
= right
;
47 rb_set_parent(node
, right
);
48 right
->size
= node
->size
;
51 node
->size
+= node
->rb_right
->size
;
53 node
->size
+= node
->rb_left
->size
;
56 static void __rb_rotate_right(struct rb_node
*node
, struct rb_root
*root
)
58 struct rb_node
*left
= node
->rb_left
;
59 struct rb_node
*parent
= rb_parent(node
);
61 if ((node
->rb_left
= left
->rb_right
))
62 rb_set_parent(left
->rb_right
, node
);
63 left
->rb_right
= node
;
65 rb_set_parent(left
, parent
);
69 if (node
== parent
->rb_right
)
70 parent
->rb_right
= left
;
72 parent
->rb_left
= left
;
76 rb_set_parent(node
, left
);
77 left
->size
= node
->size
;
80 node
->size
+= node
->rb_right
->size
;
82 node
->size
+= node
->rb_left
->size
;
85 void rb_insert_color(struct rb_node
*node
, struct rb_root
*root
)
87 struct rb_node
*parent
, *gparent
;
89 while ((parent
= rb_parent(node
)) && rb_is_red(parent
))
91 gparent
= rb_parent(parent
);
93 if (parent
== gparent
->rb_left
)
96 register struct rb_node
*uncle
= gparent
->rb_right
;
97 if (uncle
&& rb_is_red(uncle
))
100 rb_set_black(parent
);
107 if (parent
->rb_right
== node
)
109 register struct rb_node
*tmp
;
110 __rb_rotate_left(parent
, root
);
116 rb_set_black(parent
);
118 __rb_rotate_right(gparent
, root
);
121 register struct rb_node
*uncle
= gparent
->rb_left
;
122 if (uncle
&& rb_is_red(uncle
))
125 rb_set_black(parent
);
132 if (parent
->rb_left
== node
)
134 register struct rb_node
*tmp
;
135 __rb_rotate_right(parent
, root
);
141 rb_set_black(parent
);
143 __rb_rotate_left(gparent
, root
);
147 rb_set_black(root
->rb_node
);
150 static void __rb_erase_color(struct rb_node
*node
, struct rb_node
*parent
,
151 struct rb_root
*root
)
153 struct rb_node
*other
;
155 while ((!node
|| rb_is_black(node
)) && node
!= root
->rb_node
)
157 if (parent
->rb_left
== node
)
159 other
= parent
->rb_right
;
160 if (rb_is_red(other
))
164 __rb_rotate_left(parent
, root
);
165 other
= parent
->rb_right
;
167 if ((!other
->rb_left
|| rb_is_black(other
->rb_left
)) &&
168 (!other
->rb_right
|| rb_is_black(other
->rb_right
)))
172 parent
= rb_parent(node
);
176 if (!other
->rb_right
|| rb_is_black(other
->rb_right
))
178 struct rb_node
*o_left
;
179 if ((o_left
= other
->rb_left
))
180 rb_set_black(o_left
);
182 __rb_rotate_right(other
, root
);
183 other
= parent
->rb_right
;
185 rb_set_color(other
, rb_color(parent
));
186 rb_set_black(parent
);
188 rb_set_black(other
->rb_right
);
189 __rb_rotate_left(parent
, root
);
190 node
= root
->rb_node
;
196 other
= parent
->rb_left
;
197 if (rb_is_red(other
))
201 __rb_rotate_right(parent
, root
);
202 other
= parent
->rb_left
;
204 if ((!other
->rb_left
|| rb_is_black(other
->rb_left
)) &&
205 (!other
->rb_right
|| rb_is_black(other
->rb_right
)))
209 parent
= rb_parent(node
);
213 if (!other
->rb_left
|| rb_is_black(other
->rb_left
))
215 register struct rb_node
*o_right
;
216 if ((o_right
= other
->rb_right
))
217 rb_set_black(o_right
);
219 __rb_rotate_left(other
, root
);
220 other
= parent
->rb_left
;
222 rb_set_color(other
, rb_color(parent
));
223 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
)
252 child
= node
->rb_right
;
253 parent
= rb_parent(node
);
254 color
= rb_color(node
);
257 rb_set_parent(child
, parent
);
259 parent
->rb_right
= child
;
262 parent
->rb_left
= child
;
264 node
->rb_parent_color
= old
->rb_parent_color
;
265 node
->rb_right
= old
->rb_right
;
266 node
->rb_left
= old
->rb_left
;
267 node
->size
= old
->size
;
271 if (rb_parent(old
)->rb_left
== old
)
272 rb_parent(old
)->rb_left
= node
;
274 rb_parent(old
)->rb_right
= node
;
276 root
->rb_node
= node
;
278 rb_set_parent(old
->rb_left
, node
);
280 rb_set_parent(old
->rb_right
, node
);
284 parent
= rb_parent(node
);
285 color
= rb_color(node
);
288 rb_set_parent(child
, parent
);
291 if (parent
->rb_left
== node
)
292 parent
->rb_left
= child
;
294 parent
->rb_right
= child
;
297 root
->rb_node
= child
;
300 if (color
== RB_BLACK
)
301 __rb_erase_color(child
, parent
, root
);
305 * This function returns the first node (in sort order) of the tree.
307 struct rb_node
*rb_first(struct rb_root
*root
)
319 struct rb_node
*rb_last(struct rb_root
*root
)
331 struct rb_node
*rb_next(struct rb_node
*node
)
333 struct rb_node
*parent
;
335 if (rb_parent(node
) == node
)
338 /* If we have a right-hand child, go down and then left as far
340 if (node
->rb_right
) {
341 node
= node
->rb_right
;
342 while (node
->rb_left
)
347 /* No right-hand children. Everything down and left is
348 smaller than us, so any 'next' node must be in the general
349 direction of our parent. Go up the tree; any time the
350 ancestor is a right-hand child of its parent, keep going
351 up. First time it's a left-hand child of its parent, said
352 parent is our 'next' node. */
353 while ((parent
= rb_parent(node
)) && node
== parent
->rb_right
)
359 struct rb_node
*rb_prev(struct rb_node
*node
)
361 struct rb_node
*parent
;
363 if (rb_parent(node
) == node
)
366 /* If we have a left-hand child, go down and then right as far
369 node
= node
->rb_left
;
370 while (node
->rb_right
)
375 /* No left-hand children. Go up till we find an ancestor which
376 is a right-hand child of its parent */
377 while ((parent
= rb_parent(node
)) && node
== parent
->rb_left
)
383 void rb_replace_node(struct rb_node
*victim
, struct rb_node
*new,
384 struct rb_root
*root
)
386 struct rb_node
*parent
= rb_parent(victim
);
388 /* Set the surrounding nodes to point to the replacement */
390 if (victim
== parent
->rb_left
)
391 parent
->rb_left
= new;
393 parent
->rb_right
= new;
398 rb_set_parent(victim
->rb_left
, new);
399 if (victim
->rb_right
)
400 rb_set_parent(victim
->rb_right
, new);
402 /* Copy the pointers/colour from the victim to the replacement */
407 * Get the n-th node (in sort order) of the tree.
409 * \param node The root of the subtree to consider.
410 * \param n The order statistic to compute.
412 * \return Pointer to the \a n th greatest node on success, \p NULL on errors.
414 struct rb_node
*rb_nth(struct rb_node
*node
, unsigned n
)
421 size
+= node
->rb_left
->size
;
425 return rb_nth(node
->rb_left
, n
);
426 return rb_nth(node
->rb_right
, n
- size
);
430 * Get the rank of a node in O(log n) time.
432 * \param node The node to get the rank of.
433 * \param rank Result pointer.
435 * \return Positive on success, -1 on errors.
437 int rb_rank(struct rb_node
*node
, unsigned *rank
)
440 struct rb_node
*parent
;
445 *rank
+= node
->rb_left
->size
;
446 while ((parent
= rb_parent(node
))) {
447 if (node
== parent
->rb_right
) {
450 *rank
+= parent
->rb_left
->size
;