🚀 go-pugleaf

In article <4iokop$h4p@lyra.csx.cam.ac.uk> jkb@mrc-lmb.cam.ac.uk (James Bonfield) writes:
>My understanding of this is that qsort() ought to be able
>to handle any sort function, even if it's something as dumb as
>(rand()%3)-1.

The standard says that the function must return negative, zero or
positive according to whether the first argument is less than, equal
to, or greater than the second.  It is implicit in this that the
comparison function defines a total order on the elements; something
like (rand()%3)-1, or a<b, doesn't.

The point is that it must be consistent.  If qsort() compares two
elements twice, it should get the same result each time.  If a < b
then b > a.  If a < b and b < c then a < c.  Neither of the functions
mentioned above has these properties.  In particular if a is less than
b then a < b will return 1 but b < a will return 0 which is not
negative.

I suppose this should be made explicit in the standard, if it hasn't
already been.

-- Richard
--
"Hither turn thy steps, hither come to thy death and for Camilla
receive due guerdon!  Shalt thou, even thou, die by Diana's darts?"
                                              [Virgil, Aeneid X1 855-7]

James Bonfield (jkb@mrc-lmb.cam.ac.uk) wrote:
: Are there any limitations on what the sort function passed over to qsort can
: do or return? I know it's meant to return < 0, 0 or > 0 for the various
: compare operations, but which you return is purely up to your own comparison
: system.
In general, qsort will malfunction (at the least, you can get incorrect
sorting!) if

	compare(a,b) > 0 && compare(b,a) >= 0
or
	compare(b,a) > 0 && compare(a,b) >= 0

because it's not able to put the elements into disjoint sets.

-- 
Thomas E. Dickey
dickey@clark.net

In article <4iokop$h4p@lyra.csx.cam.ac.uk>, jkb@mrc-lmb.cam.ac.uk (James Bonfield) writes:
>Are there any limitations on what the sort function passed over to qsort can
>do or return?

