From: Paul Jackson <pj@sgi.com>
To: linux-kernel@vger.kernel.org
Cc: mbligh@aracnet.com, akpm@osdl.org, wli@holomorphy.com,
haveblue@us.ibm.com, colpatch@us.ibm.com
Subject: [PATCH] mask ADT: bitmap and bitop tweaks [1/22]
Date: Mon, 29 Mar 2004 04:12:49 -0800 [thread overview]
Message-ID: <20040329041249.65d365a1.pj@sgi.com> (raw)
Patch_1_of_22 - Underlying bitmap/bitop details, added ops
Add a couple of 'const' qualifiers
Add intersects, subset, xor and andnot operators.
Fix some unused bits in bitmap_complement
Change bitmap_complement to take two operands.
diffstat Patch_1_of_22:
include/asm-generic/bitops.h | 2 -
include/asm-generic/cpumask_array.h | 2 -
include/asm-i386/mpspec.h | 2 -
include/asm-x86_64/mpspec.h | 2 -
include/linux/bitmap.h | 12 +++++-
lib/bitmap.c | 67 ++++++++++++++++++++++++++++++++----
6 files changed, 75 insertions(+), 12 deletions(-)
# This is a BitKeeper generated patch for the following project:
# Project Name: Linux kernel tree
# This patch format is intended for GNU patch command version 2.5 or higher.
# This patch includes the following deltas:
# ChangeSet 1.1706 -> 1.1707
# include/asm-i386/mpspec.h 1.17 -> 1.18
# include/asm-x86_64/mpspec.h 1.8 -> 1.9
# include/asm-generic/cpumask_array.h 1.3 -> 1.4
# include/asm-generic/bitops.h 1.2 -> 1.3
# lib/bitmap.c 1.6 -> 1.7
# include/linux/bitmap.h 1.4 -> 1.5
#
# The following is the BitKeeper ChangeSet Log
# --------------------------------------------
# 04/03/28 pj@sgi.com 1.1707
# Change bitmap_complement() from inplace to separate dest and source args.
# Add bitmap xor, andnot, intersects and subset operators.
# Mark 2nd bitmap_equal() argument as 'const'
# Refine bitmap_complement to ignore unused bits in last word.
# Mark 2nd test_bit() argument as 'const'.
# --------------------------------------------
#
diff -Nru a/include/asm-generic/bitops.h b/include/asm-generic/bitops.h
--- a/include/asm-generic/bitops.h Mon Mar 29 01:03:26 2004
+++ b/include/asm-generic/bitops.h Mon Mar 29 01:03:26 2004
@@ -42,7 +42,7 @@
return retval;
}
-extern __inline__ int test_bit(int nr, long * addr)
+extern __inline__ int test_bit(int nr, const unsigned long * addr)
{
int mask;
diff -Nru a/include/asm-generic/cpumask_array.h b/include/asm-generic/cpumask_array.h
--- a/include/asm-generic/cpumask_array.h Mon Mar 29 01:03:26 2004
+++ b/include/asm-generic/cpumask_array.h Mon Mar 29 01:03:26 2004
@@ -17,7 +17,7 @@
#define cpus_and(dst,src1,src2) bitmap_and((dst).mask,(src1).mask, (src2).mask, NR_CPUS)
#define cpus_or(dst,src1,src2) bitmap_or((dst).mask, (src1).mask, (src2).mask, NR_CPUS)
#define cpus_clear(map) bitmap_clear((map).mask, NR_CPUS)
-#define cpus_complement(map) bitmap_complement((map).mask, NR_CPUS)
+#define cpus_complement(map) bitmap_complement((map).mask, (map).mask, NR_CPUS)
#define cpus_equal(map1, map2) bitmap_equal((map1).mask, (map2).mask, NR_CPUS)
#define cpus_empty(map) bitmap_empty(map.mask, NR_CPUS)
#define cpus_addr(map) ((map).mask)
diff -Nru a/include/asm-i386/mpspec.h b/include/asm-i386/mpspec.h
--- a/include/asm-i386/mpspec.h Mon Mar 29 01:03:26 2004
+++ b/include/asm-i386/mpspec.h Mon Mar 29 01:03:26 2004
@@ -60,7 +60,7 @@
#define physids_and(dst, src1, src2) bitmap_and((dst).mask, (src1).mask, (src2).mask, MAX_APICS)
#define physids_or(dst, src1, src2) bitmap_or((dst).mask, (src1).mask, (src2).mask, MAX_APICS)
#define physids_clear(map) bitmap_clear((map).mask, MAX_APICS)
-#define physids_complement(map) bitmap_complement((map).mask, MAX_APICS)
+#define physids_complement(map) bitmap_complement((map).mask, (map).mask, MAX_APICS)
#define physids_empty(map) bitmap_empty((map).mask, MAX_APICS)
#define physids_equal(map1, map2) bitmap_equal((map1).mask, (map2).mask, MAX_APICS)
#define physids_weight(map) bitmap_weight((map).mask, MAX_APICS)
diff -Nru a/include/asm-x86_64/mpspec.h b/include/asm-x86_64/mpspec.h
--- a/include/asm-x86_64/mpspec.h Mon Mar 29 01:03:26 2004
+++ b/include/asm-x86_64/mpspec.h Mon Mar 29 01:03:26 2004
@@ -214,7 +214,7 @@
#define physids_and(dst, src1, src2) bitmap_and((dst).mask, (src1).mask, (src2).mask, MAX_APICS)
#define physids_or(dst, src1, src2) bitmap_or((dst).mask, (src1).mask, (src2).mask, MAX_APICS)
#define physids_clear(map) bitmap_clear((map).mask, MAX_APICS)
-#define physids_complement(map) bitmap_complement((map).mask, MAX_APICS)
+#define physids_complement(map) bitmap_complement((map).mask, (map).mask, MAX_APICS)
#define physids_empty(map) bitmap_empty((map).mask, MAX_APICS)
#define physids_equal(map1, map2) bitmap_equal((map1).mask, (map2).mask, MAX_APICS)
#define physids_weight(map) bitmap_weight((map).mask, MAX_APICS)
diff -Nru a/include/linux/bitmap.h b/include/linux/bitmap.h
--- a/include/linux/bitmap.h Mon Mar 29 01:03:26 2004
+++ b/include/linux/bitmap.h Mon Mar 29 01:03:26 2004
@@ -13,8 +13,8 @@
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,
- unsigned long *bitmap2, int bits);
-void bitmap_complement(unsigned long *bitmap, int bits);
+ const unsigned long *bitmap2, int bits);
+void bitmap_complement(unsigned long *dst, const unsigned long *src, int bits);
static inline void bitmap_clear(unsigned long *bitmap, int bits)
{
@@ -39,6 +39,14 @@
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,
diff -Nru a/lib/bitmap.c b/lib/bitmap.c
--- a/lib/bitmap.c Mon Mar 29 01:03:26 2004
+++ b/lib/bitmap.c Mon Mar 29 01:03:26 2004
@@ -45,7 +45,7 @@
EXPORT_SYMBOL(bitmap_full);
int bitmap_equal(const unsigned long *bitmap1,
- unsigned long *bitmap2, int bits)
+ const unsigned long *bitmap2, int bits)
{
int k, lim = bits/BITS_PER_LONG;;
for (k = 0; k < lim; ++k)
@@ -61,13 +61,14 @@
}
EXPORT_SYMBOL(bitmap_equal);
-void bitmap_complement(unsigned long *bitmap, int bits)
+void bitmap_complement(unsigned long *dst, const unsigned long *src, int bits)
{
- int k;
- int nr = BITS_TO_LONGS(bits);
+ int k, lim = bits/BITS_PER_LONG;;
+ for (k = 0; k < lim; ++k)
+ dst[k] = ~src[k];
- for (k = 0; k < nr; ++k)
- bitmap[k] = ~bitmap[k];
+ if (bits % BITS_PER_LONG)
+ dst[k] = ~src[k] & ((1UL << (bits % BITS_PER_LONG)) - 1);
}
EXPORT_SYMBOL(bitmap_complement);
@@ -122,6 +123,60 @@
dst[k] = bitmap1[k] | bitmap2[k];
}
EXPORT_SYMBOL(bitmap_or);
+
+void bitmap_xor(unsigned long *dst, const unsigned long *bitmap1,
+ const unsigned long *bitmap2, int bits)
+{
+ int k;
+ int nr = BITS_TO_LONGS(bits);
+
+ for (k = 0; k < nr; k++)
+ dst[k] = bitmap1[k] ^ bitmap2[k];
+}
+EXPORT_SYMBOL(bitmap_xor);
+
+void bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1,
+ const unsigned long *bitmap2, int bits)
+{
+ int k;
+ int nr = BITS_TO_LONGS(bits);
+
+ for (k = 0; k < nr; k++)
+ dst[k] = bitmap1[k] & ~bitmap2[k];
+}
+EXPORT_SYMBOL(bitmap_andnot);
+
+int bitmap_intersects(const unsigned long *bitmap1,
+ const unsigned long *bitmap2, int bits)
+{
+ int k, lim = bits/BITS_PER_LONG;;
+ for (k = 0; k < lim; ++k)
+ if (bitmap1[k] & bitmap2[k])
+ return 1;
+
+ if (bits % BITS_PER_LONG)
+ if ((bitmap1[k] & bitmap2[k]) &
+ ((1UL << (bits % BITS_PER_LONG)) - 1))
+ return 1;
+ return 0;
+}
+EXPORT_SYMBOL(bitmap_intersects);
+
+int bitmap_subset(const unsigned long *bitmap1,
+ const unsigned long *bitmap2, int bits)
+{
+ int k, lim = bits/BITS_PER_LONG;;
+ for (k = 0; k < lim; ++k)
+ if (bitmap1[k] & ~bitmap2[k])
+ return 0;
+
+ if (bits % BITS_PER_LONG)
+ if ((bitmap1[k] & ~bitmap2[k]) &
+ ((1UL << (bits % BITS_PER_LONG)) - 1))
+ return 0;
+ return 1;
+}
+EXPORT_SYMBOL(bitmap_subset);
#if BITS_PER_LONG == 32
int bitmap_weight(const unsigned long *bitmap, int bits)
--
I won't rest till it's the best ...
Programmer, Linux Scalability
Paul Jackson <pj@sgi.com> 1.650.933.1373
next reply other threads:[~2004-03-29 13:32 UTC|newest]
Thread overview: 15+ messages / expand[flat|nested] mbox.gz Atom feed top
2004-03-29 12:12 Paul Jackson [this message]
2004-03-29 23:06 ` [PATCH] mask ADT: bitmap and bitop tweaks [1/22] Matthew Dobson
2004-03-29 23:52 ` William Lee Irwin III
2004-03-29 23:43 ` Paul Jackson
2004-03-30 1:27 ` Matthew Dobson
2004-03-30 2:06 ` William Lee Irwin III
2004-03-30 1:46 ` Paul Jackson
2004-03-30 2:55 ` William Lee Irwin III
2004-03-30 5:09 ` Paul Jackson
2004-03-30 6:36 ` William Lee Irwin III
2004-03-30 8:00 ` Paul Jackson
2004-03-30 9:22 ` William Lee Irwin III
2004-03-29 23:50 ` Paul Jackson
2004-03-30 15:53 ` Chris Friesen
2004-03-30 18:30 ` 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=20040329041249.65d365a1.pj@sgi.com \
--to=pj@sgi.com \
--cc=akpm@osdl.org \
--cc=colpatch@us.ibm.com \
--cc=haveblue@us.ibm.com \
--cc=linux-kernel@vger.kernel.org \
--cc=mbligh@aracnet.com \
--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 a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox