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.

 

[Richard Heathfield]

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?

 

[Chris Torek]

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]

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

thanks

 

[richard]

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

 

[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

 

[Philip Riebold]

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

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.

 

[Ben Pfaff]

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.

 

[Dan Pop]

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

 

[Keith Thompson]

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.

 

[CBFalconer]

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

 

[Richard Heathfield]

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?

 

[Randy Howard]

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

Perhaps surprisingly, people seem to prefer this behavior as well.

 

[Daniel Haude]

On Thu, 14 Aug 2003 18:48:44 GMT,

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

 

[Arthur J. O'Dwyer]

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]

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

 

[CBFalconer]

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

 

[Keith Thompson]

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.