diff options
| author | Anders Kaseorg <andersk@mit.edu> | 2014-12-11 05:33:22 -0500 |
|---|---|---|
| committer | Ondřej Bílka <neleai@seznam.cz> | 2014-12-21 14:11:32 +0100 |
| commit | 98fe149e34b48d0c4d69105315cc7c61be8276ec (patch) | |
| tree | eac01d656ff527b54d875ff963a6014949884813 | |
| parent | d12455f59679faee885809258ae4f10449b1f2cf (diff) | |
| download | glibc-98fe149e34b48d0c4d69105315cc7c61be8276ec.tar.gz glibc-98fe149e34b48d0c4d69105315cc7c61be8276ec.tar.xz glibc-98fe149e34b48d0c4d69105315cc7c61be8276ec.zip | |
manual: Correct guarantee about pointers compared by qsort()
C99, C11, POSIX, and the glibc implementation do guarantee that the pointers passed to the qsort comparison function lie within the array. Signed-off-by: Anders Kaseorg <andersk@mit.edu>
| -rw-r--r-- | ChangeLog | 5 | ||||
| -rw-r--r-- | manual/search.texi | 14 |
2 files changed, 13 insertions, 6 deletions
diff --git a/ChangeLog b/ChangeLog index 642f84dcb0..eaaff71555 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,8 @@ +2014-12-21 Anders Kaseorg <andersk@mit.edu> + + * manual/search.texi: (Array Sort Function): Clarify stable sorting + guarantees. + 2014-12-20 Chris Metcalf <cmetcalf@ezchip.com> * sysdeps/unix/sysv/linux/tile/localplt.data: New file. diff --git a/manual/search.texi b/manual/search.texi index 8aff57433a..662527f813 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 |