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: 20 Jan 2000 17:31:25 GMT
Organization: Aachen University of Technology (RWTH)
Lines: 47
Message-ID: <867gpd$k0u$1@nets3.rz.RWTH-Aachen.DE>
References: <R0Gh4.2371$Ll5 DOT 3502 AT news2 DOT randori DOT com>
NNTP-Posting-Host: acp3bf.physik.rwth-aachen.de
X-Trace: nets3.rz.RWTH-Aachen.DE 948389485 20510 137.226.32.75 (20 Jan 2000 17:31:25 GMT)
X-Complaints-To: abuse AT rwth-aachen DOT de
NNTP-Posting-Date: 20 Jan 2000 17:31:25 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

Kenneth F. Henderson Jr. <KenH AT hughes DOT net> wrote:

> objects to render is sorted.  It looks to be either a bug in qsort()
> or the D2 programmers providing an illegal(???) sort_func (it

Although qsort() is written by humans, like all the other code, i.e.
it may have bugs, I suspect your bug is not inside qsort, but in your
sort function.

[...]
> //The comparison function
> int sort_func(const sort_item *a,const sort_item *b)

For a start, this definition of sort_func is incorrect, strictly
spoken. By definition, comparison functions for qsort are functions
taking two void-pointers, not pointers to some special type of
object. You may cast to object pointers inside the function, but not
use in the argument list itself.

The bigger worry, however, is the following: is this really a valid
comparison function? I.e. does it define an ordering of the input
elements? I haven't analysed it completely, but I doubt it does.
It has to be guaranteed to fulfill the following rules for the
'smaller than' relation it describes:

	IF a<b and b<c   THEN a<c
        NEVER a<b and b<a, at the same time
	
From a glance at the code, I strongly doubt it fulfills the first of
these rules. If so, it may well have been the wrong idea to use qsort,
at all.

[...]
> main()
> {
> 	printf("n_sort_items = %d\n",n_sort_items);
> 	qsort(sort_list,n_sort_items,sizeof(*sort_list),(void *)sort_func);
> }

Of course, that cast of 'sort_func' to (void *) is even worse than its
original incorrect definition. Fix the definition, and you won't have
to cast.


-- 
Hans-Bernhard Broeker (broeker AT physik DOT rwth-aachen DOT de)
Even if all the snow were burnt, ashes would remain.