2,7 → 2,7 |
* lib/bitmap.c |
* Helper functions for bitmap.h. |
* |
* Tlhis source code is licensed under the GNU General Public License, |
* This source code is licensed under the GNU General Public License, |
* Version 2. See the file COPYING for more details. |
*/ |
#include <syscall.h> |
41,9 → 41,9 |
* for the best explanations of this ordering. |
*/ |
|
int __bitmap_empty(const unsigned long *bitmap, int bits) |
int __bitmap_empty(const unsigned long *bitmap, unsigned int bits) |
{ |
int k, lim = bits/BITS_PER_LONG; |
unsigned int k, lim = bits/BITS_PER_LONG; |
for (k = 0; k < lim; ++k) |
if (bitmap[k]) |
return 0; |
56,9 → 56,9 |
} |
EXPORT_SYMBOL(__bitmap_empty); |
|
int __bitmap_full(const unsigned long *bitmap, int bits) |
int __bitmap_full(const unsigned long *bitmap, unsigned int bits) |
{ |
int k, lim = bits/BITS_PER_LONG; |
unsigned int k, lim = bits/BITS_PER_LONG; |
for (k = 0; k < lim; ++k) |
if (~bitmap[k]) |
return 0; |
72,9 → 72,9 |
EXPORT_SYMBOL(__bitmap_full); |
|
int __bitmap_equal(const unsigned long *bitmap1, |
const unsigned long *bitmap2, int bits) |
const unsigned long *bitmap2, unsigned int bits) |
{ |
int k, lim = bits/BITS_PER_LONG; |
unsigned int k, lim = bits/BITS_PER_LONG; |
for (k = 0; k < lim; ++k) |
if (bitmap1[k] != bitmap2[k]) |
return 0; |
87,14 → 87,14 |
} |
EXPORT_SYMBOL(__bitmap_equal); |
|
void __bitmap_complement(unsigned long *dst, const unsigned long *src, int bits) |
void __bitmap_complement(unsigned long *dst, const unsigned long *src, unsigned int bits) |
{ |
int k, lim = bits/BITS_PER_LONG; |
unsigned int k, lim = bits/BITS_PER_LONG; |
for (k = 0; k < lim; ++k) |
dst[k] = ~src[k]; |
|
if (bits % BITS_PER_LONG) |
dst[k] = ~src[k] & BITMAP_LAST_WORD_MASK(bits); |
dst[k] = ~src[k]; |
} |
EXPORT_SYMBOL(__bitmap_complement); |
|
183,23 → 183,26 |
EXPORT_SYMBOL(__bitmap_shift_left); |
|
int __bitmap_and(unsigned long *dst, const unsigned long *bitmap1, |
const unsigned long *bitmap2, int bits) |
const unsigned long *bitmap2, unsigned int bits) |
{ |
int k; |
int nr = BITS_TO_LONGS(bits); |
unsigned int k; |
unsigned int lim = bits/BITS_PER_LONG; |
unsigned long result = 0; |
|
for (k = 0; k < nr; k++) |
for (k = 0; k < lim; k++) |
result |= (dst[k] = bitmap1[k] & bitmap2[k]); |
if (bits % BITS_PER_LONG) |
result |= (dst[k] = bitmap1[k] & bitmap2[k] & |
BITMAP_LAST_WORD_MASK(bits)); |
return result != 0; |
} |
EXPORT_SYMBOL(__bitmap_and); |
|
void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1, |
const unsigned long *bitmap2, int bits) |
const unsigned long *bitmap2, unsigned int bits) |
{ |
int k; |
int nr = BITS_TO_LONGS(bits); |
unsigned int k; |
unsigned int nr = BITS_TO_LONGS(bits); |
|
for (k = 0; k < nr; k++) |
dst[k] = bitmap1[k] | bitmap2[k]; |
207,10 → 210,10 |
EXPORT_SYMBOL(__bitmap_or); |
|
void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1, |
const unsigned long *bitmap2, int bits) |
const unsigned long *bitmap2, unsigned int bits) |
{ |
int k; |
int nr = BITS_TO_LONGS(bits); |
unsigned int k; |
unsigned int nr = BITS_TO_LONGS(bits); |
|
for (k = 0; k < nr; k++) |
dst[k] = bitmap1[k] ^ bitmap2[k]; |
218,22 → 221,25 |
EXPORT_SYMBOL(__bitmap_xor); |
|
int __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1, |
const unsigned long *bitmap2, int bits) |
const unsigned long *bitmap2, unsigned int bits) |
{ |
int k; |
int nr = BITS_TO_LONGS(bits); |
unsigned int k; |
unsigned int lim = bits/BITS_PER_LONG; |
unsigned long result = 0; |
|
for (k = 0; k < nr; k++) |
for (k = 0; k < lim; k++) |
result |= (dst[k] = bitmap1[k] & ~bitmap2[k]); |
if (bits % BITS_PER_LONG) |
result |= (dst[k] = bitmap1[k] & ~bitmap2[k] & |
BITMAP_LAST_WORD_MASK(bits)); |
return result != 0; |
} |
EXPORT_SYMBOL(__bitmap_andnot); |
|
int __bitmap_intersects(const unsigned long *bitmap1, |
const unsigned long *bitmap2, int bits) |
const unsigned long *bitmap2, unsigned int bits) |
{ |
int k, lim = bits/BITS_PER_LONG; |
unsigned int k, lim = bits/BITS_PER_LONG; |
for (k = 0; k < lim; ++k) |
if (bitmap1[k] & bitmap2[k]) |
return 1; |
246,9 → 252,9 |
EXPORT_SYMBOL(__bitmap_intersects); |
|
int __bitmap_subset(const unsigned long *bitmap1, |
const unsigned long *bitmap2, int bits) |
const unsigned long *bitmap2, unsigned int bits) |
{ |
int k, lim = bits/BITS_PER_LONG; |
unsigned int k, lim = bits/BITS_PER_LONG; |
for (k = 0; k < lim; ++k) |
if (bitmap1[k] & ~bitmap2[k]) |
return 0; |
260,9 → 266,10 |
} |
EXPORT_SYMBOL(__bitmap_subset); |
|
int __bitmap_weight(const unsigned long *bitmap, int bits) |
int __bitmap_weight(const unsigned long *bitmap, unsigned int bits) |
{ |
int k, w = 0, lim = bits/BITS_PER_LONG; |
unsigned int k, lim = bits/BITS_PER_LONG; |
int w = 0; |
|
for (k = 0; k < lim; k++) |
w += hweight_long(bitmap[k]); |
274,21 → 281,21 |
} |
EXPORT_SYMBOL(__bitmap_weight); |
|
void bitmap_set(unsigned long *map, int start, int nr) |
void bitmap_set(unsigned long *map, unsigned int start, int len) |
{ |
unsigned long *p = map + BIT_WORD(start); |
const int size = start + nr; |
const unsigned int size = start + len; |
int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG); |
unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start); |
|
while (nr - bits_to_set >= 0) { |
while (len - bits_to_set >= 0) { |
*p |= mask_to_set; |
nr -= bits_to_set; |
len -= bits_to_set; |
bits_to_set = BITS_PER_LONG; |
mask_to_set = ~0UL; |
p++; |
} |
if (nr) { |
if (len) { |
mask_to_set &= BITMAP_LAST_WORD_MASK(size); |
*p |= mask_to_set; |
} |
295,21 → 302,21 |
} |
EXPORT_SYMBOL(bitmap_set); |
|
void bitmap_clear(unsigned long *map, int start, int nr) |
void bitmap_clear(unsigned long *map, unsigned int start, int len) |
{ |
unsigned long *p = map + BIT_WORD(start); |
const int size = start + nr; |
const unsigned int size = start + len; |
int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG); |
unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start); |
|
while (nr - bits_to_clear >= 0) { |
while (len - bits_to_clear >= 0) { |
*p &= ~mask_to_clear; |
nr -= bits_to_clear; |
len -= bits_to_clear; |
bits_to_clear = BITS_PER_LONG; |
mask_to_clear = ~0UL; |
p++; |
} |
if (nr) { |
if (len) { |
mask_to_clear &= BITMAP_LAST_WORD_MASK(size); |
*p &= ~mask_to_clear; |
} |
378,7 → 385,7 |
* |
* If for example, just bits 4 through 7 are set in @buf, then @pos |
* values 4 through 7 will get mapped to 0 through 3, respectively, |
* and other @pos values will get mapped to 0. When @pos value 7 |
* and other @pos values will get mapped to -1. When @pos value 7 |
* gets mapped to (returns) @ord value 3 in this example, that means |
* that bit 7 is the 3rd (starting with 0th) set bit in @buf. |
* |
708,7 → 715,7 |
REG_OP_RELEASE, /* clear all bits in region */ |
}; |
|
static int __reg_op(unsigned long *bitmap, int pos, int order, int reg_op) |
static int __reg_op(unsigned long *bitmap, unsigned int pos, int order, int reg_op) |
{ |
int nbits_reg; /* number of bits in region */ |
int index; /* index first long of region in bitmap */ |
774,11 → 781,11 |
* Return the bit offset in bitmap of the allocated region, |
* or -errno on failure. |
*/ |
int bitmap_find_free_region(unsigned long *bitmap, int bits, int order) |
int bitmap_find_free_region(unsigned long *bitmap, unsigned int bits, int order) |
{ |
int pos, end; /* scans bitmap by regions of size order */ |
unsigned int pos, end; /* scans bitmap by regions of size order */ |
|
for (pos = 0 ; (end = pos + (1 << order)) <= bits; pos = end) { |
for (pos = 0 ; (end = pos + (1U << order)) <= bits; pos = end) { |
if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE)) |
continue; |
__reg_op(bitmap, pos, order, REG_OP_ALLOC); |
799,7 → 806,7 |
* |
* No return value. |
*/ |
void bitmap_release_region(unsigned long *bitmap, int pos, int order) |
void bitmap_release_region(unsigned long *bitmap, unsigned int pos, int order) |
{ |
__reg_op(bitmap, pos, order, REG_OP_RELEASE); |
} |
816,12 → 823,11 |
* Return 0 on success, or %-EBUSY if specified region wasn't |
* free (not all bits were zero). |
*/ |
int bitmap_allocate_region(unsigned long *bitmap, int pos, int order) |
int bitmap_allocate_region(unsigned long *bitmap, unsigned int pos, int order) |
{ |
if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE)) |
return -EBUSY; |
__reg_op(bitmap, pos, order, REG_OP_ALLOC); |
return 0; |
return __reg_op(bitmap, pos, order, REG_OP_ALLOC); |
} |
EXPORT_SYMBOL(bitmap_allocate_region); |
|