crashing qsort

Discussion in 'C Programming' started by richard, Aug 14, 2003.

  1. richard

    richard Guest

    What might cause qsort to crash?

    I'm using qsort to sort a few thousand items of a not too complex
    structure. Tried it with one data set - worked fine. Tried another
    similarly sized data set and the program dies in the midst of the
    qsort.

    My comparison function doesn't do anything fancy - just some
    strnicmp's and =='s.

    Any idea what I should look for? It's kinda hard to debug something
    that fails in the midst of a library call (a few printf's sprinkled in
    the cmp function didn't reveal anything useful).

    I don't believe it's an out-of-memory issue.

    I'm using MinGW gcc 3.2 on window2k.
     
    richard, Aug 14, 2003
    #1
    1. Advertising

  2. richard

    Derk Gwen Guest

    r# Any idea what I should look for? It's kinda hard to debug something
    # that fails in the midst of a library call (a few printf's sprinkled in
    # the cmp function didn't reveal anything useful).

    If you have anything like gdb or dbx on your system, you can find where it crashes,
    and then backtrack out of the library into your code. You can then check the
    arguments passed in to see if you're passing in invalid arguments, like passing
    in a NULL to a str* routine. Otherwise you need to use the printfs to make sure
    you've isolated in which statement it crashes. At that point print everything
    that can be valid to verify the values are acceptable. For strings, be sure to
    print the address and the contents.

    --
    Derk Gwen http://derkgwen.250free.com/html/index.html
    Raining down sulphur is like an endurance trial, man. Genocide is the
    most exhausting activity one can engage in. Next to soccer.
     
    Derk Gwen, Aug 14, 2003
    #2
    1. Advertising

  3. richard wrote:

    > What might cause qsort to crash?


    Using it improperly.

    > I'm using qsort to sort a few thousand items of a not too complex
    > structure. Tried it with one data set - worked fine. Tried another
    > similarly sized data set and the program dies in the midst of the
    > qsort.
    >
    > My comparison function doesn't do anything fancy - just some
    > strnicmp's and =='s.


    C has no standard strnicmp function.

    > Any idea what I should look for?


    Have a look at your source code. That's where the bug is.

    > It's kinda hard to debug something
    > that fails in the midst of a library call


    Now try closing your eyes, and then try to do what you're asking us to do -
    i.e. debugging your program without being able to see the source code. It's
    even harder, isn't it?

    --
    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, Aug 14, 2003
    #3
  4. richard

    Chris Torek Guest

    In article <>
    richard <> writes:
    >What might cause qsort to crash?


    Any number of things, but I suspect these three are the most common:

    - Passing incorrect input parameters to qsort (invalid "base" pointer,
    wrong "number of elements", or wrong "width of element" values --
    the comparison function pointer will probably be the one you meant
    though :) ).

    - Getting the "type signature" of the comparison function wrong.
    This has two sub-aspects, only one of which bites on today's
    common hardware. Suppose, for instance, you are qsort()ing a
    table of "char *"s. The comparison function's type signature
    must be:

    int(const void *, const void *)

    so passing strcmp -- which is int(const char *, const char *) --
    is incorrect (but due to "same representation" clause, almost
    certain to work anyway for other cases). Worse, the comparison
    function gets *pointers* to the elements to compare, which in our
    case is "pointer to <char *>". Thus this is closer, but still
    wrong:

    int my_compare(char *const *l, char *const *r) {
    return strcmp(*l, *r);
    }

    Here what you need is something like:

    int my_compare(const void *l0, const void *r0) {
    char *const *l = l0;
    char *const *r = r0;

    return strcmp(*l, *r);
    }

    (The difference between these two is not strictly academic,
    and the first version will in fact fail on a Data General
    Eclipse, where "void *" uses a byte pointer but "char *const
    *" uses a word pointer. Since today's 32-bit x86 only has one
    pointer format, and "all the world's a (32-bit) x86", the first
    -- incorrect -- version of my_compare is likely to work ...
    today. As x86-64 variants become common, there will be much
    wailing and gnashing of teeth as people discover that in fact,
    *not* all the world is a 32-bit x86 after all.)

    Finally, and if my crystal ball is working again, the third common
    problem is the one you are actually running into. If a comparison
    function is not 100% consistent in deciding that, when a<b, b>a,
    some qsort() variants will run wild. Hence this:

    int bad_compare(const void *l, const void *r) {
    return (rand() % 3) - 1;
    }

    is a terrible function to use, and causes real qsort()s to run off
    into the weeds.
    --
    In-Real-Life: Chris Torek, Wind River Systems (BSD engineering)
    Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
    email: forget about it http://67.40.109.61/torek/index.html (for the moment)
    Reading email is like searching for food in the garbage, thanks to spammers.
     
    Chris Torek, Aug 14, 2003
    #4
  5. richard

    richard Guest

    I'm passing NULL to a str* routine. I had thought str* was smart
    enough to know this.

    thanks

    On Thu, 14 Aug 2003 03:53:52 -0000, Derk Gwen <>
    wrote:

    >r# Any idea what I should look for? It's kinda hard to debug something
    ># that fails in the midst of a library call (a few printf's sprinkled in
    ># the cmp function didn't reveal anything useful).
    >
    >If you have anything like gdb or dbx on your system, you can find where it crashes,
    >and then backtrack out of the library into your code. You can then check the
    >arguments passed in to see if you're passing in invalid arguments, like passing
    >in a NULL to a str* routine. Otherwise you need to use the printfs to make sure
    >you've isolated in which statement it crashes. At that point print everything
    >that can be valid to verify the values are acceptable. For strings, be sure to
    >print the address and the contents.
     
    richard, Aug 14, 2003
    #5
  6. richard

    richard Guest

    Two other people gave comments that quickly helped me find the
    problem.

    On Thu, 14 Aug 2003 04:36:39 +0000 (UTC), Richard Heathfield
    <> wrote:

    >richard wrote:
    >
    >> What might cause qsort to crash?

    >
    >Using it improperly.
    >
    >> I'm using qsort to sort a few thousand items of a not too complex
    >> structure. Tried it with one data set - worked fine. Tried another
    >> similarly sized data set and the program dies in the midst of the
    >> qsort.
    >>
    >> My comparison function doesn't do anything fancy - just some
    >> strnicmp's and =='s.

    >
    >C has no standard strnicmp function.
    >
    >> Any idea what I should look for?

    >
    >Have a look at your source code. That's where the bug is.
    >
    >> It's kinda hard to debug something
    >> that fails in the midst of a library call

    >
    >Now try closing your eyes, and then try to do what you're asking us to do -
    >i.e. debugging your program without being able to see the source code. It's
    >even harder, isn't it?
     
    richard, Aug 14, 2003
    #6
  7. richard

    richard Guest

    The problem (or at least, the first problem I found) was trying to
    strcmp a NULL.

    fwiw, the comparison function starts:

    int cmp(const void *p1, const void *p2) {
    const Item *sp1 = *(Item * const *)p1;
    const Item *sp2 = *(Item * const *)p2;
    int r;

    r = stricmp(sp1->artist, sp2->artist);
    .....

    and the call to qsort is

    qsort((void *)(list.item), list.entries, sizeof(Item*), cmp);

    list is

    typedef struct {
    int entries;
    Item **item
    } List

    and Item contains char *artist, among other things

    Thank you

    On 14 Aug 2003 03:15:08 -0600, Chris Torek <>
    wrote:

    >In article <>
    >richard <> writes:
    >>What might cause qsort to crash?

    >
    >Any number of things, but I suspect these three are the most common:
    >
    > - Passing incorrect input parameters to qsort (invalid "base" pointer,
    > wrong "number of elements", or wrong "width of element" values --
    > the comparison function pointer will probably be the one you meant
    > though :) ).
    >
    > - Getting the "type signature" of the comparison function wrong.
    > This has two sub-aspects, only one of which bites on today's
    > common hardware. Suppose, for instance, you are qsort()ing a
    > table of "char *"s. The comparison function's type signature
    > must be:
    >
    > int(const void *, const void *)
    >
    > so passing strcmp -- which is int(const char *, const char *) --
    > is incorrect (but due to "same representation" clause, almost
    > certain to work anyway for other cases). Worse, the comparison
    > function gets *pointers* to the elements to compare, which in our
    > case is "pointer to <char *>". Thus this is closer, but still
    > wrong:
    >
    > int my_compare(char *const *l, char *const *r) {
    > return strcmp(*l, *r);
    > }
    >
    > Here what you need is something like:
    >
    > int my_compare(const void *l0, const void *r0) {
    > char *const *l = l0;
    > char *const *r = r0;
    >
    > return strcmp(*l, *r);
    > }
    >
    > (The difference between these two is not strictly academic,
    > and the first version will in fact fail on a Data General
    > Eclipse, where "void *" uses a byte pointer but "char *const
    > *" uses a word pointer. Since today's 32-bit x86 only has one
    > pointer format, and "all the world's a (32-bit) x86", the first
    > -- incorrect -- version of my_compare is likely to work ...
    > today. As x86-64 variants become common, there will be much
    > wailing and gnashing of teeth as people discover that in fact,
    > *not* all the world is a 32-bit x86 after all.)
    >
    >Finally, and if my crystal ball is working again, the third common
    >problem is the one you are actually running into. If a comparison
    >function is not 100% consistent in deciding that, when a<b, b>a,
    >some qsort() variants will run wild. Hence this:
    >
    > int bad_compare(const void *l, const void *r) {
    > return (rand() % 3) - 1;
    > }
    >
    >is a terrible function to use, and causes real qsort()s to run off
    >into the weeds.
     
    richard, Aug 14, 2003
    #7
  8. richard <> wrote in message news:<>...
    > What might cause qsort to crash?
    >
    > I'm using qsort to sort a few thousand items of a not too complex
    > structure. Tried it with one data set - worked fine. Tried another
    > similarly sized data set and the program dies in the midst of the
    > qsort.


    You don't say if the program crashes or just 'hangs'.

    If the latter _AND_ the qsort() you are using uses the quick sort
    algorithm it may be that the data is making it go quadratic, ie.
    taking time proportional to n*n rather than the more usual n*ln(n)

    Try doing a Google search for "A Killer Adversary for Quicksort"
     
    Philip Riebold, Aug 14, 2003
    #8
  9. richard

    CBFalconer Guest

    *** Evil top-posting corrected ***

    richard wrote:
    > Richard Heathfield <> wrote:
    > >richard wrote:
    > >
    > >> What might cause qsort to crash?

    > >
    > > Using it improperly.
    > >
    > >> I'm using qsort to sort a few thousand items of a not too
    > >> complex structure. Tried it with one data set - worked fine.
    > >> Tried another similarly sized data set and the program dies
    > >> in the midst of the qsort.
    > >>
    > >> My comparison function doesn't do anything fancy - just some
    > >> strnicmp's and =='s.

    > >
    > > C has no standard strnicmp function.
    > >
    > >> Any idea what I should look for?

    > >
    > > Have a look at your source code. That's where the bug is.
    > >
    > >> It's kinda hard to debug something
    > >> that fails in the midst of a library call

    > >
    > > Now try closing your eyes, and then try to do what you're
    > > asking us to do -i.e. debugging your program without being
    > > able to see the source code. It's even harder, isn't it?

    >
    > Two other people gave comments that quickly helped me find
    > the problem.


    Which doesn't alter the fact that you posted no code, nor the
    accuracy of RHs comments. Elsewhere you stated you were passing
    NULL to some str*() function. This certainly qualifies as a bug
    in your source code.

    In addition, kindly do NOT toppost in c.l.c. It will rapidly get
    people ticked off in here, and is rude and unsightly.

    --
    Chuck F () ()
    Available for consulting/temporary embedded and systems.
    <http://cbfalconer.home.att.net> USE worldnet address!
     
    CBFalconer, Aug 14, 2003
    #9
  10. richard

    Ben Pfaff Guest

    richard <> writes:

    > I'm passing NULL to a str* routine. I had thought str* was smart
    > enough to know this.


    Nope, most (all?) str*() functions yield undefined behavior on
    null pointer arguments.
    --
    Go not to Usenet for counsel, for they will say both no and yes.
     
    Ben Pfaff, Aug 14, 2003
    #10
  11. richard

    Dan Pop Guest

    In <> richard <> writes:

    >I'm passing NULL to a str* routine. I had thought str* was smart
    >enough to know this.


    And what should a str* function do when passed a null pointer instead of
    a string?

    The language specification clearly says that you cannot pass null pointers
    to functions expecting strings (unless that function's description
    explicitly allows them).

    Dan
    --
    Dan Pop
    DESY Zeuthen, RZ group
    Email:
     
    Dan Pop, Aug 14, 2003
    #11
  12. richard <> writes:
    > On 14 Aug 2003 16:32:34 GMT, (Dan Pop) wrote:
    > >In <> richard
    > ><> writes:
    > >
    > >>I'm passing NULL to a str* routine. I had thought str* was smart
    > >>enough to know this.

    > >
    > >And what should a str* function do when passed a null pointer instead of
    > >a string?

    >
    > If I had a choice, I'd like str* to treat a null pointer as 0 length
    > string, rather than crashing.


    If you think about it, that makes about as much sense as expecting a
    null int pointer to be treated as a pointer to an object with the
    value 0.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    San Diego Supercomputer Center <*> <http://www.sdsc.edu/~kst>
    Schroedinger does Shakespeare: "To be *and* not to be"
     
    Keith Thompson, Aug 14, 2003
    #12
  13. richard

    CBFalconer Guest

    "Arthur J. O'Dwyer" wrote:
    > On Thu, 14 Aug 2003, Neil Cerutti wrote:
    > >

    .... snip ...
    > >
    > > Can you give an example where a str* function treating the null
    > > pointer as "" is useful to you?

    >
    > Sure, I can. I've often wished for the ability to "defer"
    > error checking until the end of a series of operations,
    > rather than stopping after each one to check for NULLs.
    >
    > return strcpy(malloc(100), "hello world");
    >
    > If strcpy(NULL, foo) was a no-op returning NULL, the
    > above would be very useful, instead of incorrect.
    > For example, one could write a Strdup() macro, instead
    > of having to define a function to do it.
    >
    > That's the only example that comes to mind right now,
    > because it came up earlier today. But obviously if
    > str* functions *were* to take NULL in a defined manner,
    > strlen(NULL) would probably have to equal either 0
    > or (size_t)-1, and I would prefer 0. So in that one
    > particular case, str*(NULL) would "act like" str*(""),
    > although for different reasons.


    My implementations of strlcpy and strlcat treat _source_ string
    pointers of NULL as empty strings, but obviously not destination
    pointers. This will disappoint those who want immediate blow-ups
    for such usage. Available at:

    <http://cbfalconer.home.att.net/download/>

    --
    Chuck F () ()
    Available for consulting/temporary embedded and systems.
    <http://cbfalconer.home.att.net> USE worldnet address!
     
    CBFalconer, Aug 15, 2003
    #13
  14. richard wrote:

    > Two other people gave comments that quickly helped me find the
    > problem.


    Is your goal to minimise the pool of people from which you can draw
    assistance by making it as difficult as possible to help you?

    --
    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, Aug 15, 2003
    #14
  15. richard

    Randy Howard Guest

    In article <>,
    says...
    > richard <> writes:
    >
    > > I'm passing NULL to a str* routine. I had thought str* was smart
    > > enough to know this.

    >
    > Nope, most (all?) str*() functions yield undefined behavior on
    > null pointer arguments.


    Perhaps surprisingly, people seem to prefer this behavior as well.
     
    Randy Howard, Aug 15, 2003
    #15
  16. richard

    Daniel Haude Guest

    On Thu, 14 Aug 2003 18:48:44 GMT,
    richard <> wrote
    in Msg. <>

    > If I had a choice, I'd like str* to treat a null pointer as 0 length
    > string, rather than crashing.


    I'd like str* functions to return NULL when passed NULL because that'd be
    useful for malloc()s and strdup()s buried in nested str* function calls.

    Treating NULL as "" is braindead.

    --Daniel


    --
    "With me is nothing wrong! And with you?" (from r.a.m.p)
     
    Daniel Haude, Aug 15, 2003
    #16
  17. On Fri, 15 Aug 2003, CBFalconer wrote:
    >
    > "Arthur J. O'Dwyer" wrote:
    > > On Thu, 14 Aug 2003, Neil Cerutti wrote:
    > > >
    > > > Can you give an example where a str* function treating the null
    > > > pointer as "" is useful to you?

    > >
    > > Sure, I can. I've often wished for the ability to "defer"
    > > error checking until the end of a series of operations,
    > > rather than stopping after each one to check for NULLs.
    > >
    > > return strcpy(malloc(100), "hello world");
    > >
    > > If strcpy(NULL, foo) was a no-op returning NULL, the
    > > above would be very useful, instead of incorrect.
    > > For example, one could write a Strdup() macro, instead
    > > of having to define a function to do it.

    [snip]

    > My implementations of strlcpy and strlcat treat _source_ string
    > pointers of NULL as empty strings, but obviously not destination
    > pointers.


    :) That's exactly the *opposite* of what I consider logical.
    Why on earth would I want to assign *from* something that might
    be NULL? All I can think of would be if I were making a function
    that took a "default" filename or some such by the client's
    passing NULL to the function -- but then I still wouldn't want
    to treat that NULL as if it were "", but "temp.dat" or whatever.

    YMOV.

    -Arthur
     
    Arthur J. O'Dwyer, Aug 15, 2003
    #17
  18. On Fri, 15 Aug 2003, CBFalconer wrote:
    >
    > "Arthur J. O'Dwyer" wrote:
    > > On Fri, 15 Aug 2003, CBFalconer wrote:
    > > > "Arthur J. O'Dwyer" wrote:
    > > > > On Thu, 14 Aug 2003, Neil Cerutti wrote:
    > > > > >
    > > > > > Can you give an example where a str* function treating the
    > > > > > null pointer as "" is useful to you?
    > > > >
    > > > > Sure, I can. I've often wished for the ability to "defer"
    > > > > error checking until the end of a series of operations,
    > > > > rather than stopping after each one to check for NULLs.

    > >
    > > > My implementations of strlcpy and strlcat treat _source_ string
    > > > pointers of NULL as empty strings, but obviously not destination
    > > > pointers.

    > >
    > > :) That's exactly the *opposite* of what I consider logical.

    [snip]

    > For string operations on s, there are generally three cases. 1: s
    > is a valid string pointer; 2: s is NULL, and 3: s is not a valid
    > string pointer.
    >
    > Nobody has any problems with 1. 2 and 3 generally yield undefined
    > behaviour, which may or may not provoke immediate crashes. My
    > attitude is that using 2 to represent an empty string is a
    > suitable resolution of UB, and may well be useful. A developer
    > can easily add an assert statement to catch such usage. I can
    > hardly conceive of a usable assert statement to catch 3.
    >
    > Meanwhile, the behaviour of the routine using NULL is defined for
    > a greater variety of inputs.


    In other words, "Because I can."

    Not "Because the user might want to."

    That's kind of what I expected you'd say. I know it's easy to
    write string functions that do weird things with null pointers,
    but why bother if the behavior is not useful? The only useful
    behavior I can imagine is the behavior that you didn't implement
    because it was hard. :)

    If you'd come back with a code example showing how a user might
    productively *use* the behavior your strlcpy() defines, I'd
    be more mollified.

    -Arthur
     
    Arthur J. O'Dwyer, Aug 15, 2003
    #18
  19. richard

    CBFalconer Guest

    "Arthur J. O'Dwyer" wrote:
    > On Fri, 15 Aug 2003, CBFalconer wrote:
    > >

    .... snip ...
    > >
    > > Meanwhile, the behaviour of the routine using NULL is defined
    > > for a greater variety of inputs.

    >

    .... snip ...
    >
    > If you'd come back with a code example showing how a user might
    > productively *use* the behavior your strlcpy() defines, I'd
    > be more mollified.


    The only choices are: UB on that input, and define the action in
    an orderly manner. It is not a matter of using the behaviour, but
    of avoiding possible nasal demons. If the user doesn't want to
    feed it a NULL, then he should not do so. Nothing is lost.

    However, if you could guarantee that every dereference of a NULL
    pointer in every system would produce an immediate halt and
    diagnostic, I would be perfectly happy not to provide the
    behaviour. All I see in the standard is UB.

    I call this defensive programming. If it avoids an east coast
    blackout every 40 odd years it has paid for itself.

    --
    Chuck F () ()
    Available for consulting/temporary embedded and systems.
    <http://cbfalconer.home.att.net> USE worldnet address!
     
    CBFalconer, Aug 16, 2003
    #19
  20. CBFalconer <> writes:
    [...]
    > The only choices are: UB on that input, and define the action in
    > an orderly manner. It is not a matter of using the behaviour, but
    > of avoiding possible nasal demons. If the user doesn't want to
    > feed it a NULL, then he should not do so. Nothing is lost.
    >
    > However, if you could guarantee that every dereference of a NULL
    > pointer in every system would produce an immediate halt and
    > diagnostic, I would be perfectly happy not to provide the
    > behaviour. All I see in the standard is UB.
    >
    > I call this defensive programming. If it avoids an east coast
    > blackout every 40 odd years it has paid for itself.


    Sorry, but I think treating NULL as "" is counterintuitive -- enough
    so that it's nearly likele to cause a blackout as to prevent one.

    If you want to program defensively, I suggest aborting on NULL rather
    than silently hiding the client's error.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    San Diego Supercomputer Center <*> <http://www.sdsc.edu/~kst>
    Schroedinger does Shakespeare: "To be *and* not to be"
     
    Keith Thompson, Aug 16, 2003
    #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. richard

    Re: qsort and structs and ptrs

    richard, Aug 14, 2003, in forum: C Programming
    Replies:
    0
    Views:
    390
    richard
    Aug 14, 2003
  2. Debashish Chakravarty

    [possibly OT] the comparison function in qsort

    Debashish Chakravarty, Nov 23, 2003, in forum: C Programming
    Replies:
    0
    Views:
    318
    Debashish Chakravarty
    Nov 23, 2003
  3. Ingo Brueckl
    Replies:
    5
    Views:
    486
    Keith Thompson
    Dec 19, 2003
  4. Charlie Zender

    Need warning-free qsort() comparison functions

    Charlie Zender, Jan 1, 2004, in forum: C Programming
    Replies:
    21
    Views:
    1,262
  5. Joe

    qsort question

    Joe, Jan 19, 2004, in forum: C Programming
    Replies:
    8
    Views:
    571
    Paul Hsieh
    Jan 23, 2004
Loading...

Share This Page