prev up next   top/contents search

comp.lang.c FAQ list · Question 13.9

Q: Now I'm trying to sort an array of structures with qsort. My comparison function takes pointers to structures, but the compiler complains that the function is of the wrong type for qsort. How can I cast the function pointer to shut off the warning?

A: The conversions must be in the comparison function, which must be declared as accepting ``generic pointers'' (const void *) as discussed in question 13.8 above. For a hypothetical little date structure

struct mystruct {
	int year, month, day;
the comparison function might look like [footnote]
int mystructcmp(const void *p1, const void *p2)
	const struct mystruct *sp1 = p1;
	const struct mystruct *sp2 = p2;
	if(sp1->year < sp2->year) return -1;
	else if(sp1->year > sp2->year) return 1;
	else if(sp1->month < sp2->month) return -1;
	else if(sp1->month > sp2->month) return 1;
	else if(sp1->day < sp2->day) return -1;
	else if(sp1->day > sp2->day) return 1;
	else return 0;
(The conversions from generic pointers to struct mystruct pointers happen in the initializations sp1 = p1 and sp2 = p2; the compiler performs the conversions implicitly since p1 and p2 are void pointers.)

For this version of mystructcmp, the call to qsort might look like

#include <stdlib.h>
struct mystruct dates[NDATES];
int ndates;
/* ndates cells of dates[] are to be sorted */
qsort(dates, ndates, sizeof(struct mystruct), mystructcmp);

If, on the other hand, you're sorting pointers to structures, you'll need indirection, as in question 13.8; the head of the comparison function would look like

int myptrstructcmp(const void *p1, const void *p2)
	struct mystruct *sp1 = *(struct mystruct * const *)p1;
	struct mystruct *sp2 = *(struct mystruct * const *)p2;
and the call would look like
struct mystruct *dateptrs[NDATES];
qsort(dateptrs, ndates, sizeof(struct mystruct *), myptrstructcmp);

To understand why the curious pointer conversions in a qsort comparison function are necessary (and why a cast of the function pointer when calling qsort can't help), it's useful to think about how qsort works. qsort doesn't know anything about the type or representation of the data being sorted: it just shuffles around little chunks of memory. (All it knows about the chunks is their size, which you specify in qsort's third argument.) To determine whether two chunks need swapping, qsort calls your comparison function. (To swap them, it uses the equivalent of memcpy.)

Since qsort deals in a generic way with chunks of memory of unknown type, it uses generic pointers (void *) to refer to them. When qsort calls your comparison function, it passes as arguments two generic pointers to the chunks to be compared. Since it passes generic pointers, your comparison function must accept generic pointers, and convert the pointers back to their appropriate type before manipulating them (i.e. before performing the comparison). A void pointer is not the same type as a structure pointer, and on some machines it may have a different size or representation (which is why these casts are required for correctness).

If you were sorting an array of structures, and had a comparison function accepting structure pointers:

	int mywrongstructcmp(struct mystruct *, struct mystruct *);
and if you called qsort as
	qsort(dates, ndates, sizeof(struct mystruct),
		(int (*)(const void *, const void *))mywrongstructcmp);
							/* WRONG */
the cast (int (*)(const void *, const void *)) would do nothing except perhaps silence the message from the compiler telling you that this comparison function may not work with qsort. The implications of any cast you use when calling qsort will have been forgotten by the time qsort gets around to calling your comparison function: it will call them with const void * arguments, so that is what your function must accept. No prototype mechanism exists which could operate down inside qsort to convert the void pointers to struct mystruct pointers just before calling mywrongstructcmp.

In general, it is a bad idea to insert casts just to ``shut the compiler up.'' Compiler warnings are usually trying to tell you something, and unless you really know what you're doing, you ignore or muzzle them at your peril. See also question 4.9.

Additional links

References: ISO Sec.
H&S Sec. 20.5 p. 419

prev up next   contents search
about this FAQ list   about eskimo   search   feedback   copyright

Hosted by Eskimo North