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 14:24:18 GMT
Organization: Aachen University of Technology (RWTH)
Lines: 37
Message-ID: <869q6i$ika$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>
NNTP-Posting-Host: acp3bf.physik.rwth-aachen.de
X-Trace: nets3.rz.RWTH-Aachen.DE 948464658 19082 137.226.32.75 (21 Jan 2000 14:24:18 GMT)
X-Complaints-To: abuse AT rwth-aachen DOT de
NNTP-Posting-Date: 21 Jan 2000 14:24:18 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

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:

       [#4] When  the  same  objects  (consisting  of  size  bytes,
       irrespective  of  their  current positions in the array) are
       passed more  than  once  to  the  comparison  function,  the
       results  shall be consistent with one another.  That is, for
       qsort they shall define a total ordering on the  array,  and
       for  bsearch  the  same object shall always compare the same
       way with the key.

(ANSI C9x draft, section 7.20.5 "Searching and sorting utilities")

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

> AFAIK, ANSI C explicitly allows to access an array one element before the
> first one, provided that you don't write there.

I don't think it does. The only thing you may do with an array not
strictly within its bounds is *compute* a pointer pointing to the
first element past the end of the array. But you're not allowed to
dereference that pointer. You may just store it in a variable, or do
calculations with it. Reading beyond either end of the array region
causes undefined behaviour (with YAMD or ElectricFence in action, it
can trigger an exception, e.g.).
-- 
Hans-Bernhard Broeker (broeker AT physik DOT rwth-aachen DOT de)
Even if all the snow were burnt, ashes would remain.