---
lib/bitmap.c | 36 ++++++++++++++++++++++++------------
1 file changed, 24 insertions(+), 12 deletions(-)
diff --git a/lib/bitmap.c b/lib/bitmap.c
index 7889aa1..b62a8be 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -65,16 +65,17 @@ bool
bitmap_equal(const unsigned long *a, const unsigned long *b, size_t n)
{
size_t i;
+ unsigned long mask = 1;
if (memcmp(a, b, n / BITMAP_ULONG_BITS * sizeof(unsigned long))) {
return false;
}
- for (i = ROUND_DOWN(n, BITMAP_ULONG_BITS); i < n; i++) {
- if (bitmap_is_set(a, i) != bitmap_is_set(b, i)) {
- return false;
- }
- }
- return true;
+
+ i = bitmap_n_longs(n);
+ mask <<= n % BITMAP_ULONG_BITS;
+ mask -= 1;
+
+ return !mask || !((a[i] ^ b[i]) & mask);
}
/* Scans 'bitmap' from bit offset 'start' to 'end', excluding 'end' itself.
@@ -84,15 +85,26 @@ size_t
bitmap_scan(const unsigned long int *bitmap, bool target,
size_t start, size_t end)
{
- /* XXX slow */
- size_t i;
-
- for (i = start; i < end; i++) {
- if (bitmap_is_set(bitmap, i) == target) {
+ size_t count = end - start;
+ unsigned long t = -(unsigned long)(!target);
+ for (; count && start % BITMAP_ULONG_BITS; count--,start++) {
+ if (bitmap_is_set(bitmap, start) == target) {
+ return start;
+ }
+ }
+ for (; count >= BITMAP_ULONG_BITS; count -= BITMAP_ULONG_BITS) {
+ if (*bitmap_unit__(bitmap, start) != t) {
break;
}
+ start += BITMAP_ULONG_BITS;
+ }
+ for (; count; count--,start++) {
+ if (bitmap_is_set(bitmap, start) == target) {
+ return start;
+ }
}
- return i;
+
+ return start;
}
/* Returns the number of 1-bits in the 'n'-bit bitmap at 'bitmap'. */
--
2.0.3
_______________________________________________
dev mailing list
[email protected]
http://openvswitch.org/mailman/listinfo/dev
