2 SPDX-License-Identifier: GPL-2.0-or-later
5 (C) 1999 Andrea Arcangeli <andrea@suse.de>
6 (C) 2002 David Woodhouse <dwmw2@infradead.org>
13 static void __rb_rotate_left(struct rb_node
*node
, struct rb_root
*root
)
15 struct rb_node
*right
= node
->rb_right
;
16 struct rb_node
*parent
= rb_parent(node
);
18 if ((node
->rb_right
= right
->rb_left
))
19 rb_set_parent(right
->rb_left
, node
);
20 right
->rb_left
= node
;
22 rb_set_parent(right
, parent
);
26 if (node
== parent
->rb_left
)
27 parent
->rb_left
= right
;
29 parent
->rb_right
= right
;
32 root
->rb_node
= right
;
33 rb_set_parent(node
, right
);
36 static void __rb_rotate_right(struct rb_node
*node
, struct rb_root
*root
)
38 struct rb_node
*left
= node
->rb_left
;
39 struct rb_node
*parent
= rb_parent(node
);
41 if ((node
->rb_left
= left
->rb_right
))
42 rb_set_parent(left
->rb_right
, node
);
43 left
->rb_right
= node
;
45 rb_set_parent(left
, parent
);
49 if (node
== parent
->rb_right
)
50 parent
->rb_right
= left
;
52 parent
->rb_left
= left
;
56 rb_set_parent(node
, left
);
59 void rb_insert_color(struct rb_node
*node
, struct rb_root
*root
)
61 struct rb_node
*parent
, *gparent
;
63 while ((parent
= rb_parent(node
)) && rb_is_red(parent
))
65 gparent
= rb_parent(parent
);
67 if (parent
== gparent
->rb_left
)
70 register struct rb_node
*uncle
= gparent
->rb_right
;
71 if (uncle
&& rb_is_red(uncle
))
81 if (parent
->rb_right
== node
)
83 register struct rb_node
*tmp
;
84 __rb_rotate_left(parent
, root
);
92 __rb_rotate_right(gparent
, root
);
95 register struct rb_node
*uncle
= gparent
->rb_left
;
96 if (uncle
&& rb_is_red(uncle
))
106 if (parent
->rb_left
== node
)
108 register struct rb_node
*tmp
;
109 __rb_rotate_right(parent
, root
);
115 rb_set_black(parent
);
117 __rb_rotate_left(gparent
, root
);
121 rb_set_black(root
->rb_node
);
124 static void __rb_erase_color(struct rb_node
*node
, struct rb_node
*parent
,
125 struct rb_root
*root
)
127 struct rb_node
*other
;
129 while ((!node
|| rb_is_black(node
)) && node
!= root
->rb_node
)
131 if (parent
->rb_left
== node
)
133 other
= parent
->rb_right
;
134 if (rb_is_red(other
))
138 __rb_rotate_left(parent
, root
);
139 other
= parent
->rb_right
;
141 if ((!other
->rb_left
|| rb_is_black(other
->rb_left
)) &&
142 (!other
->rb_right
|| rb_is_black(other
->rb_right
)))
146 parent
= rb_parent(node
);
150 if (!other
->rb_right
|| rb_is_black(other
->rb_right
))
152 rb_set_black(other
->rb_left
);
154 __rb_rotate_right(other
, root
);
155 other
= parent
->rb_right
;
157 rb_set_color(other
, rb_color(parent
));
158 rb_set_black(parent
);
159 rb_set_black(other
->rb_right
);
160 __rb_rotate_left(parent
, root
);
161 node
= root
->rb_node
;
167 other
= parent
->rb_left
;
168 if (rb_is_red(other
))
172 __rb_rotate_right(parent
, root
);
173 other
= parent
->rb_left
;
175 if ((!other
->rb_left
|| rb_is_black(other
->rb_left
)) &&
176 (!other
->rb_right
|| rb_is_black(other
->rb_right
)))
180 parent
= rb_parent(node
);
184 if (!other
->rb_left
|| rb_is_black(other
->rb_left
))
186 rb_set_black(other
->rb_right
);
188 __rb_rotate_left(other
, root
);
189 other
= parent
->rb_left
;
191 rb_set_color(other
, rb_color(parent
));
192 rb_set_black(parent
);
193 rb_set_black(other
->rb_left
);
194 __rb_rotate_right(parent
, root
);
195 node
= root
->rb_node
;
204 void rb_erase(struct rb_node
*node
, struct rb_root
*root
)
206 struct rb_node
*child
, *parent
;
210 child
= node
->rb_right
;
211 else if (!node
->rb_right
)
212 child
= node
->rb_left
;
215 struct rb_node
*old
= node
, *left
;
217 node
= node
->rb_right
;
218 while ((left
= node
->rb_left
) != NULL
)
220 child
= node
->rb_right
;
221 parent
= rb_parent(node
);
222 color
= rb_color(node
);
225 rb_set_parent(child
, parent
);
227 parent
->rb_right
= child
;
230 parent
->rb_left
= child
;
232 node
->rb_parent_color
= old
->rb_parent_color
;
233 node
->rb_right
= old
->rb_right
;
234 node
->rb_left
= old
->rb_left
;
238 if (rb_parent(old
)->rb_left
== old
)
239 rb_parent(old
)->rb_left
= node
;
241 rb_parent(old
)->rb_right
= node
;
243 root
->rb_node
= node
;
245 rb_set_parent(old
->rb_left
, node
);
247 rb_set_parent(old
->rb_right
, node
);
251 parent
= rb_parent(node
);
252 color
= rb_color(node
);
255 rb_set_parent(child
, parent
);
258 if (parent
->rb_left
== node
)
259 parent
->rb_left
= child
;
261 parent
->rb_right
= child
;
264 root
->rb_node
= child
;
267 if (color
== RB_BLACK
)
268 __rb_erase_color(child
, parent
, root
);
272 * This function returns the first node (in sort order) of the tree.
274 struct rb_node
*rb_first(const struct rb_root
*root
)
286 struct rb_node
*rb_last(const struct rb_root
*root
)
298 struct rb_node
*rb_next(const struct rb_node
*node
)
300 struct rb_node
*parent
;
302 if (rb_parent(node
) == node
)
305 /* If we have a right-hand child, go down and then left as far
307 if (node
->rb_right
) {
308 node
= node
->rb_right
;
309 while (node
->rb_left
)
311 return (struct rb_node
*)node
;
314 /* No right-hand children. Everything down and left is
315 smaller than us, so any 'next' node must be in the general
316 direction of our parent. Go up the tree; any time the
317 ancestor is a right-hand child of its parent, keep going
318 up. First time it's a left-hand child of its parent, said
319 parent is our 'next' node. */
320 while ((parent
= rb_parent(node
)) && node
== parent
->rb_right
)
326 struct rb_node
*rb_prev(const struct rb_node
*node
)
328 struct rb_node
*parent
;
330 if (rb_parent(node
) == node
)
333 /* If we have a left-hand child, go down and then right as far
336 node
= node
->rb_left
;
337 while (node
->rb_right
)
339 return (struct rb_node
*)node
;
342 /* No left-hand children. Go up till we find an ancestor which
343 is a right-hand child of its parent */
344 while ((parent
= rb_parent(node
)) && node
== parent
->rb_left
)
350 void rb_replace_node(struct rb_node
*victim
, struct rb_node
*new,
351 struct rb_root
*root
)
353 struct rb_node
*parent
= rb_parent(victim
);
355 /* Set the surrounding nodes to point to the replacement */
357 if (victim
== parent
->rb_left
)
358 parent
->rb_left
= new;
360 parent
->rb_right
= new;
365 rb_set_parent(victim
->rb_left
, new);
366 if (victim
->rb_right
)
367 rb_set_parent(victim
->rb_right
, new);
369 /* Copy the pointers/colour from the victim to the replacement */