crashing qsort

[richard]

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.

[Derk Gwen]

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.

[Richard Heathfield]

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 : bi****@eton.pow ernet.co.uk
"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

[Chris Torek]

In article <f0************ *************** *****@4ax.com>
richard <[e-mail] e> 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(cons t 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(con st 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) [phone]
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.

[richard]

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 <de******@HotPO P.com>
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]

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

On Thu, 14 Aug 2003 04:36:39 +0000 (UTC), Richard Heathfield
<do******@addre ss.co.uk.invali d> 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]

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 <no****@elf.eng .bsdi.com>
wrote:

In article <f0************ *************** *****@4ax.com>
richard <[e-mail] e> 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(cons t 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(con st 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.

[Philip Riebold]

richard <[e-mail] e> wrote in message news:<f0******* *************** **********@4ax. com>...

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"

[CBFalconer]

*** Evil top-posting corrected ***

richard wrote:

Richard Heathfield <do******@addre ss.co.uk.invali d> 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 (cb********@yah oo.com) (cb********@wor ldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home .att.net> USE worldnet address!

[Ben Pfaff]

richard <[e-mail] e> 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.