Re: mgetgroups improvements

[Pádraig Brady]

Eric Blake wrote:
> The first was a bug I introduced when moving mgetgroups from coreutils to 
> gnulib (comparing a gid_t with -1 will fail on platforms where gid_t is 
> uint16_t; the coreutils version only used the gid argument in the getugroups 
> case, so the bug came from my new code for the getgroups case).  I didn't 
> notice it earlier because cygwin has 32-bit gid_t.  The second of these was 
> already proposed on the coreutils list, but has been further tweaked to fix 
> minor issues I've spotted during a re-review of the patch.

These look good.

> And the third is 
> something I've previously talked about, which makes mgetgroups easier to use 
> by 
> avoiding obvious duplicates with no degredation in scaling effects.
> 
> Duplicates can still exist depending on the OS implementation of getgroups

I'm not sure it's worth adding code to remove duplicates
if we can't guarantee they're all removed.
The average case and max case N would be pretty low I think,
and perhaps one could tune the algorithm for nearly sorted data?

> +  /* Remove pair-wise duplicates, as well as any duplicate of the
? +     first element.  Rather than do a full O(n log n) duplicate
> +     removal, this only visits the most common duplicates.  */

Why does the first element get extra checks.
Is it more likely to be duplicated?

> +  {
> +    gid_t first = *g;
> +    gid_t *next;
> +    gid_t *last = g + ng;
> +
> +    for (next = g + 1; next < last; next++)

Should that be <=

> +      {
> +        if (*next == first || *next == *g)
> +          ng--;
> +        else
> +          *++g = *next;
> +      }
> +  }


cheers,
Pádraig.