bitmap: implement bitmap_is_subset()

The bitmap_is_subset() function checks if the 'self' bitmap contains any
bitmaps that are not on in the 'other' bitmap. Up until this patch, it
had a declaration, but no implementation or callers. A subsequent patch
will want this function, so implement it here.

Helped-by: Junio C Hamano <gitster@pobox.com>
Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
Signed-off-by: Taylor Blau <me@ttaylorr.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

diff --git a/ewah/bitmap.c b/ewah/bitmap.c
index b5f63762824fa356d9a5f55f1cfc7959904d16fd..0d31cdc866c77dfaab69b39305213497c49a120d 100644 (file)
--- a/ewah/bitmap.c
+++ b/ewah/bitmap.c
@@ -195,6 +195,27 @@ int bitmap_equals(struct bitmap *self, struct bitmap *other)
        return 1;
 }
 
+int bitmap_is_subset(struct bitmap *self, struct bitmap *other)
+{
+       size_t common_size, i;
+
+       if (self->word_alloc < other->word_alloc)
+               common_size = self->word_alloc;
+       else {
+               common_size = other->word_alloc;
+               for (i = common_size; i < self->word_alloc; i++) {
+                       if (self->words[i])
+                               return 1;
+               }
+       }
+
+       for (i = 0; i < common_size; i++) {
+               if (self->words[i] & ~other->words[i])
+                       return 1;
+       }
+       return 0;
+}
+
 void bitmap_reset(struct bitmap *bitmap)
 {
        memset(bitmap->words, 0x0, bitmap->word_alloc * sizeof(eword_t));

diff --git a/ewah/ewok.h b/ewah/ewok.h
index 1fc555e6728603136f3098fd8aa5f51338313dea..66920965da19ab4a38db18d1b18e0f5fbaa4776f 100644 (file)
--- a/ewah/ewok.h
+++ b/ewah/ewok.h
@@ -180,7 +180,7 @@ int bitmap_get(struct bitmap *self, size_t pos);
 void bitmap_reset(struct bitmap *self);
 void bitmap_free(struct bitmap *self);
 int bitmap_equals(struct bitmap *self, struct bitmap *other);
-int bitmap_is_subset(struct bitmap *self, struct bitmap *super);
+int bitmap_is_subset(struct bitmap *self, struct bitmap *other);
 
 struct ewah_bitmap * bitmap_to_ewah(struct bitmap *bitmap);
 struct bitmap *ewah_to_bitmap(struct ewah_bitmap *ewah);