Need warning-free qsort() comparison functions

[Charlie Zender]

Hi,

I am unable to define an acceptable function argument to qsort() that
does not trigger compiler warnings.
The following function, compare_ints(), compares two integers and returns
an integer [<,=,>] 0 iff val_1 [<,==,>] val_2.
This code is stolen from http://www.cplusplus.com/ref/cstdlib/qsort.html.
The function is used as an argument to ANSI C qsort() routine in stdlib.h.

int
compare_ints(const void *val_1,const void *val_2)
{
return *(int *)val_1-*(int *)val_2;
}

However, GCC 3.3.1 produces this warning when it compiles compare_ints()
with all paranoid, pedantic debugging switches activated (see below):

foo.c: In function `compare_ints':
foo.c:4: warning: cast discards qualifiers from pointer target type

1. How may this comparison function be re-written so that it does not
trigger this warning?
Changing the function prototype is not acceptable, since the function
must be a valid argument to qsort(). However, any method of changing
the function contents, while preserving its functionality, is fair
game. The same problem afflicts the analogous comparison functions I
have for comparing char's, strings, structures.

2. What exactly is unsafe or dangerous in the existing definition?
i.e., what causes the warning in the first place?

Any help appreciated,
Charlie

The exact compile command is

gcc -std=c99 -pedantic -Wall -Wunused -Werror -W -Wmissing-prototypes
-Wconversion -Wshadow -Wpointer-arith -Wcast-qual -Wcast-align
-Wwrite-strings -c -o foo.o foo.c

This is basically what GSL recommendsd for scientific codes.

 

[Paul Pluzhnikov]

1. How may this comparison function be re-written so that it does not
trigger this warning?

return *(const int *)val_1-*(const int *)val_2;
^^^^^ ^^^^^

2. What exactly is unsafe or dangerous in the existing definition?
i.e., what causes the warning in the first place?

There is nothing dangerous about it.
What causes the warning is the fact that you *explicitly* asked to
be warned about it with '-Wcast-qual'. From 'info gcc':

`-Wcast-qual'
Warn whenever a pointer is cast so as to remove a type qualifier
from the target type. For example, warn if a `const char *' is
cast to an ordinary `char *'.

Cheers,

 

[CBFalconer]

I am unable to define an acceptable function argument to qsort()
that does not trigger compiler warnings.
.... snip ...

int
compare_ints(const void *val_1,const void *val_2)
{
return *(int *)val_1-*(int *)val_2;
}

However, GCC 3.3.1 produces this warning when it compiles

.... snip ...

int
compare_ints(const void *val_1,const void *val_2)
{
const int *i1p = val_1, i2p = val_2;

return *i1p - *i2p;
}

Look ma, no casts! However the returned expression is suspect and
subject to undefined behaviour. Better would be something like:

return (*i1p > *i2p) - (*i1p < *i2p);

Gcc is likely to optimize away any actual sign of i1p and i2p.

 

[Tauno Voipio]

Hi,

I am unable to define an acceptable function argument to qsort() that
does not trigger compiler warnings.
The following function, compare_ints(), compares two integers and returns
an integer [<,=,>] 0 iff val_1 [<,==,>] val_2.
This code is stolen from http://www.cplusplus.com/ref/cstdlib/qsort.html.
The function is used as an argument to ANSI C qsort() routine in stdlib.h.

int
compare_ints(const void *val_1,const void *val_2)
{
return *(int *)val_1-*(int *)val_2;
}

However, GCC 3.3.1 produces this warning when it compiles compare_ints()
with all paranoid, pedantic debugging switches activated (see below):

foo.c: In function `compare_ints':
foo.c:4: warning: cast discards qualifiers from pointer target type

If you cast a const thing to a non-const thing, it's absolutely correct to
warn of a potentionally bad operation. A cast non-const thing may be
changed, but the original pointer target is cannot be changed.

Make your int casts to const int casts.

HTH

Tauno Voipio
tauno voipio @ iki fi

 

[Kevin Goodsell]

Hi,

I am unable to define an acceptable function argument to qsort() that
does not trigger compiler warnings.
The following function, compare_ints(), compares two integers and returns
an integer [<,=,>] 0 iff val_1 [<,==,>] val_2.
This code is stolen from http://www.cplusplus.com/ref/cstdlib/qsort.html.
The function is used as an argument to ANSI C qsort() routine in stdlib.h.

int
compare_ints(const void *val_1,const void *val_2)
{
return *(int *)val_1-*(int *)val_2;
}

This is not a particularly good comparison function, for a few reasons.

However, GCC 3.3.1 produces this warning when it compiles compare_ints()
with all paranoid, pedantic debugging switches activated (see below):

foo.c: In function `compare_ints':
foo.c:4: warning: cast discards qualifiers from pointer target type

