summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorMartin Mikkelsen <mamikk@mamikk.no>2015-07-31 18:56:35 +0200
committerMartin Mikkelsen <mamikk@mamikk.no>2015-07-31 18:57:13 +0200
commitd5fa81995849cb263ecfcd0aa6ab661360d9213e (patch)
tree467f7d3a045a56d997e17b0a5a5ae69ce5c4cbac
parentaba8a9d1d26cc1cab2ebbeb3f1e557b5a6afdc6b (diff)
bitmap: fix bitmap_equal on bitmaps with unset bits
Given two bitmaps and the following code: Bitmap *a = bitmap_new(), *b = bitmap_new(); bitmap_set(a, 0); bitmap_unset(a, 0); These two bitmaps should now have the same bits set and they should be equal but bitmap_equal() will return false in this case because the bitmaps array in a is larger because of the bit which was previously set. Fix this by comparing only the bits which exists in both bitmaps and then check that the rest of the bits (if any) is all zero. This also adds test code for this issue.
-rw-r--r--src/basic/bitmap.c13
-rw-r--r--src/test/test-bitmap.c12
2 files changed, 22 insertions, 3 deletions
diff --git a/src/basic/bitmap.c b/src/basic/bitmap.c
index bf9d8d4d7c..e7e19b3b66 100644
--- a/src/basic/bitmap.c
+++ b/src/basic/bitmap.c
@@ -184,6 +184,9 @@ bool bitmap_iterate(Bitmap *b, Iterator *i, unsigned *n) {
}
bool bitmap_equal(Bitmap *a, Bitmap *b) {
+ size_t common_n_bitmaps;
+ Bitmap *c;
+ unsigned i;
if (!a ^ !b)
return false;
@@ -191,8 +194,14 @@ bool bitmap_equal(Bitmap *a, Bitmap *b) {
if (!a)
return true;
- if (a->n_bitmaps != b->n_bitmaps)
+ common_n_bitmaps = MIN(a->n_bitmaps, b->n_bitmaps);
+ if (memcmp(a->bitmaps, b->bitmaps, sizeof(uint64_t) * common_n_bitmaps) != 0)
return false;
- return memcmp(a->bitmaps, b->bitmaps, sizeof(uint64_t) * a->n_bitmaps) == 0;
+ c = a->n_bitmaps > b->n_bitmaps ? a : b;
+ for (i = common_n_bitmaps; i < c->n_bitmaps; i++)
+ if (c->bitmaps[i] != 0)
+ return false;
+
+ return true;
}
diff --git a/src/test/test-bitmap.c b/src/test/test-bitmap.c
index 96deeded7e..cb9e4a41f6 100644
--- a/src/test/test-bitmap.c
+++ b/src/test/test-bitmap.c
@@ -20,7 +20,7 @@
#include "bitmap.h"
int main(int argc, const char *argv[]) {
- _cleanup_bitmap_free_ Bitmap *b = NULL;
+ _cleanup_bitmap_free_ Bitmap *b = NULL, *b2 = NULL;
Iterator it;
unsigned n = (unsigned) -1, i = 0;
@@ -101,5 +101,15 @@ int main(int argc, const char *argv[]) {
assert_se(bitmap_set(b, (unsigned) -1) == -ERANGE);
+ bitmap_free(b);
+ b = NULL;
+ assert_se(bitmap_ensure_allocated(&b) == 0);
+ assert_se(bitmap_ensure_allocated(&b2) == 0);
+
+ assert_se(bitmap_equal(b, b2));
+ assert_se(bitmap_set(b, 0) == 0);
+ bitmap_unset(b, 0);
+ assert_se(bitmap_equal(b, b2));
+
return 0;
}