3 * Copyright 2011 Daniel Borkmann <dborkma@tik.ee.ethz.ch>
6 * Faculty of Computer Science, Mathematics and Natural Sciences,
7 * Leipzig University of Applied Sciences (HTWK Leipzig)
12 * (C) 1999 Andrea Arcangeli <andrea@suse.de>
13 * (C) 2002 David Woodhouse <dwmw2@infradead.org>
15 * This program is free software; you can redistribute it and/or modify
16 * it under the terms of the GNU General Public License as published by
17 * the Free Software Foundation; either version 2 of the License, or
18 * (at your option) any later version.
20 * This program is distributed in the hope that it will be useful,
21 * but WITHOUT ANY WARRANTY; without even the implied warranty of
22 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
23 * GNU General Public License for more details.
25 * You should have received a copy of the GNU General Public License
26 * along with this program; if not, write to the Free Software
27 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
36 static void __rb_rotate_left(struct rb_node
*node
, struct rb_root
*root
)
38 struct rb_node
*right
= node
->rb_right
;
39 struct rb_node
*parent
= rb_parent(node
);
41 if ((node
->rb_right
= right
->rb_left
))
42 rb_set_parent(right
->rb_left
, node
);
43 right
->rb_left
= node
;
45 rb_set_parent(right
, parent
);
49 if (node
== parent
->rb_left
)
50 parent
->rb_left
= right
;
52 parent
->rb_right
= right
;
55 root
->rb_node
= right
;
56 rb_set_parent(node
, right
);
59 static void __rb_rotate_right(struct rb_node
*node
, struct rb_root
*root
)
61 struct rb_node
*left
= node
->rb_left
;
62 struct rb_node
*parent
= rb_parent(node
);
64 if ((node
->rb_left
= left
->rb_right
))
65 rb_set_parent(left
->rb_right
, node
);
66 left
->rb_right
= node
;
68 rb_set_parent(left
, parent
);
72 if (node
== parent
->rb_right
)
73 parent
->rb_right
= left
;
75 parent
->rb_left
= left
;
79 rb_set_parent(node
, left
);
82 void rb_insert_color(struct rb_node
*node
, struct rb_root
*root
)
84 struct rb_node
*parent
, *gparent
;
86 while ((parent
= rb_parent(node
)) && rb_is_red(parent
))
88 gparent
= rb_parent(parent
);
90 if (parent
== gparent
->rb_left
)
93 register struct rb_node
*uncle
= gparent
->rb_right
;
94 if (uncle
&& rb_is_red(uncle
))
104 if (parent
->rb_right
== node
)
106 register struct rb_node
*tmp
;
107 __rb_rotate_left(parent
, root
);
113 rb_set_black(parent
);
115 __rb_rotate_right(gparent
, root
);
118 register struct rb_node
*uncle
= gparent
->rb_left
;
119 if (uncle
&& rb_is_red(uncle
))
122 rb_set_black(parent
);
129 if (parent
->rb_left
== node
)
131 register struct rb_node
*tmp
;
132 __rb_rotate_right(parent
, root
);
138 rb_set_black(parent
);
140 __rb_rotate_left(gparent
, root
);
144 rb_set_black(root
->rb_node
);
147 static void __rb_erase_color(struct rb_node
*node
, struct rb_node
*parent
,
148 struct rb_root
*root
)
150 struct rb_node
*other
;
152 while ((!node
|| rb_is_black(node
)) && node
!= root
->rb_node
)
154 if (parent
->rb_left
== node
)
156 other
= parent
->rb_right
;
157 if (rb_is_red(other
))
161 __rb_rotate_left(parent
, root
);
162 other
= parent
->rb_right
;
164 if ((!other
->rb_left
|| rb_is_black(other
->rb_left
)) &&
165 (!other
->rb_right
|| rb_is_black(other
->rb_right
)))
169 parent
= rb_parent(node
);
173 if (!other
->rb_right
|| rb_is_black(other
->rb_right
))
175 struct rb_node
*o_left
;
176 if ((o_left
= other
->rb_left
))
177 rb_set_black(o_left
);
179 __rb_rotate_right(other
, root
);
180 other
= parent
->rb_right
;
182 rb_set_color(other
, rb_color(parent
));
183 rb_set_black(parent
);
185 rb_set_black(other
->rb_right
);
186 __rb_rotate_left(parent
, root
);
187 node
= root
->rb_node
;
193 other
= parent
->rb_left
;
194 if (rb_is_red(other
))
198 __rb_rotate_right(parent
, root
);
199 other
= parent
->rb_left
;
201 if ((!other
->rb_left
|| rb_is_black(other
->rb_left
)) &&
202 (!other
->rb_right
|| rb_is_black(other
->rb_right
)))
206 parent
= rb_parent(node
);
210 if (!other
->rb_left
|| rb_is_black(other
->rb_left
))
212 register struct rb_node
*o_right
;
213 if ((o_right
= other
->rb_right
))
214 rb_set_black(o_right
);
216 __rb_rotate_left(other
, root
);
217 other
= parent
->rb_left
;
219 rb_set_color(other
, rb_color(parent
));
220 rb_set_black(parent
);
222 rb_set_black(other
->rb_left
);
223 __rb_rotate_right(parent
, root
);
224 node
= root
->rb_node
;
233 void rb_erase(struct rb_node
*node
, struct rb_root
*root
)
235 struct rb_node
*child
, *parent
;
239 child
= node
->rb_right
;
240 else if (!node
->rb_right
)
241 child
= node
->rb_left
;
244 struct rb_node
*old
= node
, *left
;
246 node
= node
->rb_right
;
247 while ((left
= node
->rb_left
) != NULL
)
249 child
= node
->rb_right
;
250 parent
= rb_parent(node
);
251 color
= rb_color(node
);
254 rb_set_parent(child
, parent
);
256 parent
->rb_right
= child
;
259 parent
->rb_left
= child
;
261 node
->rb_parent_color
= old
->rb_parent_color
;
262 node
->rb_right
= old
->rb_right
;
263 node
->rb_left
= old
->rb_left
;
267 if (rb_parent(old
)->rb_left
== old
)
268 rb_parent(old
)->rb_left
= node
;
270 rb_parent(old
)->rb_right
= node
;
272 root
->rb_node
= node
;
274 rb_set_parent(old
->rb_left
, node
);
276 rb_set_parent(old
->rb_right
, node
);
280 parent
= rb_parent(node
);
281 color
= rb_color(node
);
284 rb_set_parent(child
, parent
);
287 if (parent
->rb_left
== node
)
288 parent
->rb_left
= child
;
290 parent
->rb_right
= child
;
293 root
->rb_node
= child
;
296 if (color
== RB_BLACK
)
297 __rb_erase_color(child
, parent
, root
);
301 * This function returns the first node (in sort order) of the tree.
303 struct rb_node
*rb_first(struct rb_root
*root
)
315 struct rb_node
*rb_last(struct rb_root
*root
)
327 struct rb_node
*rb_next(struct rb_node
*node
)
329 struct rb_node
*parent
;
331 if (rb_parent(node
) == node
)
334 /* If we have a right-hand child, go down and then left as far
336 if (node
->rb_right
) {
337 node
= node
->rb_right
;
338 while (node
->rb_left
)
343 /* No right-hand children. Everything down and left is
344 smaller than us, so any 'next' node must be in the general
345 direction of our parent. Go up the tree; any time the
346 ancestor is a right-hand child of its parent, keep going
347 up. First time it's a left-hand child of its parent, said
348 parent is our 'next' node. */
349 while ((parent
= rb_parent(node
)) && node
== parent
->rb_right
)
355 struct rb_node
*rb_prev(struct rb_node
*node
)
357 struct rb_node
*parent
;
359 if (rb_parent(node
) == node
)
362 /* If we have a left-hand child, go down and then right as far
365 node
= node
->rb_left
;
366 while (node
->rb_right
)
371 /* No left-hand children. Go up till we find an ancestor which
372 is a right-hand child of its parent */
373 while ((parent
= rb_parent(node
)) && node
== parent
->rb_left
)
379 void rb_replace_node(struct rb_node
*victim
, struct rb_node
*new,
380 struct rb_root
*root
)
382 struct rb_node
*parent
= rb_parent(victim
);
384 /* Set the surrounding nodes to point to the replacement */
386 if (victim
== parent
->rb_left
)
387 parent
->rb_left
= new;
389 parent
->rb_right
= new;
394 rb_set_parent(victim
->rb_left
, new);
395 if (victim
->rb_right
)
396 rb_set_parent(victim
->rb_right
, new);
398 /* Copy the pointers/colour from the victim to the replacement */