Message-ID: <38887BFB.2D3FA7A6@cyberoptics.com> From: Eric Rudd 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: <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 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 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