This is the mail archive of the libc-alpha@sourceware.org mailing list for the glibc project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[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.


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


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]