bug-gnulib
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: mgetgroups improvements


From: Eric Blake
Subject: Re: mgetgroups improvements
Date: Fri, 04 Dec 2009 18:58:13 -0700
User-agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.8.1.23) Gecko/20090812 Thunderbird/2.0.0.23 Mnenhy/0.7.6.666

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

According to Pádraig Brady on 12/4/2009 6:20 PM:
>> +  /* 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?

Yes, for two reasons.  One, we pre-insert an arbitrary gid_t to the front
of the array (generally the effective gid), often on the assumption that
we don't know whether the effective gid will occur in the supplementary
group but we want it to be in the final set.  Two, some OS's actually list
the effective gid twice, once at the front, and once in its location
within the supplementary gid list, even if we don't insert the effective
gid.  In the degenerate case of belonging to only one group on FreeBSD
6.2, getgroups(0,NULL) returns 2, and getgroups(2,array) returns the same
element twice.  But if you belong to more than one group, then the first
element returned by getgroups may be in an arbitrary position in the rest
of the array.

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

No.  The array is indexed from 0, so last is one past the end of the
array.  The iteration over next starts at element 1 (if there are at least
two elements), because we trivially know that element 0 is equal to element 0.

- --
Don't work too hard, make some time for fun as well!

Eric Blake             address@hidden
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (Cygwin)
Comment: Public key at home.comcast.net/~ericblake/eblake.gpg
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAksZvjQACgkQ84KuGfSFAYCN+wCgwZN+xdkWIoiN38Yib9Tnjmrg
SdsAnRqdHj4fvEZi3PCq98jKg4kotf8C
=FX8n
-----END PGP SIGNATURE-----




reply via email to

[Prev in Thread] Current Thread [Next in Thread]