From: David Gibson <david@gibson.dropbear.id.au>
Date: Thu, 2 Oct 2014 14:14:58 +0000 (+1000)
Subject: bitmap: Add functions to set/clear ranges of bits
X-Git-Url: https://git.ozlabs.org/?p=ccan;a=commitdiff_plain;h=4e7f97a92ef78a956425f8d0d03e57230e131618;ds=sidebyside

bitmap: Add functions to set/clear ranges of bits

Add bitmap_zero_range() and bitmap_fill_range() functions which will set
a contiguous range of bits in the bitmap to 0 or 1.

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
---

diff --git a/ccan/bitmap/bitmap.c b/ccan/bitmap/bitmap.c
new file mode 100644
index 00000000..a6058117
--- /dev/null
+++ b/ccan/bitmap/bitmap.c
@@ -0,0 +1,60 @@
+/* Licensed under LGPLv2.1+ - see LICENSE file for details */
+
+#include "config.h"
+
+#include <ccan/bitmap/bitmap.h>
+
+#include <assert.h>
+
+#define BIT_ALIGN_DOWN(n)	((n) & ~(BITMAP_WORD_BITS - 1))
+#define BIT_ALIGN_UP(n)		BIT_ALIGN_DOWN((n) + BITMAP_WORD_BITS - 1)
+
+void bitmap_zero_range(bitmap *bitmap, unsigned long n, unsigned long m)
+{
+	unsigned long an = BIT_ALIGN_UP(n);
+	unsigned long am = BIT_ALIGN_DOWN(m);
+	bitmap_word headmask = -1ULL >> (n % BITMAP_WORD_BITS);
+	bitmap_word tailmask = ~(-1ULL >> (m % BITMAP_WORD_BITS));
+
+	assert(m >= n);
+
+	if (am < an) {
+		BITMAP_WORD(bitmap, n) &= ~bitmap_bswap(headmask & tailmask);
+		return;
+	}
+
+	if (an > n)
+		BITMAP_WORD(bitmap, n) &= ~bitmap_bswap(headmask);
+
+	if (am > an)
+		memset(&BITMAP_WORD(bitmap, an), 0,
+		       (am - an) / BITMAP_WORD_BITS * sizeof(bitmap_word));
+
+	if (m > am)
+		BITMAP_WORD(bitmap, m) &= ~bitmap_bswap(tailmask);
+}
+
+void bitmap_fill_range(bitmap *bitmap, unsigned long n, unsigned long m)
+{
+	unsigned long an = BIT_ALIGN_UP(n);
+	unsigned long am = BIT_ALIGN_DOWN(m);
+	bitmap_word headmask = -1ULL >> (n % BITMAP_WORD_BITS);
+	bitmap_word tailmask = ~(-1ULL >> (m % BITMAP_WORD_BITS));
+
+	assert(m >= n);
+
+	if (am < an) {
+		BITMAP_WORD(bitmap, n) |= bitmap_bswap(headmask & tailmask);
+		return;
+	}
+
+	if (an > n)
+		BITMAP_WORD(bitmap, n) |= bitmap_bswap(headmask);
+
+	if (am > an)
+		memset(&BITMAP_WORD(bitmap, an), 0xff,
+		       (am - an) / BITMAP_WORD_BITS * sizeof(bitmap_word));
+
+	if (m > am)
+		BITMAP_WORD(bitmap, m) |= bitmap_bswap(tailmask);
+}
diff --git a/ccan/bitmap/bitmap.h b/ccan/bitmap/bitmap.h
index 794b2650..34faf500 100644
--- a/ccan/bitmap/bitmap.h
+++ b/ccan/bitmap/bitmap.h
@@ -80,6 +80,8 @@ static inline bool bitmap_test_bit(const bitmap *bitmap, unsigned long n)
 	return !!(BITMAP_WORD(bitmap, n) & BITMAP_WORDBIT(n));
 }
 
+void bitmap_zero_range(bitmap *bitmap, unsigned long n, unsigned long m);
+void bitmap_fill_range(bitmap *bitmap, unsigned long n, unsigned long m);
 
 static inline void bitmap_zero(bitmap *bitmap, unsigned long nbits)
 {
diff --git a/ccan/bitmap/test/run-ranges.c b/ccan/bitmap/test/run-ranges.c
new file mode 100644
index 00000000..5ba383ca
--- /dev/null
+++ b/ccan/bitmap/test/run-ranges.c
@@ -0,0 +1,77 @@
+#include <ccan/bitmap/bitmap.h>
+#include <ccan/tap/tap.h>
+#include <ccan/array_size/array_size.h>
+#include <ccan/foreach/foreach.h>
+
+#include <ccan/bitmap/bitmap.c>
+
+int bitmap_sizes[] = {
+	1, 2, 3, 4, 5, 6, 7, 8,
+	16, 24, 32, 64, 256,
+	/*
+	 * Don't put too big sizes in here, or it will take forever to
+	 * run under valgrind (the test is O(n^3)).
+	 */
+};
+#define NSIZES ARRAY_SIZE(bitmap_sizes)
+#define NTESTS 2
+
+static void test_size(int nbits)
+{
+	BITMAP_DECLARE(bitmap, nbits);
+	uint32_t marker = 0xdeadbeef;
+	int i, j, k;
+	bool wrong;
+
+	for (i = 0; i < nbits; i++) {
+		for (j = i; j <= nbits; j++) {
+			bitmap_zero(bitmap, nbits);
+			bitmap_fill_range(bitmap, i, j);
+
+			wrong = false;
+			for (k = 0; k < nbits; k++) {
+				bool inrange = (k >= i) && (k < j);
+				wrong = wrong || (bitmap_test_bit(bitmap, k) != inrange);
+			}
+			ok1(!wrong);
+		}
+	}
+
+	for (i = 0; i < nbits; i++) {
+		for (j = i; j <= nbits; j++) {
+			bitmap_fill(bitmap, nbits);
+			bitmap_zero_range(bitmap, i, j);
+
+			wrong = false;
+			for (k = 0; k < nbits; k++) {
+				bool inrange = (k >= i) && (k < j);
+				wrong = wrong || (bitmap_test_bit(bitmap, k) == inrange);
+			}
+			ok1(!wrong);
+		}
+	}
+
+	ok1(marker == 0xdeadbeef);
+}
+
+int main(void)
+{
+	int totaltests = 0;
+	int i;
+
+	for (i = 0; i < NSIZES; i++) {
+		int size = bitmap_sizes[i];
+
+		/* Summing the arithmetic series gives: */
+		totaltests += size*(size + 3) + 1;
+	}
+	plan_tests(totaltests);
+
+	for (i = 0; i < NSIZES; i++) {
+		diag("Testing %d-bit bitmap", bitmap_sizes[i]);
+		test_size(bitmap_sizes[i]);
+	}
+
+	/* This exits depending on whether all tests passed */
+	return exit_status();
+}
diff --git a/ccan/bitmap/test/run.c b/ccan/bitmap/test/run.c
index b67172a5..efd245d7 100644
--- a/ccan/bitmap/test/run.c
+++ b/ccan/bitmap/test/run.c
@@ -3,6 +3,8 @@
 #include <ccan/array_size/array_size.h>
 #include <ccan/foreach/foreach.h>
 
+#include <ccan/bitmap/bitmap.c>
+
 int bitmap_sizes[] = {
 	1, 2, 3, 4, 5, 6, 7, 8,
 	16, 17, 24, 32, 33,