diff options
author | Andrew Morton <akpm@osdl.org> | 2004-06-23 18:50:51 -0700 |
---|---|---|
committer | Linus Torvalds <torvalds@ppc970.osdl.org> | 2004-06-23 18:50:51 -0700 |
commit | d6cf71d3086ea9be652ac95616cd111157fdd4c5 (patch) | |
tree | 4ae80be235b2228f27ffb70e34be0abb9f12d75f /lib | |
parent | ea0c19290646e6bb7cd3657db83eac3a0d641418 (diff) | |
download | history-d6cf71d3086ea9be652ac95616cd111157fdd4c5.tar.gz |
[PATCH] cpumask: bitmap inlining and optimizations
From: Paul Jackson <pj@sgi.com>
These bitmap improvements make it a suitable basis for fully supporting
cpumask_t and nodemask_t. Inline macros with compile-time checks enable
generating tight code on both small and large systems (large meaning cpumask_t
requires more than one unsigned long's worth of bits).
The existing bitmap_<op> macros in lib/bitmap.c are renamed to __bitmap_<op>,
and wrappers for each bitmap_<op> are exposed in include/linux/bitmap.h
This patch _includes_ Bill Irwins rewrite of the bitmap_shift operators to not
require a fixed length intermediate bitmap.
Improved comments list each available operator for easy browsing.
Signed-off-by: Paul Jackson <pj@sgi.com>
Signed-off-by: Andrew Morton <akpm@osdl.org>
Signed-off-by: Linus Torvalds <torvalds@osdl.org>
Diffstat (limited to 'lib')
-rw-r--r-- | lib/bitmap.c | 91 |
1 files changed, 47 insertions, 44 deletions
diff --git a/lib/bitmap.c b/lib/bitmap.c index a96433e3710291..7eb16be309b5ff 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -15,7 +15,8 @@ /* * bitmaps provide an array of bits, implemented using an an * array of unsigned longs. The number of valid bits in a - * given bitmap need not be an exact multiple of BITS_PER_LONG. + * given bitmap does _not_ need to be an exact multiple of + * BITS_PER_LONG. * * The possible unused bits in the last, partially used word * of a bitmap are 'don't care'. The implementation makes @@ -30,9 +31,14 @@ * if you don't input any bitmaps to these ops that have some * unused bits set, then they won't output any set unused bits * in output bitmaps. + * + * The byte ordering of bitmaps is more natural on little + * endian architectures. See the big-endian headers + * include/asm-ppc64/bitops.h and include/asm-s390/bitops.h + * for the best explanations of this ordering. */ -int bitmap_empty(const unsigned long *bitmap, int bits) +int __bitmap_empty(const unsigned long *bitmap, int bits) { int k, lim = bits/BITS_PER_LONG; for (k = 0; k < lim; ++k) @@ -40,14 +46,14 @@ int bitmap_empty(const unsigned long *bitmap, int bits) return 0; if (bits % BITS_PER_LONG) - if (bitmap[k] & ((1UL << (bits % BITS_PER_LONG)) - 1)) + if (bitmap[k] & BITMAP_LAST_WORD_MASK(bits)) return 0; return 1; } -EXPORT_SYMBOL(bitmap_empty); +EXPORT_SYMBOL(__bitmap_empty); -int bitmap_full(const unsigned long *bitmap, int bits) +int __bitmap_full(const unsigned long *bitmap, int bits) { int k, lim = bits/BITS_PER_LONG; for (k = 0; k < lim; ++k) @@ -55,14 +61,14 @@ int bitmap_full(const unsigned long *bitmap, int bits) return 0; if (bits % BITS_PER_LONG) - if (~bitmap[k] & ((1UL << (bits % BITS_PER_LONG)) - 1)) + if (~bitmap[k] & BITMAP_LAST_WORD_MASK(bits)) return 0; return 1; } -EXPORT_SYMBOL(bitmap_full); +EXPORT_SYMBOL(__bitmap_full); -int bitmap_equal(const unsigned long *bitmap1, +int __bitmap_equal(const unsigned long *bitmap1, const unsigned long *bitmap2, int bits) { int k, lim = bits/BITS_PER_LONG; @@ -71,27 +77,26 @@ int bitmap_equal(const unsigned long *bitmap1, return 0; if (bits % BITS_PER_LONG) - if ((bitmap1[k] ^ bitmap2[k]) & - ((1UL << (bits % BITS_PER_LONG)) - 1)) + if ((bitmap1[k] ^ bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits)) return 0; return 1; } -EXPORT_SYMBOL(bitmap_equal); +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, int bits) { 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] & ((1UL << (bits % BITS_PER_LONG)) - 1); + dst[k] = ~src[k] & BITMAP_LAST_WORD_MASK(bits); } -EXPORT_SYMBOL(bitmap_complement); +EXPORT_SYMBOL(__bitmap_complement); /* - * bitmap_shift_right - logical right shift of the bits in a bitmap + * __bitmap_shift_right - logical right shift of the bits in a bitmap * @dst - destination bitmap * @src - source bitmap * @nbits - shift by this many bits @@ -101,7 +106,7 @@ EXPORT_SYMBOL(bitmap_complement); * direction. Zeros are fed into the vacated MS positions and the * LS bits shifted off the bottom are lost. */ -void bitmap_shift_right(unsigned long *dst, +void __bitmap_shift_right(unsigned long *dst, const unsigned long *src, int shift, int bits) { int k, lim = BITS_TO_LONGS(bits), left = bits % BITS_PER_LONG; @@ -131,10 +136,11 @@ void bitmap_shift_right(unsigned long *dst, if (off) memset(&dst[lim - off], 0, off*sizeof(unsigned long)); } -EXPORT_SYMBOL(bitmap_shift_right); +EXPORT_SYMBOL(__bitmap_shift_right); + /* - * bitmap_shift_left - logical left shift of the bits in a bitmap + * __bitmap_shift_left - logical left shift of the bits in a bitmap * @dst - destination bitmap * @src - source bitmap * @nbits - shift by this many bits @@ -144,7 +150,8 @@ EXPORT_SYMBOL(bitmap_shift_right); * direction. Zeros are fed into the vacated LS bit positions * and those MS bits shifted off the top are lost. */ -void bitmap_shift_left(unsigned long *dst, + +void __bitmap_shift_left(unsigned long *dst, const unsigned long *src, int shift, int bits) { int k, lim = BITS_TO_LONGS(bits), left = bits % BITS_PER_LONG; @@ -170,9 +177,9 @@ void bitmap_shift_left(unsigned long *dst, if (off) memset(dst, 0, off*sizeof(unsigned long)); } -EXPORT_SYMBOL(bitmap_shift_left); +EXPORT_SYMBOL(__bitmap_shift_left); -void bitmap_and(unsigned long *dst, const unsigned long *bitmap1, +void __bitmap_and(unsigned long *dst, const unsigned long *bitmap1, const unsigned long *bitmap2, int bits) { int k; @@ -181,9 +188,9 @@ void bitmap_and(unsigned long *dst, const unsigned long *bitmap1, for (k = 0; k < nr; k++) dst[k] = bitmap1[k] & bitmap2[k]; } -EXPORT_SYMBOL(bitmap_and); +EXPORT_SYMBOL(__bitmap_and); -void bitmap_or(unsigned long *dst, const unsigned long *bitmap1, +void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1, const unsigned long *bitmap2, int bits) { int k; @@ -192,9 +199,9 @@ void bitmap_or(unsigned long *dst, const unsigned long *bitmap1, for (k = 0; k < nr; k++) dst[k] = bitmap1[k] | bitmap2[k]; } -EXPORT_SYMBOL(bitmap_or); +EXPORT_SYMBOL(__bitmap_or); -void bitmap_xor(unsigned long *dst, const unsigned long *bitmap1, +void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1, const unsigned long *bitmap2, int bits) { int k; @@ -203,9 +210,9 @@ void bitmap_xor(unsigned long *dst, const unsigned long *bitmap1, for (k = 0; k < nr; k++) dst[k] = bitmap1[k] ^ bitmap2[k]; } -EXPORT_SYMBOL(bitmap_xor); +EXPORT_SYMBOL(__bitmap_xor); -void bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1, +void __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1, const unsigned long *bitmap2, int bits) { int k; @@ -214,9 +221,9 @@ void bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1, for (k = 0; k < nr; k++) dst[k] = bitmap1[k] & ~bitmap2[k]; } -EXPORT_SYMBOL(bitmap_andnot); +EXPORT_SYMBOL(__bitmap_andnot); -int bitmap_intersects(const unsigned long *bitmap1, +int __bitmap_intersects(const unsigned long *bitmap1, const unsigned long *bitmap2, int bits) { int k, lim = bits/BITS_PER_LONG; @@ -225,14 +232,13 @@ int bitmap_intersects(const unsigned long *bitmap1, return 1; if (bits % BITS_PER_LONG) - if ((bitmap1[k] & bitmap2[k]) & - ((1UL << (bits % BITS_PER_LONG)) - 1)) + if ((bitmap1[k] & bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits)) return 1; return 0; } -EXPORT_SYMBOL(bitmap_intersects); +EXPORT_SYMBOL(__bitmap_intersects); -int bitmap_subset(const unsigned long *bitmap1, +int __bitmap_subset(const unsigned long *bitmap1, const unsigned long *bitmap2, int bits) { int k, lim = bits/BITS_PER_LONG; @@ -241,15 +247,14 @@ int bitmap_subset(const unsigned long *bitmap1, return 0; if (bits % BITS_PER_LONG) - if ((bitmap1[k] & ~bitmap2[k]) & - ((1UL << (bits % BITS_PER_LONG)) - 1)) + if ((bitmap1[k] & ~bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits)) return 0; return 1; } -EXPORT_SYMBOL(bitmap_subset); +EXPORT_SYMBOL(__bitmap_subset); #if BITS_PER_LONG == 32 -int bitmap_weight(const unsigned long *bitmap, int bits) +int __bitmap_weight(const unsigned long *bitmap, int bits) { int k, w = 0, lim = bits/BITS_PER_LONG; @@ -257,13 +262,12 @@ int bitmap_weight(const unsigned long *bitmap, int bits) w += hweight32(bitmap[k]); if (bits % BITS_PER_LONG) - w += hweight32(bitmap[k] & - ((1UL << (bits % BITS_PER_LONG)) - 1)); + w += hweight32(bitmap[k] & BITMAP_LAST_WORD_MASK(bits)); return w; } #else -int bitmap_weight(const unsigned long *bitmap, int bits) +int __bitmap_weight(const unsigned long *bitmap, int bits) { int k, w = 0, lim = bits/BITS_PER_LONG; @@ -271,13 +275,12 @@ int bitmap_weight(const unsigned long *bitmap, int bits) w += hweight64(bitmap[k]); if (bits % BITS_PER_LONG) - w += hweight64(bitmap[k] & - ((1UL << (bits % BITS_PER_LONG)) - 1)); + w += hweight64(bitmap[k] & BITMAP_LAST_WORD_MASK(bits)); return w; } #endif -EXPORT_SYMBOL(bitmap_weight); +EXPORT_SYMBOL(__bitmap_weight); /* * Bitmap printing & parsing functions: first version by Bill Irwin, @@ -394,7 +397,7 @@ int bitmap_parse(const char __user *ubuf, unsigned int ubuflen, if (nchunks == 0 && chunk == 0) continue; - bitmap_shift_left(maskp, maskp, CHUNKSZ, nmaskbits); + __bitmap_shift_left(maskp, maskp, CHUNKSZ, nmaskbits); *maskp |= chunk; nchunks++; nbits += (nchunks == 1) ? nbits_to_hold_value(chunk) : CHUNKSZ; |