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: Anders Kaseorg <andersk at mit dot edu>
- To: Rich Felker <dalias at libc dot org>
- 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 18:00:18 -0500 (EST)
- 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> <20141211162802 dot GV4574 at brightrain dot aerifal dot cx>
On Thu, 11 Dec 2014, Rich Felker wrote:
> > -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.
Note that the second sentence is unchanged in this patch. The goal of
this patch is to fix an incorrect claim in the first sentence.
> 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,
Thatâs just another way to augment the objects with a monotonic counter,
where the monotonic counter is the address.
> 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).
And this means using an additional nontrivial algorithm outside of qsort.
So Iâm not sure it counts as a way to âperform a stable sort with
@var{qsort}â.
Anyway, the reason the second sentence is there at all is to explicitly
contradict an incorrect recipe for stable qsort in previous versions of
the manual (https://sourceware.org/bugzilla/show_bug.cgi?id=10672). If
you imagine youâre a programmer who wants to do a stable sort, and search
the web for related keywords, you find the current version of the manual
http://www.gnu.org/software/libc/manual/html_node/Array-Sort-Function.html
(which actually still contains that incorrect claim, but will be fixed
with the next release), along with some previous versions of the manual
(which will probably never be updated). So I think itâs important that
the current version lets the programmer easily decide that the previous
version was wrong.
If youâd still like the second sentence changed, can I suggest doing it in
a separate patch?
Anders