This is the mail archive of the
libc-alpha@sourceware.org
mailing list for the glibc project.
Re: [PATCH] manual: Correct guarantee about pointers compared by qsort()
- From: Rich Felker <dalias at libc dot org>
- To: Anders Kaseorg <andersk at mit dot edu>
- Cc: Andreas Schwab <schwab at suse dot de>, Paul Eggert <eggert at cs dot ucla dot edu>, OndÅej BÃlka <neleai at seznam dot cz>, Florian Weimer <fweimer at redhat dot com>, libc-alpha at sourceware dot org
- Date: Thu, 11 Dec 2014 11:28:02 -0500
- Subject: Re: [PATCH] manual: Correct guarantee about pointers compared by qsort()
- Authentication-results: sourceware.org; auth=none
- References: <alpine dot DEB dot 2 dot 02 dot 1407022115210 dot 28890 at all-night-tool dot MIT dot EDU> <20141210154909 dot GA31968 at domone> <54892DF9 dot 8080007 at cs dot ucla dot edu> <mvmmw6ur0d5 dot fsf at hawking dot suse dot de> <alpine dot DEB dot 2 dot 10 dot 1412110443010 dot 37899 at buzzword-bingo dot mit dot edu> <alpine dot DEB dot 2 dot 10 dot 1412110456190 dot 37899 at buzzword-bingo dot mit dot edu>
On Thu, Dec 11, 2014 at 04:57:42AM -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.
>
> Signed-off-by: Anders Kaseorg <andersk@mit.edu>
> ---
> manual/search.texi | 10 ++++++----
> 1 file changed, 6 insertions(+), 4 deletions(-)
>
> diff --git a/manual/search.texi b/manual/search.texi
> index 8aff574..9ebcb68 100644
> --- a/manual/search.texi
> +++ b/manual/search.texi
> @@ -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 @var{qsort} is to first augment the objects
> +with a monotonic counter of some kind.
I think "the only way" is mistaken. I would simply add to the previous
sentence:
"and therefore, the addresses of the objects may not be used as part
of the comparison for producing a stable sort"
or similar. If the next sentence is also desired, it could say "One
way", or "The canonical way" rather than "The only way". Note that
another way, often optimal in time anyway due to the smaller amount of
data to be moved, is to create a new array of pointers to objects in
the original array. Then the array of pointers can be sorted using the
address (not the address of the pointer, but the address stored in the
pointer) as a factor, and then the objects in the original array can
be moved into the resulting order if desired (often it's not needed to
do so anyway).
Rich