non-standard behaviour of qsort on SunOS 5.8?

[arne.muller]

Hello,

I just had to find out that a program that runs fine under linux and
True64 alpha crashed with a segmentation fault under SunOS 5.8. I
drilled down and it appears that if the sun qsort gets a vector in
which all elements are equivalent, my comparsion function raises
SEGSEGV.

The problem seems to be that all elements are the same sun qsort
always passes NULL as the first element to the comparsion function. Is
this standard conform ? Well, I guess I miss something, so here comes
a test:

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

typedef struct {
int n ;
double score;
} DS;

static int cmp(const void *aptr, const void *bptr);

int cmp(const void *aptr, const void *bptr) {
DS *a = *((DS**)aptr);
DS *b = *((DS**)bptr);

return a->score > b->score ? a->score == b->score ? 0 : -1 : 1;
}

int main(int argc, char *argv[]) {
DS** vec;
int i;
int n;
double f;

f = 1.0/(double)RAND_MAX;
n = argc > 0 ? atoi(argv[1]) : 5;
vec = (DS**)malloc(n * sizeof(DS*));
for ( i=0; i<n; i++ ) {
vec = (DS*)malloc(sizeof(DS));
if ( argv[2][0] == 'a' ) {
vec->score = rand()*f;
} else if ( argv[2][0] == 'b' ) {
vec->score = 3.123;
} else if ( argv[2][0] == 'c' ) {
vec->score = 3.123;
}
fprintf(stderr, "score = %f\n", vec->score);
}
if ( argv[2][0] == 'c' ) vec[0]->score = 445.6;
qsort(vec, n, sizeof(DS*), cmp);
fputs("*** sorted *** \n", stderr);
for ( i=0; i<n; i++ ) {
fprintf(stderr, "score = %f\n", vec->score);
}

return 0;
}

Then:

cc -g -o testit testit.c

running this on sunOS 5.8 gives:

3 random values are sorted
$$ ./testit 3 a
score = 0.513871
score = 0.175726
score = 0.308634
*** sorted ***
score = 0.513871
score = 0.308634
score = 0.175726

3 values (all the same) are sorted
$$ ./testit 3 b
score = 3.123000
score = 3.123000
score = 3.123000
Segmentation Fault

3 values (all but but) are the same
$$ ./testit 3 c
score = 3.123000
score = 3.123000
score = 3.123000
*** sorted ***
score = 445.600000
score = 3.123000
score = 3.123000

in gdb I found out that:

score = 3.123000
score = 3.123000
score = 3.123000

Program received signal SIGSEGV, Segmentation fault.
0x0001091c in cmp (aptr=0x2111c, bptr=0x21124) at testit.c:15
15 return a->score > b->score ? a->score == b->score ? 0 : -1 :
1;
(gdb) print a
$1 = (DS *) 0x0
(gdb) print b
$2 = (DS *) 0x21150
(gdb)

so the pointer passed to the cmp function are not NULL, but 'a' is NULL
(i.g. the de-referenced aptr). In my situtqtion I have a list of
structure to be sorted on the 'score' attribute, so I realy need a
pointer to DS structrue, and it happenes that sometimes there are only
a few elements in the array and they have the same score.

I realy got stuck here, any ideas wha's going on, and why other systems
(win32 with gcc, linux with gcc, True64 with cc) are more forgiving?

thanks for your help
+kind regards,

Arne

ps: I read http://c-faq.com/lib/qsort2.html (comp.lang.c FAQ list ·
Question 13.9) but still seem to miss the point ...

 

[Martin Ambuhl]

Hello,

I just had to find out that a program that runs fine under linux and
True64 alpha crashed with a segmentation fault under SunOS 5.8. I
drilled down and it appears that if the sun qsort gets a vector in
which all elements are equivalent, my comparsion function raises
SEGSEGV.

The problem seems to be that all elements are the same sun qsort
always passes NULL as the first element to the comparsion function. Is
this standard conform ? Well, I guess I miss something, so here comes
a test:

Among other things (overlooking the silly forms of the malloc calls and
qsort calls, incorrect and misleading tests on argc, excessive casting,
etc.), try fixing this nonsensical return statement:

