From: Paul Jackson <pj@sgi.com>
To: Paul Jackson <pj@sgi.com>
Cc: colpatch@us.ibm.com, wli@holomorphy.com, rusty@rustcorp.com.au,
linux-kernel@vger.kernel.org
Subject: [Patch 5 of 17] cpumask v4 - Optimize and extend bitmap.
Date: Thu, 22 Apr 2004 00:07:07 -0700 [thread overview]
Message-ID: <20040422000707.68f35fb6.pj@sgi.com> (raw)
In-Reply-To: <20040421232247.22ffe1f2.pj@sgi.com>
mask5-bitmap-extensions - Optimize and extend bitmap.
This 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.
Index: 2.6.5.bitmap/include/linux/bitmap.h
===================================================================
--- 2.6.5.bitmap.orig/include/linux/bitmap.h 2004-04-07 21:22:32.000000000 -0700
+++ 2.6.5.bitmap/include/linux/bitmap.h 2004-04-07 21:23:52.000000000 -0700
@@ -1,59 +1,250 @@
-#ifndef __LINUX_BITMAP_H
-#define __LINUX_BITMAP_H
+#ifndef __LINUX__bitmap_H
+#define __LINUX__bitmap_H
#ifndef __ASSEMBLY__
-#include <linux/config.h>
-#include <linux/compiler.h>
#include <linux/types.h>
-#include <linux/kernel.h>
#include <linux/bitops.h>
#include <linux/string.h>
-int bitmap_empty(const unsigned long *bitmap, int bits);
-int bitmap_full(const unsigned long *bitmap, int bits);
-int bitmap_equal(const unsigned long *bitmap1,
- const unsigned long *bitmap2, int bits);
-void bitmap_complement(unsigned long *dst, const unsigned long *src, int bits);
+/*
+ * bitmaps provide bit arrays that consume one or more unsigned
+ * longs. The bitmap interface and available operations are listed
+ * here, in bitmap.h
+ *
+ * Function implementations generic to all architectures are in
+ * lib/bitmap.c. Functions implementations that are architecture
+ * specific are in various include/asm-<arch>/bitops.h headers
+ * and other arch/<arch> specific files.
+ *
+ * See lib/bitmap.c for more details.
+ */
+
+/*
+ * The available bitmap operations and their rough meaning in the
+ * case that the bitmap is a single unsigned long are thus:
+ *
+ * bitmap_clear(dst, nbits) *dst = 0UL
+ * bitmap_fill(dst, nbits) *dst = ~0UL
+ * bitmap_copy(dst, src, nbits) *dst = *src
+ * bitmap_and(dst, src1, src2, nbits) *dst = *src1 & *src2
+ * bitmap_or(dst, src1, src2, nbits) *dst = *src1 | *src2
+ * bitmap_xor(dst, src1, src2, nbits) *dst = *src1 ^ *src2
+ * bitmap_andnot(dst, src1, src2, nbits) *dst = *src1 & ~(*src2)
+ * bitmap_complement(dst, src, nbits) *dst = ~(*src)
+ * bitmap_equal(src1, src2, nbits) Are *src1 and *src2 equal?
+ * bitmap_intersects(src1, src2, nbits) Do *src1 and *src2 overlap?
+ * bitmap_subset(src1, src2, nbits) Is *src1 a subset of *src2?
+ * bitmap_empty(src, nbits) Are all bits zero in *src?
+ * bitmap_full(src, nbits) Are all bits set in *src?
+ * bitmap_weight(src, nbits) Hamming Weight: number set bits
+ * bitmap_shift_right(dst, src, n, nbits) *dst = *src >> n
+ * bitmap_shift_left(dst, src, n, nbits) *dst = *src << n
+ * bitmap_scnprintf(buf, len, src, nbits) Print bitmap src to buf
+ * bitmap_parse(ubuf, ulen, dst, nbits) Parse bitmap dst from buf
+ */
+
+/*
+ * Also the following operations in asm/bitops.h apply to bitmaps.
+ *
+ * set_bit(bit, addr) *addr |= bit
+ * clear_bit(bit, addr) *addr &= ~bit
+ * change_bit(bit, addr) *addr ^= bit
+ * test_bit(bit, addr) Is bit set in *addr?
+ * test_and_set_bit(bit, addr) Set bit and return old value
+ * test_and_clear_bit(bit, addr) Clear bit and return old value
+ * test_and_change_bit(bit, addr) Change bit and return old value
+ * find_first_zero_bit(addr, nbits) Position first zero bit in *addr
+ * find_first_bit(addr, nbits) Position first set bit in *addr
+ * find_next_zero_bit(addr, nbits, bit) Position next zero bit in *addr >= bit
+ * find_next_bit(addr, nbits, bit) Position next set bit in *addr >= bit
+ */
+
+/*
+ * The DECLARE_BITMAP(name,bits) macro, in linux/types.h, can be used
+ * to declare an array named 'name' of just enough unsigned longs to
+ * contain all bit positions from 0 to 'bits' - 1.
+ */
+
+/*
+ * lib/bitmap.c provides these functions:
+ */
+
+extern int __bitmap_empty(const unsigned long *bitmap, int bits);
+extern int __bitmap_full(const unsigned long *bitmap, int bits);
+extern int __bitmap_equal(const unsigned long *bitmap1,
+ const unsigned long *bitmap2, int bits);
+extern void __bitmap_complement(unsigned long *dst, const unsigned long *src,
+ int bits);
+extern void __bitmap_shift_right(unsigned long *dst,
+ const unsigned long *src, int shift, int bits);
+extern void __bitmap_shift_left(unsigned long *dst,
+ const unsigned long *src, int shift, int bits);
+extern void __bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
+ const unsigned long *bitmap2, int bits);
+extern void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
+ const unsigned long *bitmap2, int bits);
+extern void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1,
+ const unsigned long *bitmap2, int bits);
+extern void __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1,
+ const unsigned long *bitmap2, int bits);
+extern int __bitmap_intersects(const unsigned long *bitmap1,
+ const unsigned long *bitmap2, int bits);
+extern int __bitmap_subset(const unsigned long *bitmap1,
+ const unsigned long *bitmap2, int bits);
+extern int __bitmap_weight(const unsigned long *bitmap, int bits);
+
+extern int bitmap_scnprintf(char *buf, unsigned int len,
+ const unsigned long *src, int nbits);
+extern int bitmap_parse(const char __user *ubuf, unsigned int ulen,
+ unsigned long *dst, int nbits);
+
+#define BITMAP_LAST_WORD_MASK(nbits) \
+( \
+ ((nbits) % BITS_PER_LONG) ? \
+ (1UL<<((nbits) % BITS_PER_LONG))-1 : ~0UL \
+)
-static inline void bitmap_clear(unsigned long *bitmap, int bits)
+static inline void bitmap_clear(unsigned long *dst, int nbits)
{
- CLEAR_BITMAP((unsigned long *)bitmap, bits);
+ if (nbits <= BITS_PER_LONG)
+ *dst = 0UL;
+ else
+ CLEAR_BITMAP(dst, nbits);
}
-static inline void bitmap_fill(unsigned long *bitmap, int bits)
+static inline void bitmap_fill(unsigned long *dst, int nbits)
{
- memset(bitmap, 0xff, BITS_TO_LONGS(bits)*sizeof(unsigned long));
+ size_t nlongs = BITS_TO_LONGS(nbits);
+ if (nlongs > 1) {
+ int len = (nlongs - 1) * sizeof(unsigned long);
+ memset(dst, 0xff, len);
+ }
+ dst[nlongs - 1] = BITMAP_LAST_WORD_MASK(nbits);
}
-static inline void bitmap_copy(unsigned long *dst,
- const unsigned long *src, int bits)
+static inline void bitmap_copy(unsigned long *dst, const unsigned long *src,
+ int nbits)
{
- memcpy(dst, src, BITS_TO_LONGS(bits)*sizeof(unsigned long));
+ if (nbits <= BITS_PER_LONG)
+ *dst = *src;
+ else {
+ int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
+ memcpy(dst, src, len);
+ }
}
-void bitmap_shift_right(unsigned long *dst,
- const unsigned long *src, int shift, int bits);
-void bitmap_shift_left(unsigned long *dst,
- const unsigned long *src, int shift, int bits);
-void bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
- const unsigned long *bitmap2, int bits);
-void bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
- const unsigned long *bitmap2, int bits);
-void bitmap_xor(unsigned long *dst, const unsigned long *bitmap1,
- const unsigned long *bitmap2, int bits);
-void bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1,
- const unsigned long *bitmap2, int bits);
-int bitmap_intersects(const unsigned long *bitmap1,
- const unsigned long *bitmap2, int bits);
-int bitmap_subset(const unsigned long *bitmap1,
- const unsigned long *bitmap2, int bits);
-int bitmap_weight(const unsigned long *bitmap, int bits);
-int bitmap_scnprintf(char *buf, unsigned int buflen,
- const unsigned long *maskp, int bits);
-int bitmap_parse(const char __user *ubuf, unsigned int ubuflen,
- unsigned long *maskp, int bits);
+static inline void bitmap_and(unsigned long *dst, const unsigned long *src1,
+ const unsigned long *src2, int nbits)
+{
+ if (nbits <= BITS_PER_LONG)
+ *dst = *src1 & *src2;
+ else
+ __bitmap_and(dst, src1, src2, nbits);
+}
+
+static inline void bitmap_or(unsigned long *dst, const unsigned long *src1,
+ const unsigned long *src2, int nbits)
+{
+ if (nbits <= BITS_PER_LONG)
+ *dst = *src1 | *src2;
+ else
+ __bitmap_or(dst, src1, src2, nbits);
+}
+
+static inline void bitmap_xor(unsigned long *dst, const unsigned long *src1,
+ const unsigned long *src2, int nbits)
+{
+ if (nbits <= BITS_PER_LONG)
+ *dst = *src1 ^ *src2;
+ else
+ __bitmap_xor(dst, src1, src2, nbits);
+}
+
+static inline void bitmap_andnot(unsigned long *dst, const unsigned long *src1,
+ const unsigned long *src2, int nbits)
+{
+ if (nbits <= BITS_PER_LONG)
+ *dst = *src1 & ~(*src2);
+ else
+ __bitmap_andnot(dst, src1, src2, nbits);
+}
+
+static inline void bitmap_complement(unsigned long *dst, const unsigned long *src,
+ int nbits)
+{
+ if (nbits <= BITS_PER_LONG)
+ *dst = ~(*src) & BITMAP_LAST_WORD_MASK(nbits);
+ else
+ __bitmap_complement(dst, src, nbits);
+}
+
+static inline int bitmap_equal(const unsigned long *src1,
+ const unsigned long *src2, int nbits)
+{
+ if (nbits <= BITS_PER_LONG)
+ return ! ((*src1 ^ *src2) & BITMAP_LAST_WORD_MASK(nbits));
+ else
+ return __bitmap_equal(src1, src2, nbits);
+}
+
+static inline int bitmap_intersects(const unsigned long *src1,
+ const unsigned long *src2, int nbits)
+{
+ if (nbits <= BITS_PER_LONG)
+ return ((*src1 & *src2) & BITMAP_LAST_WORD_MASK(nbits)) != 0;
+ else
+ return __bitmap_intersects(src1, src2, nbits);
+}
+
+static inline int bitmap_subset(const unsigned long *src1,
+ const unsigned long *src2, int nbits)
+{
+ if (nbits <= BITS_PER_LONG)
+ return ! ((*src1 & ~(*src2)) & BITMAP_LAST_WORD_MASK(nbits));
+ else
+ return __bitmap_subset(src1, src2, nbits);
+}
+
+static inline int bitmap_empty(const unsigned long *src, int nbits)
+{
+ if (nbits <= BITS_PER_LONG)
+ return ! (*src & BITMAP_LAST_WORD_MASK(nbits));
+ else
+ return __bitmap_empty(src, nbits);
+}
+
+static inline int bitmap_full(const unsigned long *src, int nbits)
+{
+ if (nbits <= BITS_PER_LONG)
+ return ! (~(*src) & BITMAP_LAST_WORD_MASK(nbits));
+ else
+ return __bitmap_full(src, nbits);
+}
+
+static inline int bitmap_weight(const unsigned long *src, int nbits)
+{
+ return __bitmap_weight(src, nbits);
+}
+
+static inline void bitmap_shift_right(unsigned long *dst,
+ const unsigned long *src, int n, int nbits)
+{
+ if (nbits <= BITS_PER_LONG)
+ *dst = *src >> n;
+ else
+ __bitmap_shift_right(dst, src, n, nbits);
+}
+
+static inline void bitmap_shift_left(unsigned long *dst,
+ const unsigned long *src, int n, int nbits)
+{
+ if (nbits <= BITS_PER_LONG)
+ *dst = (*src << n) & BITMAP_LAST_WORD_MASK(nbits);
+ else
+ __bitmap_shift_left(dst, src, n, nbits);
+}
#endif /* __ASSEMBLY__ */
-#endif /* __LINUX_BITMAP_H */
+#endif /* __LINUX__bitmap_H */
Index: 2.6.5.bitmap/lib/bitmap.c
===================================================================
--- 2.6.5.bitmap.orig/lib/bitmap.c 2004-04-07 21:22:32.000000000 -0700
+++ 2.6.5.bitmap/lib/bitmap.c 2004-04-07 21:23:52.000000000 -0700
@@ -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,11 +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.
*/
-#define MAX_BITMAP_BITS 512U /* for ia64 NR_CPUS maximum */
-
-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)
@@ -42,14 +46,14 @@
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)
@@ -57,14 +61,14 @@
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;
@@ -73,56 +77,85 @@
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);
-void bitmap_shift_right(unsigned long *dst,
+void __bitmap_shift_right(unsigned long *dst,
const unsigned long *src, int shift, int bits)
{
- int k;
- DECLARE_BITMAP(__shr_tmp, MAX_BITMAP_BITS);
-
- BUG_ON(bits > MAX_BITMAP_BITS);
- bitmap_clear(__shr_tmp, bits);
- for (k = 0; k < bits - shift; ++k)
- if (test_bit(k + shift, src))
- set_bit(k, __shr_tmp);
- bitmap_copy(dst, __shr_tmp, bits);
+ int k, lim = BITS_TO_LONGS(bits), left = bits % BITS_PER_LONG;
+ int off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG;
+ unsigned long mask = (1UL << left) - 1;
+ for (k = 0; off + k < lim; ++k) {
+ unsigned long upper, lower;
+
+ /*
+ * If shift is not word aligned, take lower rem bits of
+ * word above and make them the top rem bits of result.
+ */
+ if (!rem || off + k + 1 >= lim)
+ upper = 0;
+ else {
+ upper = src[off + k + 1];
+ if (off + k + 1 == lim - 1 && left)
+ upper &= mask;
+ }
+ lower = src[off + k];
+ if (left && off + k == lim - 1)
+ lower &= mask;
+ dst[k] = upper << (BITS_PER_LONG - rem) | lower >> rem;
+ if (left && k == lim - 1)
+ dst[k] &= mask;
+ }
+ if (off)
+ memset(&dst[lim - off], 0, off*sizeof(unsigned long));
}
-EXPORT_SYMBOL(bitmap_shift_right);
+EXPORT_SYMBOL(__bitmap_shift_right);
-void bitmap_shift_left(unsigned long *dst,
+void __bitmap_shift_left(unsigned long *dst,
const unsigned long *src, int shift, int bits)
{
- int k;
- DECLARE_BITMAP(__shl_tmp, MAX_BITMAP_BITS);
-
- BUG_ON(bits > MAX_BITMAP_BITS);
- bitmap_clear(__shl_tmp, bits);
- for (k = bits; k >= shift; --k)
- if (test_bit(k - shift, src))
- set_bit(k, __shl_tmp);
- bitmap_copy(dst, __shl_tmp, bits);
+ int k, lim = BITS_TO_LONGS(bits), left = bits % BITS_PER_LONG;
+ int off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG;
+ for (k = lim - off - 1; k >= 0; --k) {
+ unsigned long upper, lower;
+
+ /*
+ * If shift is not word aligned, take upper rem bits of
+ * word below and make them the bottom rem bits of result.
+ */
+ if (rem && k > 0)
+ lower = src[k - 1];
+ else
+ lower = 0;
+ upper = src[k];
+ if (left && k == lim - 1)
+ upper &= (1UL << left) - 1;
+ dst[k + off] = lower >> (BITS_PER_LONG - rem) | upper << rem;
+ if (left && k + off == lim - 1)
+ dst[k + off] &= (1UL << left) - 1;
+ }
+ 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;
@@ -131,9 +164,9 @@
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;
@@ -142,9 +175,9 @@
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;
@@ -153,9 +186,9 @@
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;
@@ -164,9 +197,9 @@
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;
@@ -175,14 +208,13 @@
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;
@@ -191,15 +223,14 @@
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;
@@ -207,13 +238,12 @@
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;
@@ -221,13 +251,12 @@
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,
@@ -344,7 +373,7 @@
if (nchunks == 0 && chunk == 0)
continue;
- bitmap_shift_right(maskp, maskp, CHUNKSZ, nmaskbits);
+ __bitmap_shift_right(maskp, maskp, CHUNKSZ, nmaskbits);
*maskp |= chunk;
nchunks++;
nbits += (nchunks == 1) ? nbits_to_hold_value(chunk) : CHUNKSZ;
--
I won't rest till it's the best ...
Programmer, Linux Scalability
Paul Jackson <pj@sgi.com> 1.650.933.1373
next prev parent reply other threads:[~2004-04-22 7:19 UTC|newest]
Thread overview: 20+ messages / expand[flat|nested] mbox.gz Atom feed top
2004-04-22 6:22 [Patch 0 of 17] cpumask v4 - bitmap and cpumask cleanup Paul Jackson
2004-04-22 7:05 ` [Patch 1 of 17] cpumask v4 - Document bitmap.c bit model Paul Jackson
2004-04-22 7:06 ` [Patch 2 of 17] cpumask v4 - Dont generate nonzero unused bits in bitmap Paul Jackson
2004-04-22 7:07 ` [Patch 3 of 17] cpumask v4 - New bitmap operators and two op complement Paul Jackson
2004-04-22 7:07 ` [Patch 4 of 17] cpumask v4 - two missing 'const' qualifiers in bitops/bitmap Paul Jackson
2004-04-22 7:07 ` Paul Jackson [this message]
2004-04-22 7:07 ` [Patch 6 of 17] cpumask v4 - Uninline find_next_bit on ia64 Paul Jackson
2004-04-22 7:07 ` [Patch 7 of 17] cpumask v4 - Rewrite cpumask.h to use bitmap directly Paul Jackson
2004-04-22 7:07 ` [Patch 8 of 17] cpumask v4 - Remove 26 no longer used cpumask headers Paul Jackson
2004-04-22 7:07 ` [Patch 9 of 17] cpumask v4 - Recode obsolete cpumask macros - arch i386 Paul Jackson
2004-04-22 7:07 ` [Patch 10 of 17] cpumask v4 - Recode obsolete cpumask macros - arch ppc64 Paul Jackson
2004-04-22 7:07 ` [Patch 11 of 17] cpumask v4 - Recode obsolete cpumask macros - arch x86_64 Paul Jackson
2004-04-22 7:07 ` [Patch 12 of 17] cpumask v4 - Remove obsolete emulation from cpumask.h Paul Jackson
2004-04-22 7:07 ` [Patch 13 of 17] cpumask v4 - Simplify some sparc64 cpumask loop code Paul Jackson
2004-04-22 7:07 ` [Patch 14 of 17] cpumask v4 - Optimize i386 cpumask macro usage Paul Jackson
2004-04-22 7:07 ` [Patch 15 of 17] cpumask v4 - Convert physids_complement() to use both args Paul Jackson
2004-04-22 7:07 ` [Patch 16 of 17] cpumask v4 - Remove cpumask hack from asm-x86_64/topology.h Paul Jackson
2004-04-22 7:07 ` [Patch 17 of 17] cpumask v4 - Cpumask code clarification in kernel/sched.c Paul Jackson
2004-04-22 16:25 ` [Patch 0 of 17] cpumask v4 - bitmap and cpumask cleanup Joe Korty
2004-04-22 17:00 ` Paul Jackson
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20040422000707.68f35fb6.pj@sgi.com \
--to=pj@sgi.com \
--cc=colpatch@us.ibm.com \
--cc=linux-kernel@vger.kernel.org \
--cc=rusty@rustcorp.com.au \
--cc=wli@holomorphy.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.