aboutsummaryrefslogtreecommitdiffstats
path: root/lib/bitmap.c
diff options
context:
space:
mode:
Diffstat (limited to 'lib/bitmap.c')
-rw-r--r--lib/bitmap.c111
1 files changed, 56 insertions, 55 deletions
diff --git a/lib/bitmap.c b/lib/bitmap.c
index 06f7e4fe8d2d..1e031f2c9aba 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -40,9 +40,9 @@
40 * for the best explanations of this ordering. 40 * for the best explanations of this ordering.
41 */ 41 */
42 42
43int __bitmap_empty(const unsigned long *bitmap, int bits) 43int __bitmap_empty(const unsigned long *bitmap, unsigned int bits)
44{ 44{
45 int k, lim = bits/BITS_PER_LONG; 45 unsigned int k, lim = bits/BITS_PER_LONG;
46 for (k = 0; k < lim; ++k) 46 for (k = 0; k < lim; ++k)
47 if (bitmap[k]) 47 if (bitmap[k])
48 return 0; 48 return 0;
@@ -55,9 +55,9 @@ int __bitmap_empty(const unsigned long *bitmap, int bits)
55} 55}
56EXPORT_SYMBOL(__bitmap_empty); 56EXPORT_SYMBOL(__bitmap_empty);
57 57
58int __bitmap_full(const unsigned long *bitmap, int bits) 58int __bitmap_full(const unsigned long *bitmap, unsigned int bits)
59{ 59{
60 int k, lim = bits/BITS_PER_LONG; 60 unsigned int k, lim = bits/BITS_PER_LONG;
61 for (k = 0; k < lim; ++k) 61 for (k = 0; k < lim; ++k)
62 if (~bitmap[k]) 62 if (~bitmap[k])
63 return 0; 63 return 0;
@@ -71,9 +71,9 @@ int __bitmap_full(const unsigned long *bitmap, int bits)
71EXPORT_SYMBOL(__bitmap_full); 71EXPORT_SYMBOL(__bitmap_full);
72 72
73int __bitmap_equal(const unsigned long *bitmap1, 73int __bitmap_equal(const unsigned long *bitmap1,
74 const unsigned long *bitmap2, int bits) 74 const unsigned long *bitmap2, unsigned int bits)
75{ 75{
76 int k, lim = bits/BITS_PER_LONG; 76 unsigned int k, lim = bits/BITS_PER_LONG;
77 for (k = 0; k < lim; ++k) 77 for (k = 0; k < lim; ++k)
78 if (bitmap1[k] != bitmap2[k]) 78 if (bitmap1[k] != bitmap2[k])
79 return 0; 79 return 0;
@@ -86,14 +86,14 @@ int __bitmap_equal(const unsigned long *bitmap1,
86} 86}
87EXPORT_SYMBOL(__bitmap_equal); 87EXPORT_SYMBOL(__bitmap_equal);
88 88
89void __bitmap_complement(unsigned long *dst, const unsigned long *src, int bits) 89void __bitmap_complement(unsigned long *dst, const unsigned long *src, unsigned int bits)
90{ 90{
91 int k, lim = bits/BITS_PER_LONG; 91 unsigned int k, lim = bits/BITS_PER_LONG;
92 for (k = 0; k < lim; ++k) 92 for (k = 0; k < lim; ++k)
93 dst[k] = ~src[k]; 93 dst[k] = ~src[k];
94 94
95 if (bits % BITS_PER_LONG) 95 if (bits % BITS_PER_LONG)
96 dst[k] = ~src[k] & BITMAP_LAST_WORD_MASK(bits); 96 dst[k] = ~src[k];
97} 97}
98EXPORT_SYMBOL(__bitmap_complement); 98EXPORT_SYMBOL(__bitmap_complement);
99 99
@@ -182,23 +182,26 @@ void __bitmap_shift_left(unsigned long *dst,
182EXPORT_SYMBOL(__bitmap_shift_left); 182EXPORT_SYMBOL(__bitmap_shift_left);
183 183
184int __bitmap_and(unsigned long *dst, const unsigned long *bitmap1, 184int __bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
185 const unsigned long *bitmap2, int bits) 185 const unsigned long *bitmap2, unsigned int bits)
186{ 186{
187 int k; 187 unsigned int k;
188 int nr = BITS_TO_LONGS(bits); 188 unsigned int lim = bits/BITS_PER_LONG;
189 unsigned long result = 0; 189 unsigned long result = 0;
190 190
191 for (k = 0; k < nr; k++) 191 for (k = 0; k < lim; 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));
193 return result != 0; 196 return result != 0;
194} 197}
195EXPORT_SYMBOL(__bitmap_and); 198EXPORT_SYMBOL(__bitmap_and);
196 199
197void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1, 200void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
198 const unsigned long *bitmap2, int bits) 201 const unsigned long *bitmap2, unsigned int bits)
199{ 202{
200 int k; 203 unsigned int k;
201 int nr = BITS_TO_LONGS(bits); 204 unsigned int nr = BITS_TO_LONGS(bits);
202 205
203 for (k = 0; k < nr; k++) 206 for (k = 0; k < nr; k++)
204 dst[k] = bitmap1[k] | bitmap2[k]; 207 dst[k] = bitmap1[k] | bitmap2[k];
@@ -206,10 +209,10 @@ void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
206EXPORT_SYMBOL(__bitmap_or); 209EXPORT_SYMBOL(__bitmap_or);
207 210
208void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1, 211void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1,
209 const unsigned long *bitmap2, int bits) 212 const unsigned long *bitmap2, unsigned int bits)
210{ 213{
211 int k; 214 unsigned int k;
212 int nr = BITS_TO_LONGS(bits); 215 unsigned int nr = BITS_TO_LONGS(bits);
213 216
214 for (k = 0; k < nr; k++) 217 for (k = 0; k < nr; k++)
215 dst[k] = bitmap1[k] ^ bitmap2[k]; 218 dst[k] = bitmap1[k] ^ bitmap2[k];
@@ -217,22 +220,25 @@ void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1,
217EXPORT_SYMBOL(__bitmap_xor); 220EXPORT_SYMBOL(__bitmap_xor);
218 221
219int __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1, 222int __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1,
220 const unsigned long *bitmap2, int bits) 223 const unsigned long *bitmap2, unsigned int bits)
221{ 224{
222 int k; 225 unsigned int k;
223 int nr = BITS_TO_LONGS(bits); 226 unsigned int lim = bits/BITS_PER_LONG;
224 unsigned long result = 0; 227 unsigned long result = 0;
225 228
226 for (k = 0; k < nr; k++) 229 for (k = 0; k < lim; k++)
227 result |= (dst[k] = bitmap1[k] & ~bitmap2[k]); 230 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));
228 return result != 0; 234 return result != 0;
229} 235}
230EXPORT_SYMBOL(__bitmap_andnot); 236EXPORT_SYMBOL(__bitmap_andnot);
231 237
232int __bitmap_intersects(const unsigned long *bitmap1, 238int __bitmap_intersects(const unsigned long *bitmap1,
233 const unsigned long *bitmap2, int bits) 239 const unsigned long *bitmap2, unsigned int bits)
234{ 240{
235 int k, lim = bits/BITS_PER_LONG; 241 unsigned int k, lim = bits/BITS_PER_LONG;
236 for (k = 0; k < lim; ++k) 242 for (k = 0; k < lim; ++k)
237 if (bitmap1[k] & bitmap2[k]) 243 if (bitmap1[k] & bitmap2[k])
238 return 1; 244 return 1;
@@ -245,9 +251,9 @@ int __bitmap_intersects(const unsigned long *bitmap1,
245EXPORT_SYMBOL(__bitmap_intersects); 251EXPORT_SYMBOL(__bitmap_intersects);
246 252
247int __bitmap_subset(const unsigned long *bitmap1, 253int __bitmap_subset(const unsigned long *bitmap1,
248 const unsigned long *bitmap2, int bits) 254 const unsigned long *bitmap2, unsigned int bits)
249{ 255{
250 int k, lim = bits/BITS_PER_LONG; 256 unsigned int k, lim = bits/BITS_PER_LONG;
251 for (k = 0; k < lim; ++k) 257 for (k = 0; k < lim; ++k)
252 if (bitmap1[k] & ~bitmap2[k]) 258 if (bitmap1[k] & ~bitmap2[k])
253 return 0; 259 return 0;
@@ -259,9 +265,10 @@ int __bitmap_subset(const unsigned long *bitmap1,
259} 265}
260EXPORT_SYMBOL(__bitmap_subset); 266EXPORT_SYMBOL(__bitmap_subset);
261 267
262int __bitmap_weight(const unsigned long *bitmap, int bits) 268int __bitmap_weight(const unsigned long *bitmap, unsigned int bits)
263{ 269{
264 int k, w = 0, lim = bits/BITS_PER_LONG; 270 unsigned int k, lim = bits/BITS_PER_LONG;
271 int w = 0;
265 272
266 for (k = 0; k < lim; k++) 273 for (k = 0; k < lim; k++)
267 w += hweight_long(bitmap[k]); 274 w += hweight_long(bitmap[k]);
@@ -273,42 +280,42 @@ int __bitmap_weight(const unsigned long *bitmap, int bits)
273} 280}
274EXPORT_SYMBOL(__bitmap_weight); 281EXPORT_SYMBOL(__bitmap_weight);
275 282
276void bitmap_set(unsigned long *map, int start, int nr) 283void bitmap_set(unsigned long *map, unsigned int start, int len)
277{ 284{
278 unsigned long *p = map + BIT_WORD(start); 285 unsigned long *p = map + BIT_WORD(start);
279 const int size = start + nr; 286 const unsigned int size = start + len;
280 int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG); 287 int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG);
281 unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start); 288 unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start);
282 289
283 while (nr - bits_to_set >= 0) { 290 while (len - bits_to_set >= 0) {
284 *p |= mask_to_set; 291 *p |= mask_to_set;
285 nr -= bits_to_set; 292 len -= bits_to_set;
286 bits_to_set = BITS_PER_LONG; 293 bits_to_set = BITS_PER_LONG;
287 mask_to_set = ~0UL; 294 mask_to_set = ~0UL;
288 p++; 295 p++;
289 } 296 }
290 if (nr) { 297 if (len) {
291 mask_to_set &= BITMAP_LAST_WORD_MASK(size); 298 mask_to_set &= BITMAP_LAST_WORD_MASK(size);
292 *p |= mask_to_set; 299 *p |= mask_to_set;
293 } 300 }
294} 301}
295EXPORT_SYMBOL(bitmap_set); 302EXPORT_SYMBOL(bitmap_set);
296 303
297void bitmap_clear(unsigned long *map, int start, int nr) 304void bitmap_clear(unsigned long *map, unsigned int start, int len)
298{ 305{
299 unsigned long *p = map + BIT_WORD(start); 306 unsigned long *p = map + BIT_WORD(start);
300 const int size = start + nr; 307 const unsigned int size = start + len;
301 int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG); 308 int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG);
302 unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start); 309 unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start);
303 310
304 while (nr - bits_to_clear >= 0) { 311 while (len - bits_to_clear >= 0) {
305 *p &= ~mask_to_clear; 312 *p &= ~mask_to_clear;
306 nr -= bits_to_clear; 313 len -= bits_to_clear;
307 bits_to_clear = BITS_PER_LONG; 314 bits_to_clear = BITS_PER_LONG;
308 mask_to_clear = ~0UL; 315 mask_to_clear = ~0UL;
309 p++; 316 p++;
310 } 317 }
311 if (nr) { 318 if (len) {
312 mask_to_clear &= BITMAP_LAST_WORD_MASK(size); 319 mask_to_clear &= BITMAP_LAST_WORD_MASK(size);
313 *p &= ~mask_to_clear; 320 *p &= ~mask_to_clear;
314 } 321 }
@@ -664,13 +671,8 @@ static int __bitmap_parselist(const char *buf, unsigned int buflen,
664 671
665int bitmap_parselist(const char *bp, unsigned long *maskp, int nmaskbits) 672int bitmap_parselist(const char *bp, unsigned long *maskp, int nmaskbits)
666{ 673{
667 char *nl = strchr(bp, '\n'); 674 char *nl = strchrnul(bp, '\n');
668 int len; 675 int len = nl - bp;
669
670 if (nl)
671 len = nl - bp;
672 else
673 len = strlen(bp);
674 676
675 return __bitmap_parselist(bp, len, 0, maskp, nmaskbits); 677 return __bitmap_parselist(bp, len, 0, maskp, nmaskbits);
676} 678}
@@ -716,7 +718,7 @@ EXPORT_SYMBOL(bitmap_parselist_user);
716 * 718 *
717 * If for example, just bits 4 through 7 are set in @buf, then @pos 719 * 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, 720 * values 4 through 7 will get mapped to 0 through 3, respectively,
719 * and other @pos values will get mapped to 0. When @pos value 7 721 * and other @pos values will get mapped to -1. When @pos value 7
720 * gets mapped to (returns) @ord value 3 in this example, that means 722 * 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. 723 * that bit 7 is the 3rd (starting with 0th) set bit in @buf.
722 * 724 *
@@ -1046,7 +1048,7 @@ enum {
1046 REG_OP_RELEASE, /* clear all bits in region */ 1048 REG_OP_RELEASE, /* clear all bits in region */
1047}; 1049};
1048 1050
1049static int __reg_op(unsigned long *bitmap, int pos, int order, int reg_op) 1051static int __reg_op(unsigned long *bitmap, unsigned int pos, int order, int reg_op)
1050{ 1052{
1051 int nbits_reg; /* number of bits in region */ 1053 int nbits_reg; /* number of bits in region */
1052 int index; /* index first long of region in bitmap */ 1054 int index; /* index first long of region in bitmap */
@@ -1112,11 +1114,11 @@ done:
1112 * Return the bit offset in bitmap of the allocated region, 1114 * Return the bit offset in bitmap of the allocated region,
1113 * or -errno on failure. 1115 * or -errno on failure.
1114 */ 1116 */
1115int bitmap_find_free_region(unsigned long *bitmap, int bits, int order) 1117int bitmap_find_free_region(unsigned long *bitmap, unsigned int bits, int order)
1116{ 1118{
1117 int pos, end; /* scans bitmap by regions of size order */ 1119 unsigned int pos, end; /* scans bitmap by regions of size order */
1118 1120
1119 for (pos = 0 ; (end = pos + (1 << order)) <= bits; pos = end) { 1121 for (pos = 0 ; (end = pos + (1U << order)) <= bits; pos = end) {
1120 if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE)) 1122 if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE))
1121 continue; 1123 continue;
1122 __reg_op(bitmap, pos, order, REG_OP_ALLOC); 1124 __reg_op(bitmap, pos, order, REG_OP_ALLOC);
@@ -1137,7 +1139,7 @@ EXPORT_SYMBOL(bitmap_find_free_region);
1137 * 1139 *
1138 * No return value. 1140 * No return value.
1139 */ 1141 */
1140void bitmap_release_region(unsigned long *bitmap, int pos, int order) 1142void bitmap_release_region(unsigned long *bitmap, unsigned int pos, int order)
1141{ 1143{
1142 __reg_op(bitmap, pos, order, REG_OP_RELEASE); 1144 __reg_op(bitmap, pos, order, REG_OP_RELEASE);
1143} 1145}
@@ -1154,12 +1156,11 @@ EXPORT_SYMBOL(bitmap_release_region);
1154 * Return 0 on success, or %-EBUSY if specified region wasn't 1156 * Return 0 on success, or %-EBUSY if specified region wasn't
1155 * free (not all bits were zero). 1157 * free (not all bits were zero).
1156 */ 1158 */
1157int bitmap_allocate_region(unsigned long *bitmap, int pos, int order) 1159int bitmap_allocate_region(unsigned long *bitmap, unsigned int pos, int order)
1158{ 1160{
1159 if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE)) 1161 if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE))
1160 return -EBUSY; 1162 return -EBUSY;
1161 __reg_op(bitmap, pos, order, REG_OP_ALLOC); 1163 return __reg_op(bitmap, pos, order, REG_OP_ALLOC);
1162 return 0;
1163} 1164}
1164EXPORT_SYMBOL(bitmap_allocate_region); 1165EXPORT_SYMBOL(bitmap_allocate_region);
1165 1166