That's true, but hardly the biggest concern in this case, I think.

1. How may this comparison function be re-written so that it does not
trigger this warning?

int compare_ints(const void *val_1, const void *val_2)
{
const int *v1 = val_1, *v2 = val_2;
if (*v1 < *v2) return -1;
if (*v1 > *v2) return 1;
return 0;
}

This version also does not risk undefined behavior due to integer
overflow, and uses no casts.

Changing the function prototype is not acceptable, since the function
must be a valid argument to qsort(). However, any method of changing
the function contents, while preserving its functionality, is fair
game. The same problem afflicts the analogous comparison functions I
have for comparing char's, strings, structures.

2. What exactly is unsafe or dangerous in the existing definition?
i.e., what causes the warning in the first place?

Discarding a cv (const-volatile) qualifier. I don't know if this is a
required diagnostic, but it's generally a good one. The point is that
the 'const' in 'const void *' says "the thing pointed to should not be
modified." When you remove that 'const' by casting to 'int *' (as
opposed to 'const int *') you allow the possibility of modifying the
stuff that is pointed to.

-Kevin

 

[Charlie Zender]

return *(const int *)val_1-*(const int *)val_2;

Ahhh. Cool. Got it.

Thanks,
Charlie

 

[Peter Pichler]

Hi,

I am unable to define an acceptable function argument to qsort() that
does not trigger compiler warnings.
The following function, compare_ints(), compares two integers and returns
an integer [<,=,>] 0 iff val_1 [<,==,>] val_2.
This code is stolen from http://www.cplusplus.com/ref/cstdlib/qsort.html.
The function is used as an argument to ANSI C qsort() routine in stdlib.h.

int
compare_ints(const void *val_1,const void *val_2)
{
return *(int *)val_1-*(int *)val_2;
}

However, GCC 3.3.1 produces this warning when it compiles compare_ints()
with all paranoid, pedantic debugging switches activated (see below):

