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/module.h>
26 static void __rb_rotate_left(struct rb_node
*node
, struct rb_root
*root
)
28 struct rb_node
*right
= node
->rb_right
;
29 struct rb_node
*parent
= rb_parent(node
);
31 if ((node
->rb_right
= right
->rb_left
))
32 rb_set_parent(right
->rb_left
, node
);
33 right
->rb_left
= node
;
35 rb_set_parent(right
, parent
);
39 if (node
== parent
->rb_left
)
40 parent
->rb_left
= right
;
42 parent
->rb_right
= right
;
45 root
->rb_node
= right
;
46 rb_set_parent(node
, right
);
49 static void __rb_rotate_right(struct rb_node
*node
, struct rb_root
*root
)
51 struct rb_node
*left
= node
->rb_left
;
52 struct rb_node
*parent
= rb_parent(node
);
54 if ((node
->rb_left
= left
->rb_right
))
55 rb_set_parent(left
->rb_right
, node
);
56 left
->rb_right
= node
;
58 rb_set_parent(left
, parent
);
62 if (node
== parent
->rb_right
)
63 parent
->rb_right
= left
;
65 parent
->rb_left
= left
;
69 rb_set_parent(node
, left
);
72 void rb_insert_color(struct rb_node
*node
, struct rb_root
*root
)
74 struct rb_node
*parent
, *gparent
;
76 while ((parent
= rb_parent(node
)) && rb_is_red(parent
))
78 gparent
= rb_parent(parent
);
80 if (parent
== gparent
->rb_left
)
83 register struct rb_node
*uncle
= gparent
->rb_right
;
84 if (uncle
&& rb_is_red(uncle
))
94 if (parent
->rb_right
== node
)
96 register struct rb_node
*tmp
;
97 __rb_rotate_left(parent
, root
);
103 rb_set_black(parent
);
105 __rb_rotate_right(gparent
, root
);
108 register struct rb_node
*uncle
= gparent
->rb_left
;
109 if (uncle
&& rb_is_red(uncle
))
112 rb_set_black(parent
);
119 if (parent
->rb_left
== node
)
121 register struct rb_node
*tmp
;
122 __rb_rotate_right(parent
, root
);
128 rb_set_black(parent
);
130 __rb_rotate_left(gparent
, root
);
134 rb_set_black(root
->rb_node
);
136 EXPORT_SYMBOL(rb_insert_color
);
138 static void __rb_erase_color(struct rb_node
*node
, struct rb_node
*parent
,
139 struct rb_root
*root
)
141 struct rb_node
*other
;
143 while ((!node
|| rb_is_black(node
)) && node
!= root
->rb_node
)
145 if (parent
->rb_left
== node
)
147 other
= parent
->rb_right
;
148 if (rb_is_red(other
))
152 __rb_rotate_left(parent
, root
);
153 other
= parent
->rb_right
;
155 if ((!other
->rb_left
|| rb_is_black(other
->rb_left
)) &&
156 (!other
->rb_right
|| rb_is_black(other
->rb_right
)))
160 parent
= rb_parent(node
);
164 if (!other
->rb_right
|| rb_is_black(other
->rb_right
))
166 rb_set_black(other
->rb_left
);
168 __rb_rotate_right(other
, root
);
169 other
= parent
->rb_right
;
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
;
181 other
= parent
->rb_left
;
182 if (rb_is_red(other
))
186 __rb_rotate_right(parent
, root
);
187 other
= parent
->rb_left
;
189 if ((!other
->rb_left
|| rb_is_black(other
->rb_left
)) &&
190 (!other
->rb_right
|| rb_is_black(other
->rb_right
)))
194 parent
= rb_parent(node
);
198 if (!other
->rb_left
|| rb_is_black(other
->rb_left
))
200 rb_set_black(other
->rb_right
);
202 __rb_rotate_left(other
, root
);
203 other
= parent
->rb_left
;
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
;
218 void rb_erase(struct rb_node
*node
, struct rb_root
*root
)
220 struct rb_node
*child
, *parent
;
224 child
= node
->rb_right
;
225 else if (!node
->rb_right
)
226 child
= node
->rb_left
;
229 struct rb_node
*old
= node
, *left
;
231 node
= node
->rb_right
;
232 while ((left
= node
->rb_left
) != NULL
)
235 if (rb_parent(old
)) {
236 if (rb_parent(old
)->rb_left
== old
)
237 rb_parent(old
)->rb_left
= node
;
239 rb_parent(old
)->rb_right
= node
;
241 root
->rb_node
= node
;
243 child
= node
->rb_right
;
244 parent
= rb_parent(node
);
245 color
= rb_color(node
);
251 rb_set_parent(child
, parent
);
252 parent
->rb_left
= child
;
254 node
->rb_right
= old
->rb_right
;
255 rb_set_parent(old
->rb_right
, node
);
258 node
->rb_parent_color
= old
->rb_parent_color
;
259 node
->rb_left
= old
->rb_left
;
260 rb_set_parent(old
->rb_left
, node
);
265 parent
= rb_parent(node
);
266 color
= rb_color(node
);
269 rb_set_parent(child
, parent
);
272 if (parent
->rb_left
== node
)
273 parent
->rb_left
= child
;
275 parent
->rb_right
= child
;
278 root
->rb_node
= child
;
281 if (color
== RB_BLACK
)
282 __rb_erase_color(child
, parent
, root
);
284 EXPORT_SYMBOL(rb_erase
);
287 * This function returns the first node (in sort order) of the tree.
289 struct rb_node
*rb_first(const struct rb_root
*root
)
300 EXPORT_SYMBOL(rb_first
);
302 struct rb_node
*rb_last(const struct rb_root
*root
)
313 EXPORT_SYMBOL(rb_last
);
315 struct rb_node
*rb_next(const struct rb_node
*node
)
317 struct rb_node
*parent
;
319 if (rb_parent(node
) == node
)
322 /* If we have a right-hand child, go down and then left as far
324 if (node
->rb_right
) {
325 node
= node
->rb_right
;
326 while (node
->rb_left
)
328 return (struct rb_node
*)node
;
331 /* No right-hand children. Everything down and left is
332 smaller than us, so any 'next' node must be in the general
333 direction of our parent. Go up the tree; any time the
334 ancestor is a right-hand child of its parent, keep going
335 up. First time it's a left-hand child of its parent, said
336 parent is our 'next' node. */
337 while ((parent
= rb_parent(node
)) && node
== parent
->rb_right
)
342 EXPORT_SYMBOL(rb_next
);
344 struct rb_node
*rb_prev(const struct rb_node
*node
)
346 struct rb_node
*parent
;
348 if (rb_parent(node
) == node
)
351 /* If we have a left-hand child, go down and then right as far
354 node
= node
->rb_left
;
355 while (node
->rb_right
)
357 return (struct rb_node
*)node
;
360 /* No left-hand children. Go up till we find an ancestor which
361 is a right-hand child of its parent */
362 while ((parent
= rb_parent(node
)) && node
== parent
->rb_left
)
367 EXPORT_SYMBOL(rb_prev
);
369 void rb_replace_node(struct rb_node
*victim
, struct rb_node
*new,
370 struct rb_root
*root
)
372 struct rb_node
*parent
= rb_parent(victim
);
374 /* Set the surrounding nodes to point to the replacement */
376 if (victim
== parent
->rb_left
)
377 parent
->rb_left
= new;
379 parent
->rb_right
= new;
384 rb_set_parent(victim
->rb_left
, new);
385 if (victim
->rb_right
)
386 rb_set_parent(victim
->rb_right
, new);
388 /* Copy the pointers/colour from the victim to the replacement */
391 EXPORT_SYMBOL(rb_replace_node
);
This page took 0.038425 seconds and 5 git commands to generate.