Message-ID: <38887BFB.2D3FA7A6@cyberoptics.com>
From: Eric Rudd <rudd AT cyberoptics DOT com>
Organization: CyberOptics
X-Mailer: Mozilla 4.08 [en] (Win95; U)
MIME-Version: 1.0
Newsgroups: comp.os.msdos.djgpp
Subject: Re: qsort() bug?  Or invalid usage???
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>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Lines: 54
Date: Fri, 21 Jan 2000 09:32:11 -0600
NNTP-Posting-Host: 38.196.93.9
X-Trace: client 948468737 38.196.93.9 (Fri, 21 Jan 2000 10:32:17 EST)
NNTP-Posting-Date: Fri, 21 Jan 2000 10:32:17 EST
To: djgpp AT delorie DOT com
DJ-Gateway: from newsgroup comp.os.msdos.djgpp
Reply-To: djgpp AT delorie DOT com

Hans-Bernhard Broeker wrote:

> Eli Zaretskii <eliz AT is DOT elta DOT co DOT il> wrote:
> > Eric Rudd wrote:
> [...]
> >> I don't think that a good implementation should do this, but
> >> I can find nothing in the ANSI standard that would prohibit such behavior.
>
> I don't have the full text of the older ANSI standard at hand, but
> at least in the upcoming ANSI C99, it's clearly stated:

[snip]

> If the given comparison function violates these 'shall' rules, that
> results in undefined behaviour. I.e.: everything's allowed, from that
> point onwards, including illegal accesses outside array bounds, by
> qsort() or bsearch().

In C90, it's not worded as explicitly, but it's implied.  Here's an excerpt from
7.10.5.2:

     ...The [comparison] function shall return an integer less than, equal
     to, or greater than zero if the first argument is considered to be
     respectively less than, equal to, or greater than the second.

I think it's clear from both standards that an inconsistent comparison function
results in undefined behavior of qsort.  However, I don't know how to *guarantee*
consistent behavior in the comparison function, so the quality of implementation
is important.  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; 2) did a "fuzzy" sort with a "fuzzy" comparison function.

In case anyone is interested in exploring the potential pitfalls, here is the
comparison routine that I used:

#include <stdlib.h>
int fltcmp(const void *a, const void *b) { /* Comparison based on */
   double x, y;                            /* floating-point values */
   int retval;

   x = atof((const char *) a);
   y = atof((const char *) b);
   retval = 0;
   if (x > y) retval =  1;
   if (x < y) retval = -1;
   return retval;
}

I will try it out with the new qsort, to see if the problems have been resolved.

-Eric Rudd
rudd AT cyberoptics DOT com