Add most used bitmap and bitops functions into bitmap.c and bitops.c.
Theses functions are mostly copied from Linux kernel source.
Some of these functions are already redefined in the VNC server. Some
of them could be used for some block stuff. The yet yo be submitted
NUMA work also need bitmaps.
Signed-off-by: Corentin Chary
---
Makefile.objs |1 +
bitmap.c | 255 +
bitmap.h | 222 ++
bitops.c | 142 ++
bitops.h | 272 +
osdep.h |4 +
6 files changed, 896 insertions(+), 0 deletions(-)
create mode 100644 bitmap.c
create mode 100644 bitmap.h
create mode 100644 bitops.c
create mode 100644 bitops.h
diff --git a/Makefile.objs b/Makefile.objs
index a6dd2ab..d4afde8 100644
--- a/Makefile.objs
+++ b/Makefile.objs
@@ -83,6 +83,7 @@ common-obj-y += qemu-char.o savevm.o #aio.o
common-obj-y += msmouse.o ps2.o
common-obj-y += qdev.o qdev-properties.o
common-obj-y += block-migration.o
+common-obj-y += bitmap.c bitops.c
common-obj-$(CONFIG_BRLAPI) += baum.o
common-obj-$(CONFIG_POSIX) += migration-exec.o migration-unix.o migration-fd.o
diff --git a/bitmap.c b/bitmap.c
new file mode 100644
index 000..eaafbea
--- /dev/null
+++ b/bitmap.c
@@ -0,0 +1,255 @@
+/*
+ * Bitmap Module
+ *
+ * Stolen from linux/src/lib/bitmap.c
+ *
+ * Copyright (C) 2010 Corentin Chary
+ *
+ * This source code is licensed under the GNU General Public License,
+ * Version 2.
+ */
+
+#include "bitops.h"
+#include "bitmap.h"
+
+/*
+ * bitmaps provide an array of bits, implemented using an an
+ * array of unsigned longs. The number of valid bits in a
+ * 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
+ * no particular effort to keep them zero. It ensures that
+ * their value will not affect the results of any operation.
+ * The bitmap operations that return Boolean (bitmap_empty,
+ * for example) or scalar (bitmap_weight, for example) results
+ * carefully filter out these unused bits from impacting their
+ * results.
+ *
+ * These operations actually hold to a slightly stronger rule:
+ * 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.
+ */
+
+int __bitmap_empty(const unsigned long *bitmap, int bits)
+{
+int k, lim = bits/BITS_PER_LONG;
+
+for (k = 0; k < lim; ++k) {
+if (bitmap[k]) {
+return 0;
+}
+}
+if (bits % BITS_PER_LONG) {
+if (bitmap[k] & BITMAP_LAST_WORD_MASK(bits)) {
+return 0;
+}
+}
+
+return 1;
+}
+
+int __bitmap_full(const unsigned long *bitmap, int bits)
+{
+int k, lim = bits/BITS_PER_LONG;
+
+for (k = 0; k < lim; ++k) {
+if (~bitmap[k]) {
+return 0;
+}
+}
+
+if (bits % BITS_PER_LONG) {
+if (~bitmap[k] & BITMAP_LAST_WORD_MASK(bits)) {
+return 0;
+}
+}
+
+return 1;
+}
+
+int __bitmap_equal(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]) & BITMAP_LAST_WORD_MASK(bits)) {
+return 0;
+}
+}
+
+return 1;
+}
+
+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] & BITMAP_LAST_WORD_MASK(bits);
+}
+}
+
+int __bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
+ const unsigned long *bitmap2, int bits)
+{
+int k;
+int nr = BITS_TO_LONGS(bits);
+unsigned long result = 0;
+
+for (k = 0; k < nr; k++) {
+result |= (dst[k] = bitmap1[k] & bitmap2[k]);
+}
+return result != 0;
+}
+
+void __bitmap_or(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];
+}
+}
+
+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];
+}
+}
+
+int __bitmap_andnot(unsigned long *dst, const unsig
