[v2] manual: Correct guarantee about pointers compared by qsort()
diff mbox

Message ID alpine.DEB.2.10.1412110532540.37899@buzzword-bingo.mit.edu
State New
Headers show

Commit Message

Anders Kaseorg Dec. 11, 2014, 10:33 a.m. UTC
C99, C11, POSIX, and the glibc implementation do guarantee that the
pointers passed to the qsort comparison function lie within the array.

(Also, fix a small typographical mistake: @var{qsort} should be
@code{qsort}.)

Signed-off-by: Anders Kaseorg <andersk@mit.edu>
---
 manual/search.texi | 14 ++++++++------
 1 file changed, 8 insertions(+), 6 deletions(-)

Comments

Jonathan Nieder Dec. 12, 2014, 8:26 a.m. UTC | #1
Anders Kaseorg wrote:

> C99, C11, POSIX, and the glibc implementation do guarantee that the
> pointers passed to the qsort comparison function lie within the array.
>
> (Also, fix a small typographical mistake: @var{qsort} should be
> @code{qsort}.)
>
> Signed-off-by: Anders Kaseorg <andersk@mit.edu>
> ---
>  manual/search.texi | 14 ++++++++------
>  1 file changed, 8 insertions(+), 6 deletions(-)

For what it's worth,
Reviewed-by: Jonathan Nieder <jrnieder@gmail.com>
Ondřej Bílka Dec. 21, 2014, 1:13 p.m. UTC | #2
On Thu, Dec 11, 2014 at 05:33:22AM -0500, Anders Kaseorg wrote:
> C99, C11, POSIX, and the glibc implementation do guarantee that the
> pointers passed to the qsort comparison function lie within the array.
> 
> (Also, fix a small typographical mistake: @var{qsort} should be
> @code{qsort}.)
> 
ok, I commited this addendum.

Patch
diff mbox

diff --git a/manual/search.texi b/manual/search.texi
index 8aff574..662527f 100644
--- a/manual/search.texi
+++ b/manual/search.texi
@@ -164,8 +164,8 @@  To sort an array using an arbitrary comparison function, use the
 @comment ISO
 @deftypefun void qsort (void *@var{array}, size_t @var{count}, size_t @var{size}, comparison_fn_t @var{compare})
 @safety{@prelim{}@mtsafe{}@assafe{}@acunsafe{@acucorrupt{}}}
-The @var{qsort} function sorts the array @var{array}.  The array contains
-@var{count} elements, each of which is of size @var{size}.
+The @code{qsort} function sorts the array @var{array}.  The array
+contains @var{count} elements, each of which is of size @var{size}.
 
 The @var{compare} function is used to perform the comparison on the
 array elements.  This function is called with two pointer arguments and
@@ -180,10 +180,12 @@  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.
 
-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.
+Although the object addresses passed to the comparison function lie
+within the array, they need not correspond with the original locations
+of those objects because the sorting algorithm may swap around objects
+in the array before making some comparisons.  The only way to perform
+a stable sort with @code{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