Subject: Re: [PATCH v3 10/13] ewah: implement `struct ewah_or_iterator`

From: Taylor Blau <[email-masked]>
Date: Fri, 28 Feb 2025 19:22:06 -0500

On Fri, Feb 28, 2025 at 11:01:30AM +0100, Patrick Steinhardt wrote:
> On Tue, Nov 19, 2024 at 05:07:47PM -0500, Taylor Blau wrote:
> > diff --git a/ewah/ewah_bitmap.c b/ewah/ewah_bitmap.c
> > index 8785cbc54a8..b3a7ada0714 100644
> > --- a/ewah/ewah_bitmap.c
> > +++ b/ewah/ewah_bitmap.c
> > @@ -372,6 +372,39 @@ void ewah_iterator_init(struct ewah_iterator *it, struct ewah_bitmap *parent)
> >  		read_new_rlw(it);
> >  }
> >
> > +void ewah_or_iterator_init(struct ewah_or_iterator *it,
> > +			   struct ewah_bitmap **parents, size_t nr)
> > +{
> > +	size_t i;
> > +
> > +	memset(it, 0, sizeof(*it));
> > +
> > +	ALLOC_ARRAY(it->its, nr);
> > +	for (i = 0; i < nr; i++)
> > +		ewah_iterator_init(&it->its[it->nr++], parents[i]);
> > +}
> > +
> > +int ewah_or_iterator_next(eword_t *next, struct ewah_or_iterator *it)
> > +{
> > +	eword_t buf, out = 0;
> > +	size_t i;
> > +	int ret = 0;
> > +
> > +	for (i = 0; i < it->nr; i++)
> > +		if (ewah_iterator_next(&buf, &it->its[i])) {
> > +			out |= buf;
> > +			ret = 1;
> > +		}
> > +
> > +	*next = out;
> > +	return ret;
> > +}
>
> Yup, this looks rather straight-forward: we advance each of our
> subiterators and or their respective results into the accumulated result
> that we end up returning to the user.
>
> One thing that surprised me though is that we don't seem to be able to
> tell whether all of the iterators could be moved on to the next result
> or not. But I guess that makes sense: iterators of lower levels will
> cover less objects and will thus eventually be exhausted before the
> iterators on the higher levels.

Exactly. Conceptually each iterator ends with an infinite number of
zero'd bits, and indeed they are expected to be different lengths for
the reason you mention.

> > +void ewah_or_iterator_free(struct ewah_or_iterator *it)
> > +{
> > +	free(it->its);
> > +}
> > +
>
> This should be called `ewar_or_iterator_release()` because we don't
> releate `it`, as documented by our style guide.

Great call, thanks.

Thanks,
Taylor