Need warning-free qsort() comparison functions

Discussion in 'C Programming' started by Charlie Zender, Jan 1, 2004.

  1. 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.
    --
    Charlie Zender, , (949) 824-2987, Department of Earth
    System Science, University of California, Irvine CA 92697-3100
    Visiting NCAR 12/13/03--1/17/04: ***********************************
    Voice/FAX: (303) 497-1724/1348, Office: Mesa Lab 259b **************
     
    Charlie Zender, Jan 1, 2004
    #1
    1. Advertising

  2. Charlie Zender <> writes:

    > 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,
    --
    In order to understand recursion you must first understand recursion.
    Remove /-nsp/ for email.
     
    Paul Pluzhnikov, Jan 1, 2004
    #2
    1. Advertising

  3. Charlie Zender

    CBFalconer Guest

    Charlie Zender wrote:
    >
    > 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.

    --
    Chuck F () ()
    Available for consulting/temporary embedded and systems.
    <http://cbfalconer.home.att.net> USE worldnet address!
     
    CBFalconer, Jan 1, 2004
    #3
  4. Charlie Zender

    Tauno Voipio Guest

    "Charlie Zender" <> wrote in message
    news:...
    > 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
     
    Tauno Voipio, Jan 1, 2004
    #4
  5. Charlie Zender wrote:

    > 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
    --
    My email address is valid, but changes periodically.
    To contact me please use the address from a recent posting.
     
    Kevin Goodsell, Jan 1, 2004
    #5
  6. > return *(const int *)val_1-*(const int *)val_2;

    Ahhh. Cool. Got it.

    Thanks,
    Charlie
    --
    Charlie Zender, , (949) 824-2987, Department of Earth
    System Science, University of California, Irvine CA 92697-3100
    Visiting NCAR 12/13/03--1/17/04: ***********************************
    Voice/FAX: (303) 497-1724/1348, Office: Mesa Lab 259b **************
     
    Charlie Zender, Jan 1, 2004
    #6
  7. "Charlie Zender" <> wrote in message
    news:...
    > 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
     
    Peter Pichler, Jan 1, 2004
    #7
  8. 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() */


    --
    Charlie Zender, , (949) 824-2987, Department of Earth
    System Science, University of California, Irvine CA 92697-3100
    Visiting NCAR 12/13/03--1/17/04: ***********************************
    Voice/FAX: (303) 497-1724/1348, Office: Mesa Lab 259b **************
     
    Charlie Zender, Jan 1, 2004
    #8
  9. Charlie Zender

    Ben Pfaff Guest

    Charlie Zender <> writes:

    > 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.
    --
    "IMO, Perl is an excellent language to break your teeth on"
    --Micah Cowan
     
    Ben Pfaff, Jan 1, 2004
    #9
  10. Charlie Zender

    Al Bowers Guest

    Charlie Zender wrote:

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

    >
    >
    > 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;
    }

    --
    Al Bowers
    Tampa, Fl USA
    mailto: (remove the x to send email)
    http://www.geocities.com/abowers822/
     
    Al Bowers, Jan 2, 2004
    #10
  11. Charlie Zender

    Severian Guest

    On 01 Jan 2004 14:29:27 -0800, Ben Pfaff <> wrote:

    >Charlie Zender <> writes:
    >
    >> 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
     
    Severian, Jan 2, 2004
    #11
  12. Charlie Zender

    Ben Pfaff Guest

    Severian <> writes:

    > 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 :)
    --
    Just another C hacker.
     
    Ben Pfaff, Jan 2, 2004
    #12
  13. Charlie Zender

    Al Bowers Guest

    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;

    --
    Al Bowers
    Tampa, Fl USA
    mailto: (remove the x to send email)
    http://www.geocities.com/abowers822/
     
    Al Bowers, Jan 2, 2004
    #13
  14. Charlie Zender

    Severian Guest

    On 01 Jan 2004 16:23:39 -0800, Ben Pfaff <> wrote:

    >Severian <> writes:
    >
    >> 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 :)


    D'oh. I'll blame it on my new year's hangover!
     
    Severian, Jan 2, 2004
    #14
  15. CBFalconer <> writes:

    > 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?

    --
    Maurizio Loreti http://www.pd.infn.it/~loreti/mlo.html
    Dept. of Physics, Univ. of Padova, Italy ROT13:
     
    Maurizio Loreti, Jan 2, 2004
    #15
  16. Charlie Zender

    CBFalconer Guest

    Maurizio Loreti wrote:
    > CBFalconer <> writes:
    >
    > > 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?


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

    --
    Chuck F () ()
    Available for consulting/temporary embedded and systems.
    <http://cbfalconer.home.att.net> USE worldnet address!
     
    CBFalconer, Jan 2, 2004
    #16
  17. Thanks, I like your return statement best and will adopt it.

    Charlie

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


    --
    Charlie Zender, , (949) 824-2987, Department of Earth
    System Science, University of California, Irvine CA 92697-3100
    Visiting NCAR 12/13/03--1/17/04: ***********************************
    Voice/FAX: (303) 497-1724/1348, Office: Mesa Lab 259b **************
     
    Charlie Zender, Jan 2, 2004
    #17

  18. > 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
    --
    Charlie Zender, , (949) 824-2987, Department of Earth
    System Science, University of California, Irvine CA 92697-3100
    Visiting NCAR 12/13/03--1/17/04: ***********************************
    Voice/FAX: (303) 497-1724/1348, Office: Mesa Lab 259b **************
     
    Charlie Zender, Jan 2, 2004
    #18
  19. On Fri, 2 Jan 2004, Charlie Zender wrote:
    >
    > 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);


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

    -Arthur
     
    Arthur J. O'Dwyer, Jan 2, 2004
    #19
  20. CBFalconer wrote:

    > Maurizio Loreti wrote:
    >> CBFalconer <> writes:
    >>
    >> > 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?

    >
    > 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!

    --
    Richard Heathfield :
    "Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
    C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
    K&R answers, C books, etc: http://users.powernet.co.uk/eton
     
    Richard Heathfield, Jan 3, 2004
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Debashish Chakravarty

    [possibly OT] the comparison function in qsort

    Debashish Chakravarty, Nov 23, 2003, in forum: C Programming
    Replies:
    0
    Views:
    316
    Debashish Chakravarty
    Nov 23, 2003
  2. Ingo Brueckl
    Replies:
    5
    Views:
    485
    Keith Thompson
    Dec 19, 2003
  3. monkeys paw

    qsort warning

    monkeys paw, Apr 27, 2004, in forum: C Programming
    Replies:
    9
    Views:
    3,275
    Ben Pfaff
    Apr 27, 2004
  4. Spoon

    Comparison function in qsort()

    Spoon, Apr 12, 2006, in forum: C Programming
    Replies:
    14
    Views:
    621
    Robert Latest
    Apr 18, 2006
  5. David Mathog

    comparison function for qsort() question

    David Mathog, Jan 30, 2008, in forum: C Programming
    Replies:
    7
    Views:
    485
Loading...

Share This Page