int cmp(const void *aptr, const void *bptr) {
DS *a = *((DS**)aptr);
DS *b = *((DS**)bptr);

return a->score > b->score ? a->score == b->score ? 0 : -1 : 1;
}

There are no prizes given for obfuscating your code, and I fear that the
main victim of your game is you.

 

[arne.muller]

Thanks, for your reply (even though I feel a bit like a school boy
beeing bullied by his teacher) ... .

please see below ..

Among other things (overlooking the silly forms of the malloc calls and
qsort calls, incorrect and misleading tests on argc, excessive casting,
etc.), try fixing this nonsensical return statement:

Well, the casting seems to be the only way to get around warnings about
incompatible types in cmp.

What's wrong/silly with the malloc? It's just an example from a larger
framework.

ok, I got it, this is indeed stupid, but I wonder how gcc with warings
enabled could let this happen (probably silently reapired by faulty
code;-). It actually gave the correct results.

There are no prizes given for obfuscating your code, and I fear that the
main victim of your game is you.

thanks!

 

[Richard Heathfield]

(e-mail address removed) said:

Thanks, for your reply (even though I feel a bit like a school boy
beeing bullied by his teacher) ... .

That's Martin for you. Don't let his style discourage you from taking his
advice. He knows his stuff. And he may be a grumpy old curmudgeon, but he's
*our* grumpy old curmudgeon!

Martin Ambuhl wrote:

Well, the casting seems to be the only way to get around warnings about
incompatible types in cmp.

See below.

What's wrong/silly with the malloc? It's just an example from a larger
framework.

vec = (DS**)malloc(n * sizeof(DS*));

is gerharsterly.

vec = malloc(n * sizeof *vec);

is much cleaner.

int cmp(const void *aptr, const void *bptr) {
const DS *a = aptr;
const DS *b = bptr;
return (a->score < b->score) - (a->score > b->score);
}

I don't know which way up you want the array. If the above makes the array
come out upside-down, replace the return with:

return (a->score > b->score) - (a->score < b->score);

 

[lawrence.jones]

int cmp(const void *aptr, const void *bptr) {
DS *a = *((DS**)aptr);
DS *b = *((DS**)bptr);

return a->score > b->score ? a->score == b->score ? 0 : -1 : 1;
}

Your comparison function is defective, it returns -1 if a > b and 1 if
a <= b, which is invalid (hence the crash). You probably meant:

return a->score > b->score ? 1 : a->score == b->score ? 0 : -1;

On the other hand, it's probably clearer and less error prone to write:

if (a->score > b->score) return 1;
if (a->score < b->score) return -1;
return 0;

It's also easier to extend to multiple keys, should you need to do so in
the future.

-Larry Jones

I don't NEED to compromise my principles, because they don't have
the slightest bearing on what happens to me anyway. -- Calvin

 

[Martin Ambuhl]

That's Martin for you. Don't let his style discourage you from taking his
advice. He knows his stuff. And he may be a grumpy old curmudgeon, but he's
*our* grumpy old curmudgeon!

I tried warning people of this, posting for several weeks as "Knemon"
(e-mail address removed). The triple hint (grouch in two languages and the
name of the grouch in Menander's play) seems to have worked: newgroups
that have frequent responses to "Martin Ambuhl" (e-mail address removed)
had almost none to the nom-de-net. My excursion into the land of
pseudonymous posting has ended.

 

[arne.muller]

Dear Richard,

(e-mail address removed) said:


That's Martin for you. Don't let his style discourage you from taking his
advice. He knows his stuff. And he may be a grumpy old curmudgeon, but he's
*our* grumpy old curmudgeon!

thanks for your reply (don't worry I won't give up so easily... ;-)

See below.


vec = (DS**)malloc(n * sizeof(DS*));

is gerharsterly.

vec = malloc(n * sizeof *vec);

is much cleaner.

Ok, I get it - I don't have to cast these pointers explicitely (because
the compiler is smart enough to work this out?), and indeed the 'sizeof
variable' looks nicer, too.

int cmp(const void *aptr, const void *bptr) {
const DS *a = aptr;
const DS *b = bptr;
return (a->score < b->score) - (a->score > b->score);
}

Sorry, I think there's a mis-understanding due to my wrong code. This
is the simplified version:

