summaryrefslogtreecommitdiff
path: root/ewah
diff options
context:
space:
mode:
Diffstat (limited to 'ewah')
-rw-r--r--ewah/bitmap.c54
-rw-r--r--ewah/ewah_bitmap.c15
-rw-r--r--ewah/ewok.h3
3 files changed, 52 insertions, 20 deletions
diff --git a/ewah/bitmap.c b/ewah/bitmap.c
index d8cec585af..0d31cdc866 100644
--- a/ewah/bitmap.c
+++ b/ewah/bitmap.c
@@ -35,18 +35,26 @@ struct bitmap *bitmap_new(void)
return bitmap_word_alloc(32);
}
+struct bitmap *bitmap_dup(const struct bitmap *src)
+{
+ struct bitmap *dst = bitmap_word_alloc(src->word_alloc);
+ COPY_ARRAY(dst->words, src->words, src->word_alloc);
+ return dst;
+}
+
+static void bitmap_grow(struct bitmap *self, size_t word_alloc)
+{
+ size_t old_size = self->word_alloc;
+ ALLOC_GROW(self->words, word_alloc, self->word_alloc);
+ memset(self->words + old_size, 0x0,
+ (self->word_alloc - old_size) * sizeof(eword_t));
+}
+
void bitmap_set(struct bitmap *self, size_t pos)
{
size_t block = EWAH_BLOCK(pos);
- if (block >= self->word_alloc) {
- size_t old_size = self->word_alloc;
- self->word_alloc = block ? block * 2 : 1;
- REALLOC_ARRAY(self->words, self->word_alloc);
- memset(self->words + old_size, 0x0,
- (self->word_alloc - old_size) * sizeof(eword_t));
- }
-
+ bitmap_grow(self, block + 1);
self->words[block] |= EWAH_MASK(pos);
}
@@ -121,6 +129,15 @@ void bitmap_and_not(struct bitmap *self, struct bitmap *other)
self->words[i] &= ~other->words[i];
}
+void bitmap_or(struct bitmap *self, const struct bitmap *other)
+{
+ size_t i;
+
+ bitmap_grow(self, other->word_alloc);
+ for (i = 0; i < other->word_alloc; i++)
+ self->words[i] |= other->words[i];
+}
+
void bitmap_or_ewah(struct bitmap *self, struct ewah_bitmap *other)
{
size_t original_size = self->word_alloc;
@@ -178,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/ewah_bitmap.c b/ewah/ewah_bitmap.c
index d59b1afe3d..2a8c7c5c33 100644
--- a/ewah/ewah_bitmap.c
+++ b/ewah/ewah_bitmap.c
@@ -19,6 +19,7 @@
#include "git-compat-util.h"
#include "ewok.h"
#include "ewok_rlw.h"
+#include "cache.h"
static inline size_t min_size(size_t a, size_t b)
{
@@ -33,20 +34,13 @@ static inline size_t max_size(size_t a, size_t b)
static inline void buffer_grow(struct ewah_bitmap *self, size_t new_size)
{
size_t rlw_offset = (uint8_t *)self->rlw - (uint8_t *)self->buffer;
-
- if (self->alloc_size >= new_size)
- return;
-
- self->alloc_size = new_size;
- REALLOC_ARRAY(self->buffer, self->alloc_size);
+ ALLOC_GROW(self->buffer, new_size, self->alloc_size);
self->rlw = self->buffer + (rlw_offset / sizeof(eword_t));
}
static inline void buffer_push(struct ewah_bitmap *self, eword_t value)
{
- if (self->buffer_size + 1 >= self->alloc_size)
- buffer_grow(self, self->buffer_size * 3 / 2);
-
+ buffer_grow(self, self->buffer_size + 1);
self->buffer[self->buffer_size++] = value;
}
@@ -137,8 +131,7 @@ void ewah_add_dirty_words(
rlw_set_literal_words(self->rlw, literals + can_add);
- if (self->buffer_size + can_add >= self->alloc_size)
- buffer_grow(self, (self->buffer_size + can_add) * 3 / 2);
+ buffer_grow(self, self->buffer_size + can_add);
if (negate) {
size_t i;
diff --git a/ewah/ewok.h b/ewah/ewok.h
index 011852bef1..66920965da 100644
--- a/ewah/ewok.h
+++ b/ewah/ewok.h
@@ -173,13 +173,14 @@ struct bitmap {
struct bitmap *bitmap_new(void);
struct bitmap *bitmap_word_alloc(size_t word_alloc);
+struct bitmap *bitmap_dup(const struct bitmap *src);
void bitmap_set(struct bitmap *self, size_t pos);
void bitmap_unset(struct bitmap *self, size_t pos);
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);