Root/
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 | struct rb_node *parent = rb_parent(node); |
30 | |
31 | if ((node->rb_right = right->rb_left)) |
32 | rb_set_parent(right->rb_left, node); |
33 | right->rb_left = node; |
34 | |
35 | rb_set_parent(right, parent); |
36 | |
37 | if (parent) |
38 | { |
39 | if (node == parent->rb_left) |
40 | parent->rb_left = right; |
41 | else |
42 | parent->rb_right = right; |
43 | } |
44 | else |
45 | root->rb_node = right; |
46 | rb_set_parent(node, right); |
47 | } |
48 | |
49 | static void __rb_rotate_right(struct rb_node *node, struct rb_root *root) |
50 | { |
51 | struct rb_node *left = node->rb_left; |
52 | struct rb_node *parent = rb_parent(node); |
53 | |
54 | if ((node->rb_left = left->rb_right)) |
55 | rb_set_parent(left->rb_right, node); |
56 | left->rb_right = node; |
57 | |
58 | rb_set_parent(left, parent); |
59 | |
60 | if (parent) |
61 | { |
62 | if (node == parent->rb_right) |
63 | parent->rb_right = left; |
64 | else |
65 | parent->rb_left = left; |
66 | } |
67 | else |
68 | root->rb_node = left; |
69 | rb_set_parent(node, left); |
70 | } |
71 | |
72 | void rb_insert_color(struct rb_node *node, struct rb_root *root) |
73 | { |
74 | struct rb_node *parent, *gparent; |
75 | |
76 | while ((parent = rb_parent(node)) && rb_is_red(parent)) |
77 | { |
78 | gparent = rb_parent(parent); |
79 | |
80 | if (parent == gparent->rb_left) |
81 | { |
82 | { |
83 | register struct rb_node *uncle = gparent->rb_right; |
84 | if (uncle && rb_is_red(uncle)) |
85 | { |
86 | rb_set_black(uncle); |
87 | rb_set_black(parent); |
88 | rb_set_red(gparent); |
89 | node = gparent; |
90 | continue; |
91 | } |
92 | } |
93 | |
94 | if (parent->rb_right == node) |
95 | { |
96 | register struct rb_node *tmp; |
97 | __rb_rotate_left(parent, root); |
98 | tmp = parent; |
99 | parent = node; |
100 | node = tmp; |
101 | } |
102 | |
103 | rb_set_black(parent); |
104 | rb_set_red(gparent); |
105 | __rb_rotate_right(gparent, root); |
106 | } else { |
107 | { |
108 | register struct rb_node *uncle = gparent->rb_left; |
109 | if (uncle && rb_is_red(uncle)) |
110 | { |
111 | rb_set_black(uncle); |
112 | rb_set_black(parent); |
113 | rb_set_red(gparent); |
114 | node = gparent; |
115 | continue; |
116 | } |
117 | } |
118 | |
119 | if (parent->rb_left == node) |
120 | { |
121 | register struct rb_node *tmp; |
122 | __rb_rotate_right(parent, root); |
123 | tmp = parent; |
124 | parent = node; |
125 | node = tmp; |
126 | } |
127 | |
128 | rb_set_black(parent); |
129 | rb_set_red(gparent); |
130 | __rb_rotate_left(gparent, root); |
131 | } |
132 | } |
133 | |
134 | rb_set_black(root->rb_node); |
135 | } |
136 | EXPORT_SYMBOL(rb_insert_color); |
137 | |
138 | static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, |
139 | struct rb_root *root) |
140 | { |
141 | struct rb_node *other; |
142 | |
143 | while ((!node || rb_is_black(node)) && node != root->rb_node) |
144 | { |
145 | if (parent->rb_left == node) |
146 | { |
147 | other = parent->rb_right; |
148 | if (rb_is_red(other)) |
149 | { |
150 | rb_set_black(other); |
151 | rb_set_red(parent); |
152 | __rb_rotate_left(parent, root); |
153 | other = parent->rb_right; |
154 | } |
155 | if ((!other->rb_left || rb_is_black(other->rb_left)) && |
156 | (!other->rb_right || rb_is_black(other->rb_right))) |
157 | { |
158 | rb_set_red(other); |
159 | node = parent; |
160 | parent = rb_parent(node); |
161 | } |
162 | else |
163 | { |
164 | if (!other->rb_right || rb_is_black(other->rb_right)) |
165 | { |
166 | rb_set_black(other->rb_left); |
167 | rb_set_red(other); |
168 | __rb_rotate_right(other, root); |
169 | other = parent->rb_right; |
170 | } |
171 | rb_set_color(other, rb_color(parent)); |
172 | rb_set_black(parent); |
173 | rb_set_black(other->rb_right); |
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 (rb_is_red(other)) |
183 | { |
184 | rb_set_black(other); |
185 | rb_set_red(parent); |
186 | __rb_rotate_right(parent, root); |
187 | other = parent->rb_left; |
188 | } |
189 | if ((!other->rb_left || rb_is_black(other->rb_left)) && |
190 | (!other->rb_right || rb_is_black(other->rb_right))) |
191 | { |
192 | rb_set_red(other); |
193 | node = parent; |
194 | parent = rb_parent(node); |
195 | } |
196 | else |
197 | { |
198 | if (!other->rb_left || rb_is_black(other->rb_left)) |
199 | { |
200 | rb_set_black(other->rb_right); |
201 | rb_set_red(other); |
202 | __rb_rotate_left(other, root); |
203 | other = parent->rb_left; |
204 | } |
205 | rb_set_color(other, rb_color(parent)); |
206 | rb_set_black(parent); |
207 | rb_set_black(other->rb_left); |
208 | __rb_rotate_right(parent, root); |
209 | node = root->rb_node; |
210 | break; |
211 | } |
212 | } |
213 | } |
214 | if (node) |
215 | rb_set_black(node); |
216 | } |
217 | |
218 | void rb_erase(struct rb_node *node, struct rb_root *root) |
219 | { |
220 | struct rb_node *child, *parent; |
221 | int color; |
222 | |
223 | if (!node->rb_left) |
224 | child = node->rb_right; |
225 | else if (!node->rb_right) |
226 | child = node->rb_left; |
227 | else |
228 | { |
229 | struct rb_node *old = node, *left; |
230 | |
231 | node = node->rb_right; |
232 | while ((left = node->rb_left) != NULL) |
233 | node = left; |
234 | |
235 | if (rb_parent(old)) { |
236 | if (rb_parent(old)->rb_left == old) |
237 | rb_parent(old)->rb_left = node; |
238 | else |
239 | rb_parent(old)->rb_right = node; |
240 | } else |
241 | root->rb_node = node; |
242 | |
243 | child = node->rb_right; |
244 | parent = rb_parent(node); |
245 | color = rb_color(node); |
246 | |
247 | if (parent == old) { |
248 | parent = node; |
249 | } else { |
250 | if (child) |
251 | rb_set_parent(child, parent); |
252 | parent->rb_left = child; |
253 | |
254 | node->rb_right = old->rb_right; |
255 | rb_set_parent(old->rb_right, node); |
256 | } |
257 | |
258 | node->rb_parent_color = old->rb_parent_color; |
259 | node->rb_left = old->rb_left; |
260 | rb_set_parent(old->rb_left, node); |
261 | |
262 | goto color; |
263 | } |
264 | |
265 | parent = rb_parent(node); |
266 | color = rb_color(node); |
267 | |
268 | if (child) |
269 | rb_set_parent(child, parent); |
270 | if (parent) |
271 | { |
272 | if (parent->rb_left == node) |
273 | parent->rb_left = child; |
274 | else |
275 | parent->rb_right = child; |
276 | } |
277 | else |
278 | root->rb_node = child; |
279 | |
280 | color: |
281 | if (color == RB_BLACK) |
282 | __rb_erase_color(child, parent, root); |
283 | } |
284 | EXPORT_SYMBOL(rb_erase); |
285 | |
286 | /* |
287 | * This function returns the first node (in sort order) of the tree. |
288 | */ |
289 | struct rb_node *rb_first(const struct rb_root *root) |
290 | { |
291 | struct rb_node *n; |
292 | |
293 | n = root->rb_node; |
294 | if (!n) |
295 | return NULL; |
296 | while (n->rb_left) |
297 | n = n->rb_left; |
298 | return n; |
299 | } |
300 | EXPORT_SYMBOL(rb_first); |
301 | |
302 | struct rb_node *rb_last(const 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_right) |
310 | n = n->rb_right; |
311 | return n; |
312 | } |
313 | EXPORT_SYMBOL(rb_last); |
314 | |
315 | struct rb_node *rb_next(const struct rb_node *node) |
316 | { |
317 | struct rb_node *parent; |
318 | |
319 | if (rb_parent(node) == node) |
320 | return NULL; |
321 | |
322 | /* If we have a right-hand child, go down and then left as far |
323 | as we can. */ |
324 | if (node->rb_right) { |
325 | node = node->rb_right; |
326 | while (node->rb_left) |
327 | node=node->rb_left; |
328 | return (struct rb_node *)node; |
329 | } |
330 | |
331 | /* No right-hand children. Everything down and left is |
332 | smaller than us, so any 'next' node must be in the general |
333 | direction of our parent. Go up the tree; any time the |
334 | ancestor is a right-hand child of its parent, keep going |
335 | up. First time it's a left-hand child of its parent, said |
336 | parent is our 'next' node. */ |
337 | while ((parent = rb_parent(node)) && node == parent->rb_right) |
338 | node = parent; |
339 | |
340 | return parent; |
341 | } |
342 | EXPORT_SYMBOL(rb_next); |
343 | |
344 | struct rb_node *rb_prev(const struct rb_node *node) |
345 | { |
346 | struct rb_node *parent; |
347 | |
348 | if (rb_parent(node) == node) |
349 | return NULL; |
350 | |
351 | /* If we have a left-hand child, go down and then right as far |
352 | as we can. */ |
353 | if (node->rb_left) { |
354 | node = node->rb_left; |
355 | while (node->rb_right) |
356 | node=node->rb_right; |
357 | return (struct rb_node *)node; |
358 | } |
359 | |
360 | /* No left-hand children. Go up till we find an ancestor which |
361 | is a right-hand child of its parent */ |
362 | while ((parent = rb_parent(node)) && node == parent->rb_left) |
363 | node = parent; |
364 | |
365 | return parent; |
366 | } |
367 | EXPORT_SYMBOL(rb_prev); |
368 | |
369 | void rb_replace_node(struct rb_node *victim, struct rb_node *new, |
370 | struct rb_root *root) |
371 | { |
372 | struct rb_node *parent = rb_parent(victim); |
373 | |
374 | /* Set the surrounding nodes to point to the replacement */ |
375 | if (parent) { |
376 | if (victim == parent->rb_left) |
377 | parent->rb_left = new; |
378 | else |
379 | parent->rb_right = new; |
380 | } else { |
381 | root->rb_node = new; |
382 | } |
383 | if (victim->rb_left) |
384 | rb_set_parent(victim->rb_left, new); |
385 | if (victim->rb_right) |
386 | rb_set_parent(victim->rb_right, new); |
387 | |
388 | /* Copy the pointers/colour from the victim to the replacement */ |
389 | *new = *victim; |
390 | } |
391 | EXPORT_SYMBOL(rb_replace_node); |
392 |
Branches:
ben-wpan
ben-wpan-stefan
javiroman/ks7010
jz-2.6.34
jz-2.6.34-rc5
jz-2.6.34-rc6
jz-2.6.34-rc7
jz-2.6.35
jz-2.6.36
jz-2.6.37
jz-2.6.38
jz-2.6.39
jz-3.0
jz-3.1
jz-3.11
jz-3.12
jz-3.13
jz-3.15
jz-3.16
jz-3.18-dt
jz-3.2
jz-3.3
jz-3.4
jz-3.5
jz-3.6
jz-3.6-rc2-pwm
jz-3.9
jz-3.9-clk
jz-3.9-rc8
jz47xx
jz47xx-2.6.38
master
Tags:
od-2011-09-04
od-2011-09-18
v2.6.34-rc5
v2.6.34-rc6
v2.6.34-rc7
v3.9