]>
git.proxmox.com Git - mirror_ubuntu-bionic-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/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 struct rb_node
*o_left
;
167 if ((o_left
= other
->rb_left
))
168 rb_set_black(o_left
);
170 __rb_rotate_right(other
, root
);
171 other
= parent
->rb_right
;
173 rb_set_color(other
, rb_color(parent
));
174 rb_set_black(parent
);
176 rb_set_black(other
->rb_right
);
177 __rb_rotate_left(parent
, root
);
178 node
= root
->rb_node
;
184 other
= parent
->rb_left
;
185 if (rb_is_red(other
))
189 __rb_rotate_right(parent
, root
);
190 other
= parent
->rb_left
;
192 if ((!other
->rb_left
|| rb_is_black(other
->rb_left
)) &&
193 (!other
->rb_right
|| rb_is_black(other
->rb_right
)))
197 parent
= rb_parent(node
);
201 if (!other
->rb_left
|| rb_is_black(other
->rb_left
))
203 register struct rb_node
*o_right
;
204 if ((o_right
= other
->rb_right
))
205 rb_set_black(o_right
);
207 __rb_rotate_left(other
, root
);
208 other
= parent
->rb_left
;
210 rb_set_color(other
, rb_color(parent
));
211 rb_set_black(parent
);
213 rb_set_black(other
->rb_left
);
214 __rb_rotate_right(parent
, root
);
215 node
= root
->rb_node
;
224 void rb_erase(struct rb_node
*node
, struct rb_root
*root
)
226 struct rb_node
*child
, *parent
;
230 child
= node
->rb_right
;
231 else if (!node
->rb_right
)
232 child
= node
->rb_left
;
235 struct rb_node
*old
= node
, *left
;
237 node
= node
->rb_right
;
238 while ((left
= node
->rb_left
) != NULL
)
240 child
= node
->rb_right
;
241 parent
= rb_parent(node
);
242 color
= rb_color(node
);
245 rb_set_parent(child
, parent
);
247 parent
->rb_right
= child
;
250 parent
->rb_left
= child
;
252 node
->rb_parent_color
= old
->rb_parent_color
;
253 node
->rb_right
= old
->rb_right
;
254 node
->rb_left
= old
->rb_left
;
258 if (rb_parent(old
)->rb_left
== old
)
259 rb_parent(old
)->rb_left
= node
;
261 rb_parent(old
)->rb_right
= node
;
263 root
->rb_node
= node
;
265 rb_set_parent(old
->rb_left
, node
);
267 rb_set_parent(old
->rb_right
, node
);
271 parent
= rb_parent(node
);
272 color
= rb_color(node
);
275 rb_set_parent(child
, parent
);
278 if (parent
->rb_left
== node
)
279 parent
->rb_left
= child
;
281 parent
->rb_right
= child
;
284 root
->rb_node
= child
;
287 if (color
== RB_BLACK
)
288 __rb_erase_color(child
, parent
, root
);
290 EXPORT_SYMBOL(rb_erase
);
293 * This function returns the first node (in sort order) of the tree.
295 struct rb_node
*rb_first(const struct rb_root
*root
)
306 EXPORT_SYMBOL(rb_first
);
308 struct rb_node
*rb_last(const struct rb_root
*root
)
319 EXPORT_SYMBOL(rb_last
);
321 struct rb_node
*rb_next(const struct rb_node
*node
)
323 struct rb_node
*parent
;
325 if (rb_parent(node
) == node
)
328 /* If we have a right-hand child, go down and then left as far
330 if (node
->rb_right
) {
331 node
= node
->rb_right
;
332 while (node
->rb_left
)
334 return (struct rb_node
*)node
;
337 /* No right-hand children. Everything down and left is
338 smaller than us, so any 'next' node must be in the general
339 direction of our parent. Go up the tree; any time the
340 ancestor is a right-hand child of its parent, keep going
341 up. First time it's a left-hand child of its parent, said
342 parent is our 'next' node. */
343 while ((parent
= rb_parent(node
)) && node
== parent
->rb_right
)
348 EXPORT_SYMBOL(rb_next
);
350 struct rb_node
*rb_prev(const struct rb_node
*node
)
352 struct rb_node
*parent
;
354 if (rb_parent(node
) == node
)
357 /* If we have a left-hand child, go down and then right as far
360 node
= node
->rb_left
;
361 while (node
->rb_right
)
363 return (struct rb_node
*)node
;
366 /* No left-hand children. Go up till we find an ancestor which
367 is a right-hand child of its parent */
368 while ((parent
= rb_parent(node
)) && node
== parent
->rb_left
)
373 EXPORT_SYMBOL(rb_prev
);
375 void rb_replace_node(struct rb_node
*victim
, struct rb_node
*new,
376 struct rb_root
*root
)
378 struct rb_node
*parent
= rb_parent(victim
);
380 /* Set the surrounding nodes to point to the replacement */
382 if (victim
== parent
->rb_left
)
383 parent
->rb_left
= new;
385 parent
->rb_right
= new;
390 rb_set_parent(victim
->rb_left
, new);
391 if (victim
->rb_right
)
392 rb_set_parent(victim
->rb_right
, new);
394 /* Copy the pointers/colour from the victim to the replacement */
397 EXPORT_SYMBOL(rb_replace_node
);