1 /*
2 Red Black Trees
3 (C) 1999 Andrea Arcangeli <andrea@suse.de>
4
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.
9
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.
14
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
18
19 linux/lib/rbtree.c
20 */
21
22 #include <linux/rbtree.h>
23 #include <linux/module.h>
24
__rb_rotate_left(rb_node_t * node,rb_root_t * root)25 static void __rb_rotate_left(rb_node_t * node, rb_root_t * root)
26 {
27 rb_node_t * right = node->rb_right;
28
29 if ((node->rb_right = right->rb_left))
30 right->rb_left->rb_parent = node;
31 right->rb_left = node;
32
33 if ((right->rb_parent = node->rb_parent))
34 {
35 if (node == node->rb_parent->rb_left)
36 node->rb_parent->rb_left = right;
37 else
38 node->rb_parent->rb_right = right;
39 }
40 else
41 root->rb_node = right;
42 node->rb_parent = right;
43 }
44
__rb_rotate_right(rb_node_t * node,rb_root_t * root)45 static void __rb_rotate_right(rb_node_t * node, rb_root_t * root)
46 {
47 rb_node_t * left = node->rb_left;
48
49 if ((node->rb_left = left->rb_right))
50 left->rb_right->rb_parent = node;
51 left->rb_right = node;
52
53 if ((left->rb_parent = node->rb_parent))
54 {
55 if (node == node->rb_parent->rb_right)
56 node->rb_parent->rb_right = left;
57 else
58 node->rb_parent->rb_left = left;
59 }
60 else
61 root->rb_node = left;
62 node->rb_parent = left;
63 }
64
rb_insert_color(rb_node_t * node,rb_root_t * root)65 void rb_insert_color(rb_node_t * node, rb_root_t * root)
66 {
67 rb_node_t * parent, * gparent;
68
69 while ((parent = node->rb_parent) && parent->rb_color == RB_RED)
70 {
71 gparent = parent->rb_parent;
72
73 if (parent == gparent->rb_left)
74 {
75 {
76 register rb_node_t * uncle = gparent->rb_right;
77 if (uncle && uncle->rb_color == RB_RED)
78 {
79 uncle->rb_color = RB_BLACK;
80 parent->rb_color = RB_BLACK;
81 gparent->rb_color = RB_RED;
82 node = gparent;
83 continue;
84 }
85 }
86
87 if (parent->rb_right == node)
88 {
89 register rb_node_t * tmp;
90 __rb_rotate_left(parent, root);
91 tmp = parent;
92 parent = node;
93 node = tmp;
94 }
95
96 parent->rb_color = RB_BLACK;
97 gparent->rb_color = RB_RED;
98 __rb_rotate_right(gparent, root);
99 } else {
100 {
101 register rb_node_t * uncle = gparent->rb_left;
102 if (uncle && uncle->rb_color == RB_RED)
103 {
104 uncle->rb_color = RB_BLACK;
105 parent->rb_color = RB_BLACK;
106 gparent->rb_color = RB_RED;
107 node = gparent;
108 continue;
109 }
110 }
111
112 if (parent->rb_left == node)
113 {
114 register rb_node_t * tmp;
115 __rb_rotate_right(parent, root);
116 tmp = parent;
117 parent = node;
118 node = tmp;
119 }
120
121 parent->rb_color = RB_BLACK;
122 gparent->rb_color = RB_RED;
123 __rb_rotate_left(gparent, root);
124 }
125 }
126
127 root->rb_node->rb_color = RB_BLACK;
128 }
129 EXPORT_SYMBOL(rb_insert_color);
130
__rb_erase_color(rb_node_t * node,rb_node_t * parent,rb_root_t * root)131 static void __rb_erase_color(rb_node_t * node, rb_node_t * parent,
132 rb_root_t * root)
133 {
134 rb_node_t * other;
135
136 while ((!node || node->rb_color == RB_BLACK) && node != root->rb_node)
137 {
138 if (parent->rb_left == node)
139 {
140 other = parent->rb_right;
141 if (other->rb_color == RB_RED)
142 {
143 other->rb_color = RB_BLACK;
144 parent->rb_color = RB_RED;
145 __rb_rotate_left(parent, root);
146 other = parent->rb_right;
147 }
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))
152 {
153 other->rb_color = RB_RED;
154 node = parent;
155 parent = node->rb_parent;
156 }
157 else
158 {
159 if (!other->rb_right ||
160 other->rb_right->rb_color == RB_BLACK)
161 {
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;
168 }
169 other->rb_color = parent->rb_color;
170 parent->rb_color = RB_BLACK;
171 if (other->rb_right)
172 other->rb_right->rb_color = RB_BLACK;
173 __rb_rotate_left(parent, root);
174 node = root->rb_node;
175 break;
176 }
177 }
178 else
179 {
180 other = parent->rb_left;
181 if (other->rb_color == RB_RED)
182 {
183 other->rb_color = RB_BLACK;
184 parent->rb_color = RB_RED;
185 __rb_rotate_right(parent, root);
186 other = parent->rb_left;
187 }
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))
192 {
193 other->rb_color = RB_RED;
194 node = parent;
195 parent = node->rb_parent;
196 }
197 else
198 {
199 if (!other->rb_left ||
200 other->rb_left->rb_color == RB_BLACK)
201 {
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;
208 }
209 other->rb_color = parent->rb_color;
210 parent->rb_color = RB_BLACK;
211 if (other->rb_left)
212 other->rb_left->rb_color = RB_BLACK;
213 __rb_rotate_right(parent, root);
214 node = root->rb_node;
215 break;
216 }
217 }
218 }
219 if (node)
220 node->rb_color = RB_BLACK;
221 }
222
rb_erase(rb_node_t * node,rb_root_t * root)223 void rb_erase(rb_node_t * node, rb_root_t * root)
224 {
225 rb_node_t * child, * parent;
226 int color;
227
228 if (!node->rb_left)
229 child = node->rb_right;
230 else if (!node->rb_right)
231 child = node->rb_left;
232 else
233 {
234 rb_node_t * old = node, * left;
235
236 node = node->rb_right;
237 while ((left = node->rb_left))
238 node = left;
239 child = node->rb_right;
240 parent = node->rb_parent;
241 color = node->rb_color;
242
243 if (child)
244 child->rb_parent = parent;
245 if (parent)
246 {
247 if (parent->rb_left == node)
248 parent->rb_left = child;
249 else
250 parent->rb_right = child;
251 }
252 else
253 root->rb_node = child;
254
255 if (node->rb_parent == old)
256 parent = node;
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;
261
262 if (old->rb_parent)
263 {
264 if (old->rb_parent->rb_left == old)
265 old->rb_parent->rb_left = node;
266 else
267 old->rb_parent->rb_right = node;
268 } else
269 root->rb_node = node;
270
271 old->rb_left->rb_parent = node;
272 if (old->rb_right)
273 old->rb_right->rb_parent = node;
274 goto color;
275 }
276
277 parent = node->rb_parent;
278 color = node->rb_color;
279
280 if (child)
281 child->rb_parent = parent;
282 if (parent)
283 {
284 if (parent->rb_left == node)
285 parent->rb_left = child;
286 else
287 parent->rb_right = child;
288 }
289 else
290 root->rb_node = child;
291
292 color:
293 if (color == RB_BLACK)
294 __rb_erase_color(child, parent, root);
295 }
296 EXPORT_SYMBOL(rb_erase);
297
298 /*
299 * This function returns the first node (in sort order) of the tree.
300 */
rb_first(rb_root_t * root)301 rb_node_t *rb_first(rb_root_t *root)
302 {
303 rb_node_t *n;
304
305 n = root->rb_node;
306 if (!n)
307 return NULL;
308 while (n->rb_left)
309 n = n->rb_left;
310 return n;
311 }
312 EXPORT_SYMBOL(rb_first);
313
rb_last(rb_root_t * root)314 rb_node_t *rb_last(rb_root_t *root)
315 {
316 rb_node_t *n;
317
318 n = root->rb_node;
319 if (!n)
320 return NULL;
321 while (n->rb_right)
322 n = n->rb_right;
323 return n;
324 }
325 EXPORT_SYMBOL(rb_last);
326
rb_next(rb_node_t * node)327 rb_node_t *rb_next(rb_node_t *node)
328 {
329 /* If we have a right-hand child, go down and then left as far
330 as we can. */
331 if (node->rb_right) {
332 node = node->rb_right;
333 while (node->rb_left)
334 node = node->rb_left;
335 return node;
336 }
337
338 /* No right-hand children. Everything down and left is
339 smaller than us, so any 'next' node must be in the general
340 direction of our parent. Go up the tree; any time the
341 ancestor is a right-hand child of its parent, keep going
342 up. First time it's a left-hand child of its parent, said
343 parent is our 'next' node. */
344 while (node->rb_parent && node == node->rb_parent->rb_right)
345 node = node->rb_parent;
346
347 return node->rb_parent;
348 }
349 EXPORT_SYMBOL(rb_next);
350
rb_prev(rb_node_t * node)351 rb_node_t *rb_prev(rb_node_t *node)
352 {
353 /* If we have a left-hand child, go down and then right as far
354 as we can. */
355 if (node->rb_left) {
356 node = node->rb_left;
357 while (node->rb_right)
358 node = node->rb_right;
359 return node;
360 }
361
362 /* No left-hand children. Go up till we find an ancestor which
363 is a right-hand child of its parent */
364 while (node->rb_parent && node == node->rb_parent->rb_left)
365 node = node->rb_parent;
366
367 return node->rb_parent;
368 }
369 EXPORT_SYMBOL(rb_prev);
370