ia64/xen-unstable

view xen/common/bitmap.c @ 9706:3c05406f5e0a

In some cases, say for instance for some bizzare reason
the tree was checked out of CVS, which doens't neccessarily
store file permissions, mkbuildtree may not be executable.
So run them explicitly via bash.

Signed-Off-By: Horms <horms@verge.net.au>
author kaf24@firebug.cl.cam.ac.uk
date Thu Apr 13 11:24:00 2006 +0100 (2006-04-13)
parents 4293d6760cef
children fa5bc90a3cb7
line source
1 /*
2 * lib/bitmap.c
3 * Helper functions for bitmap.h.
4 *
5 * This source code is licensed under the GNU General Public License,
6 * Version 2. See the file COPYING for more details.
7 */
8 #include <xen/config.h>
9 #include <xen/types.h>
10 #include <xen/errno.h>
11 #include <xen/bitmap.h>
12 #include <xen/bitops.h>
14 /*
15 * bitmaps provide an array of bits, implemented using an an
16 * array of unsigned longs. The number of valid bits in a
17 * given bitmap does _not_ need to be an exact multiple of
18 * BITS_PER_LONG.
19 *
20 * The possible unused bits in the last, partially used word
21 * of a bitmap are 'don't care'. The implementation makes
22 * no particular effort to keep them zero. It ensures that
23 * their value will not affect the results of any operation.
24 * The bitmap operations that return Boolean (bitmap_empty,
25 * for example) or scalar (bitmap_weight, for example) results
26 * carefully filter out these unused bits from impacting their
27 * results.
28 *
29 * These operations actually hold to a slightly stronger rule:
30 * if you don't input any bitmaps to these ops that have some
31 * unused bits set, then they won't output any set unused bits
32 * in output bitmaps.
33 *
34 * The byte ordering of bitmaps is more natural on little
35 * endian architectures. See the big-endian headers
36 * include/asm-ppc64/bitops.h and include/asm-s390/bitops.h
37 * for the best explanations of this ordering.
38 */
40 int __bitmap_empty(const unsigned long *bitmap, int bits)
41 {
42 int k, lim = bits/BITS_PER_LONG;
43 for (k = 0; k < lim; ++k)
44 if (bitmap[k])
45 return 0;
47 if (bits % BITS_PER_LONG)
48 if (bitmap[k] & BITMAP_LAST_WORD_MASK(bits))
49 return 0;
51 return 1;
52 }
53 EXPORT_SYMBOL(__bitmap_empty);
55 int __bitmap_full(const unsigned long *bitmap, int bits)
56 {
57 int k, lim = bits/BITS_PER_LONG;
58 for (k = 0; k < lim; ++k)
59 if (~bitmap[k])
60 return 0;
62 if (bits % BITS_PER_LONG)
63 if (~bitmap[k] & BITMAP_LAST_WORD_MASK(bits))
64 return 0;
66 return 1;
67 }
68 EXPORT_SYMBOL(__bitmap_full);
70 int __bitmap_equal(const unsigned long *bitmap1,
71 const unsigned long *bitmap2, int bits)
72 {
73 int k, lim = bits/BITS_PER_LONG;
74 for (k = 0; k < lim; ++k)
75 if (bitmap1[k] != bitmap2[k])
76 return 0;
78 if (bits % BITS_PER_LONG)
79 if ((bitmap1[k] ^ bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits))
80 return 0;
82 return 1;
83 }
84 EXPORT_SYMBOL(__bitmap_equal);
86 void __bitmap_complement(unsigned long *dst, const unsigned long *src, int bits)
87 {
88 int k, lim = bits/BITS_PER_LONG;
89 for (k = 0; k < lim; ++k)
90 dst[k] = ~src[k];
92 if (bits % BITS_PER_LONG)
93 dst[k] = ~src[k] & BITMAP_LAST_WORD_MASK(bits);
94 }
95 EXPORT_SYMBOL(__bitmap_complement);
97 /*
98 * __bitmap_shift_right - logical right shift of the bits in a bitmap
99 * @dst - destination bitmap
100 * @src - source bitmap
101 * @nbits - shift by this many bits
102 * @bits - bitmap size, in bits
103 *
104 * Shifting right (dividing) means moving bits in the MS -> LS bit
105 * direction. Zeros are fed into the vacated MS positions and the
106 * LS bits shifted off the bottom are lost.
107 */
108 void __bitmap_shift_right(unsigned long *dst,
109 const unsigned long *src, int shift, int bits)
110 {
111 int k, lim = BITS_TO_LONGS(bits), left = bits % BITS_PER_LONG;
112 int off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG;
113 unsigned long mask = (1UL << left) - 1;
114 for (k = 0; off + k < lim; ++k) {
115 unsigned long upper, lower;
117 /*
118 * If shift is not word aligned, take lower rem bits of
119 * word above and make them the top rem bits of result.
120 */
121 if (!rem || off + k + 1 >= lim)
122 upper = 0;
123 else {
124 upper = src[off + k + 1];
125 if (off + k + 1 == lim - 1 && left)
126 upper &= mask;
127 }
128 lower = src[off + k];
129 if (left && off + k == lim - 1)
130 lower &= mask;
131 dst[k] = upper << (BITS_PER_LONG - rem) | lower >> rem;
132 if (left && k == lim - 1)
133 dst[k] &= mask;
134 }
135 if (off)
136 memset(&dst[lim - off], 0, off*sizeof(unsigned long));
137 }
138 EXPORT_SYMBOL(__bitmap_shift_right);
141 /*
142 * __bitmap_shift_left - logical left shift of the bits in a bitmap
143 * @dst - destination bitmap
144 * @src - source bitmap
145 * @nbits - shift by this many bits
146 * @bits - bitmap size, in bits
147 *
148 * Shifting left (multiplying) means moving bits in the LS -> MS
149 * direction. Zeros are fed into the vacated LS bit positions
150 * and those MS bits shifted off the top are lost.
151 */
153 void __bitmap_shift_left(unsigned long *dst,
154 const unsigned long *src, int shift, int bits)
155 {
156 int k, lim = BITS_TO_LONGS(bits), left = bits % BITS_PER_LONG;
157 int off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG;
158 for (k = lim - off - 1; k >= 0; --k) {
159 unsigned long upper, lower;
161 /*
162 * If shift is not word aligned, take upper rem bits of
163 * word below and make them the bottom rem bits of result.
164 */
165 if (rem && k > 0)
166 lower = src[k - 1];
167 else
168 lower = 0;
169 upper = src[k];
170 if (left && k == lim - 1)
171 upper &= (1UL << left) - 1;
172 dst[k + off] = lower >> (BITS_PER_LONG - rem) | upper << rem;
173 if (left && k + off == lim - 1)
174 dst[k + off] &= (1UL << left) - 1;
175 }
176 if (off)
177 memset(dst, 0, off*sizeof(unsigned long));
178 }
179 EXPORT_SYMBOL(__bitmap_shift_left);
181 void __bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
182 const unsigned long *bitmap2, int bits)
183 {
184 int k;
185 int nr = BITS_TO_LONGS(bits);
187 for (k = 0; k < nr; k++)
188 dst[k] = bitmap1[k] & bitmap2[k];
189 }
190 EXPORT_SYMBOL(__bitmap_and);
192 void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
193 const unsigned long *bitmap2, int bits)
194 {
195 int k;
196 int nr = BITS_TO_LONGS(bits);
198 for (k = 0; k < nr; k++)
199 dst[k] = bitmap1[k] | bitmap2[k];
200 }
201 EXPORT_SYMBOL(__bitmap_or);
203 void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1,
204 const unsigned long *bitmap2, int bits)
205 {
206 int k;
207 int nr = BITS_TO_LONGS(bits);
209 for (k = 0; k < nr; k++)
210 dst[k] = bitmap1[k] ^ bitmap2[k];
211 }
212 EXPORT_SYMBOL(__bitmap_xor);
214 void __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1,
215 const unsigned long *bitmap2, int bits)
216 {
217 int k;
218 int nr = BITS_TO_LONGS(bits);
220 for (k = 0; k < nr; k++)
221 dst[k] = bitmap1[k] & ~bitmap2[k];
222 }
223 EXPORT_SYMBOL(__bitmap_andnot);
225 int __bitmap_intersects(const unsigned long *bitmap1,
226 const unsigned long *bitmap2, int bits)
227 {
228 int k, lim = bits/BITS_PER_LONG;
229 for (k = 0; k < lim; ++k)
230 if (bitmap1[k] & bitmap2[k])
231 return 1;
233 if (bits % BITS_PER_LONG)
234 if ((bitmap1[k] & bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits))
235 return 1;
236 return 0;
237 }
238 EXPORT_SYMBOL(__bitmap_intersects);
240 int __bitmap_subset(const unsigned long *bitmap1,
241 const unsigned long *bitmap2, int bits)
242 {
243 int k, lim = bits/BITS_PER_LONG;
244 for (k = 0; k < lim; ++k)
245 if (bitmap1[k] & ~bitmap2[k])
246 return 0;
248 if (bits % BITS_PER_LONG)
249 if ((bitmap1[k] & ~bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits))
250 return 0;
251 return 1;
252 }
253 EXPORT_SYMBOL(__bitmap_subset);
255 #if BITS_PER_LONG == 32
256 int __bitmap_weight(const unsigned long *bitmap, int bits)
257 {
258 int k, w = 0, lim = bits/BITS_PER_LONG;
260 for (k = 0; k < lim; k++)
261 w += hweight32(bitmap[k]);
263 if (bits % BITS_PER_LONG)
264 w += hweight32(bitmap[k] & BITMAP_LAST_WORD_MASK(bits));
266 return w;
267 }
268 #else
269 int __bitmap_weight(const unsigned long *bitmap, int bits)
270 {
271 int k, w = 0, lim = bits/BITS_PER_LONG;
273 for (k = 0; k < lim; k++)
274 w += hweight64(bitmap[k]);
276 if (bits % BITS_PER_LONG)
277 w += hweight64(bitmap[k] & BITMAP_LAST_WORD_MASK(bits));
279 return w;
280 }
281 #endif
282 EXPORT_SYMBOL(__bitmap_weight);
284 /*
285 * Bitmap printing & parsing functions: first version by Bill Irwin,
286 * second version by Paul Jackson, third by Joe Korty.
287 */
289 #define CHUNKSZ 32
290 #define nbits_to_hold_value(val) fls(val)
291 #define roundup_power2(val,modulus) (((val) + (modulus) - 1) & ~((modulus) - 1))
292 #define unhex(c) (isdigit(c) ? (c - '0') : (toupper(c) - 'A' + 10))
293 #define BASEDEC 10 /* fancier cpuset lists input in decimal */
295 /**
296 * bitmap_scnprintf - convert bitmap to an ASCII hex string.
297 * @buf: byte buffer into which string is placed
298 * @buflen: reserved size of @buf, in bytes
299 * @maskp: pointer to bitmap to convert
300 * @nmaskbits: size of bitmap, in bits
301 *
302 * Exactly @nmaskbits bits are displayed. Hex digits are grouped into
303 * comma-separated sets of eight digits per set.
304 */
305 int bitmap_scnprintf(char *buf, unsigned int buflen,
306 const unsigned long *maskp, int nmaskbits)
307 {
308 int i, word, bit, len = 0;
309 unsigned long val;
310 const char *sep = "";
311 int chunksz;
312 u32 chunkmask;
314 chunksz = nmaskbits & (CHUNKSZ - 1);
315 if (chunksz == 0)
316 chunksz = CHUNKSZ;
318 i = roundup_power2(nmaskbits, CHUNKSZ) - CHUNKSZ;
319 for (; i >= 0; i -= CHUNKSZ) {
320 chunkmask = ((1ULL << chunksz) - 1);
321 word = i / BITS_PER_LONG;
322 bit = i % BITS_PER_LONG;
323 val = (maskp[word] >> bit) & chunkmask;
324 len += scnprintf(buf+len, buflen-len, "%s%0*lx", sep,
325 (chunksz+3)/4, val);
326 chunksz = CHUNKSZ;
327 sep = ",";
328 }
329 return len;
330 }
331 EXPORT_SYMBOL(bitmap_scnprintf);
333 /*
334 * bscnl_emit(buf, buflen, rbot, rtop, bp)
335 *
336 * Helper routine for bitmap_scnlistprintf(). Write decimal number
337 * or range to buf, suppressing output past buf+buflen, with optional
338 * comma-prefix. Return len of what would be written to buf, if it
339 * all fit.
340 */
341 static inline int bscnl_emit(char *buf, int buflen, int rbot, int rtop, int len)
342 {
343 if (len > 0)
344 len += scnprintf(buf + len, buflen - len, ",");
345 if (rbot == rtop)
346 len += scnprintf(buf + len, buflen - len, "%d", rbot);
347 else
348 len += scnprintf(buf + len, buflen - len, "%d-%d", rbot, rtop);
349 return len;
350 }
352 /**
353 * bitmap_scnlistprintf - convert bitmap to list format ASCII string
354 * @buf: byte buffer into which string is placed
355 * @buflen: reserved size of @buf, in bytes
356 * @maskp: pointer to bitmap to convert
357 * @nmaskbits: size of bitmap, in bits
358 *
359 * Output format is a comma-separated list of decimal numbers and
360 * ranges. Consecutively set bits are shown as two hyphen-separated
361 * decimal numbers, the smallest and largest bit numbers set in
362 * the range. Output format is compatible with the format
363 * accepted as input by bitmap_parselist().
364 *
365 * The return value is the number of characters which would be
366 * generated for the given input, excluding the trailing '\0', as
367 * per ISO C99.
368 */
369 int bitmap_scnlistprintf(char *buf, unsigned int buflen,
370 const unsigned long *maskp, int nmaskbits)
371 {
372 int len = 0;
373 /* current bit is 'cur', most recently seen range is [rbot, rtop] */
374 int cur, rbot, rtop;
376 rbot = cur = find_first_bit(maskp, nmaskbits);
377 while (cur < nmaskbits) {
378 rtop = cur;
379 cur = find_next_bit(maskp, nmaskbits, cur+1);
380 if (cur >= nmaskbits || cur > rtop + 1) {
381 len = bscnl_emit(buf, buflen, rbot, rtop, len);
382 rbot = cur;
383 }
384 }
385 return len;
386 }
387 EXPORT_SYMBOL(bitmap_scnlistprintf);
389 /**
390 * bitmap_find_free_region - find a contiguous aligned mem region
391 * @bitmap: an array of unsigned longs corresponding to the bitmap
392 * @bits: number of bits in the bitmap
393 * @order: region size to find (size is actually 1<<order)
394 *
395 * This is used to allocate a memory region from a bitmap. The idea is
396 * that the region has to be 1<<order sized and 1<<order aligned (this
397 * makes the search algorithm much faster).
398 *
399 * The region is marked as set bits in the bitmap if a free one is
400 * found.
401 *
402 * Returns either beginning of region or negative error
403 */
404 int bitmap_find_free_region(unsigned long *bitmap, int bits, int order)
405 {
406 unsigned long mask;
407 int pages = 1 << order;
408 int i;
410 if(pages > BITS_PER_LONG)
411 return -EINVAL;
413 /* make a mask of the order */
414 mask = (1ul << (pages - 1));
415 mask += mask - 1;
417 /* run up the bitmap pages bits at a time */
418 for (i = 0; i < bits; i += pages) {
419 int index = i/BITS_PER_LONG;
420 int offset = i - (index * BITS_PER_LONG);
421 if((bitmap[index] & (mask << offset)) == 0) {
422 /* set region in bimap */
423 bitmap[index] |= (mask << offset);
424 return i;
425 }
426 }
427 return -ENOMEM;
428 }
429 EXPORT_SYMBOL(bitmap_find_free_region);
431 /**
432 * bitmap_release_region - release allocated bitmap region
433 * @bitmap: a pointer to the bitmap
434 * @pos: the beginning of the region
435 * @order: the order of the bits to release (number is 1<<order)
436 *
437 * This is the complement to __bitmap_find_free_region and releases
438 * the found region (by clearing it in the bitmap).
439 */
440 void bitmap_release_region(unsigned long *bitmap, int pos, int order)
441 {
442 int pages = 1 << order;
443 unsigned long mask = (1ul << (pages - 1));
444 int index = pos/BITS_PER_LONG;
445 int offset = pos - (index * BITS_PER_LONG);
446 mask += mask - 1;
447 bitmap[index] &= ~(mask << offset);
448 }
449 EXPORT_SYMBOL(bitmap_release_region);
451 int bitmap_allocate_region(unsigned long *bitmap, int pos, int order)
452 {
453 int pages = 1 << order;
454 unsigned long mask = (1ul << (pages - 1));
455 int index = pos/BITS_PER_LONG;
456 int offset = pos - (index * BITS_PER_LONG);
458 /* We don't do regions of pages > BITS_PER_LONG. The
459 * algorithm would be a simple look for multiple zeros in the
460 * array, but there's no driver today that needs this. If you
461 * trip this BUG(), you get to code it... */
462 BUG_ON(pages > BITS_PER_LONG);
463 mask += mask - 1;
464 if (bitmap[index] & (mask << offset))
465 return -EBUSY;
466 bitmap[index] |= (mask << offset);
467 return 0;
468 }
469 EXPORT_SYMBOL(bitmap_allocate_region);