foo.c: In function `compare_ints':
foo.c:4: warning: cast discards qualifiers from pointer target type

1. How may this comparison function be re-written so that it does not
trigger this warning?

How about return *(const int *)val_1-*(const int *)val_2; ?
The qualifiers you are casting away (discarding) are 'const'.

2. What exactly is unsafe or dangerous in the existing definition?
i.e., what causes the warning in the first place?

Casting const away is almost always daangerous and usually a sign of bad
design.

Peter

 

[Charlie Zender]

Thanks, I ended up combining yours and Godsell's recommendations into
comparison functions like the following:

int /* O [enm] Comparison result [<,=,>] 0 iff val_1 [<,==,>] val_2 */
nco_cmp_int /* [fnc] Compare two integers */
(const void *val_1, /* I [nbr] Number to compare */
const void *val_2) /* I [nbr] Number to compare */
{
/* Purpose: Compare two integers
Function is suitable for argument to ANSI C qsort() routine in
stdlib.h
Code based on responses to my comp.lang.c thread 20040101 */
const int * const val_1_ip=val_1;
const int * const val_2_ip=val_2;
return (*val_1_ip > *val_2_ip) - (*val_1_ip < *val_2_ip);
} /* end nco_cmp_int() */

 

[Ben Pfaff]

int /* O [enm] Comparison result [<,=,>] 0 iff val_1 [<,==,>] val_2 */
nco_cmp_int /* [fnc] Compare two integers */
(const void *val_1, /* I [nbr] Number to compare */
const void *val_2) /* I [nbr] Number to compare */
{
/* Purpose: Compare two integers
Function is suitable for argument to ANSI C qsort() routine in
stdlib.h
Code based on responses to my comp.lang.c thread 20040101 */
const int * const val_1_ip=val_1;
const int * const val_2_ip=val_2;
return (*val_1_ip > *val_2_ip) - (*val_1_ip < *val_2_ip);
} /* end nco_cmp_int() */

Do you really find code with that comment style readable? It
looks pretty bad to me.

 

[Al Bowers]

Ahhh. Cool. Got it.

No. Others have pointed out that this is a dangerous statement.
You have the possibility of integer underflow(overflow).
In addition, there are other problems with the code.
To correct the code:

/* qsort example */
#include <stdio.h>
#include <stdlib.h>

int compare (const void * a, const void * b)
{
const int *i1 = a, *i2 = b;
return *i1<*i2?-1*i1>*i2);
}

int main ()
{
int n,values[] = { 40, 10, 100, 90, 20, 25 };
qsort (values, 6, sizeof(int), compare);
for (n=0; n<6; n++)
printf ("%d ",values[n]);
putchar('\n');
return 0;
}

 

[Severian]

int /* O [enm] Comparison result [<,=,>] 0 iff val_1 [<,==,>] val_2 */
nco_cmp_int /* [fnc] Compare two integers */
(const void *val_1, /* I [nbr] Number to compare */
const void *val_2) /* I [nbr] Number to compare */
{
/* Purpose: Compare two integers
Function is suitable for argument to ANSI C qsort() routine in
stdlib.h
Code based on responses to my comp.lang.c thread 20040101 */
const int * const val_1_ip=val_1;
const int * const val_2_ip=val_2;
return (*val_1_ip > *val_2_ip) - (*val_1_ip < *val_2_ip);
} /* end nco_cmp_int() */

Do you really find code with that comment style readable? It
looks pretty bad to me.

Pretty much gave me a headache too.

I would prefer:

int compints(const void *p1, const void *p2)
{
const int *pi1, *pi2;
return *pi1 - *pi2;
}

Of course if you're convinced that the things being compared may not
really be signed ints, or would result in overflow, you could use an
actual comparison, as Goodsell recommended.

Wherefore any comments? If someone can't understand what that code is
doing, they have no reason to be looking at it!

- Sev

 

[Ben Pfaff]

I would prefer:

int compints(const void *p1, const void *p2)
{
const int *pi1, *pi2;
return *pi1 - *pi2;
}

I'd prefer to see pi1 and pi2 initialized

 

[Al Bowers]

Severian wrote:

I would prefer:

int compints(const void *p1, const void *p2)
{
const int *pi1, *pi2;
return *pi1 - *pi2;
}

Of course if you're convinced that the things being compared may not
really be signed ints, or would result in overflow, you could use an
actual comparison, as Goodsell recommended.

Wherefore any comments?

As written, function compints is flawed.
ITYM
const int *pi1 = p1, *pi2 = p2;

 

[Severian]

I'd prefer to see pi1 and pi2 initialized

D'oh. I'll blame it on my new year's hangover!

 

[Maurizio Loreti]

int
compare_ints(const void *val_1,const void *val_2)
{
const int *i1p = val_1, i2p = val_2;

I think you mean "const int *i1p = val_1, *i2p = val_2;", don't you?

 

[CBFalconer]

I think you mean "const int *i1p = val_1, *i2p = val_2;", don't you?

It's all the fault of this contrary keyboard. Never trust
them, verify everything.

 

[Charlie Zender]

Thanks, I like your return statement best and will adopt it.

Charlie

 

[Charlie Zender]

Do you really find code with that comment style readable?
Yes

It looks pretty bad to me.

That is probably because it is very dense.
With good syntax highlighting (e.g., Emacs), you get used to it.
I realize it is non-standard but it works for me for scientific programming.
Without documenting the input/output characteristics of the arguments,
and their "dimensional units", I would soon be lost.

Charlie

 

[Arthur J. O'Dwyer]

Thanks, I like your return statement best and will adopt it.

But please please PLEASE add some whitespace to it!

return (*i1 < *i2)? -1: (*i1 > *i2);

-Arthur

 

[Richard Heathfield]

It's all the fault of this contrary keyboard. Never trust
them, verify everything.

This is truer than it should be. My keyboard (of which I am very fond, and
about which I will not hear a word raised in anger) occasionally takes it
upon itself to insert random characters in the stream. For example, when I
indulge in that very bad habit of travelling long distances up with the
cursor keys in insert mode (instead of typing, say, ESC39k, as God
intended), it will slide a surreptitious 8 into the text. Downwards? 2,
naturally. You may even have seen examples of this in my Usenet articles on
occasion.

Also, occasionally, the shift key gets stuck, and needs an additional tap to
unstick it. Perversely, this doesn't matter so much in insert mode, since I
CAN AT LEast see that it's happened, so I can correct for it. But when I'm
in command mode, it can get a bit - um, thank heaven for ESC:q!