Another followup stated a condition which is probably correct (the standard
isn't exactly explicit about it) but you are obeying that condition so it
is not your problem.

>I know it's meant to return < 0, 0 or > 0 for the various compare operations,
>but which you return is purely up to your own comparison system.

Exactly.

>On tracking down a bug in some old code I noticed that we had the
>compare function returning something like "a > b" instead of "b - a".
>Now this is obviously some silly bug in our coding,

Actually it's a silly question.  Just one sentence earlier, you gave the
exact reason why it doesn't matter if you do "a > b" instead of "a - b".
(Actually it can matter:  if "a - b" would overflow then doing "a > b"
will fix it instead of yielding undefined behavior :-)
On the other hand, doing "a > b" instead of "a < b" reverses the order
of the result -- no difference in technical validity, but likely only
one of these matches your requirement.

>such functions appear to make [one implementation's] qsort() function
>underflow the passed array.

This should not happen.

>#include <stdio.h>
>#include <stdlib.h>
>static int sort_func(const void *pa, const void *pb) {
>    const int *a = (int *)pa;
>    const int *b = (int *)pb;
>    return *a > *b;
>}

Incidentally, if you returned "a > b" instead of "*a > *b" then you would
likely be returning inconsistent results, violating the probably correct
condition which someone else posted.

>#define NUM_ELE 10
>int main() {
>    int i;
>    int crashme;     /* removing this line fixes things! */

This makes me suspicious that your test program is not exactly what you
posted, and your test program has a bug in some other part of its code
that already yielded undefined behavior.

>    int sortme[NUM_ELE];
>    srand(time(NULL));

Or it might be this bug right here.  The standard library function time()
returns type time_t which might not be int.  Your main() function assumes
that it must be int.  You can fix this by adding "#include <time.h>".

>    for (i=0; i<NUM_ELE; i++) {
>        sortme[i] = rand()%100+50;
>    }
>    qsort((void *)sortme, NUM_ELE, sizeof(int), sort_func);
>    return 0;
>}
>Adding some debugging information to this and printing up the array
>before and after sorting (including the values (666) immediately above
>and below the array) shows that the contents of memory outside of the
>array actually get swapped with memory inside the array. I can make it
>overflow too.

You probably have a bug in the other code that you haven't shown.
There's no 666 in the code you've shown.

>My understanding of this is that qsort() ought to be able to handle any
>sort function, even if it's something as dumb as (rand()%3)-1.

That would not be a sort function (it might even assert that a < b and
b < c and c < a).  As for whether qsort() is required to contend with
such nonsense, it "probably" isn't.
--
 <<  If this were the company's opinion, I would not be allowed to post it.  >>
"I paid money for this car, I pay taxes for vehicle registration and a driver's
license, so I can drive in any lane I want, and no innocent victim gets to call
the cops just 'cause the lane's not goin' the same direction as me" - J Spammer

> > Are there any limitations on what the sort function

It's better to call it a comparison function; qsort() is the sort function.

> > passed over to qsort can do or return?

The standard states

#  The 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.

In other words, it must yield an ordering of the possible data values.
This is only the case if

	1. It is a pure function:
	   repeated calls to compar(x,y) yield a result having the
	       same sign each time

	2. It is antisymmetric (I think that's the right word):
	   if compar(x,y) <  0, then compar(y,x) >  0
	   if compar(x,y) == 0, then compar(y,x) == 0
	   if compar(x,y) >  0, then compar(y,x) <  0

	3. If is transitive:
	   if compar(x,y) > 0 && compar(y,z) > 0, then compar(x,z) > 0

> > I know it's meant to return < 0, 0 or > 0 for the various compare
> > operations, but which you return is purely up to your own comparison
> > system.

Yes, so long as it obeys *some* comparison system.
 
> > On tracking down a bug in some old code I noticed that we had the
> > compare function returning something like "a > b" instead of "b - a".
> 
> Just one sentence earlier, you gave the exact reason why
> it doesn't matter if you do "a > b" instead of "a - b".

Of course it matters.  With this function, if compar(x,y) > 0, then
compar(y,x) == 0.  This is not antisymmetric.
it is not a proper comparison function and the behavior is undefined.

> (Actually it can matter:  if "a - b" would overflow then doing "a > b"
> will fix it instead of yielding undefined behavior :-)

Well, "a - b" is indeed unsuitable in general due to potential overflow.
If the numbers being subtracted are floating-point or are signed integers,
then arithmetic overflow may occur, causing undefined behavior.  It might
be safe if they are unsigned integers, but then, unless they are narrower
than int, you run into implementation-defined behavior on converting the
result of the subtraction to the int that the function returns.

But changing to "a > b", as noted, does not fix it.  If simple arithmetic
comparison is what you want, then you should use something like:

	(a > b)? 1: (a < b)? -1: 0

Terser equivalents, but probably considered less clear by most people, are:

	(a < b)? -1: (a > b)
and
	(a > b) - (a < b)

> > My understanding of this is that qsort() ought to be able to handle any
> > [comparison] function, even if it's something as dumb as (rand()%3)-1.
> 
> That would not be a [comparison] function (it might even assert that a < b
> and b < c and c < a).

Right.  In fact, it would not necessarily obey any of the three properties
mentioned above, so the behavior of qsort() would be undefined.

-- 
Mark Brader                 At any rate, C++ != C.  Actually, the value of the
msb@sq.com                  expression "C++ != C" is [undefined].
SoftQuad Inc., Toronto                                  -- Peter da Silva

My text in this article is in the public domain.

jkb@mrc-lmb.cam.ac.uk (James Bonfield) writes:

|Are there any limitations on what the sort function passed over to qsort can
|do or return? I know it's meant to return < 0, 0 or > 0 for the various
|compare operations, but which you return is purely up to your own comparison
|system.

|On tracking down a bug in some old code I noticed that we had the
|compare function returning something like "a > b" instead of "b - a".
|Now this is obviously some silly bug in our coding, but "a > b" is still
|a valid sort function surely? The reason I ask is that this that such
|functions appear to make the Irix 5.3 qsort() function underflow the
|passed array. Please check the following function to verify that I
|haven't done something daft.

As others have pointed out, b - a runs the risk of overflow if a and b
are large enough in magnitude and of opposite sign.  That's why it is
often recommended against as a value to return from the compare function.
BTW, without overflow, b - a is positive if b > a, not if a > b.


|#include <stdio.h>
|#include <stdlib.h>

|static int sort_func(const void *pa, const void *pb)
|{
|    const int *a = (int *)pa;
|    const int *b = (int *)pb;

|    return *a > *b;
|}

This function returns either a 0 if *a <= *b or a 1 if *a > *b.  Since
keys are considered equal if sort_func() returns zero, this will not
properly discern a case where the first argument must appear before
the second.  It would surprise me not at all if qsort() relied on
sort_func() having the property that

	!!sort_func(p1, p2) == -1 * !!sort_func(p2, p1)

which does not hold for this function.  (The Standard wording seems
to me to require this property, but I'm not a duly certified language
lawyer...)

Try 

	static int sort_func(const void *pa, const void *pb)
	{
	    const int *a = (int *)pa;
	    const int *b = (int *)pb;

	    return (*a > *b) - (*a < *b);
	}

instead.
-- 
		Matthew Saltzman
		Clemson University Math Sciences
		mjs@clemson.edu

I wrote:

>             It would surprise me not at all if qsort() relied on
                                                         ^^^^^^^^^
>sort_func() having the property that

>	!!sort_func(p1, p2) == -1 * !!sort_func(p2, p1)

Of course, in comp.std.c, I should have said "...were permitted to rely on..."
-- 
		Matthew Saltzman
		Clemson University Math Sciences
		mjs@clemson.edu

In article <4iqjar$2m9@usenet.pa.dec.com>, diamond@tbj.dec.com (Norman Diamond) writes:
>In article <4iokop$h4p@lyra.csx.cam.ac.uk>, jkb@mrc-lmb.cam.ac.uk (James Bonfield) writes:
>>Are there any limitations on what the sort function passed over to qsort can
>>do or return?
>
>>I know it's meant to return < 0, 0 or > 0 for the various compare operations,
>>but which you return is purely up to your own comparison system.
>
>Exactly.
>
>>On tracking down a bug in some old code I noticed that we had the
>>compare function returning something like "a > b" instead of "b - a".
>>Now this is obviously some silly bug in our coding,
>
>Actually it's a silly question.  Just one sentence earlier, you gave the
>exact reason why it doesn't matter if you do "a > b" instead of "a - b".

The expression a > b can only have the values 0 or 1; therefore, if your
qsort comparison returns a > b it will never return a negative value.  If
a is less than b, it will return 0, which to qsort means they are equal.  I
do not believe that is what you want.

--
Roger Wells (speaking only for myself)

In article <1996Mar21.113301.2622@sq.com>, msb@sq.com (Mark Brader) writes:
#  The 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.

>In other words, it must yield an ordering of the possible data values.
>This is only the case if
>
>1. It is a pure function:
>   repeated calls to compar(x,y) yield a result having the
>       same sign each time
>
>2. It is antisymmetric (I think that's the right word):
>   if compar(x,y) <  0, then compar(y,x) >  0
>   if compar(x,y) == 0, then compar(y,x) == 0
>   if compar(x,y) >  0, then compar(y,x) <  0
>
>3. If is transitive:
>   if compar(x,y) > 0 && compar(y,z) > 0, then compar(x,z) > 0

You have given an intuitively and logically reasonable definition of a
comparison system, but the standard does not.  The standard has trouble
defining a pure binary numeration system and even has trouble refering
to a document which did it.  Until the standard finds a definition of a
comparison system, it is defective.

>>>On tracking down a bug in some old code I noticed that we had the
>>>compare function returning something like "a > b" instead of "b - a".

>>Just one sentence earlier, you gave the exact reason why
>>it doesn't matter if you do "a > b" instead of "a - b".

>Of course it matters.  With this function, if compar(x,y) > 0, then
>compar(y,x) == 0.  This is not antisymmetric.

Argh!  I was remembering what the hardware usually does for comparison
instructions, and forgot that C operators lose part of that information.
I must be getting Cnile.

>(a > b)? 1: (a < b)? -1: 0

Yup.  Incidentally, do you think the average implementation's
interprocedural optimization phase will change this user function into
one machine instruction in the library's qsort() function :-?
--
 <<  If this were the company's opinion, I would not be allowed to post it.  >>
"I paid money for this car, I pay taxes for vehicle registration and a driver's
license, so I can drive in any lane I want, and no innocent victim gets to call
the cops just 'cause the lane's not goin' the same direction as me" - J Spammer

In article <4iokop$h4p@lyra.csx.cam.ac.uk>
           jkb@mrc-lmb.cam.ac.uk "James Bonfield" writes:

> Are there any limitations on what the sort function passed over to qsort can
> do or return? I know it's meant to return < 0, 0 or > 0 for the various
> compare operations, but which you return is purely up to your own comparison
> system.
> 

[snip]

> static int sort_func(const void *pa, const void *pb)
> {
>     const int *a = (int *)pa;
>     const int *b = (int *)pb;
> 
>     return *a > *b;
>
> }

You need a function which returns "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" [ ANSI/ISO 9899-1990
7.10.5.2].

sort_funct returns 0, 0, and 1, respectively for the 3 cases enumerated.

Brevity is satisfied by:
     return *a < *b ? -1 : *a > *b;

You may find that conformity to the interface is better shown by:
     return (*a < *b) ? -1 : ((*a == *b) ? 0 : 1);

I think I prefer to avoid the multiple dereferencing with:

static int sort_func(const void *pa, const void *pb)
{
    int a = *(const int *)pa;
    int b = *(const int *)pb;

    return a < b ? -1 : a > b;
}
--
walter briscoe

In article <4it51b$ng8@usenet.pa.dec.com>, diamond@tbj.dec.com (Norman Diamond) writes:
|>
|>>>Just one sentence earlier, you gave the exact reason why
|>>>it doesn't matter if you do "a > b" instead of "a - b".
|>
|>>Of course it matters.  With this function, if compar(x,y) > 0, then
|>>compar(y,x) == 0.  This is not antisymmetric.
|>
|>Argh!  I was remembering what the hardware usually does for comparison
|>instructions, and forgot that C operators lose part of that information.
|>I must be getting Cnile.
|>
|>>(a > b)? 1: (a < b)? -1: 0
|>
|>Yup.  Incidentally, do you think the average implementation's
|>interprocedural optimization phase will change this user function into
|>one machine instruction in the library's qsort() function :-?

I'd be quite impressed if it did.

Alternatively, how about this:

    return ((signed int) ((unsigned int)a - (unsigned int)b));

--

Chris Volpe				Phone: (518) 387-7766 (Dial Comm 8*833
GE Corporate R&D			Fax:   (518) 387-6560
PO Box 8, Schenectady, NY 12301		Email: volpecr@crd.ge.com

#  The 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.
 
> > In other words, it must yield an ordering of the possible data values.
> > This is only the case if
> > 1. It is a pure function...
> > 2. It is antisymmetric (I think that's the right word)...
> > 3. If is transitive...
> 
> You have given an intuitively and logically reasonable definition of a
> comparison system, but the standard does not.

The standard does not have to define a "comparison system", because it
does not use that term in the cited passage.  What this poster has called
"an intuitively and logically reasonable definition of a comparison system"
was intended as a statement of the obvious implications of the cited
passage.  (Specifically, these implications follow from the use of the
expressions "considered to be ... less than, equal to, or greater than".)

> Until the standard finds a definition of a comparison system, it is
> defective.

Nonsense; the cited passage is perfectly clear.
-- 
Mark Brader          "Yet again, I begged him to explain himself in plain
SoftQuad Inc.         English.  This request always surprises him, as he
msb@sq.com            is always under the extraordinary impression that
Toronto               he has done so."       -- Lynn & Jay, "Yes Minister"

My text in this article is in the public domain.

> Alternatively, how about this:
> 
>     return ((signed int) ((unsigned int)a - (unsigned int)b));

Assuming that a and b are int, this line cannot produce undefined
behavior, but if a < b, the value returned is implementation-defined
and in particular its sign is not specified by the standard.

If the implementation allows this returned value to be non-negative
for some values of a and b, then the function is not a legitimate
comparison function for qsort() because it may not be transitive.
Therefore the code is not strictly conforming.
-- 
Mark Brader, msb@sq.com        "do right; have fun; make money"
SoftQuad Inc., Toronto              -- Ian Darwin on Yuri Rubinsky (1952-96)

My text in this article is in the public domain.

In <<4iukhc$5nr@rdsunx.crd.ge.com>>, 
volpe@bart.crd.ge.com (Christopher R. Volpe) wrote:


>Alternatively, how about this:

>    return ((signed int) ((unsigned int)a - (unsigned int)b));


	That won't work.  First consider a=-32 and b = 31, which, with 16-bit
ints becomes:
   (signed int) ( (unsigned int) -32 - (unsigned int) 31 )
== (signed int)                65504 -                31  
== (signed int)                65473 
== -63 (a negative value, as it should)

	Now, multiple each value by 1000.  Since the relationship is the same,
we should again get a negative number, however:
   (signed int) ( (unsigned int) -32000 - (unsigned int) 31000 )
== (signed int) (                 33536 -                31000)
== (signed int) (                  2536)
== 2536 (a positiove value)

In article <4iukhc$5nr@rdsunx.crd.ge.com>, volpe@bart.crd.ge.com (Christopher R. Volpe) writes:
>In article <4it51b$ng8@usenet.pa.dec.com>, diamond@tbj.dec.com (Norman Diamond) writes:
>>>>Just one sentence earlier, you gave the exact reason why
>>>>it doesn't matter if you do "a > b" instead of "a - b".

>>>Of course it matters.  With this function, if compar(x,y) > 0, then
>>>compar(y,x) == 0.  This is not antisymmetric.

>>Argh!  I was remembering what the hardware usually does for comparison
>>instructions, and forgot that C operators lose part of that information.
>>I must be getting Cnile.

>>>(a > b)? 1: (a < b)? -1: 0

>>Yup.  Incidentally, do you think the average implementation's
>>interprocedural optimization phase will change this user function into
>>one machine instruction in the library's qsort() function :-?

>I'd be quite impressed if it did.
>Alternatively, how about this:
>    return ((signed int) ((unsigned int)a - (unsigned int)b));

If this alternative is a reply to my snarky question about quality of
implementation (which was a bit off-topic) then the answer is that it
will probably work even under "reasonable" implementations.  However,
if you're asking what the standard says about your alternative, the
effect is not strictly conforming and again might cause undefined
behavior if the standard requires the comparison function to be reasonable.
The problem is that the conversion from unsigned int to signed int will
be implementation-defined about half the time.
--
 <<  If this were the company's opinion, I would not be allowed to post it.  >>
"I paid money for this car, I pay taxes for vehicle registration and a driver's
license, so I can drive in any lane I want, and no innocent victim gets to call
the cops just 'cause the lane's not goin' the same direction as me" - J Spammer

> >             It would surprise me not at all if qsort() relied on
>                                                          ^^^^^^^^^
> > sort_func() having the property that
> 
> >	!!sort_func(p1, p2) == -1 * !!sort_func(p2, p1)
> 
> Of course, in comp.std.c, I should have said "...were permitted to rely on..."

Better yet, you should have not have assumed that !!x would produce -1
when x < 0.  <grin>

Incidentally, I have encountered code where the comparison function for
qsort() actually WAS specified with a return expression like *a < *b that
produced 0 when it should have produced -1.  The interesting part is that,
on the particular machine the programmer had been using, the sort worked
correctly.  Evidently this particular qsort() implementation only tested
whether the comparison function returned a positive value or not.

-- 
Mark Brader, msb@sq.com, SoftQuad Inc., Toronto
        "I'm a little worried about the bug-eater," she said.  "We're embedded
        in bugs, have you noticed?"             -- Niven, "The Integral Trees"

My text in this article is in the public domain.

msb@sq.com (Mark Brader) writes:

>> >	!!sort_func(p1, p2) == -1 * !!sort_func(p2, p1)

>Better yet, you should have not have assumed that !!x would produce -1
>when x < 0.  <grin>

Oh, damn...  What could I possibly have been thinking?
-- 
		Matthew Saltzman
		Clemson University Math Sciences
		mjs@clemson.edu

[I posted a similar article yesterday, but it didn't seem to make it to the
'net.  Appologize if this is redundant.]

On Fri, 22 Mar 1996 20:26:15 GMT in article <1996Mar22.202615.9926@sq.com>
    msb@sq.com (Mark Brader) (Mark Brader) wrote:

>#  The 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.
> 
>> > In other words, it must yield an ordering of the possible data values.
>> > This is only the case if
>> > 1. It is a pure function...
>> > 2. It is antisymmetric (I think that's the right word)...
>> > 3. If is transitive...

I have to disagree.  While agreeing that what is stated here was roughly the
intent of the committee, the standard doesn't say it.  (I don't really see the

In comparing two values 'a' and 'b', I could specify that I consider 'a' less
than 'b' when ((long) time()) produces an odd number, but 'a' greater than 'b'
otherwise.  I can then write a comparison function that implements this
definition.  I see nothing in this that would violate the standard, but it would
probably break many implementations of qsort().  I cannot imagine any use for
such a comparison definition, but it looks legal to me.

I think the standard needs to say that successive results generated by the
comparison function must be mutually consistent.  I won't try to suggest wording
to capture that concept.

--
Peter Curran                               pcurran@inforamp.net

I now agree that non antisymmetric or nontransitive sort comparison functions
are indeed invalid. I can see how this can be construed from the ansi
standard, but can also see how it's possible to construe otherwise. In short
it doesn't really state such things explicitly. Anyway, that aside I thought I
should reply to the last note about this.

In article <4iqjar$2m9@usenet.pa.dec.com> diamond@tbj.dec.com (Norman Diamond) writes:

>>such functions appear to make [one implementation's] qsort() function
>>underflow the passed array.
>
>This should not happen.

Well, that depends on whether or not you class qsorts behaviour as undefined
for such functions.

>>#define NUM_ELE 10
>>int main() {
>>    int i;
>>    int crashme;     /* removing this line fixes things! */
>
>This makes me suspicious that your test program is not exactly what you
>posted, and your test program has a bug in some other part of its code
>that already yielded undefined behavior.

Actually it's true - it does cause it to go wrong. I've got an example now
that used explicitly defined numbers to cause a crash. With the crashme line
in the program dies. Without it the program modifies memory not within the
boundaries of qsort. My program is:

#include <stdio.h>
#include <stdlib.h>

static int sort_func(const void *pa, const void *pb)
{
    const int *a = (int *)pa;
    const int *b = (int *)pb;

    return *a > *b;
}

#define NUM_ELE 10
int main() {
    int i;
    int crashme;     /* removing this line fixes things! */
    int sortme[NUM_ELE] = {148, 104, 126, 74, 108, 131, 129, 131, 125, 77};

    for (i=0; i<NUM_ELE; i++) printf("%d ", sortme[i]);
    putchar('\n');

    qsort((void *)(sortme+1), NUM_ELE-2, sizeof(int), sort_func);

    for (i=0; i<NUM_ELE; i++) printf("%d ", sortme[i]);
    putchar('\n');

    return 0;
}

>b < c and c < a).  As for whether qsort() is required to contend with
>such nonsense, it "probably" isn't.

Agreed. Hence the above discoveries are most likely entirely within the realm
of acceptability.

Perhaps the most interesting point to come out of this is the inefficiency of
some qsort algorithms. Sorting 100,000 elements (with a "consistent" sort
comparison function) gave the following approximations (ran several times with
random input - of course these results may just reflect the random number
generator woes!):

OSF/1 V3.0	~72K
Linux (gnu lib)	~153K
Irix 5.3	~170K
Solaris 5.3	~305K

Thanks for all the suggestions everyone has made.
Cheers,

	James
--
James Bonfield (jkb@mrc-lmb.cam.ac.uk)   Tel: 01223 402499   Fax: 01223 412282
Medical Research Council - Laboratory of Molecular Biology,
Hills Road, Cambridge, CB2 2QH, England.

In article <4jgltp$f9l@lyra.csx.cam.ac.uk>
           jkb@mrc-lmb.cam.ac.uk "James Bonfield" writes:

>I now agree that non antisymmetric or nontransitive sort comparison functions
>are indeed invalid. I can see how this can be construed from the ansi
>standard, but can also see how it's possible to construe otherwise.

I don't. 7.10.5.2:

"The contents of the array are sorted into ascending
 order according to a comparison function pointed to by compar". 

If the comparison function produces inconsistent results then it is at odds
with that sentence. At best that sentence has no well-defined meaning and
the 'sort' operation as a whole has undefined behaviour.

>it doesn't really state such things explicitly. Anyway, that aside I thought I
>should reply to the last note about this.
>
>In article <4iqjar$2m9@usenet.pa.dec.com> diamond@tbj.dec.com (Norman Diamond)
> writes:
>
>>>such functions appear to make [one implementation's] qsort() function
>>>underflow the passed array.
>>
>>This should not happen.
>
>Well, that depends on whether or not you class qsorts behaviour as undefined
>for such functions.

To put it another way, if there is a defined behaviour with such a function,
what is it?

>>>#define NUM_ELE 10
>>>int main() {
>>>    int i;
>>>    int crashme;     /* removing this line fixes things! */
>>
>>This makes me suspicious that your test program is not exactly what you
>>posted, and your test program has a bug in some other part of its code
>>that already yielded undefined behavior.
>
>Actually it's true - it does cause it to go wrong. I've got an example now
>that used explicitly defined numbers to cause a crash. With the crashme line
>in the program dies. Without it the program modifies memory not within the
>boundaries of qsort. My program is:
>
>#include <stdio.h>
>#include <stdlib.h>
>
>static int sort_func(const void *pa, const void *pb)
>{
>    const int *a = (int *)pa;
>    const int *b = (int *)pb;

It would be more consistent (as well as killing a warning from my compiler)
if you cast to (const int *), better still don't cast at all.

>
>    return *a > *b;
>}

This clearly violates a 'shall' in the standard and results in undefined
behaviour. With the specific data in this case return *a - *b; would be OK.

"The 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."

>#define NUM_ELE 10
>int main() {
>    int i;
>    int crashme;     /* removing this line fixes things! */
>    int sortme[NUM_ELE] = {148, 104, 126, 74, 108, 131, 129, 131, 125, 77};
>
>    for (i=0; i<NUM_ELE; i++) printf("%d ", sortme[i]);
>    putchar('\n');
>
>    qsort((void *)(sortme+1), NUM_ELE-2, sizeof(int), sort_func);
>
>    for (i=0; i<NUM_ELE; i++) printf("%d ", sortme[i]);
>    putchar('\n');
>
>    return 0;
>}
>
>>b < c and c < a).  As for whether qsort() is required to contend with
>>such nonsense, it "probably" isn't.
>
>Agreed. Hence the above discoveries are most likely entirely within the realm
>of acceptability.
>
>Perhaps the most interesting point to come out of this is the inefficiency of
>some qsort algorithms. Sorting 100,000 elements (with a "consistent" sort
>comparison function) gave the following approximations (ran several times with
>random input - of course these results may just reflect the random number
>generator woes!):
>
>OSF/1 V3.0      ~72K
>Linux (gnu lib) ~153K
>Irix 5.3        ~170K
>Solaris 5.3     ~305K

What do these numbers represent?

-- 
-----------------------------------------
Lawrence Kirby | fred@genesis.demon.co.uk
Wilts, England | 70734.126@compuserve.com
-----------------------------------------

On Thu, 04 Apr 96 18:57:54 GMT in article <828644274snz@genesis.demon.co.uk>
    Lawrence Kirby <fred@genesis.demon.co.uk> (Lawrence Kirby) wrote:

>In article <4jgltp$f9l@lyra.csx.cam.ac.uk>
>           jkb@mrc-lmb.cam.ac.uk "James Bonfield" writes:

>>I now agree that non antisymmetric or nontransitive sort comparison functions
>>are indeed invalid. I can see how this can be construed from the ansi
>>standard, but can also see how it's possible to construe otherwise.

>I don't. 7.10.5.2:

>"The contents of the array are sorted into ascending
> order according to a comparison function pointed to by compar". 

>If the comparison function produces inconsistent results then it is at odds
>with that sentence. At best that sentence has no well-defined meaning and
>the 'sort' operation as a whole has undefined behaviour.

<snip>

From the standard:
>"The 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."

Again, agreeing that the intent was that the comparison function be consistent,
this statement does not require it.  (Actually, consistent is not quite the word
I mean here - it must be consistent with a well-specified definition  - that is
implied by the first quote, above -  but that definition need not lead to a
comparison function that produces the same result for the same values on
successive calls, or follows other "sensible" patterns.)

There is nothing here that demands that what one "considers to be ... less
than", etc., remain static over the duration of a call to qsort().  As I
suggested earlier, one could define a ordering that is time-dependent, or
changes in some other way between calls to the comparison function.  I see
nothing here that precludes a comparison function from then implementing such a
definition.  As long as the comparison function produces results match the rules
that have been established for considering values to be less than, etc., each
other each time it is called, whether those rules are static or not,, the
requirements of the standard have been met.

This is clearly "language lawyering" of the worst kind.  Anyone who writes such
a comparison function will almost certainly get a well-earned mess.  However, I
see nothing in the standard that contradicts this interpretation.  For logical
correctness, I think the definition of the comparison function needs to be
tightened, although its hardly of pressing urgency.)

--
Peter Curran                               pcurran@inforamp.net

In article <4k28t4$2g0@sam.inforamp.net>
           pcurran@inforamp.net "Peter Curran" writes:

>On Thu, 04 Apr 96 18:57:54 GMT in article <828644274snz@genesis.demon.co.uk>
>    Lawrence Kirby <fred@genesis.demon.co.uk> (Lawrence Kirby) wrote:
>
>>In article <4jgltp$f9l@lyra.csx.cam.ac.uk>
>>           jkb@mrc-lmb.cam.ac.uk "James Bonfield" writes:
>
>>>I now agree that non antisymmetric or nontransitive sort comparison functions
>>>are indeed invalid. I can see how this can be construed from the ansi
>>>standard, but can also see how it's possible to construe otherwise.
>
>>I don't. 7.10.5.2:
>
>>"The contents of the array are sorted into ascending
>> order according to a comparison function pointed to by compar". 
>
>>If the comparison function produces inconsistent results then it is at odds
>>with that sentence. At best that sentence has no well-defined meaning and
>>the 'sort' operation as a whole has undefined behaviour.
>
><snip>
>
>From the standard:
>>"The 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."
>
>Again, agreeing that the intent was that the comparison function be consistent,
>this statement does not require it.  (Actually, consistent is not quite the
> word
>I mean here - it must be consistent with a well-specified definition  - that is
>implied by the first quote, above -  but that definition need not lead to a
>comparison function that produces the same result for the same values on
>successive calls, or follows other "sensible" patterns.)

It *must*  lead to a comparison that produces the same result for the same
values on successive calls or else the term 'sort' is not applicable and
qsort() has undefined behaviour.

>There is nothing here that demands that what one "considers to be ... less
>than", etc., remain static over the duration of a call to qsort().  As I
>suggested earlier, one could define a ordering that is time-dependent, or
>changes in some other way between calls to the comparison function.  I see
>nothing here that precludes a comparison function from then implementing such a
>definition.

Such a comparison function is not consistent with sorting.
It is not the job of the C standard to define basic computer science terms.
Sorting has a well defined meaning and your comparison function is
inconsistent with that meaning.

> As long as the comparison function produces results match the
> rules
>that have been established for considering values to be less than, etc., each
>other each time it is called, whether those rules are static or not,, the
>requirements of the standard have been met.

Undefined behaviour occurs where no behaviour is defined (3.16) i.e. you
don't need to violate an explicit requirement in the standard to invoke it.

>This is clearly "language lawyering" of the worst kind.  Anyone who writes such
>a comparison function will almost certainly get a well-earned mess.  However, I
>see nothing in the standard that contradicts this interpretation.  For logical
>correctness, I think the definition of the comparison function needs to be
>tightened, although its hardly of pressing urgency.)

If you can find any definition as to what the behaviour should be with your
comparison function, explain what it is. Otherwise the behaviour is
undefined.

-- 
-----------------------------------------
Lawrence Kirby | fred@genesis.demon.co.uk
Wilts, England | 70734.126@compuserve.com
-----------------------------------------

On Fri, 05 Apr 96 17:49:42 GMT in article <828726582snz@genesis.demon.co.uk>
    Lawrence Kirby <fred@genesis.demon.co.uk> (Lawrence Kirby) wrote:

>If you can find any definition as to what the behaviour should be with your
>comparison function, explain what it is. Otherwise the behaviour is
>undefined.

IMHO, qsort() is required to return an array that is sorted according to the
criteria implied by the comparison function.  That is, at the point where qsort
returns, the array must match the order implied by the comparison function.  If
the comparison function definition is such that the order changes (although the
*definition* of the order must remain fixed), then IMHO the current wording of
the standard can be read as meaning that it is qsort's problem to deal with it.
This all hinges on how one interprets the word "considered" in the standard -
that is a very vague term to use in a standard, and IMHO can reasonably lead to
confusion.  If a "snapshot" is taken at the time qsort() returns, the array must
match order implied by the comparison function.  If the definition of the
comparison criteria cannot provide a definite sort order for the array at any
instant, then I agree that it is invalid, but if it does provide such an
definite order at any instant, then I think the current standard permits it.

Let me give another example of a problematic comparison function that seems to
me to satisfy all the requirements of the standard, but leads, I think, to
unintended problems for implementing qsort.

The comparison function returns 1 if the first value is greater than the second
value, or -1 if the second   However, if they are equal, the function then
compares the values of the pointers to the parameters (the actual arguments of
the function) - if the first is greater, 1 is returned, if the second is greater
-1 is returned, otherwise 0 is returned.

This function is a (misguided) attempt to create a stable sort.  It is only a
valid comparison function if qsort() only passes pointers to elements in the
array being sorted to the comparison function - otherwise, the pointer
comparisons are (probably) undefined.  This comparions function will "work"
(i.e. not produce undefined behaviour) for some possible implementations of
qsort(), but not others.  It would also produce a consistent sort order for some
implementations, but not others.  (I think Bubble Sort could be implemented with
these restriction.  Quicksort would be trickier, or a lot slower.)

So - is this comparison function legal or not?  I cannot see anything in the
standard that disallows it.  I think the requirement to avoid undefined
behaviour in this case can reasonably be interpreted as falling on qsort(), not
on the comparison function.  I am sure the committee never intended such a
think, but I the current standard can reasonably be read as containing them.

--
Peter Curran                               pcurran@inforamp.net

In article <4k69bf$ehg@sam.inforamp.net>
           pcurran@inforamp.net "Peter Curran" writes:

>On Fri, 05 Apr 96 17:49:42 GMT in article <828726582snz@genesis.demon.co.uk>
>    Lawrence Kirby <fred@genesis.demon.co.uk> (Lawrence Kirby) wrote:
>
>>If you can find any definition as to what the behaviour should be with your
>>comparison function, explain what it is. Otherwise the behaviour is
>>undefined.
>
>IMHO, qsort() is required to return an array that is sorted according to the
>criteria implied by the comparison function.  That is, at the point where qsort
>returns, the array must match the order implied by the comparison function.

But if the comparison function is inconsistent it implies no order at all.
If there is no ordering that is consistent with the values returned by the
comparison function then clearly your requirement cannot be fulfilled.

> If
>the comparison function definition is such that the order changes (although the
>*definition* of the order must remain fixed), then IMHO the current wording of
>the standard can be read as meaning that it is qsort's problem to deal with it.

No, qsort() is defined as a sorting function and what you describe is not
a valid sorting operation.

>This all hinges on how one interprets the word "considered" in the standard -

The critical word is 'sorted'. I suggest you read section 5 (i.e. the
first section of chapter 5) in Knuth Vol 3 to get a reasonable idea of what
a sort is. I repeat that it is not the job of the C standard to define
basic computer science terms. Particularly relevant:

"An ordering relation ``<'' is specified on the keys so that, for any three
 key values a, b, c, the following conditions are satisfied:

 i)  Exactly one of the possibilities a < b, a = b, b < a is true. (This is
     the law of trichotomy.)

 ii) If a < b and b < c, then a < c. (The law of transitivity.)

...

  The goal of sorting is to determine a permutation p(1)p(2)...p(N) of
the records, which puts the keys in nondescending order:

         K     <= K     <= ... <= K 
          p(1)     p(2)            p(N)
"

What you suggest above is not a valid ordering relation so cannot be used
in a sort.

>that is a very vague term to use in a standard, and IMHO can reasonably lead to
>confusion.  If a "snapshot" is taken at the time qsort() returns, the array
> must
>match order implied by the comparison function.  If the definition of the
>comparison criteria cannot provide a definite sort order for the array at any
>instant, then I agree that it is invalid, but if it does provide such an
>definite order at any instant, then I think the current standard permits it.

What do you mean 'at any instant'? The relation doesn't have license to
change during the sort operation.

>Let me give another example of a problematic comparison function that seems to
>me to satisfy all the requirements of the standard, but leads, I think, to
>unintended problems for implementing qsort.
>
>The comparison function returns 1 if the first value is greater than the second
>value, or -1 if the second   However, if they are equal, the function then
>compares the values of the pointers to the parameters (the actual arguments of
>the function) - if the first is greater, 1 is returned, if the second is
> greater
>-1 is returned, otherwise 0 is returned.

>This function is a (misguided) attempt to create a stable sort.  It is only a
>valid comparison function if qsort() only passes pointers to elements in the
>array being sorted to the comparison function - otherwise, the pointer
>comparisons are (probably) undefined.

OK, however since the algorithm is unspecified you can't say any more than
this results in undefined behaviour.

  This comparions function will "work"
>(i.e. not produce undefined behaviour) for some possible implementations of
>qsort(), but not others.  It would also produce a consistent sort order for
> some
>implementations, but not others.  (I think Bubble Sort could be implemented
> with
>these restriction.  Quicksort would be trickier, or a lot slower.)

Whether a particular qsort() 'works' or not is not important, only whether
all implementations are guaranteed to work or not i.e. whether the code
is strictly conforming (apart from the issue of the unspecified order for
equal keys).

>So - is this comparison function legal or not?  I cannot see anything in the
>standard that disallows it.  I think the requirement to avoid undefined
>behaviour in this case can reasonably be interpreted as falling on qsort(), not
>on the comparison function.  I am sure the committee never intended such a
>think, but I the current standard can reasonably be read as containing them.

Assuming that the particular qsort() implementation does only pass
pointers to the array's elements you violate the rules for the relation,
certainly i) and probably ii) also. So the operation as a whole isn't a sort
and the standard defines no behaviour for it.

-- 
-----------------------------------------
Lawrence Kirby | fred@genesis.demon.co.uk
Wilts, England | 70734.126@compuserve.com
-----------------------------------------

On Mon, 08 Apr 96 13:56:53 GMT in article <828971813snz@genesis.demon.co.uk>
    Lawrence Kirby <fred@genesis.demon.co.uk> (Lawrence Kirby) wrote:

>>IMHO, qsort() is required to return an array that is sorted according to the
>>criteria implied by the comparison function.  That is, at the point where qsort
>>returns, the array must match the order implied by the comparison function.

The comparison function I postulated *is* consistent, at any instant in time.
(Just to be clear - another correspondent suggested my original posting may not
have said quite what I intended.  The comparison function I suggested., or
intended, calculates as result by comparison of the values pointed at by the
parameters, in a way we can all agree is acceptable.  However, it then calls
time(), and if the result it odd it negates the result before returning it.  In
a conventional implementation of time(), it reverses the order every second, but
defines a consistent order at any given time.)

>The critical word is 'sorted'. I suggest you read section 5 (i.e. the
>first section of chapter 5) in Knuth Vol 3 to get a reasonable idea of what
>a sort is. 

I can assure you that I read Knuth cover to cover, within a few weeks of its
first publication.  I really don't think this kind of insult is necessary here.

There isn't much point in continuing this.  We will have to agree to disagree.
I understand how you are reaching the conclusions you are reaching (and I agree
it should be possible to reach them).  However I think that you are stretching
the text of the standard beyond the breaking point to get there.

--
Peter Curran                               pcurran@inforamp.net

In article <4kbl1l$74r@sam.inforamp.net> pcurran@inforamp.net (Peter
Curran) writes:

> On Mon, 08 Apr 96 13:56:53 GMT in article
>     <828971813snz@genesis.demon.co.uk> Lawrence Kirby
>     <fred@genesis.demon.co.uk> (Lawrence Kirby) wrote:

>>> IMHO, qsort() is required to return an array that is sorted
>>> according to the criteria implied by the comparison function.
>>> That is, at the point where qsort returns, the array must match
>>> the order implied by the comparison function.

> The comparison function I postulated *is* consistent, at any instant
> in time.  (Just to be clear - another correspondent suggested my
> original posting may not have said quite what I intended.  The
> comparison function I suggested., or intended, calculates as result
> by comparison of the values pointed at by the parameters, in a way
> we can all agree is acceptable.  However, it then calls time(), and
> if the result it odd it negates the result before returning it.  In
> a conventional implementation of time(), it reverses the order every
> second, but defines a consistent order at any given time.)

So what happens if the array is large enough that qsort takes longer
than a second to complete?  The return values from the comparison
function are no longer consistent.  Is the compiler vendor then
obligated to produce an implementation of qsort that will complete a
sort in a constant amount of time?  That is what breaks your
comparison function.

Just a Thought,
Jim Trigg

On Tue, 9 Apr 1996 14:54:14 GMT in article <9livf9cusp.fsf@marks.jyacc.com>
    jtrigg@marks.jyacc.com (Jim Trigg) (Jim Trigg) wrote:

>So what happens if the array is large enough that qsort takes longer
>than a second to complete?  The return values from the comparison
>function are no longer consistent.  Is the compiler vendor then
>obligated to produce an implementation of qsort that will complete a
>sort in a constant amount of time?  That is what breaks your
>comparison function.

AARRRGGHHH!!  I presume you have just started reading this thread!  (BTW,
completing in half a second won't solve the problem if it happens to start a
quarter of a second before time() changes.)

I will not post any more on this, but I can't leave it like this.  That is the
WHOLE POINT of my hypothesized comparison function!!!  To summarize:

I defined when I consider a value to be less than/equal to/greater than another,
and wrote a comparison function that implements this definition.  The function
is completely consistent with this definition.  Whenever it is invoked, it will
return the appropriate and correct value.  This is what the standard requires me
to do, and I have done it.  Any problems should now lie with qsort().  The
standard represents a contract between users and implementors of C.  I have
fulfillled my side of the bargain as a user - now it is the implementor's turn.

This, of course, is unreasonable.  I, of course, completely understand that it
is virtually impossible to implement such a qsort().  However, IMHO, the
standard as written requires it, and so the standard should be fixed - someday
when The Committee has nothing better to do.

--
Peter Curran                               pcurran@inforamp.net