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

Message ID 20141210154909.GA31968@domone
State New
Headers show

Commit Message

Ondřej Bílka Dec. 10, 2014, 3:49 p.m. UTC
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.

Comments

Andreas Schwab Dec. 10, 2014, 4:01 p.m. UTC | #1
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.
Ondřej Bílka Dec. 10, 2014, 4:03 p.m. UTC | #2
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.
Paul Eggert Dec. 11, 2014, 5:39 a.m. UTC | #3
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.
Florian Weimer Dec. 11, 2014, 9:24 a.m. UTC | #4
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.)
Andreas Schwab Dec. 11, 2014, 9:39 a.m. UTC | #5
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.
Anders Kaseorg Dec. 11, 2014, 9:44 a.m. UTC | #6
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
Paul Eggert Dec. 12, 2014, 2:53 a.m. UTC | #7
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....)
Roland McGrath Dec. 12, 2014, 3:39 a.m. UTC | #8
> (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".

Patch
diff mbox

diff --git a/ChangeLog b/ChangeLog
index c2d99a0..bf140d3 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,9 @@ 
+2014-12-10  Anders Kaseorg  <andersk@MIT.EDU>
+
+	[BZ #10672]
+	* manual/search.texi: (Array Sort Function): Remove claim how make
+	qsort stable.
+
 2014-12-10  Andreas Schwab  <schwab@suse.de>
 
 	[BZ #12847]
diff --git a/NEWS b/NEWS
index 7b32c03..4235d37 100644
--- a/NEWS
+++ b/NEWS
@@ -9,12 +9,12 @@  Version 2.21
 
 * The following bugs are resolved with this release:
 
-  6652, 12847, 12926, 13862, 14132, 14138, 14171, 14498, 15215, 15884,
-  16469, 16619, 16740, 16857, 17192, 17266, 17344, 17363, 17370, 17371,
-  17411, 17460, 17475, 17485, 17501, 17506, 17508, 17522, 17555, 17570,
-  17571, 17572, 17573, 17574, 17581, 17582, 17583, 17584, 17585, 17589,
-  17594, 17601, 17608, 17616, 17625, 17633, 17647, 17653, 17664, 17665,
-  17668, 17682.
+  6652, 10672, 12847, 12926, 13862, 14132, 14138, 14171, 14498, 15215,
+  15884, 16469, 16619, 16740, 16857, 17192, 17266, 17344, 17363, 17370,
+  17371, 17411, 17460, 17475, 17485, 17501, 17506, 17508, 17522, 17555,
+  17570, 17571, 17572, 17573, 17574, 17581, 17582, 17583, 17584, 17585,
+  17589, 17594, 17601, 17608, 17616, 17625, 17633, 17647, 17653, 17664,
+  17665, 17668, 17682.
 
 * CVE-2104-7817 The wordexp function could ignore the WRDE_NOCMD flag
   under certain input conditions resulting in the execution of a shell for
diff --git a/manual/search.texi b/manual/search.texi
index 509a543..8aff574 100644
--- a/manual/search.texi
+++ b/manual/search.texi
@@ -180,11 +180,10 @@  This can make a difference when the comparison considers only part of
 the elements.  Two elements with the same sort key may differ in other
 respects.
 
-If you want the effect of a stable sort, you can get this result by
-writing the comparison function so that, lacking other reason
-distinguish between two elements, it compares them by their addresses.
-Note that doing this may make the sorting algorithm less efficient, so
-do it only if necessary.
+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 only way to perform a stable sort with @var{qsort}
+is to first augment the objects with a monotonic counter of some kind.
 
 Here is a simple example of sorting an array of doubles in numerical
 order, using the comparison function defined above (@pxref{Comparison