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