Re: [RFC PATCH 04/10] ewah/bitmap: always allocate 2 more words

From: Jonathan Tan <jonathantanmy@google.com>
Date: Oct 10, 2019, 23:40 UTC
Message-ID: <20191010234040.168894-1-jonathantanmy@google.com>
In-Reply-To: <20190913130226.7449-5-chriscool@tuxfamily.org>

Show 7 quoted lines

> From: Jeff King <peff@peff.net>
> 
> In a following patch we will allocate a variable number
> of words in some bitmaps. When iterating over the words we
> will need a mark to tell us when to stop iterating. Let's
> always allocate 2 more words, that will always contain 0,
> as that mark.

[snip]

Show 7 quoted lines

>  	if (block >= self->word_alloc) {
>  		size_t old_size = self->word_alloc;
> -		self->word_alloc = block * 2;
> +		self->word_alloc = (block + 1) * 2;
>  		REALLOC_ARRAY(self->words, self->word_alloc);
>  		memset(self->words + old_size, 0x0,
>  			(self->word_alloc - old_size) * sizeof(eword_t));

This patch set was mentioned as needing more thorough review in "What's Cooking" [1], so I thought I'd give it a try. As Peff said [2], the justification in the commit message looks incorrect. He suggests that it is most likely because "block" might be 0 (which is possible because a previous patch eliminated the minimum of 32), which makes sense to me.

In any case, the next patch does not use 0 as a sentinel mark. Iteration stops when word_alloc is reached anyway, and since this is a regular bitmap, 0 is a valid word and cannot be used as a sentinel. (Maybe 0 is a valid word in a compressed EWAH bitmap too...not sure about that.)

I think this should be squashed with patch 3, adding to that commit message "since word_alloc might be 0, we need to change the growth function". (Or just make the minimum word_alloc be 1 or 32 or something positive, if that's possible.)

[1] https://public-inbox.org/git/xmqq36g5444k.fsf@gitster-ct.c.googlers.com/ [2] https://public-inbox.org/git/20191002155721.GD6116@sigill.intra.peff.net/