From: Hans-Bernhard Broeker <broeker AT acp3bf DOT physik DOT rwth-aachen DOT de>
Newsgroups: comp.os.msdos.djgpp
Subject: Re: qsort() bug?  Or invalid usage???
Date: 21 Jan 2000 18:06:02 GMT
Organization: Aachen University of Technology (RWTH)
Lines: 55
Message-ID: <86a76a$nro$1@nets3.rz.RWTH-Aachen.DE>
References: <R0Gh4.2371$Ll5 DOT 3502 AT news2 DOT randori DOT com> <867gpd$k0u$1 AT nets3 DOT rz DOT RWTH-Aachen DOT DE> <388758A7 DOT 1B64BDF9 AT cyberoptics DOT com> <388824A4 DOT 7E8CA268 AT is DOT elta DOT co DOT il> <869q6i$ika$1 AT nets3 DOT rz DOT RWTH-Aachen DOT DE> <38887BFB DOT 2D3FA7A6 AT cyberoptics DOT com>
NNTP-Posting-Host: acp3bf.physik.rwth-aachen.de
X-Trace: nets3.rz.RWTH-Aachen.DE 948477962 24440 137.226.32.75 (21 Jan 2000 18:06:02 GMT)
X-Complaints-To: abuse AT rwth-aachen DOT de
NNTP-Posting-Date: 21 Jan 2000 18:06:02 GMT
User-Agent: tin/1.4-19991113 ("No Labels") (UNIX) (Linux/2.0.0 (i586))
Originator: broeker@
To: djgpp AT delorie DOT com
DJ-Gateway: from newsgroup comp.os.msdos.djgpp
Reply-To: djgpp AT delorie DOT com

Eric Rudd <rudd AT cyberoptics DOT com> wrote:

> I think it's clear from both standards that an inconsistent
> comparison function results in undefined behavior of qsort.

Yep. Guess someone filed a Defect Report to complain that the older
version didn't really state that clearly enough, so the changed the
wording. The new version leaves no room for doubt.

> However, I don't know how to *guarantee* consistent behavior in the
> comparison function, so the quality of implementation is important.

I guess your example case would have to be covered by the usual rule
that 'Thou shalt not test floating point numbers for exact
(in)equality'. Especially not on an x87 FPU without taking special
precautions against excess precision :-)

> The problem of inconsistent comparison functions would be of little
> importance if the implementation of qsort 1) never deferenced beyond
> the ends of the array, no matter what nonsense is returned from the
> comparison function; 

Additional work overhead, for one. Stability under incorrect usage has
never really been a strong point of the C Standard Library, so why
should qsort() be treated differently? C does it fast and dirty, not
rock-solid and slow :-)

> 2) did a "fuzzy" sort with a "fuzzy" comparison function.

But that wouldn't be 'sorting' any longer. Not even to mention that
anno domini 1989, I don't think the 'fuzzy' hype had already
happened...

Just some minor comments regarding that comparison function you show:

>    x = atof((const char *) a);
>    y = atof((const char *) b);

Bad idea. atof()ing the same string more than once is a waste of time
and effort. Scanning strings into floating point numbers is just about
the slowest operation in the whole library. Only non-hardwired
transcendental functions are bound to be even slower.

And, of course, the potential of getting the comparison wrong would
become smaller without the atof() calls, too.

>    retval = 0;
>    if (x > y) retval =  1;
>    if (x < y) retval = -1;

For this part to word as advertised, I think the '-ffloat-store' gcc
option might be needed.
-- 
Hans-Bernhard Broeker (broeker AT physik DOT rwth-aachen DOT de)
Even if all the snow were burnt, ashes would remain.