ia64/xen-unstable

view xen/common/rangeset.c @ 9776:72f9c751d3ea

Replace &foo[0] with foo where the latter seems cleaner
(which is usually, and particularly when its an argument
to one of the bitops functions).

Signed-off-by: Keir Fraser <keir@xensource.com>
author kaf24@firebug.cl.cam.ac.uk
date Wed Apr 19 18:32:20 2006 +0100 (2006-04-19)
parents 03382076472c
children 03fd2accb4d9
line source
1 /******************************************************************************
2 * rangeset.c
3 *
4 * Creation, maintenance and automatic destruction of per-domain sets of
5 * numeric ranges.
6 *
7 * Copyright (c) 2005, K A Fraser
8 */
10 #include <xen/sched.h>
11 #include <xen/rangeset.h>
13 /* An inclusive range [s,e] and pointer to next range in ascending order. */
14 struct range {
15 struct list_head list;
16 unsigned long s, e;
17 };
19 struct rangeset {
20 /* Owning domain and threaded list of rangesets. */
21 struct list_head rangeset_list;
22 struct domain *domain;
24 /* Ordered list of ranges contained in this set, and protecting lock. */
25 struct list_head range_list;
26 spinlock_t lock;
28 /* Pretty-printing name. */
29 char name[32];
31 /* RANGESETF flags. */
32 unsigned int flags;
33 };
35 /*****************************
36 * Private range functions hide the underlying linked-list implemnetation.
37 */
39 /* Find highest range lower than or containing s. NULL if no such range. */
40 static struct range *find_range(
41 struct rangeset *r, unsigned long s)
42 {
43 struct range *x = NULL, *y;
45 list_for_each_entry ( y, &r->range_list, list )
46 {
47 if ( y->s > s )
48 break;
49 x = y;
50 }
52 return x;
53 }
55 /* Return the lowest range in the set r, or NULL if r is empty. */
56 static struct range *first_range(
57 struct rangeset *r)
58 {
59 if ( list_empty(&r->range_list) )
60 return NULL;
61 return list_entry(r->range_list.next, struct range, list);
62 }
64 /* Return range following x in ascending order, or NULL if x is the highest. */
65 static struct range *next_range(
66 struct rangeset *r, struct range *x)
67 {
68 if ( x->list.next == &r->range_list )
69 return NULL;
70 return list_entry(x->list.next, struct range, list);
71 }
73 /* Insert range y after range x in r. Insert as first range if x is NULL. */
74 static void insert_range(
75 struct rangeset *r, struct range *x, struct range *y)
76 {
77 list_add(&y->list, (x != NULL) ? &x->list : &r->range_list);
78 }
80 /* Remove a range from its list and free it. */
81 static void destroy_range(
82 struct range *x)
83 {
84 list_del(&x->list);
85 xfree(x);
86 }
88 /*****************************
89 * Core public functions
90 */
92 int rangeset_add_range(
93 struct rangeset *r, unsigned long s, unsigned long e)
94 {
95 struct range *x, *y;
96 int rc = 0;
98 ASSERT(s <= e);
100 spin_lock(&r->lock);
102 x = find_range(r, s);
103 y = find_range(r, e);
105 if ( x == y )
106 {
107 if ( (x == NULL) || ((x->e < s) && ((x->e + 1) != s)) )
108 {
109 x = xmalloc(struct range);
110 if ( x == NULL )
111 {
112 rc = -ENOMEM;
113 goto out;
114 }
116 x->s = s;
117 x->e = e;
119 insert_range(r, y, x);
120 }
121 else if ( x->e < e )
122 x->e = e;
123 }
124 else
125 {
126 if ( x == NULL )
127 {
128 x = first_range(r);
129 x->s = s;
130 }
131 else if ( (x->e < s) && ((x->e + 1) != s) )
132 {
133 x = next_range(r, x);
134 x->s = s;
135 }
137 x->e = (y->e > e) ? y->e : e;
139 for ( ; ; )
140 {
141 y = next_range(r, x);
142 if ( (y == NULL) || (y->e > x->e) )
143 break;
144 destroy_range(y);
145 }
146 }
148 y = next_range(r, x);
149 if ( (y != NULL) && ((x->e + 1) == y->s) )
150 {
151 x->e = y->e;
152 destroy_range(y);
153 }
155 out:
156 spin_unlock(&r->lock);
157 return rc;
158 }
160 int rangeset_remove_range(
161 struct rangeset *r, unsigned long s, unsigned long e)
162 {
163 struct range *x, *y, *t;
164 int rc = 0;
166 ASSERT(s <= e);
168 spin_lock(&r->lock);
170 x = find_range(r, s);
171 y = find_range(r, e);
173 if ( x == y )
174 {
175 if ( (x == NULL) || (x->e < s) )
176 goto out;
178 if ( (x->s < s) && (x->e > e) )
179 {
180 y = xmalloc(struct range);
181 if ( y == NULL )
182 {
183 rc = -ENOMEM;
184 goto out;
185 }
187 y->s = e + 1;
188 y->e = x->e;
189 x->e = s - 1;
191 insert_range(r, x, y);
192 }
193 else if ( (x->s == s) && (x->e <= e) )
194 destroy_range(x);
195 else if ( x->s == s )
196 x->s = e + 1;
197 else if ( x->e <= e )
198 x->e = s - 1;
199 }
200 else
201 {
202 if ( x == NULL )
203 x = first_range(r);
205 if ( x->s < s )
206 {
207 x->e = s - 1;
208 x = next_range(r, x);
209 }
211 while ( x != y )
212 {
213 t = x;
214 x = next_range(r, x);
215 destroy_range(t);
216 }
218 x->s = e + 1;
219 if ( x->s > x->e )
220 destroy_range(x);
221 }
223 out:
224 spin_unlock(&r->lock);
225 return rc;
226 }
228 int rangeset_contains_range(
229 struct rangeset *r, unsigned long s, unsigned long e)
230 {
231 struct range *x;
232 int contains;
234 ASSERT(s <= e);
236 spin_lock(&r->lock);
237 x = find_range(r, s);
238 contains = (x && (x->e >= e));
239 spin_unlock(&r->lock);
241 return contains;
242 }
244 int rangeset_add_singleton(
245 struct rangeset *r, unsigned long s)
246 {
247 return rangeset_add_range(r, s, s);
248 }
250 int rangeset_remove_singleton(
251 struct rangeset *r, unsigned long s)
252 {
253 return rangeset_remove_range(r, s, s);
254 }
256 int rangeset_contains_singleton(
257 struct rangeset *r, unsigned long s)
258 {
259 return rangeset_contains_range(r, s, s);
260 }
262 int rangeset_is_empty(
263 struct rangeset *r)
264 {
265 return list_empty(&r->range_list);
266 }
268 struct rangeset *rangeset_new(
269 struct domain *d, char *name, unsigned int flags)
270 {
271 struct rangeset *r;
273 r = xmalloc(struct rangeset);
274 if ( r == NULL )
275 return NULL;
277 spin_lock_init(&r->lock);
278 INIT_LIST_HEAD(&r->range_list);
280 BUG_ON(flags & ~RANGESETF_prettyprint_hex);
281 r->flags = flags;
283 if ( name != NULL )
284 {
285 strncpy(r->name, name, sizeof(r->name));
286 r->name[sizeof(r->name)-1] = '\0';
287 }
288 else
289 {
290 sprintf(r->name, "(no name)");
291 }
293 if ( (r->domain = d) != NULL )
294 {
295 spin_lock(&d->rangesets_lock);
296 list_add(&r->rangeset_list, &d->rangesets);
297 spin_unlock(&d->rangesets_lock);
298 }
300 return r;
301 }
303 void rangeset_destroy(
304 struct rangeset *r)
305 {
306 struct range *x;
308 if ( r == NULL )
309 return;
311 if ( r->domain != NULL )
312 {
313 spin_lock(&r->domain->rangesets_lock);
314 list_del(&r->rangeset_list);
315 spin_unlock(&r->domain->rangesets_lock);
316 }
318 while ( (x = first_range(r)) != NULL )
319 destroy_range(x);
321 xfree(r);
322 }
324 void rangeset_domain_initialise(
325 struct domain *d)
326 {
327 INIT_LIST_HEAD(&d->rangesets);
328 spin_lock_init(&d->rangesets_lock);
329 }
331 void rangeset_domain_destroy(
332 struct domain *d)
333 {
334 struct rangeset *r;
336 while ( !list_empty(&d->rangesets) )
337 {
338 r = list_entry(d->rangesets.next, struct rangeset, rangeset_list);
340 BUG_ON(r->domain != d);
341 r->domain = NULL;
342 list_del(&r->rangeset_list);
344 rangeset_destroy(r);
345 }
346 }
348 /*****************************
349 * Pretty-printing functions
350 */
352 static void print_limit(struct rangeset *r, unsigned long s)
353 {
354 printk((r->flags & RANGESETF_prettyprint_hex) ? "%lx" : "%lu", s);
355 }
357 void rangeset_printk(
358 struct rangeset *r)
359 {
360 int nr_printed = 0;
361 struct range *x;
363 spin_lock(&r->lock);
365 printk("%-10s {", r->name);
367 for ( x = first_range(r); x != NULL; x = next_range(r, x) )
368 {
369 if ( nr_printed++ )
370 printk(",");
371 printk(" ");
372 print_limit(r, x->s);
373 if ( x->s != x->e )
374 {
375 printk("-");
376 print_limit(r, x->e);
377 }
378 }
380 printk(" }");
382 spin_unlock(&r->lock);
383 }
385 void rangeset_domain_printk(
386 struct domain *d)
387 {
388 struct rangeset *r;
390 printk("Rangesets belonging to domain %u:\n", d->domain_id);
392 spin_lock(&d->rangesets_lock);
394 if ( list_empty(&d->rangesets) )
395 printk(" None\n");
397 list_for_each_entry ( r, &d->rangesets, rangeset_list )
398 {
399 printk(" ");
400 rangeset_printk(r);
401 printk("\n");
402 }
404 spin_unlock(&d->rangesets_lock);
405 }