3 (C) 1999 Andrea Arcangeli <andrea@suse.de>
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation; either version 2 of the License, or
8 (at your option) any later version.
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with this program; if not, write to the Free Software
17 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
22 #include <linux/rbtree.h>
23 #include <linux/module.h>
25 static void __rb_rotate_left(rb_node_t * node, rb_root_t * root)
27 rb_node_t * 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(rb_node_t * node, rb_root_t * root)
47 rb_node_t * 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(rb_node_t * node, rb_root_t * root)
67 rb_node_t * 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 rb_node_t * 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 rb_node_t * 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 rb_node_t * 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 rb_node_t * 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;
129 EXPORT_SYMBOL(rb_insert_color);
131 static void __rb_erase_color(rb_node_t * node, rb_node_t * parent,
136 while ((!node || node->rb_color == RB_BLACK) && node != root->rb_node)
138 if (parent->rb_left == node)
140 other = parent->rb_right;
141 if (other->rb_color == RB_RED)
143 other->rb_color = RB_BLACK;
144 parent->rb_color = RB_RED;
145 __rb_rotate_left(parent, root);
146 other = parent->rb_right;
148 if ((!other->rb_left ||
149 other->rb_left->rb_color == RB_BLACK)
150 && (!other->rb_right ||
151 other->rb_right->rb_color == RB_BLACK))
153 other->rb_color = RB_RED;
155 parent = node->rb_parent;
159 if (!other->rb_right ||
160 other->rb_right->rb_color == RB_BLACK)
162 register rb_node_t * o_left;
163 if ((o_left = other->rb_left))
164 o_left->rb_color = RB_BLACK;
165 other->rb_color = RB_RED;
166 __rb_rotate_right(other, root);
167 other = parent->rb_right;
169 other->rb_color = parent->rb_color;
170 parent->rb_color = RB_BLACK;
172 other->rb_right->rb_color = RB_BLACK;
173 __rb_rotate_left(parent, root);
174 node = root->rb_node;
180 other = parent->rb_left;
181 if (other->rb_color == RB_RED)
183 other->rb_color = RB_BLACK;
184 parent->rb_color = RB_RED;
185 __rb_rotate_right(parent, root);
186 other = parent->rb_left;
188 if ((!other->rb_left ||
189 other->rb_left->rb_color == RB_BLACK)
190 && (!other->rb_right ||
191 other->rb_right->rb_color == RB_BLACK))
193 other->rb_color = RB_RED;
195 parent = node->rb_parent;
199 if (!other->rb_left ||
200 other->rb_left->rb_color == RB_BLACK)
202 register rb_node_t * o_right;
203 if ((o_right = other->rb_right))
204 o_right->rb_color = RB_BLACK;
205 other->rb_color = RB_RED;
206 __rb_rotate_left(other, root);
207 other = parent->rb_left;
209 other->rb_color = parent->rb_color;
210 parent->rb_color = RB_BLACK;
212 other->rb_left->rb_color = RB_BLACK;
213 __rb_rotate_right(parent, root);
214 node = root->rb_node;
220 node->rb_color = RB_BLACK;
223 void rb_erase(rb_node_t * node, rb_root_t * root)
225 rb_node_t * child, * parent;
229 child = node->rb_right;
230 else if (!node->rb_right)
231 child = node->rb_left;
234 rb_node_t * old = node, * left;
236 node = node->rb_right;
237 while ((left = node->rb_left))
239 child = node->rb_right;
240 parent = node->rb_parent;
241 color = node->rb_color;
244 child->rb_parent = parent;
247 if (parent->rb_left == node)
248 parent->rb_left = child;
250 parent->rb_right = child;
253 root->rb_node = child;
255 if (node->rb_parent == old)
257 node->rb_parent = old->rb_parent;
258 node->rb_color = old->rb_color;
259 node->rb_right = old->rb_right;
260 node->rb_left = old->rb_left;
264 if (old->rb_parent->rb_left == old)
265 old->rb_parent->rb_left = node;
267 old->rb_parent->rb_right = node;
269 root->rb_node = node;
271 old->rb_left->rb_parent = node;
273 old->rb_right->rb_parent = node;
277 parent = node->rb_parent;
278 color = node->rb_color;
281 child->rb_parent = parent;
284 if (parent->rb_left == node)
285 parent->rb_left = child;
287 parent->rb_right = child;
290 root->rb_node = child;
293 if (color == RB_BLACK)
294 __rb_erase_color(child, parent, root);
296 EXPORT_SYMBOL(rb_erase);