int cmp(const void *aptr, const void *bptr) {
DS *a = *((DS* const*)aptr);
DS *b = *((DS* const*)bptr);

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

int main(int argc, char *argv[]) {
DS **vec;
int i;
double f;

f = 1.0/RAND_MAX;
vec = malloc(5 * sizeof *vec); /* vector with 5 pointers to DS */
for ( i=0; i<5; i++ ) {
/* get the DS and let vec point to it */
vec = malloc(sizeof(DS));
vec->score = rand()*f;
fprintf(stderr, "score = %f\n", vec->score);
}
qsort(vec, 5, sizeof *vec, cmp);
fputs("*** sorted *** \n", stderr);
for ( i=0; i<5; i++ ) {
fprintf(stderr, "score = %f\n", vec->score);
}

return 0;
}

What I want is that vec is a pointer of pointers to DS structures. I my
real application I've pointers to structures similar to DS that need to
be malloced malloc'ed separately as above. I then have an array of 5
pointers to these strucutres, and I'd like to sort these pointers
according to the structrues they're poiting to. Well, I find this
rather complicated, so if you could once more simplify my code ;-)

Your assignment in const DS *a = aptr; a would still be the pointer to
the pointer of DS, no? I've tested it, and the code compiles without
warnings, but it does not do the proper sor but the binary does not
crash (though this doesn't mean the code is correct ...).

This is actually very similar to the example in the comp.lang.c fag
q13.9 (at least that's what I think).

I don't know which way up you want the array. If the above makes the array
come out upside-down, replace the return with:

return (a->score > b->score) - (a->score < b->score);

Well, I guess I'm still lost ... :-(

thanks,

Arne

 

[Keith Thompson]

int main(int argc, char *argv[]) {
DS **vec; [...]
vec = malloc(5 * sizeof *vec); /* vector with 5 pointers to DS */ [...]
What I want is that vec is a pointer of pointers to DS structures. I my
real application I've pointers to structures similar to DS that need to
be malloced malloc'ed separately as above. I then have an array of 5
pointers to these strucutres, and I'd like to sort these pointers
according to the structrues they're poiting to.

The phrase "a pointer of pointers" doesn't make sense. What you want,
I think, is for vec to be a pointer to (the first element of) an array
of pointers to DS structures. (A pointer to the first element of an
array is often referred to as a pointer to the array. Strictly
speaking, this is incorrect; C does have pointers to array, and
they're a different thing -- and not often useful.)

You might want to read section 6 of the comp.lang.c FAQ,
<http://www.c-faq.com/>.

 

[Richard Heathfield]

(e-mail address removed) said:

Sorry, I think there's a mis-understanding due to my wrong code.

The only other possibility I can think of is that you are sorting an array
of pointers to DS, in which case I presume you'll want to do this:

int cmp(const void *aptr, const void *bptr) {
DS* const *a = aptr;
DS* const *b = bptr;
return (a[0]->score < b[0]->score) - (a[0]->score > b[0]->score);
}

(Not tested.)

 

[=?ISO-8859-1?Q?=22Nils_O=2E_Sel=E5sdal=22?=]

(e-mail address removed) said:


That's Martin for you. Don't let his style discourage you from taking his
advice. He knows his stuff. And he may be a grumpy old curmudgeon, but he's
*our* grumpy old curmudgeon!



See below.


vec = (DS**)malloc(n * sizeof(DS*));

is gerharsterly.

vec = malloc(n * sizeof *vec);

is much cleaner.


int cmp(const void *aptr, const void *bptr) {
const DS *a = aptr;
const DS *b = bptr;
return (a->score < b->score) - (a->score > b->score);
}

I don't know which way up you want the array. If the above makes the array
come out upside-down, replace the return with:

return (a->score > b->score) - (a->score < b->score);

He does however have an array of /pointers/ to DS objects, so this
compare function will not do.

 

[arne.muller]

Thanks for your reply,

I've defenetely already learned one important thing from this thread:
Keep it simple (very simple if possible) ... . Complexity such as
MyType ***x (luckily) do not seem to be considered good style ...

int main(int argc, char *argv[]) {
DS **vec; [...]
vec = malloc(5 * sizeof *vec); /* vector with 5 pointers to DS */ [...]
What I want is that vec is a pointer of pointers to DS structures. I my
real application I've pointers to structures similar to DS that need to
be malloced malloc'ed separately as above. I then have an array of 5
pointers to these strucutres, and I'd like to sort these pointers
according to the structrues they're poiting to.

The phrase "a pointer of pointers" doesn't make sense. What you want,
I think, is for vec to be a pointer to (the first element of) an array
of pointers to DS structures. (A pointer to the first element of an
array is often referred to as a pointer to the array. Strictly
speaking, this is incorrect; C does have pointers to array, and
they're a different thing -- and not often useful.)

You might want to read section 6 of the comp.lang.c FAQ,
<http://www.c-faq.com/>.

Well, I've chosen bad terminology, and what you're writing makes sense.
Question 6.13 of the faq explains this very well (thanks "*pointing" it
out ;-). The faq says:

"Instead of a pointer to an array, consider using a pointer to one of
the array's elements."

In my case
DS **vec is equivalent to DS *vec[] right? And

vec = malloc(5 * sizeof *vec); /* vector with 5 pointers to DS */

points to the first element of vec[] ...

So I guess I can be happy with my code?

Arne

 

[Keith Thompson]

Keith Thompson wrote: [...]

You might want to read section 6 of the comp.lang.c FAQ,
<http://www.c-faq.com/>.

Well, I've chosen bad terminology, and what you're writing makes sense.
Question 6.13 of the faq explains this very well (thanks "*pointing" it
out ;-). The faq says:

"Instead of a pointer to an array, consider using a pointer to one of
the array's elements."

In my case
DS **vec is equivalent to DS *vec[] right? And

What? No, it's not equivalent.

DS **vec declared vec as a pointer to pointer to DS.

DS *vec[] declares vec as an array (of unspecified size) of pointers
to DS.

Arrays are not pointers. Pointers are not arrays.

What sometimes causes confusion is that (a) in most contexts, an array
expression is implicitly converted to the address of the array's first
element, and (b) in a function parameter declaration, "foo bar[]"
really means "foo *bar".

 

[arne.muller]

Hello,

"Instead of a pointer to an array, consider using a pointer to one of
the array's elements."

In my case
DS **vec is equivalent to DS *vec[] right? And

What? No, it's not equivalent.

DS **vec declared vec as a pointer to pointer to DS.

DS **vec declares vec as an array (of unspecified size) of pointers
to DS.

Arrays are not pointers. Pointers are not arrays.

What sometimes causes confusion is that (a) in most contexts, an array
expression is implicitly converted to the address of the array's first
element, and (b) in a function parameter declaration, "foo bar[]"
really means "foo *bar".

ok, but in a function body, such as

int main(int argc, char *argv[]) {

DS **vec1;
DS *vec2[5];

the array length must be specified, whereas in the function argument
list as in main it's not (as you pointed out above - I'd just like to
be sire that I understood this correctly ...). So you can't have a
dyamically allocated *array* declared in the function's body, you must
use a pointer?

regards,

Arne

 

[Richard Heathfield]

(e-mail address removed) said:

Keith Thompson wrote:

What sometimes causes confusion is that (a) in most contexts, an array
expression is implicitly converted to the address of the array's first
element, and (b) in a function parameter declaration, "foo bar[]"
really means "foo *bar".

ok, but in a function body, such as

int main(int argc, char *argv[]) {

DS **vec1;
DS *vec2[5];

the array length must be specified,

Yes, because you're telling the compiler how many elements you want the
array to have.

whereas in the function argument
list as in main it's not (as you pointed out above - I'd just like to
be sire that I understood this correctly ...).

Right, because the array already exists, so presumably you know how many
elements it has, and presumably you will provide the function with that
information. For example, in main, argv is a pointer to the first element
in an array of char *, and argc tells you how many elements in that array
are valid - i.e. it's okay to deref any of the pointers argv[0] through
argv[argc - 1].

So you can't have a
dyamically allocated *array* declared in the function's body, you must
use a pointer?

The only way to create a dynamically allocated array is to call malloc,
calloc, or realloc. Each of these functions, if successful, returns a
pointer to the allocated space. You can pass this pointer around to various
functions, but it's always a pointer, never an array. It just happens that
C's syntax allows you to treat it, most of the time, as if it were an
array. (I say "most of the time" because, for example, you can't get the
"array"'s size using sizeof, and there are one or two other nit-pickinesses
to consider, too, which a relative beginner is unlikely to encounter at
first.)

 

[Barry Schwarz]

Hello,

"Instead of a pointer to an array, consider using a pointer to one of
the array's elements."

In my case
DS **vec is equivalent to DS *vec[] right? And

What? No, it's not equivalent.

DS **vec declared vec as a pointer to pointer to DS.

DS **vec declares vec as an array (of unspecified size) of pointers
to DS.

Arrays are not pointers. Pointers are not arrays.

What sometimes causes confusion is that (a) in most contexts, an array
expression is implicitly converted to the address of the array's first
element, and (b) in a function parameter declaration, "foo bar[]"
really means "foo *bar".

ok, but in a function body, such as

int main(int argc, char *argv[]) {

DS **vec1;
DS *vec2[5];

the array length must be specified, whereas in the function argument

The array size need not be specified if the compiler can determine the
size from other information, such as an initialization list.

list as in main it's not (as you pointed out above - I'd just like to
be sire that I understood this correctly ...). So you can't have a

Because in this case you are not receiving an array but a pointer.

dyamically allocated *array* declared in the function's body, you must
use a pointer?

If you have a C99 compiler, you can use variable length arrays that
need not be defined until your program determines the size at run
time. You still have to specify the length, it just needn't be
constant.


Remove del for email

 

[Simon Biber]

(e-mail address removed) said:

Sorry, I think there's a mis-understanding due to my wrong code.

The only other possibility I can think of is that you are sorting an array
of pointers to DS, in which case I presume you'll want to do this:

int cmp(const void *aptr, const void *bptr) {
DS* const *a = aptr;
DS* const *b = bptr;
return (a[0]->score < b[0]->score) - (a[0]->score > b[0]->score);
}

This is one of the first elegant pieces of code I learnt on comp.lang.c.
Once I saw a cast-less qsort compare function I was hooked.

It's one of the few places where I use the keyword const other than at
the beginning of a declaration.

Too many C tutorials still recommend ghastly things like casting cmp
function pointers...
int fcmp(DS **a, DS **b);
qsort(base, nelem, width, (int(*)(const void*,const void*))fcmp);

Now I avoid casts wherever possible. About the only place I still use
them are in arguments to <ctype.h> functions (is_____ and to_____) and
when printing pointers or size_t arguments with printf. It's a pity I
still can't rely on C libraries to get %zu right.

 

[Richard Heathfield]

Simon Biber said:

int cmp(const void *aptr, const void *bptr) {
DS* const *a = aptr;
DS* const *b = bptr;
return (a[0]->score < b[0]->score) - (a[0]->score > b[0]->score);
}

This is one of the first elegant pieces of code I learnt on comp.lang.c.
Once I saw a cast-less qsort compare function I was hooked.

Yeah. I once showed, in a clc article, how to do[1] a comparison function,
complete with cast, and someone (quite rightly) replied something like
"wouldn't it be easier to just do this properly?" It took another round or
so before I found out what he meant but, when I did, it was definitely an
"Aah!" moment for me.



[1] actually, how not to do...

 

[Ben Pfaff]

Simon Biber said:

int cmp(const void *aptr, const void *bptr) {
DS* const *a = aptr;
DS* const *b = bptr;
return (a[0]->score < b[0]->score) - (a[0]->score > b[0]->score);
}

This is one of the first elegant pieces of code I learnt on comp.lang.c.
Once I saw a cast-less qsort compare function I was hooked.

Yeah. I once showed, in a clc article, how to do[1] a comparison function,
complete with cast, and someone (quite rightly) replied something like
"wouldn't it be easier to just do this properly?" It took another round or
so before I found out what he meant but, when I did, it was definitely an
"Aah!" moment for me.

I have actually received multiple (two? three?) bug reports
against my binary trees library that turned out to be due to the
reporter having tried to implement the comparison function in
terms of a subtraction that could overflow.

The more code I write, the less clever I get.