ia64/xen-unstable

view xen/common/rbtree.c @ 19835:edfdeb150f27

Fix buildsystem to detect udev > version 124

udev removed the udevinfo symlink from versions higher than 123 and
xen's build-system could not detect if udev is in place and has the
required version.

Signed-off-by: Marc-A. Dahlhaus <mad@wol.de>
author Keir Fraser <keir.fraser@citrix.com>
date Thu Jun 25 13:02:37 2009 +0100 (2009-06-25)
parents f210a633571c
children
line source
1 /*
2 Red Black Trees
3 (C) 1999 Andrea Arcangeli <andrea@suse.de>
4 (C) 2002 David Woodhouse <dwmw2@infradead.org>
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.
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.
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
20 linux/lib/rbtree.c
21 */
23 #include <xen/config.h>
24 #include <xen/types.h>
25 #include <xen/rbtree.h>
27 static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
28 {
29 struct rb_node *right = node->rb_right;
30 struct rb_node *parent = rb_parent(node);
32 if ((node->rb_right = right->rb_left))
33 rb_set_parent(right->rb_left, node);
34 right->rb_left = node;
36 rb_set_parent(right, parent);
38 if (parent)
39 {
40 if (node == parent->rb_left)
41 parent->rb_left = right;
42 else
43 parent->rb_right = right;
44 }
45 else
46 root->rb_node = right;
47 rb_set_parent(node, right);
48 }
50 static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
51 {
52 struct rb_node *left = node->rb_left;
53 struct rb_node *parent = rb_parent(node);
55 if ((node->rb_left = left->rb_right))
56 rb_set_parent(left->rb_right, node);
57 left->rb_right = node;
59 rb_set_parent(left, parent);
61 if (parent)
62 {
63 if (node == parent->rb_right)
64 parent->rb_right = left;
65 else
66 parent->rb_left = left;
67 }
68 else
69 root->rb_node = left;
70 rb_set_parent(node, left);
71 }
73 void rb_insert_color(struct rb_node *node, struct rb_root *root)
74 {
75 struct rb_node *parent, *gparent;
77 while ((parent = rb_parent(node)) && rb_is_red(parent))
78 {
79 gparent = rb_parent(parent);
81 if (parent == gparent->rb_left)
82 {
83 {
84 register struct rb_node *uncle = gparent->rb_right;
85 if (uncle && rb_is_red(uncle))
86 {
87 rb_set_black(uncle);
88 rb_set_black(parent);
89 rb_set_red(gparent);
90 node = gparent;
91 continue;
92 }
93 }
95 if (parent->rb_right == node)
96 {
97 register struct rb_node *tmp;
98 __rb_rotate_left(parent, root);
99 tmp = parent;
100 parent = node;
101 node = tmp;
102 }
104 rb_set_black(parent);
105 rb_set_red(gparent);
106 __rb_rotate_right(gparent, root);
107 } else {
108 {
109 register struct rb_node *uncle = gparent->rb_left;
110 if (uncle && rb_is_red(uncle))
111 {
112 rb_set_black(uncle);
113 rb_set_black(parent);
114 rb_set_red(gparent);
115 node = gparent;
116 continue;
117 }
118 }
120 if (parent->rb_left == node)
121 {
122 register struct rb_node *tmp;
123 __rb_rotate_right(parent, root);
124 tmp = parent;
125 parent = node;
126 node = tmp;
127 }
129 rb_set_black(parent);
130 rb_set_red(gparent);
131 __rb_rotate_left(gparent, root);
132 }
133 }
135 rb_set_black(root->rb_node);
136 }
137 EXPORT_SYMBOL(rb_insert_color);
139 static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
140 struct rb_root *root)
141 {
142 struct rb_node *other;
144 while ((!node || rb_is_black(node)) && node != root->rb_node)
145 {
146 if (parent->rb_left == node)
147 {
148 other = parent->rb_right;
149 if (rb_is_red(other))
150 {
151 rb_set_black(other);
152 rb_set_red(parent);
153 __rb_rotate_left(parent, root);
154 other = parent->rb_right;
155 }
156 if ((!other->rb_left || rb_is_black(other->rb_left)) &&
157 (!other->rb_right || rb_is_black(other->rb_right)))
158 {
159 rb_set_red(other);
160 node = parent;
161 parent = rb_parent(node);
162 }
163 else
164 {
165 if (!other->rb_right || rb_is_black(other->rb_right))
166 {
167 struct rb_node *o_left;
168 if ((o_left = other->rb_left))
169 rb_set_black(o_left);
170 rb_set_red(other);
171 __rb_rotate_right(other, root);
172 other = parent->rb_right;
173 }
174 rb_set_color(other, rb_color(parent));
175 rb_set_black(parent);
176 if (other->rb_right)
177 rb_set_black(other->rb_right);
178 __rb_rotate_left(parent, root);
179 node = root->rb_node;
180 break;
181 }
182 }
183 else
184 {
185 other = parent->rb_left;
186 if (rb_is_red(other))
187 {
188 rb_set_black(other);
189 rb_set_red(parent);
190 __rb_rotate_right(parent, root);
191 other = parent->rb_left;
192 }
193 if ((!other->rb_left || rb_is_black(other->rb_left)) &&
194 (!other->rb_right || rb_is_black(other->rb_right)))
195 {
196 rb_set_red(other);
197 node = parent;
198 parent = rb_parent(node);
199 }
200 else
201 {
202 if (!other->rb_left || rb_is_black(other->rb_left))
203 {
204 register struct rb_node *o_right;
205 if ((o_right = other->rb_right))
206 rb_set_black(o_right);
207 rb_set_red(other);
208 __rb_rotate_left(other, root);
209 other = parent->rb_left;
210 }
211 rb_set_color(other, rb_color(parent));
212 rb_set_black(parent);
213 if (other->rb_left)
214 rb_set_black(other->rb_left);
215 __rb_rotate_right(parent, root);
216 node = root->rb_node;
217 break;
218 }
219 }
220 }
221 if (node)
222 rb_set_black(node);
223 }
225 void rb_erase(struct rb_node *node, struct rb_root *root)
226 {
227 struct rb_node *child, *parent;
228 int color;
230 if (!node->rb_left)
231 child = node->rb_right;
232 else if (!node->rb_right)
233 child = node->rb_left;
234 else
235 {
236 struct rb_node *old = node, *left;
238 node = node->rb_right;
239 while ((left = node->rb_left) != NULL)
240 node = left;
241 child = node->rb_right;
242 parent = rb_parent(node);
243 color = rb_color(node);
245 if (child)
246 rb_set_parent(child, parent);
247 if (parent == old) {
248 parent->rb_right = child;
249 parent = node;
250 } else
251 parent->rb_left = child;
253 node->rb_parent_color = old->rb_parent_color;
254 node->rb_right = old->rb_right;
255 node->rb_left = old->rb_left;
257 if (rb_parent(old))
258 {
259 if (rb_parent(old)->rb_left == old)
260 rb_parent(old)->rb_left = node;
261 else
262 rb_parent(old)->rb_right = node;
263 } else
264 root->rb_node = node;
266 rb_set_parent(old->rb_left, node);
267 if (old->rb_right)
268 rb_set_parent(old->rb_right, node);
269 goto color;
270 }
272 parent = rb_parent(node);
273 color = rb_color(node);
275 if (child)
276 rb_set_parent(child, parent);
277 if (parent)
278 {
279 if (parent->rb_left == node)
280 parent->rb_left = child;
281 else
282 parent->rb_right = child;
283 }
284 else
285 root->rb_node = child;
287 color:
288 if (color == RB_BLACK)
289 __rb_erase_color(child, parent, root);
290 }
291 EXPORT_SYMBOL(rb_erase);
293 /*
294 * This function returns the first node (in sort order) of the tree.
295 */
296 struct rb_node *rb_first(struct rb_root *root)
297 {
298 struct rb_node *n;
300 n = root->rb_node;
301 if (!n)
302 return NULL;
303 while (n->rb_left)
304 n = n->rb_left;
305 return n;
306 }
307 EXPORT_SYMBOL(rb_first);
309 struct rb_node *rb_last(struct rb_root *root)
310 {
311 struct rb_node *n;
313 n = root->rb_node;
314 if (!n)
315 return NULL;
316 while (n->rb_right)
317 n = n->rb_right;
318 return n;
319 }
320 EXPORT_SYMBOL(rb_last);
322 struct rb_node *rb_next(struct rb_node *node)
323 {
324 struct rb_node *parent;
326 if (rb_parent(node) == node)
327 return NULL;
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 }
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 ((parent = rb_parent(node)) && node == parent->rb_right)
345 node = parent;
347 return parent;
348 }
349 EXPORT_SYMBOL(rb_next);
351 struct rb_node *rb_prev(struct rb_node *node)
352 {
353 struct rb_node *parent;
355 if (rb_parent(node) == node)
356 return NULL;
358 /* If we have a left-hand child, go down and then right as far
359 as we can. */
360 if (node->rb_left) {
361 node = node->rb_left;
362 while (node->rb_right)
363 node=node->rb_right;
364 return node;
365 }
367 /* No left-hand children. Go up till we find an ancestor which
368 is a right-hand child of its parent */
369 while ((parent = rb_parent(node)) && node == parent->rb_left)
370 node = parent;
372 return parent;
373 }
374 EXPORT_SYMBOL(rb_prev);
376 void rb_replace_node(struct rb_node *victim, struct rb_node *new,
377 struct rb_root *root)
378 {
379 struct rb_node *parent = rb_parent(victim);
381 /* Set the surrounding nodes to point to the replacement */
382 if (parent) {
383 if (victim == parent->rb_left)
384 parent->rb_left = new;
385 else
386 parent->rb_right = new;
387 } else {
388 root->rb_node = new;
389 }
390 if (victim->rb_left)
391 rb_set_parent(victim->rb_left, new);
392 if (victim->rb_right)
393 rb_set_parent(victim->rb_right, new);
395 /* Copy the pointers/colour from the victim to the replacement */
396 *new = *victim;
397 }
398 EXPORT_SYMBOL(rb_replace_node);