Re: [PATCH 03/10] sha1-array: provide oid_array_remove_if

From: Jeff King <peff@peff.net>
Date: Aug 9, 2018, 19:24 UTC
Message-ID: <20180809192454.GB32376@sigill.intra.peff.net>
In-Reply-To: <CAGZ79kYtKZJ0Dm0ejxrotnoaNERtR0J6=DMCgweCObdJr0K6-w@mail.gmail.com>

On Thu, Aug 09, 2018 at 10:25:52AM -0700, Stefan Beller wrote:

Show 13 quoted lines

> On Thu, Aug 9, 2018 at 12:39 AM Martin Ågren <martin.agren@gmail.com> wrote:
> >
> > On 9 August 2018 at 00:17, Stefan Beller <sbeller@google.com> wrote:
> > > +int oid_array_remove_if(struct oid_array *array,
> > > +                       for_each_oid_fn fn,
> > > +                       void *data)
> > > +{
> > > +       int i, j;
> > > +       char *to_remove = xcalloc(array->nr, sizeof(char));
> >
> > Do you really need this scratch space?
> 
> I don't think so, when we reorder the items while iterating over them.

Even with keeping the order this can be done in a single linear pass. See filter_string_list() for an example.

The one twist here is that you cannot:

  oidcpy(array->oid[i], array->oid[j]);

when i==j, because of memcpy restrictions. With the current implementation it would suffice to use struct assignment (and really, every oidcpy() could just be struct assignment these days). But you could also just do:

  if (i != j)
    oidcpy(array->oid[i], array->oid[j]);

Show 7 quoted lines

> > I can't entirely follow this index-fiddling, but then I haven't had my
> > morning coffee yet, so please forgive me if this is nonsense. Would it
> > suffice to let i point out where to place items (starting at the first
> > item not to keep) and j where to take them from (i.e., the items to
> > keep, after the initial run)?
> 
> I thought this is what happens, just after the actual loop of calls.

I think the point is that we can just maintain those meanings during the single walk through the array. The result is simpler to read and more efficient.

-Peff