[COMMITED,v2] manual: Remove incorrect claim that qsort() can be stabilized
Commit Message
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
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".
@@ -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]
@@ -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
@@ -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