This is the mail archive of the 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]

Re: [PATCH] manual: Correct guarantee about pointers compared by qsort()

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

"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).


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