Re: [PATCH v2 13/24] bitmap: add bitmap_diff_nonzero()

From: Junio C Hamano <gitster@pobox.com>
Date: Nov 22, 2020, 22:01 UTC
Message-ID: <xmqqtuthoxu6.fsf@gitster.c.googlers.com>
In-Reply-To: <4840c64c51d65ea7bf1ebe03cad4588267db0207.1605649533.git.me@ttaylorr.com>

Taylor Blau <me@ttaylorr.com> writes:

> From: Derrick Stolee <dstolee@microsoft.com>
>
> The bitmap_diff_nonzero() checks if the 'self' bitmap contains any bits
> that are not on in the 'other' bitmap.

In other words, it yields false if and only if self is a subset of other? I have to say that "diff_nonzero" is much less helpful than words like "subset" or "superset" when I try to imagine what the function would compute.

If this were widely used helper function, I may insist on flipping the polarity and call it bitmap_is_subset(), but I dunno...

> Also, delete the declaration of bitmap_is_subset() as it is not used or
> implemented.

;-)

Show 18 quoted lines

> Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
> Signed-off-by: Taylor Blau <me@ttaylorr.com>
> ---
>  ewah/bitmap.c | 24 ++++++++++++++++++++++++
>  ewah/ewok.h   |  2 +-
>  2 files changed, 25 insertions(+), 1 deletion(-)
>
> diff --git a/ewah/bitmap.c b/ewah/bitmap.c
> index eb7e2539be..e2ebeac0e5 100644
> --- a/ewah/bitmap.c
> +++ b/ewah/bitmap.c
> @@ -200,6 +200,30 @@ int bitmap_equals(struct bitmap *self, struct bitmap *other)
>  	return 1;
>  }
>  
> +int bitmap_diff_nonzero(struct bitmap *self, struct bitmap *other)
> +{
> +	struct bitmap *small;

It is not wrong per-se, but s/small/smaller/ would be more natural?

I actually think it would be easier to follow the logic to replace this pointer with

	size_t common_size;

Then the code becomes

	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])
				... self is *not* subset ...
	}

	for (i = 0; i < common_size; i++)
		if (self->words[i] & ~other->words[i]))
			... self is *not* subset ...

Show 37 quoted lines

> +	size_t i;
> +
> +	if (self->word_alloc < other->word_alloc) {
> +		small = self;
> +	} else {
> +		small = other;
> +
> +		for (i = other->word_alloc; i < self->word_alloc; i++) {
> +			if (self->words[i] != 0)
> +				return 1;
> +		}
> +	}
> +
> +	for (i = 0; i < small->word_alloc; 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 1fc555e672..156c71d06d 100644
> --- 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_diff_nonzero(struct bitmap *self, struct bitmap *other);
>  
>  struct ewah_bitmap * bitmap_to_ewah(struct bitmap *bitmap);
>  struct bitmap *ewah_to_bitmap(struct ewah_bitmap *ewah);