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