byron@astro.Princeton.EDU (Byron Rakitzis) (12/07/90)
The only ANSI compiler I have is gcc, so forgive me if I turn out to be complaining about a bug in gcc. I'm writing my own header file for symbols to be found in libc. I declared qsort as: void qsort(void *, int, int, int (*)(void *, void *)); This is okay, except that gcc then complains if strcmp or any function not taking (void *, void *) as arguments is passed to qsort. Is this correct? Could someone please enlighten me? The alternative: void qsort(void *, int, int, int (*)()); hurts typechecking, as far as I can tell. Thanks much. Byron Rakitzis.
gwyn@smoke.brl.mil (Doug Gwyn) (12/08/90)
In article <4559@idunno.Princeton.EDU> byron@astro.Princeton.EDU (Byron Rakitzis) writes: > void qsort(void *, int, int, int (*)(void *, void *)); >This is okay, except that gcc then complains if strcmp or any >function not taking (void *, void *) as arguments is passed to qsort. It SHOULD complain, since internally qsort() is going to be passing void* arguments to the function, so it had better be defined with compatible argument types.
scs@adam.mit.edu (Steve Summit) (12/08/90)
In article <4559@idunno.Princeton.EDU> byron@astro.Princeton.EDU (Byron Rakitzis) writes: >The only ANSI compiler I have is gcc... >I'm writing my own header file for symbols to be found in libc. Too bad you have to. Someone has to have done this for gcc by now. >I declared qsort as: > void qsort(void *, int, int, int (*)(void *, void *)); >This is okay, except that gcc then complains if strcmp or any >function not taking (void *, void *) as arguments is passed to qsort. Sometimes even weird, mutant compilers are trying to tell you something with their error and warning messages :-) . (No slam against gcc; once again, it has gotten a subtle point right.) As Chris Torek pointed out long ago, strong typing in C (particularly of function pointer arguments) can cause headaches. This, however, is not one of them. In fact, the qsort/strcmp case is one common problem that function pointer prototype checking should help to clean up. It happens that ANSI X3.159 guarantees that a void * is compatible with a char *, so mixing the two in this way should perhaps yield warnings, not errors (footnote 1), but this is a (doubly) red herring in this case. First of all, the callback function you hand to qsort really is called with two void *'s. (Jim Van Zandt was just asking about this a few weeks ago.) It is _not_ called with two pointers-to- whatever-your-datatype is. Remember that your qsort prototype (correctly) gives the type of the first argument as void *. This means that whether you are sorting an array of characters, or an array of integers, or an array of structures, or an array of pointers to characters, qsort gets a pointer-to-void as its handle on the array, and can't possibly pass pointers to anything else back to the comparison routine. Even if the equivalence between void * and char * let you get away with char *array[MAXSTRINGS]; size_t narray; ...fill in array... qsort(array, narray, sizeof(char *), strcmp); you would still be making a big mistake. The comparison function is called with two pointers to the objects being compared, and the objects being compared here are pointers to characters. That is, the comparison function is called with pointers to pointers to characters, or char **'s, which is certainly not what strcmp expects. You must write a special comparison function int pstrcmp(void *p1, void *p2) { return strcmp(*(char **)p1, *(char **)p2); } which retrieves the char *'s from the original array and passes them to strcmp. The only way strcmp could even begin to be used directly as a comparison function for qsort would be if an array of arrays of characters (i.e. a two-dimensional array) were being sorted. It would look something like char array2[MAXSTRINGS][MAXLEN]; ...fill in array... qsort(array2, narray, MAXLEN, strcmp); (We could let the compiler figure the right element size for us by using sizeof(array2[0]) as qsort's third argument; this might be a good idea, to avoid errors, but it hides what's going on.) In this case, we could either ignore the message from gcc, or call it a bug (footnote 1) and fix it, or use a different intermediary function int p2strcmp(void *p1, void *p2) { return strcmp((char *)p1, (char *)p2); } to make the casts explicit. Using an array of fixed-size arrays is a poor way of sorting strings, though, because it either risks truncation (if MAXLEN is too small) or wastes space (if MAXLEN is too big), or both. (Of course, in a real program, both the strings and the array of pointers to them would be dynamically allocated, eliminating built-in limitations either on string length or number of strings.) I may add qsort/strcmp to the FAQ list one day; it comes up often enough. Steve Summit scs@adam.mit.edu P.S. to Byron Rakitzis: apologies if you were, in fact, using an array of arrays, as in the second example. The array of pointers (the first example) brings up the more interesting question, and is (once you get the comparison function right) the more useful implementation. Footnote 1. ANSI X3.159 says (section 3.1.2.5) that "A pointer to void shall have the same representation and alignment requirements as a pointer to a character type." It also says (section 3.2.2.3) that "A pointer to void may be converted to or from a pointer to any incomplete or object type." It is usually held that these latter conversions should be performed silently, that is, neither extern void *malloc(); int *ip = malloc(sizeof(int)); nor int i; void *p = &i; should result in any error (or warning) messages. (Of course, X3.159 says nothing about what diagnostics a translator must not produce, only some that it must, so a compiler can issue any extra messages it wants.) Should either of these guarantees let us pass an int (*)(char *, char *) (that is, a pointer to a function of two arguments, char * and char *, returning int) to a function expecting int (*)(void *, void *) ? The first guarantee (bit-level equivalence of void * and char *) might; the second does not. Other pointers coerce silently to and from void *'s when the compiler knows about the coercion. If we have extern void f(int *); and we call int i; void *vp = &i; f(vp); the code will work (as long as the prototype is in scope; the possibility that it might not be is a good reason not to depend on implicit argument coercions). The case with function prototypes "within" function pointers is quite different, however. In a call through a pointer to a function expecting a void * argument, the compiler is going to arrange that a void * be passed, and the function being called had better expect a void *. That it does was supposed to be guaranteed when the function pointer was initialized, which is why modern compilers check function pointer prototypes, and generate fussy-looking warnings. (There may be a paragraph in X3.159 that discusses the extra checking appropriate for function pointer prototypes; I'm not sure at the moment.) If we had int icmp(int *, int *); and tried to pass it as the comparison function to qsort, a complaint from the compiler would certainly be appropriate, because qsort is going to pass void *'s to that function, not int *'s, regardless of any implicit coercion between void * and int * that might occur in other contexts. Somewhere inside qsort is code something like int (*compar)(void *, void *); void *p1, *p2; ... r = compar(p1, p2); and there is nothing there to tell the compiler that any coercion of the arguments might be required.