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
25 static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
27 struct rb_node *right = node->rb_right;
29 if ((node->rb_right = right->rb_left))
30 right->rb_left->rb_parent = node;
31 right->rb_left = node;
33 if ((right->rb_parent = node->rb_parent))
35 if (node == node->rb_parent->rb_left)
36 node->rb_parent->rb_left = right;
38 node->rb_parent->rb_right = right;
41 root->rb_node = right;
42 node->rb_parent = right;
45 static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
47 struct rb_node *left = node->rb_left;
49 if ((node->rb_left = left->rb_right))
50 left->rb_right->rb_parent = node;
51 left->rb_right = node;
53 if ((left->rb_parent = node->rb_parent))
55 if (node == node->rb_parent->rb_right)
56 node->rb_parent->rb_right = left;
58 node->rb_parent->rb_left = left;
62 node->rb_parent = left;
65 void rb_insert_color(struct rb_node *node, struct rb_root *root)
67 struct rb_node *parent, *gparent;
69 while ((parent = node->rb_parent) && parent->rb_color == RB_RED)
71 gparent = parent->rb_parent;
73 if (parent == gparent->rb_left)
76 register struct rb_node *uncle = gparent->rb_right;
77 if (uncle && uncle->rb_color == RB_RED)
79 uncle->rb_color = RB_BLACK;
80 parent->rb_color = RB_BLACK;
81 gparent->rb_color = RB_RED;
87 if (parent->rb_right == node)
89 register struct rb_node *tmp;
90 __rb_rotate_left(parent, root);
96 parent->rb_color = RB_BLACK;
97 gparent->rb_color = RB_RED;
98 __rb_rotate_right(gparent, root);
101 register struct rb_node *uncle = gparent->rb_left;
102 if (uncle && uncle->rb_color == RB_RED)
104 uncle->rb_color = RB_BLACK;
105 parent->rb_color = RB_BLACK;
106 gparent->rb_color = RB_RED;
112 if (parent->rb_left == node)
114 register struct rb_node *tmp;
115 __rb_rotate_right(parent, root);
121 parent->rb_color = RB_BLACK;
122 gparent->rb_color = RB_RED;
123 __rb_rotate_left(gparent, root);
127 root->rb_node->rb_color = RB_BLACK;
130 static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
131 struct rb_root *root)
133 struct rb_node *other;
135 while ((!node || node->rb_color == RB_BLACK) && node != root->rb_node)
137 if (parent->rb_left == node)
139 other = parent->rb_right;
140 if (other->rb_color == RB_RED)
142 other->rb_color = RB_BLACK;
143 parent->rb_color = RB_RED;
144 __rb_rotate_left(parent, root);
145 other = parent->rb_right;
147 if ((!other->rb_left ||
148 other->rb_left->rb_color == RB_BLACK)
149 && (!other->rb_right ||
150 other->rb_right->rb_color == RB_BLACK))
152 other->rb_color = RB_RED;
154 parent = node->rb_parent;
158 if (!other->rb_right ||
159 other->rb_right->rb_color == RB_BLACK)
161 register struct rb_node *o_left;
162 if ((o_left = other->rb_left))
163 o_left->rb_color = RB_BLACK;
164 other->rb_color = RB_RED;
165 __rb_rotate_right(other, root);
166 other = parent->rb_right;
168 other->rb_color = parent->rb_color;
169 parent->rb_color = RB_BLACK;
171 other->rb_right->rb_color = RB_BLACK;
172 __rb_rotate_left(parent, root);
173 node = root->rb_node;
179 other = parent->rb_left;
180 if (other->rb_color == RB_RED)
182 other->rb_color = RB_BLACK;
183 parent->rb_color = RB_RED;
184 __rb_rotate_right(parent, root);
185 other = parent->rb_left;
187 if ((!other->rb_left ||
188 other->rb_left->rb_color == RB_BLACK)
189 && (!other->rb_right ||
190 other->rb_right->rb_color == RB_BLACK))
192 other->rb_color = RB_RED;
194 parent = node->rb_parent;
198 if (!other->rb_left ||
199 other->rb_left->rb_color == RB_BLACK)
201 register struct rb_node *o_right;
202 if ((o_right = other->rb_right))
203 o_right->rb_color = RB_BLACK;
204 other->rb_color = RB_RED;
205 __rb_rotate_left(other, root);
206 other = parent->rb_left;
208 other->rb_color = parent->rb_color;
209 parent->rb_color = RB_BLACK;
211 other->rb_left->rb_color = RB_BLACK;
212 __rb_rotate_right(parent, root);
213 node = root->rb_node;
219 node->rb_color = RB_BLACK;
222 void rb_erase(struct rb_node *node, struct rb_root *root)
224 struct rb_node *child, *parent;
228 child = node->rb_right;
229 else if (!node->rb_right)
230 child = node->rb_left;
233 struct rb_node *old = node, *left;
235 node = node->rb_right;
236 while ((left = node->rb_left) != NULL)
238 child = node->rb_right;
239 parent = node->rb_parent;
240 color = node->rb_color;
243 child->rb_parent = parent;
246 if (parent->rb_left == node)
247 parent->rb_left = child;
249 parent->rb_right = child;
252 root->rb_node = child;
254 if (node->rb_parent == old)
256 node->rb_parent = old->rb_parent;
257 node->rb_color = old->rb_color;
258 node->rb_right = old->rb_right;
259 node->rb_left = old->rb_left;
263 if (old->rb_parent->rb_left == old)
264 old->rb_parent->rb_left = node;
266 old->rb_parent->rb_right = node;
268 root->rb_node = node;
270 old->rb_left->rb_parent = node;
272 old->rb_right->rb_parent = node;
276 parent = node->rb_parent;
277 color = node->rb_color;
280 child->rb_parent = parent;
283 if (parent->rb_left == node)
284 parent->rb_left = child;
286 parent->rb_right = child;
289 root->rb_node = child;
292 if (color == RB_BLACK)
293 __rb_erase_color(child, parent, root);
297 * This function returns the first node (in sort order) of the tree.
299 struct rb_node *rb_first(struct rb_root *root)
311 struct rb_node *rb_last(struct rb_root *root)
323 struct rb_node *rb_next(struct rb_node *node)
325 /* If we have a right-hand child, go down and then left as far
327 if (node->rb_right) {
328 node = node->rb_right;
329 while (node->rb_left)
334 /* No right-hand children. Everything down and left is
335 smaller than us, so any 'next' node must be in the general
336 direction of our parent. Go up the tree; any time the
337 ancestor is a right-hand child of its parent, keep going
338 up. First time it's a left-hand child of its parent, said
339 parent is our 'next' node. */
340 while (node->rb_parent && node == node->rb_parent->rb_right)
341 node = node->rb_parent;
343 return node->rb_parent;
346 struct rb_node *rb_prev(struct rb_node *node)
348 /* If we have a left-hand child, go down and then right as far
351 node = node->rb_left;
352 while (node->rb_right)
357 /* No left-hand children. Go up till we find an ancestor which
358 is a right-hand child of its parent */
359 while (node->rb_parent && node == node->rb_parent->rb_left)
360 node = node->rb_parent;
362 return node->rb_parent;
365 void rb_replace_node(struct rb_node *victim, struct rb_node *new,
366 struct rb_root *root)
368 struct rb_node *parent = victim->rb_parent;
370 /* Set the surrounding nodes to point to the replacement */
372 if (victim == parent->rb_left)
373 parent->rb_left = new;
375 parent->rb_right = new;
380 victim->rb_left->rb_parent = new;
381 if (victim->rb_right)
382 victim->rb_right->rb_parent = new;
384 /* Copy the pointers/colour from the victim to the replacement */