diff options
Diffstat (limited to 'lib/bitmap.c')
| -rw-r--r-- | lib/bitmap.c | 111 |
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 | ||
| 43 | int __bitmap_empty(const unsigned long *bitmap, int bits) | 43 | int __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 | } |
| 56 | EXPORT_SYMBOL(__bitmap_empty); | 56 | EXPORT_SYMBOL(__bitmap_empty); |
| 57 | 57 | ||
| 58 | int __bitmap_full(const unsigned long *bitmap, int bits) | 58 | int __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) | |||
| 71 | EXPORT_SYMBOL(__bitmap_full); | 71 | EXPORT_SYMBOL(__bitmap_full); |
| 72 | 72 | ||
| 73 | int __bitmap_equal(const unsigned long *bitmap1, | 73 | int __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 | } |
| 87 | EXPORT_SYMBOL(__bitmap_equal); | 87 | EXPORT_SYMBOL(__bitmap_equal); |
| 88 | 88 | ||
| 89 | void __bitmap_complement(unsigned long *dst, const unsigned long *src, int bits) | 89 | void __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 | } |
| 98 | EXPORT_SYMBOL(__bitmap_complement); | 98 | EXPORT_SYMBOL(__bitmap_complement); |
| 99 | 99 | ||
| @@ -182,23 +182,26 @@ void __bitmap_shift_left(unsigned long *dst, | |||
| 182 | EXPORT_SYMBOL(__bitmap_shift_left); | 182 | EXPORT_SYMBOL(__bitmap_shift_left); |
| 183 | 183 | ||
| 184 | int __bitmap_and(unsigned long *dst, const unsigned long *bitmap1, | 184 | int __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 | } |
| 195 | EXPORT_SYMBOL(__bitmap_and); | 198 | EXPORT_SYMBOL(__bitmap_and); |
| 196 | 199 | ||
| 197 | void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1, | 200 | void __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, | |||
| 206 | EXPORT_SYMBOL(__bitmap_or); | 209 | EXPORT_SYMBOL(__bitmap_or); |
| 207 | 210 | ||
| 208 | void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1, | 211 | void __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, | |||
| 217 | EXPORT_SYMBOL(__bitmap_xor); | 220 | EXPORT_SYMBOL(__bitmap_xor); |
| 218 | 221 | ||
| 219 | int __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1, | 222 | int __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 | } |
| 230 | EXPORT_SYMBOL(__bitmap_andnot); | 236 | EXPORT_SYMBOL(__bitmap_andnot); |
| 231 | 237 | ||
| 232 | int __bitmap_intersects(const unsigned long *bitmap1, | 238 | int __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, | |||
| 245 | EXPORT_SYMBOL(__bitmap_intersects); | 251 | EXPORT_SYMBOL(__bitmap_intersects); |
| 246 | 252 | ||
| 247 | int __bitmap_subset(const unsigned long *bitmap1, | 253 | int __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 | } |
| 260 | EXPORT_SYMBOL(__bitmap_subset); | 266 | EXPORT_SYMBOL(__bitmap_subset); |
| 261 | 267 | ||
| 262 | int __bitmap_weight(const unsigned long *bitmap, int bits) | 268 | int __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 | } |
| 274 | EXPORT_SYMBOL(__bitmap_weight); | 281 | EXPORT_SYMBOL(__bitmap_weight); |
| 275 | 282 | ||
| 276 | void bitmap_set(unsigned long *map, int start, int nr) | 283 | void 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 | } |
| 295 | EXPORT_SYMBOL(bitmap_set); | 302 | EXPORT_SYMBOL(bitmap_set); |
| 296 | 303 | ||
| 297 | void bitmap_clear(unsigned long *map, int start, int nr) | 304 | void 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 | ||
| 665 | int bitmap_parselist(const char *bp, unsigned long *maskp, int nmaskbits) | 672 | int 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 | ||
| 1049 | static int __reg_op(unsigned long *bitmap, int pos, int order, int reg_op) | 1051 | static 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 | */ |
| 1115 | int bitmap_find_free_region(unsigned long *bitmap, int bits, int order) | 1117 | int 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 | */ |
| 1140 | void bitmap_release_region(unsigned long *bitmap, int pos, int order) | 1142 | void 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 | */ |
| 1157 | int bitmap_allocate_region(unsigned long *bitmap, int pos, int order) | 1159 | int 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 | } |
| 1164 | EXPORT_SYMBOL(bitmap_allocate_region); | 1165 | EXPORT_SYMBOL(bitmap_allocate_region); |
| 1165 | 1166 | ||
