diff options
| author | Anders Kaseorg <andersk@MIT.EDU> | 2014-07-02 21:17:50 -0400 |
|---|---|---|
| committer | Ondřej Bílka <neleai@seznam.cz> | 2014-12-10 16:24:44 +0100 |
| commit | f5f46d51f75083e27fae79cee6cd7707888faba3 (patch) | |
| tree | 5a31623e034dfa63c27d713ec8b189e380cde710 | |
| parent | b987c89126b84b06c22b13c2827499bc9d9e5e88 (diff) | |
| download | glibc-f5f46d51f75083e27fae79cee6cd7707888faba3.zip glibc-f5f46d51f75083e27fae79cee6cd7707888faba3.tar.gz glibc-f5f46d51f75083e27fae79cee6cd7707888faba3.tar.bz2 | |
manual: Remove incorrect claim that qsort() can be stabilized
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>
| -rw-r--r-- | ChangeLog | 6 | ||||
| -rw-r--r-- | NEWS | 12 | ||||
| -rw-r--r-- | manual/search.texi | 9 |
3 files changed, 16 insertions, 11 deletions
@@ -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 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 |