bitmap.c (e2627dce268024aff962132057cb8acb219c9c40) bitmap.c (da3dae54e4ff09886b9a19224c8d9556bb2ba096)
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 <linux/export.h>

--- 26 unchanged lines hidden (view full) ---

35 * in output bitmaps.
36 *
37 * The byte ordering of bitmaps is more natural on little
38 * endian architectures. See the big-endian headers
39 * include/asm-ppc64/bitops.h and include/asm-s390/bitops.h
40 * for the best explanations of this ordering.
41 */
42
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 <linux/export.h>

--- 26 unchanged lines hidden (view full) ---

35 * in output bitmaps.
36 *
37 * The byte ordering of bitmaps is more natural on little
38 * endian architectures. See the big-endian headers
39 * include/asm-ppc64/bitops.h and include/asm-s390/bitops.h
40 * for the best explanations of this ordering.
41 */
42
43int __bitmap_empty(const unsigned long *bitmap, unsigned int bits)
43int __bitmap_empty(const unsigned long *bitmap, int bits)
44{
44{
45 unsigned int k, lim = bits/BITS_PER_LONG;
45 int k, lim = bits/BITS_PER_LONG;
46 for (k = 0; k < lim; ++k)
47 if (bitmap[k])
48 return 0;
49
50 if (bits % BITS_PER_LONG)
51 if (bitmap[k] & BITMAP_LAST_WORD_MASK(bits))
52 return 0;
53
54 return 1;
55}
56EXPORT_SYMBOL(__bitmap_empty);
57
46 for (k = 0; k < lim; ++k)
47 if (bitmap[k])
48 return 0;
49
50 if (bits % BITS_PER_LONG)
51 if (bitmap[k] & BITMAP_LAST_WORD_MASK(bits))
52 return 0;
53
54 return 1;
55}
56EXPORT_SYMBOL(__bitmap_empty);
57
58int __bitmap_full(const unsigned long *bitmap, unsigned int bits)
58int __bitmap_full(const unsigned long *bitmap, int bits)
59{
59{
60 unsigned int k, lim = bits/BITS_PER_LONG;
60 int k, lim = bits/BITS_PER_LONG;
61 for (k = 0; k < lim; ++k)
62 if (~bitmap[k])
63 return 0;
64
65 if (bits % BITS_PER_LONG)
66 if (~bitmap[k] & BITMAP_LAST_WORD_MASK(bits))
67 return 0;
68
69 return 1;
70}
71EXPORT_SYMBOL(__bitmap_full);
72
73int __bitmap_equal(const unsigned long *bitmap1,
61 for (k = 0; k < lim; ++k)
62 if (~bitmap[k])
63 return 0;
64
65 if (bits % BITS_PER_LONG)
66 if (~bitmap[k] & BITMAP_LAST_WORD_MASK(bits))
67 return 0;
68
69 return 1;
70}
71EXPORT_SYMBOL(__bitmap_full);
72
73int __bitmap_equal(const unsigned long *bitmap1,
74 const unsigned long *bitmap2, unsigned int bits)
74 const unsigned long *bitmap2, int bits)
75{
75{
76 unsigned int k, lim = bits/BITS_PER_LONG;
76 int k, lim = bits/BITS_PER_LONG;
77 for (k = 0; k < lim; ++k)
78 if (bitmap1[k] != bitmap2[k])
79 return 0;
80
81 if (bits % BITS_PER_LONG)
82 if ((bitmap1[k] ^ bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits))
83 return 0;
84
85 return 1;
86}
87EXPORT_SYMBOL(__bitmap_equal);
88
77 for (k = 0; k < lim; ++k)
78 if (bitmap1[k] != bitmap2[k])
79 return 0;
80
81 if (bits % BITS_PER_LONG)
82 if ((bitmap1[k] ^ bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits))
83 return 0;
84
85 return 1;
86}
87EXPORT_SYMBOL(__bitmap_equal);
88
89void __bitmap_complement(unsigned long *dst, const unsigned long *src, unsigned int bits)
89void __bitmap_complement(unsigned long *dst, const unsigned long *src, int bits)
90{
90{
91 unsigned int k, lim = bits/BITS_PER_LONG;
91 int k, lim = bits/BITS_PER_LONG;
92 for (k = 0; k < lim; ++k)
93 dst[k] = ~src[k];
94
95 if (bits % BITS_PER_LONG)
92 for (k = 0; k < lim; ++k)
93 dst[k] = ~src[k];
94
95 if (bits % BITS_PER_LONG)
96 dst[k] = ~src[k];
96 dst[k] = ~src[k] & BITMAP_LAST_WORD_MASK(bits);
97}
98EXPORT_SYMBOL(__bitmap_complement);
99
100/**
101 * __bitmap_shift_right - logical right shift of the bits in a bitmap
102 * @dst : destination bitmap
103 * @src : source bitmap
104 * @shift : shift by this many bits

--- 72 unchanged lines hidden (view full) ---

177 dst[k + off] &= (1UL << left) - 1;
178 }
179 if (off)
180 memset(dst, 0, off*sizeof(unsigned long));
181}
182EXPORT_SYMBOL(__bitmap_shift_left);
183
184int __bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
97}
98EXPORT_SYMBOL(__bitmap_complement);
99
100/**
101 * __bitmap_shift_right - logical right shift of the bits in a bitmap
102 * @dst : destination bitmap
103 * @src : source bitmap
104 * @shift : shift by this many bits

--- 72 unchanged lines hidden (view full) ---

177 dst[k + off] &= (1UL << left) - 1;
178 }
179 if (off)
180 memset(dst, 0, off*sizeof(unsigned long));
181}
182EXPORT_SYMBOL(__bitmap_shift_left);
183
184int __bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
185 const unsigned long *bitmap2, unsigned int bits)
185 const unsigned long *bitmap2, int bits)
186{
186{
187 unsigned int k;
188 unsigned int lim = bits/BITS_PER_LONG;
187 int k;
188 int nr = BITS_TO_LONGS(bits);
189 unsigned long result = 0;
190
189 unsigned long result = 0;
190
191 for (k = 0; k < lim; k++)
191 for (k = 0; k < nr; k++)
192 result |= (dst[k] = bitmap1[k] & bitmap2[k]);
192 result |= (dst[k] = bitmap1[k] & bitmap2[k]);
193 if (bits % BITS_PER_LONG)
194 result |= (dst[k] = bitmap1[k] & bitmap2[k] &
195 BITMAP_LAST_WORD_MASK(bits));
196 return result != 0;
197}
198EXPORT_SYMBOL(__bitmap_and);
199
200void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
193 return result != 0;
194}
195EXPORT_SYMBOL(__bitmap_and);
196
197void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
201 const unsigned long *bitmap2, unsigned int bits)
198 const unsigned long *bitmap2, int bits)
202{
199{
203 unsigned int k;
204 unsigned int nr = BITS_TO_LONGS(bits);
200 int k;
201 int nr = BITS_TO_LONGS(bits);
205
206 for (k = 0; k < nr; k++)
207 dst[k] = bitmap1[k] | bitmap2[k];
208}
209EXPORT_SYMBOL(__bitmap_or);
210
211void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1,
202
203 for (k = 0; k < nr; k++)
204 dst[k] = bitmap1[k] | bitmap2[k];
205}
206EXPORT_SYMBOL(__bitmap_or);
207
208void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1,
212 const unsigned long *bitmap2, unsigned int bits)
209 const unsigned long *bitmap2, int bits)
213{
210{
214 unsigned int k;
215 unsigned int nr = BITS_TO_LONGS(bits);
211 int k;
212 int nr = BITS_TO_LONGS(bits);
216
217 for (k = 0; k < nr; k++)
218 dst[k] = bitmap1[k] ^ bitmap2[k];
219}
220EXPORT_SYMBOL(__bitmap_xor);
221
222int __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1,
213
214 for (k = 0; k < nr; k++)
215 dst[k] = bitmap1[k] ^ bitmap2[k];
216}
217EXPORT_SYMBOL(__bitmap_xor);
218
219int __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1,
223 const unsigned long *bitmap2, unsigned int bits)
220 const unsigned long *bitmap2, int bits)
224{
221{
225 unsigned int k;
226 unsigned int lim = bits/BITS_PER_LONG;
222 int k;
223 int nr = BITS_TO_LONGS(bits);
227 unsigned long result = 0;
228
224 unsigned long result = 0;
225
229 for (k = 0; k < lim; k++)
226 for (k = 0; k < nr; k++)
230 result |= (dst[k] = bitmap1[k] & ~bitmap2[k]);
227 result |= (dst[k] = bitmap1[k] & ~bitmap2[k]);
231 if (bits % BITS_PER_LONG)
232 result |= (dst[k] = bitmap1[k] & ~bitmap2[k] &
233 BITMAP_LAST_WORD_MASK(bits));
234 return result != 0;
235}
236EXPORT_SYMBOL(__bitmap_andnot);
237
238int __bitmap_intersects(const unsigned long *bitmap1,
228 return result != 0;
229}
230EXPORT_SYMBOL(__bitmap_andnot);
231
232int __bitmap_intersects(const unsigned long *bitmap1,
239 const unsigned long *bitmap2, unsigned int bits)
233 const unsigned long *bitmap2, int bits)
240{
234{
241 unsigned int k, lim = bits/BITS_PER_LONG;
235 int k, lim = bits/BITS_PER_LONG;
242 for (k = 0; k < lim; ++k)
243 if (bitmap1[k] & bitmap2[k])
244 return 1;
245
246 if (bits % BITS_PER_LONG)
247 if ((bitmap1[k] & bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits))
248 return 1;
249 return 0;
250}
251EXPORT_SYMBOL(__bitmap_intersects);
252
253int __bitmap_subset(const unsigned long *bitmap1,
236 for (k = 0; k < lim; ++k)
237 if (bitmap1[k] & bitmap2[k])
238 return 1;
239
240 if (bits % BITS_PER_LONG)
241 if ((bitmap1[k] & bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits))
242 return 1;
243 return 0;
244}
245EXPORT_SYMBOL(__bitmap_intersects);
246
247int __bitmap_subset(const unsigned long *bitmap1,
254 const unsigned long *bitmap2, unsigned int bits)
248 const unsigned long *bitmap2, int bits)
255{
249{
256 unsigned int k, lim = bits/BITS_PER_LONG;
250 int k, lim = bits/BITS_PER_LONG;
257 for (k = 0; k < lim; ++k)
258 if (bitmap1[k] & ~bitmap2[k])
259 return 0;
260
261 if (bits % BITS_PER_LONG)
262 if ((bitmap1[k] & ~bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits))
263 return 0;
264 return 1;
265}
266EXPORT_SYMBOL(__bitmap_subset);
267
251 for (k = 0; k < lim; ++k)
252 if (bitmap1[k] & ~bitmap2[k])
253 return 0;
254
255 if (bits % BITS_PER_LONG)
256 if ((bitmap1[k] & ~bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits))
257 return 0;
258 return 1;
259}
260EXPORT_SYMBOL(__bitmap_subset);
261
268int __bitmap_weight(const unsigned long *bitmap, unsigned int bits)
262int __bitmap_weight(const unsigned long *bitmap, int bits)
269{
263{
270 unsigned int k, lim = bits/BITS_PER_LONG;
271 int w = 0;
264 int k, w = 0, lim = bits/BITS_PER_LONG;
272
273 for (k = 0; k < lim; k++)
274 w += hweight_long(bitmap[k]);
275
276 if (bits % BITS_PER_LONG)
277 w += hweight_long(bitmap[k] & BITMAP_LAST_WORD_MASK(bits));
278
279 return w;
280}
281EXPORT_SYMBOL(__bitmap_weight);
282
265
266 for (k = 0; k < lim; k++)
267 w += hweight_long(bitmap[k]);
268
269 if (bits % BITS_PER_LONG)
270 w += hweight_long(bitmap[k] & BITMAP_LAST_WORD_MASK(bits));
271
272 return w;
273}
274EXPORT_SYMBOL(__bitmap_weight);
275
283void bitmap_set(unsigned long *map, unsigned int start, int len)
276void bitmap_set(unsigned long *map, int start, int nr)
284{
285 unsigned long *p = map + BIT_WORD(start);
277{
278 unsigned long *p = map + BIT_WORD(start);
286 const unsigned int size = start + len;
279 const int size = start + nr;
287 int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG);
288 unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start);
289
280 int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG);
281 unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start);
282
290 while (len - bits_to_set >= 0) {
283 while (nr - bits_to_set >= 0) {
291 *p |= mask_to_set;
284 *p |= mask_to_set;
292 len -= bits_to_set;
285 nr -= bits_to_set;
293 bits_to_set = BITS_PER_LONG;
294 mask_to_set = ~0UL;
295 p++;
296 }
286 bits_to_set = BITS_PER_LONG;
287 mask_to_set = ~0UL;
288 p++;
289 }
297 if (len) {
290 if (nr) {
298 mask_to_set &= BITMAP_LAST_WORD_MASK(size);
299 *p |= mask_to_set;
300 }
301}
302EXPORT_SYMBOL(bitmap_set);
303
291 mask_to_set &= BITMAP_LAST_WORD_MASK(size);
292 *p |= mask_to_set;
293 }
294}
295EXPORT_SYMBOL(bitmap_set);
296
304void bitmap_clear(unsigned long *map, unsigned int start, int len)
297void bitmap_clear(unsigned long *map, int start, int nr)
305{
306 unsigned long *p = map + BIT_WORD(start);
298{
299 unsigned long *p = map + BIT_WORD(start);
307 const unsigned int size = start + len;
300 const int size = start + nr;
308 int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG);
309 unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start);
310
301 int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG);
302 unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start);
303
311 while (len - bits_to_clear >= 0) {
304 while (nr - bits_to_clear >= 0) {
312 *p &= ~mask_to_clear;
305 *p &= ~mask_to_clear;
313 len -= bits_to_clear;
306 nr -= bits_to_clear;
314 bits_to_clear = BITS_PER_LONG;
315 mask_to_clear = ~0UL;
316 p++;
317 }
307 bits_to_clear = BITS_PER_LONG;
308 mask_to_clear = ~0UL;
309 p++;
310 }
318 if (len) {
311 if (nr) {
319 mask_to_clear &= BITMAP_LAST_WORD_MASK(size);
320 *p &= ~mask_to_clear;
321 }
322}
323EXPORT_SYMBOL(bitmap_clear);
324
325/*
326 * bitmap_find_next_zero_area - find a contiguous aligned zero area

--- 339 unchanged lines hidden (view full) ---

666 a++;
667 }
668 } while (buflen && c == ',');
669 return 0;
670}
671
672int bitmap_parselist(const char *bp, unsigned long *maskp, int nmaskbits)
673{
312 mask_to_clear &= BITMAP_LAST_WORD_MASK(size);
313 *p &= ~mask_to_clear;
314 }
315}
316EXPORT_SYMBOL(bitmap_clear);
317
318/*
319 * bitmap_find_next_zero_area - find a contiguous aligned zero area

--- 339 unchanged lines hidden (view full) ---

659 a++;
660 }
661 } while (buflen && c == ',');
662 return 0;
663}
664
665int bitmap_parselist(const char *bp, unsigned long *maskp, int nmaskbits)
666{
674 char *nl = strchrnul(bp, '\n');
675 int len = nl - bp;
667 char *nl = strchr(bp, '\n');
668 int len;
676
669
670 if (nl)
671 len = nl - bp;
672 else
673 len = strlen(bp);
674
677 return __bitmap_parselist(bp, len, 0, maskp, nmaskbits);
678}
679EXPORT_SYMBOL(bitmap_parselist);
680
681
682/**
683 * bitmap_parselist_user()
684 *

--- 28 unchanged lines hidden (view full) ---

713 * @bits: number of valid bit positions in @buf
714 *
715 * Map the bit at position @pos in @buf (of length @bits) to the
716 * ordinal of which set bit it is. If it is not set or if @pos
717 * is not a valid bit position, map to -1.
718 *
719 * If for example, just bits 4 through 7 are set in @buf, then @pos
720 * values 4 through 7 will get mapped to 0 through 3, respectively,
675 return __bitmap_parselist(bp, len, 0, maskp, nmaskbits);
676}
677EXPORT_SYMBOL(bitmap_parselist);
678
679
680/**
681 * bitmap_parselist_user()
682 *

--- 28 unchanged lines hidden (view full) ---

711 * @bits: number of valid bit positions in @buf
712 *
713 * Map the bit at position @pos in @buf (of length @bits) to the
714 * ordinal of which set bit it is. If it is not set or if @pos
715 * is not a valid bit position, map to -1.
716 *
717 * If for example, just bits 4 through 7 are set in @buf, then @pos
718 * values 4 through 7 will get mapped to 0 through 3, respectively,
721 * and other @pos values will get mapped to -1. When @pos value 7
719 * and other @pos values will get mapped to 0. When @pos value 7
722 * gets mapped to (returns) @ord value 3 in this example, that means
723 * that bit 7 is the 3rd (starting with 0th) set bit in @buf.
724 *
725 * The bit positions 0 through @bits are valid positions in @buf.
726 */
727static int bitmap_pos_to_ord(const unsigned long *buf, int pos, int bits)
728{
729 int i, ord;

--- 149 unchanged lines hidden (view full) ---

879 *
880 * Set the n-th bit of @dst iff there exists some m such that the
881 * n-th bit of @relmap is set, the m-th bit of @orig is set, and
882 * the n-th bit of @relmap is also the m-th _set_ bit of @relmap.
883 * (If you understood the previous sentence the first time your
884 * read it, you're overqualified for your current job.)
885 *
886 * In other words, @orig is mapped onto (surjectively) @dst,
720 * gets mapped to (returns) @ord value 3 in this example, that means
721 * that bit 7 is the 3rd (starting with 0th) set bit in @buf.
722 *
723 * The bit positions 0 through @bits are valid positions in @buf.
724 */
725static int bitmap_pos_to_ord(const unsigned long *buf, int pos, int bits)
726{
727 int i, ord;

--- 149 unchanged lines hidden (view full) ---

877 *
878 * Set the n-th bit of @dst iff there exists some m such that the
879 * n-th bit of @relmap is set, the m-th bit of @orig is set, and
880 * the n-th bit of @relmap is also the m-th _set_ bit of @relmap.
881 * (If you understood the previous sentence the first time your
882 * read it, you're overqualified for your current job.)
883 *
884 * In other words, @orig is mapped onto (surjectively) @dst,
887 * using the the map { <n, m> | the n-th bit of @relmap is the
885 * using the map { <n, m> | the n-th bit of @relmap is the
888 * m-th set bit of @relmap }.
889 *
890 * Any set bits in @orig above bit number W, where W is the
891 * weight of (number of set bits in) @relmap are mapped nowhere.
892 * In particular, if for all bits m set in @orig, m >= W, then
893 * @dst will end up empty. In situations where the possibility
894 * of such an empty result is not desired, one way to avoid it is
895 * to use the bitmap_fold() operator, below, to first fold the

--- 31 unchanged lines hidden (view full) ---

927 * Example [2] for bitmap_fold() + bitmap_onto():
928 * Let's say @relmap has these ten bits set:
929 * 40 41 42 43 45 48 53 61 74 95
930 * (for the curious, that's 40 plus the first ten terms of the
931 * Fibonacci sequence.)
932 *
933 * Further lets say we use the following code, invoking
934 * bitmap_fold() then bitmap_onto, as suggested above to
886 * m-th set bit of @relmap }.
887 *
888 * Any set bits in @orig above bit number W, where W is the
889 * weight of (number of set bits in) @relmap are mapped nowhere.
890 * In particular, if for all bits m set in @orig, m >= W, then
891 * @dst will end up empty. In situations where the possibility
892 * of such an empty result is not desired, one way to avoid it is
893 * to use the bitmap_fold() operator, below, to first fold the

--- 31 unchanged lines hidden (view full) ---

925 * Example [2] for bitmap_fold() + bitmap_onto():
926 * Let's say @relmap has these ten bits set:
927 * 40 41 42 43 45 48 53 61 74 95
928 * (for the curious, that's 40 plus the first ten terms of the
929 * Fibonacci sequence.)
930 *
931 * Further lets say we use the following code, invoking
932 * bitmap_fold() then bitmap_onto, as suggested above to
935 * avoid the possitility of an empty @dst result:
933 * avoid the possibility of an empty @dst result:
936 *
937 * unsigned long *tmp; // a temporary bitmap's bits
938 *
939 * bitmap_fold(tmp, orig, bitmap_weight(relmap, bits), bits);
940 * bitmap_onto(dst, tmp, relmap, bits);
941 *
942 * Then this table shows what various values of @dst would be, for
943 * various @orig's. I list the zero-based positions of each set bit.

--- 99 unchanged lines hidden (view full) ---

1043 */
1044
1045enum {
1046 REG_OP_ISFREE, /* true if region is all zero bits */
1047 REG_OP_ALLOC, /* set all bits in region */
1048 REG_OP_RELEASE, /* clear all bits in region */
1049};
1050
934 *
935 * unsigned long *tmp; // a temporary bitmap's bits
936 *
937 * bitmap_fold(tmp, orig, bitmap_weight(relmap, bits), bits);
938 * bitmap_onto(dst, tmp, relmap, bits);
939 *
940 * Then this table shows what various values of @dst would be, for
941 * various @orig's. I list the zero-based positions of each set bit.

--- 99 unchanged lines hidden (view full) ---

1041 */
1042
1043enum {
1044 REG_OP_ISFREE, /* true if region is all zero bits */
1045 REG_OP_ALLOC, /* set all bits in region */
1046 REG_OP_RELEASE, /* clear all bits in region */
1047};
1048
1051static int __reg_op(unsigned long *bitmap, unsigned int pos, int order, int reg_op)
1049static int __reg_op(unsigned long *bitmap, int pos, int order, int reg_op)
1052{
1053 int nbits_reg; /* number of bits in region */
1054 int index; /* index first long of region in bitmap */
1055 int offset; /* bit offset region in bitmap[index] */
1056 int nlongs_reg; /* num longs spanned by region in bitmap */
1057 int nbitsinlong; /* num bits of region in each spanned long */
1058 unsigned long mask; /* bitmask for one long of region */
1059 int i; /* scans bitmap by longs */

--- 49 unchanged lines hidden (view full) ---

1109 * Find a region of free (zero) bits in a @bitmap of @bits bits and
1110 * allocate them (set them to one). Only consider regions of length
1111 * a power (@order) of two, aligned to that power of two, which
1112 * makes the search algorithm much faster.
1113 *
1114 * Return the bit offset in bitmap of the allocated region,
1115 * or -errno on failure.
1116 */
1050{
1051 int nbits_reg; /* number of bits in region */
1052 int index; /* index first long of region in bitmap */
1053 int offset; /* bit offset region in bitmap[index] */
1054 int nlongs_reg; /* num longs spanned by region in bitmap */
1055 int nbitsinlong; /* num bits of region in each spanned long */
1056 unsigned long mask; /* bitmask for one long of region */
1057 int i; /* scans bitmap by longs */

--- 49 unchanged lines hidden (view full) ---

1107 * Find a region of free (zero) bits in a @bitmap of @bits bits and
1108 * allocate them (set them to one). Only consider regions of length
1109 * a power (@order) of two, aligned to that power of two, which
1110 * makes the search algorithm much faster.
1111 *
1112 * Return the bit offset in bitmap of the allocated region,
1113 * or -errno on failure.
1114 */
1117int bitmap_find_free_region(unsigned long *bitmap, unsigned int bits, int order)
1115int bitmap_find_free_region(unsigned long *bitmap, int bits, int order)
1118{
1116{
1119 unsigned int pos, end; /* scans bitmap by regions of size order */
1117 int pos, end; /* scans bitmap by regions of size order */
1120
1118
1121 for (pos = 0 ; (end = pos + (1U << order)) <= bits; pos = end) {
1119 for (pos = 0 ; (end = pos + (1 << order)) <= bits; pos = end) {
1122 if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE))
1123 continue;
1124 __reg_op(bitmap, pos, order, REG_OP_ALLOC);
1125 return pos;
1126 }
1127 return -ENOMEM;
1128}
1129EXPORT_SYMBOL(bitmap_find_free_region);

--- 4 unchanged lines hidden (view full) ---

1134 * @pos: beginning of bit region to release
1135 * @order: region size (log base 2 of number of bits) to release
1136 *
1137 * This is the complement to __bitmap_find_free_region() and releases
1138 * the found region (by clearing it in the bitmap).
1139 *
1140 * No return value.
1141 */
1120 if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE))
1121 continue;
1122 __reg_op(bitmap, pos, order, REG_OP_ALLOC);
1123 return pos;
1124 }
1125 return -ENOMEM;
1126}
1127EXPORT_SYMBOL(bitmap_find_free_region);

--- 4 unchanged lines hidden (view full) ---

1132 * @pos: beginning of bit region to release
1133 * @order: region size (log base 2 of number of bits) to release
1134 *
1135 * This is the complement to __bitmap_find_free_region() and releases
1136 * the found region (by clearing it in the bitmap).
1137 *
1138 * No return value.
1139 */
1142void bitmap_release_region(unsigned long *bitmap, unsigned int pos, int order)
1140void bitmap_release_region(unsigned long *bitmap, int pos, int order)
1143{
1144 __reg_op(bitmap, pos, order, REG_OP_RELEASE);
1145}
1146EXPORT_SYMBOL(bitmap_release_region);
1147
1148/**
1149 * bitmap_allocate_region - allocate bitmap region
1150 * @bitmap: array of unsigned longs corresponding to the bitmap
1151 * @pos: beginning of bit region to allocate
1152 * @order: region size (log base 2 of number of bits) to allocate
1153 *
1154 * Allocate (set bits in) a specified region of a bitmap.
1155 *
1156 * Return 0 on success, or %-EBUSY if specified region wasn't
1157 * free (not all bits were zero).
1158 */
1141{
1142 __reg_op(bitmap, pos, order, REG_OP_RELEASE);
1143}
1144EXPORT_SYMBOL(bitmap_release_region);
1145
1146/**
1147 * bitmap_allocate_region - allocate bitmap region
1148 * @bitmap: array of unsigned longs corresponding to the bitmap
1149 * @pos: beginning of bit region to allocate
1150 * @order: region size (log base 2 of number of bits) to allocate
1151 *
1152 * Allocate (set bits in) a specified region of a bitmap.
1153 *
1154 * Return 0 on success, or %-EBUSY if specified region wasn't
1155 * free (not all bits were zero).
1156 */
1159int bitmap_allocate_region(unsigned long *bitmap, unsigned int pos, int order)
1157int bitmap_allocate_region(unsigned long *bitmap, int pos, int order)
1160{
1161 if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE))
1162 return -EBUSY;
1158{
1159 if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE))
1160 return -EBUSY;
1163 return __reg_op(bitmap, pos, order, REG_OP_ALLOC);
1161 __reg_op(bitmap, pos, order, REG_OP_ALLOC);
1162 return 0;
1164}
1165EXPORT_SYMBOL(bitmap_allocate_region);
1166
1167/**
1168 * bitmap_copy_le - copy a bitmap, putting the bits into little-endian order.
1169 * @dst: destination buffer
1170 * @src: bitmap to copy
1171 * @nbits: number of bits in the bitmap

--- 16 unchanged lines hidden --- 		1163}
1164EXPORT_SYMBOL(bitmap_allocate_region);
1165
1166/**
1167 * bitmap_copy_le - copy a bitmap, putting the bits into little-endian order.
1168 * @dst: destination buffer
1169 * @src: bitmap to copy
1170 * @nbits: number of bits in the bitmap

--- 16 unchanged lines hidden ---