[COMMITED,v2] manual: Remove incorrect claim that qsort() can be stabilized

On Wed, Jul 02, 2014 at 09:17:50PM -0400, Anders Kaseorg wrote:
> Under certain conditions on the size of the array and its items,
> qsort() may fall back to an in-place quicksort if it cannot allocate
> memory for a temporary array with malloc().  This algorithm is not a
> stable sort even if the comparison function is written in the
> described manner.
> 
> Fixes #10672.
> 
> Signed-off-by: Anders Kaseorg <andersk@mit.edu>
> 
> ---
> On Tue, 1 Jul 2014, Florian Weimer wrote:
> > I would suggest to remove the entire paragraph instead, or perhaps a warning
> > that the pointers with which the comparison function is called do not
> > necessarily have to reside within the input array.
> 
> What do you think about this wording, then?  (The problem is not actually 
> about pointers residing outside the input array, because it happens that 
> the algorithm where that occurs is stable.  But I agree it’s worth 
> mentioning too.)
> 
As it looks ok now I commited it with changelog and NEWS entry.

Ondřej Bílka <neleai@seznam.cz> writes:

> +	[BZ #10672]
> +	* manual/search.texi: (Array Sort Function): Remove claim how make

s/how make/how to make/

Andreas.

On Wed, Dec 10, 2014 at 05:01:40PM +0100, Andreas Schwab wrote:
> Ondřej Bílka <neleai@seznam.cz> writes:
> 
> > +	[BZ #10672]
> > +	* manual/search.texi: (Array Sort Function): Remove claim how make
> 
> s/how make/how to make/
> 
Fixed, thanks.

Ondřej Bílka wrote:
> +The addresses passed to the comparison function need not correspond with
> +the original location of the objects, and need not even lie within the
> +original array.

The last clause is incorrect.  C11 and POSIX both require that the addresses 
passed to the comparison function must point to elements of the original array, 
and glibc qsort conforms to the standards here.  Please fix this.

On 12/11/2014 06:39 AM, Paul Eggert wrote:
> Ondřej Bílka wrote:
>> +The addresses passed to the comparison function need not correspond with
>> +the original location of the objects, and need not even lie within the
>> +original array.
>
> The last clause is incorrect.  C11 and POSIX both require that the
> addresses passed to the comparison function must point to elements of
> the original array, and glibc qsort conforms to the standards here.

Ugh, that's a new requirement in C99, isn't it?

(Although the expressions which are required to evaluate to true do not 
evaluate to false if the element lies outside the array being compared 
because they are simply undefined.)

Paul Eggert <eggert@cs.ucla.edu> writes:

> The last clause is incorrect.  C11 and POSIX both require that the
> addresses passed to the comparison function must point to elements of the
> original array, and glibc qsort conforms to the standards here.

That is only true for bsearch:

    "The comparison function pointed to by compar is called with two
    arguments that point to the key object and to an array element, in
    that order."

The description for qsort does not say that:

    "The contents of the array are sorted into ascending order according
    to a comparison function pointed to by compar, which is called with
    two arguments that point to the objects being compared."

Andreas.

On Thu, 11 Dec 2014, Andreas Schwab wrote:
> Paul Eggert <eggert@cs.ucla.edu> writes:
> 
> > The last clause is incorrect.  C11 and POSIX both require that the
> > addresses passed to the comparison function must point to elements of the
> > original array, and glibc qsort conforms to the standards here.
> 
> That is only true for bsearch:
> 
>     "The comparison function pointed to by compar is called with two
>     arguments that point to the key object and to an array element, in
>     that order."
> 
> The description for qsort does not say that:
> 
>     "The contents of the array are sorted into ascending order according
>     to a comparison function pointed to by compar, which is called with
>     two arguments that point to the objects being compared."

No, Paul is right, see C99 §7.20.5/C11 §7.22.5, outside of the main 
description for qsort:

“The implementation shall ensure that the second argument of the 
comparison function (when called from bsearch), or both arguments (when 
called from qsort), are pointers to elements of the array.”

Anders

Florian Weimer wrote:
> Ugh, that's a new requirement in C99, isn't it?

Yes, this qsort requirement wasn't in C89.

(Though I wouldn't call it "new".  Many people I work with were in kindergarten 
when C99 came out....)

> (Though I wouldn't call it "new".  Many people I work with were in kindergarten 
> when C99 came out....)

The term you're looking for is "newfangled".  
And the other one is "whippersnappers".