debuggers.hg

view xen/common/rbtree.c @ 22855:1d1eec7e1fb4

xl: Perform minimal validation of virtual disk file while parsing config file

This patch performs some very basic validation on the virtual disk
file passed through the config file. This validation ensures that we
don't go too far with the initialization like spawn qemu and more
while there could be some potentially fundamental issues.

[ Patch fixed up to work with PHYSTYPE_EMPTY 22808:6ec61438713a -iwj ]

Signed-off-by: Kamala Narasimhan <kamala.narasimhan@citrix.com>
Acked-by: Ian Jackson <ian.jackson@eu.citrix.com>
Signed-off-by: Ian Jackson <ian.jackson@eu.citrix.com>
Committed-by: Ian Jackson <ian.jackson@eu.citrix.com>
author Kamala Narasimhan <kamala.narasimhan@gmail.com>
date Tue Jan 25 18:09:49 2011 +0000 (2011-01-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);