kers@hpld.hpl.hp.com (Kers) (09/01/89)
Two questions. First, about the compatability of function types in pANS C. Here's an (fragmentary) example that illustrates my problem. #include <stdlib.h> #include <string.h> ... qsort( Base, NMembers, Size, strcmp ); ... Assuming that the Base, NMembers, and Size arguments are OK, is strcmp suitable for passing as an argument - without explicit casting? - with explicit casting? - ever? *Or* do I have to write my own function (with two void* arguments), which operates by calling strcmp after suitable casting, and hand that in? The issue has arisen in some code we are writing, where generic procedures abound (for example, a hash table packages that allows a table to be created with particular hashing & comparison operations passed in), and we'd like to preserve type information "as long as possible" - ie, not declare things as accepting void* parameters just because we're going to pass them to generic procedures. Second, about typedefs for function types. I'd like to be able to declare a type for a function, so that I can use it for declaring arguments. I'm a little unclear about how I do so. typedef char * (char *) MonadicStringFunction; As I read the pANS (DEC 1988, Section 3.5.5), that would be OK; the type's a function declarator with the name omitted. (The compiler I'm using has a problem with this at the moment, but I'd like to understand the pANS, and the compiler at home may have a different tale to tell.) Assuming that I can get a suitable typedef set up, I'd then like to declare parameters with that type: extern int example( MonadicStringFunction arg ); Would I need to add the * to ensure the argument is treated as a function pointer, or is this one of the places where the lattitude about functions and pointers applies? (I'm quite happy to add the * here). Can I also use the typedef in a *definition*: MonadicStringFunction boring( char *arg ) { return arg; } so that the compiler can catch me out if I make a type error? Although I have access to a copy of the pANS, I'm still trying to navigate my way round it; K&R II doesn't give enough detail to answer my questions (or, if it does, I've missed it several times). I'd appreciate it if someone could answer my questions, either directly, or by pointing me to the pertinent section of the pANS. Finally, I was going to post this to comp.std.c, but decided it wasn't discussion "about" the standard. Would that have been a more appropriate place? -- Regards, Kers. "If anything anyone lacks, they'll find it all ready in stacks."
kers@hpld.hpl.hp.com (Kers) (09/01/89)
Urhm. After my previous posting (let's hope they go out together) I found some discussion in comp.std.c on the function pointer issue. I can't imagine how I'd missed it before; I apologise. The typedef question stands, as does my remaining question: if I cast (say) (int (*)( void *, void *)) strcmp, and pass it to (say) qsort (as the compar parameter), can I expect it to work, and does such usage conform to the pANS? (I suspect the answers to be Yes (on many implementations) and No, respectively). -- Regards, Kers. "If anything anyone lacks, they'll find it all ready in stacks."
chris@mimsy.UUCP (Chris Torek) (09/01/89)
In article <KERS.89Aug31164048@cdollin.hpl.hp.com> kers@hpld.hpl.hp.com (Kers) writes: >if I cast (say) (int (*)( void *, void *)) strcmp, and pass it to (say) qsort >(as the compar parameter), can I expect it to work, and does such usage >conform to the pANS? (I suspect the answers to be Yes (on many >implementations) and No, respectively). Actually, the answers FOR THIS PARTICULAR CASE are `yes' and `yes'. Given a pointer whose type is <pointer to function (args) returning t>, you can always (by the proposed standard, at least) cast it to some other function pointer type (<ptr to fn (args') returning t'>) and then back, and the result (after casting back) will act the same as the original. Normally, however, you have to use that `cast-back' to force it to work. In this particular case, however, the two types are int (*)(void *, void *) [qsort compare function] and int (*)(char *, char *) [strcmp] and `void *' and `char *' are required to be `the same' in representation, since historically `char *' has been used where the pANS uses `void *'. (In fact, in Classic C, qsort's fourth argument has the second type above, not the first.) In order not to break such code, the pANS has a constraint that is supposed to make those two function-pointer types interchangeable. Whether this might be `deprecated' (and hence vanish in C-00 in 2001, or whatever), I am not sure. Certainly it would be prettier to cast back. On the other hand, little helper functions for changing types are ugly. (You need the `unnamed function' notation I keep bringing up every year :-) .) -- In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163) Domain: chris@mimsy.umd.edu Path: uunet!mimsy!chris
ok@cs.mu.oz.au (Richard O'Keefe) (09/01/89)
In article <19361@mimsy.UUCP>, chris@mimsy.UUCP (Chris Torek) writes: > In article <KERS.89Aug31164048@cdollin.hpl.hp.com> kers@hpld.hpl.hp.com > (Kers) writes: > >if I cast (say) (int (*)( void *, void *)) strcmp, and pass it to (say) qsort > >(as the compar parameter), can I expect it to work, and does such usage > Actually, the answers FOR THIS PARTICULAR CASE are `yes' and `yes'. > int (*)(void *, void *) [qsort compare function] > and int (*)(char *, char *) [strcmp] If you want to sort an array of strings, e.g. char *myarray[N_Of_Strings]; ... qsort(myarray, N_Of_Strings, sizeof myarray[0], {{SOMETHING}}) **don't** try to pass 'strcmp' as the fourth argument of qsort(). The comparison function is not given the elements of the array, but ``POINTERS to the elements being compared''. What you need is int strptrcmp(char **s1, char **s2) { return strcmp(*s1, *s2); } and pass that as the fourth argument. I can't think of any case where it would make sense to pass strcmp to qsort(). Did you know that C.A.R.Hoare pointed out in 1962 that Quicksort does 1.4 times as many comparisons as [the number done by merge sort]? He should know: he invented it.
chris@mimsy.UUCP (Chris Torek) (09/01/89)
>In article <19361@mimsy.UUCP> I wrote: >>... the answers FOR THIS PARTICULAR CASE are `yes' and `yes'. >> int (*)(void *, void *) [qsort compare function] >> and int (*)(char *, char *) [strcmp] In article <1996@munnari.oz.au> ok@cs.mu.oz.au (Richard O'Keefe) writes: >If you want to sort an array of strings ... **don't** try to pass >'strcmp' as the fourth argument of qsort(). ... What you need is > int strptrcmp(char **s1, char **s2) > { return strcmp(*s1, *s2); } Oops, quite right. I got tied up in the `do the two function types match' question and never noticed the fact that qsort is passing pointers to the objects (here pointers to char *), rather than to that to which the objects point. >Did you know that C.A.R.Hoare pointed out in 1962 that Quicksort does >1.4 times as many comparisons as [the number done by merge sort]? >He should know: he invented it. Yes, but everyone likes to analyse Quicksort. :-) That is, I think the reason it is used so often is, well, because it is used so often. (Familiarity breeds distemper, or something like that :-/ ) -- In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163) Domain: chris@mimsy.umd.edu Path: uunet!mimsy!chris
flaps@dgp.toronto.edu (Alan J Rosenthal) (09/01/89)
ok@cs.mu.oz.au (Richard O'Keefe) writes: >If you want to sort an array of strings, e.g. > char *myarray[N_Of_Strings]; > ... > qsort(myarray, N_Of_Strings, sizeof myarray[0], {{SOMETHING}}) >**don't** try to pass 'strcmp' as the fourth argument of qsort()... >What you need is > int strptrcmp(char **s1, char **s2) > { return strcmp(*s1, *s2); } Actually, you should write int strptrcmp(void *s1, void *s2) { return(strcmp(*(char **)s1, *(char **)s2)); } The original form will only work when the representation of (char **) is the same as the representation of (void *), something not guaranteed by ansi C and in fact not true on all machines (albeit true on most). ajr
bader+@andrew.cmu.edu (Miles Bader) (09/02/89)
ok@cs.mu.oz.au (Richard O'Keefe) writes: > and pass that as the fourth argument. I can't think of any case where it > would make sense to pass strcmp to qsort(). When you have an array of fixed sized buffers (strings), e.g. char strings[20][30]. It's not particularly *efficient* to do this, but it is correct...
lmiller@venera.isi.edu (Larry Miller) (09/02/89)
In article <19361@mimsy.UUCP> chris@mimsy.UUCP (Chris Torek) writes: > >Given a pointer whose type is <pointer to function (args) returning t>, >you can always (by the proposed standard, at least) cast it to some >other function pointer type (<ptr to fn (args') returning t'>) and then >back, and the result (after casting back) will act the same as the >original. Normally, however, you have to use that `cast-back' to force >it to work. In this particular case, however, the two types are > > int (*)(void *, void *) [qsort compare function] >and int (*)(char *, char *) [strcmp] > >and `void *' and `char *' are required to be `the same' in >representation, since historically `char *' has been used where the >pANS uses `void *'. (In fact, in Classic C, qsort's fourth argument >has the second type above, not the first.) In order not to break such >code, the pANS has a constraint that is supposed to make those two >function-pointer types interchangeable. This is my interpretation also, but GNU, in particular, disallows this. Since my copy of the draft standard is very old (Nov, 1985), could someone refer to a specific section in the latest draft? Also, it's my interpretation that in a function taking a (void *), that this would work, without cast, for anything *. Specifically, qsort: void qsort(void *base, size_t n, size_t width, int (*f)(const void *, const void *)); Can be passed a char ** as the first element WITHOUT specifically casting to void * (as long as the prototype is in scope). Larry Miller lmiller@venera.isi.edu (no uucp) USC/ISI 213-822-1511 4676 Admiralty Way Marina del Rey, CA. 90292
gwyn@smoke.BRL.MIL (Doug Gwyn) (09/03/89)
In article <KERS.89Aug31163340@cdollin.hpl.hp.com> kers@hpld.hpl.hp.com (Kers) writes: > qsort( Base, NMembers, Size, strcmp ); >... is strcmp suitable for passing as an argument > - without explicit casting? > - with explicit casting? > - ever? I don't think it has a type compatible with the declared parameter for qsort. Therefore it violated the pANS semantic constraints. However, casting it to the appropriate type is allowed, and having done so it will actually work since the pANS requires char* and void* to be represented identically. In fact this specific example motivated the current pANS wording about these matters. What I do, though, is provide my own function that receives generic pointers and cast them as needed inside that function. It doesn't place quite so much trust in the implementation, and if I change from char* strings to counted strings, for example, it facilitates making the change (the cast at qsort invocation approach would no longer be valid in such a case). >Second, about typedefs for function types. I'd like to be able to declare a >type for a function, so that I can use it for declaring arguments. I'm a >little unclear about how I do so. > > typedef char * (char *) MonadicStringFunction; > >As I read the pANS (DEC 1988, Section 3.5.5), that would be OK; the type's a >function declarator with the name omitted. I haven't tried to figure out how you read the pANS, but typedefs work as follows (and if the pANS says otherwise, it's broken): typedef <normal declarator INCLUDING an identifier>; /* now the identifier has that type */ So your example should be written typedef char *MonadicStringFunction(char *); Just now I looked up the pANS grammar, and "typedef" is treated grammatically as just a storage class specifier (like "register"). I think you must have been looking at the syntax for type names, which have nothing to do with typedef. (Think of a type name as the part of a cast between the parentheses.) > extern int example( MonadicStringFunction arg ); >Would I need to add the * to ensure the argument is treated as a function >pointer... I think so. You want a pointer to a function, you should declare it as such. The automatic conversion of identifier designating a function to a pointer occurs only in expressions, not in declarations. For usage exactly as you show in the example, you need the typedef: typedef char *(*MonadicStringFunction)(char *); If you wanted to retain the previous declaration (which might be more convenient), then declare example like this: extern int example( MonadicStringFunction *arg ); >Can I also use the typedef in a *definition*: > MonadicStringFunction boring( char *arg ) { return arg; } With the first (non-pointer) typedef, you're supposed to be able to. Some compilers have historically had trouble handling this kind of usage, though. >Finally, I was going to post this to comp.std.c, but decided it wasn't >discussion "about" the standard. Would that have been a more appropriate >place? Only insofar as you're reporting difficulty extracting this information from the pANS. However, typedefs predate the pANS so this is a general C usage issue for the most part. (Compatibility of function arguments is Standard C specific.)
gwyn@smoke.BRL.MIL (Doug Gwyn) (09/03/89)
In article <9488@venera.isi.edu> lmiller@venera.isi.edu.UUCP (Larry Miller) writes: > This is my interpretation also, but GNU, in particular, disallows > this. Since my copy of the draft standard is very old (Nov, 1985), > could someone refer to a specific section in the latest draft? The "same representation" requirements were added approximately a year ago. It is possible that the compiler you're using was based on an older draft proposed standard. > void qsort(void *base, size_t n, size_t width, > int (*f)(const void *, const void *)); > Can be passed a char ** as the first element WITHOUT specifically > casting to void * (as long as the prototype is in scope). Yes, because in the presence of a prototype the arguments are converted to the declared types as though by assignment, and these pointer types happen to be assignment-compatible (section 3.3.16).
ok@cs.mu.oz.au (Richard O'Keefe) (09/03/89)
In article <1989Sep1.113440.28300@jarvis.csri.toronto.edu>, flaps@dgp.toronto.edu (Alan J Rosenthal) writes: > ok@cs.mu.oz.au (Richard O'Keefe) writes: > >What you need is > > int strptrcmp(char **s1, char **s2) > > { return strcmp(*s1, *s2); } > Actually, you should write > int strptrcmp(void *s1, void *s2) > { return(strcmp(*(char **)s1, *(char **)s2)); } Sorry; I was working from an old manual with char *base and so on. I haven't got a current AN$I C draft: too co$tly. If you're sorting an array of numbers, a half-way decent radix sort will GROSSLY outperform qsort(), and if you're sorting anything else qsort() is too inefficient anyway.
gwyn@smoke.BRL.MIL (Doug Gwyn) (09/04/89)
In article <1999@munnari.oz.au> ok@cs.mu.oz.au (Richard O'Keefe) writes: >If you're sorting an array of numbers, a half-way decent radix sort will >GROSSLY outperform qsort(), and if you're sorting anything else qsort() >is too inefficient anyway. Unless the sorting operation is a bottleneck in your application, you're probably better off using a prepackaged tested sorting routine like qsort(), guaranteed to be in every (hosted) C library, than spending the time it takes to get an adequate replacement designed, coded, and tested. qsort() isn't too bad for sorting internal tables in most applications; its main deficiency is having to perform a function call for every comparison. One tip: since the array of records undergoes numerous element swaps during the sort, it is often best to set up an array of pointers to the actual data items and sort the array of pointers instead.
karl@haddock.ima.isc.com (Karl Heuer) (09/05/89)
ok@cs.mu.oz.au (Richard O'Keefe) writes: >flaps@dgp.toronto.edu (Alan J Rosenthal) writes: >>ok@cs.mu.oz.au (Richard O'Keefe) writes: >>>int cmp(char **s1, char **s2) { return strcmp(*s1, *s2); } > >>Actually, you should write >>int cmp(void *s1, void *s2) { return(strcmp(*(char **)s1, *(char **)s2)); } > >Sorry; I was working from an old [pre-ANSI] manual with char *base and so on. That's not the reason for the correction. The correct pre-ANSI code couldn't use "void *" or a prototype, but you'd still have to declare the arguments to be generic ("char *") and then cast them to "char **". This isn't just a quibble. There are many real machines out there that have more than one pointer format. The code will fail in mysterious ways if you don't declare the formal arguments to be the same type as the actuals. Karl W. Z. Heuer (ima!haddock!karl or karl@haddock.isc.com), The Walking Lint ("But I tried it on my VAX, and it worked, so it must be right!")
ok@cs.mu.oz.au (Richard O'Keefe) (09/05/89)
I wrote int cmp(char **s1, char **s2) { return strcmp(*s1, *s2); } flaps@dgp.toronto.edu (Alan J Rosenthal) correct this to int cmp(void *s1, void *s2) { return(strcmp(*(char **)s1, *(char **)s2)); } Karl Heuer pointed out This isn't just a quibble. There are many real machines out there that have more than one pointer format. The code will fail in mysterious ways if you don't declare the formal arguments to be the same type as the actuals. Related but different question: I believe that the draft standard requires void* and char* to have the same representation. I understand that this doesn't mean that char* and char** will be the same, or that void* and char** will be the same, but will void** and char** be the same?
walter@hpclwjm.HP.COM (Walter Murray) (09/06/89)
A couple of differing viewpoints to the responses Doug posted: (I haven't been able to mail to the author of the basenote.) >> extern int example( MonadicStringFunction arg ); >>Would I need to add the * to ensure the argument is treated as a function >>pointer... >I think so. You want a pointer to a function, you should declare it as such. >The automatic conversion of identifier designating a function to a pointer >occurs only in expressions, not in declarations. As I read the dpANS, the * is not necessary. There is an adjustment that occurs in function declarations and definitions, analogous to the automatic conversion that occurs in expressions. See 3.5.4.3 and 3.7.1. (In the dpANS of 12/7/88, see page 69, lines 22-24, and page 83, lines 23-26.) >>Can I also use the typedef in a *definition*: >> MonadicStringFunction boring( char *arg ) { return arg; } >With the first (non-pointer) typedef, you're supposed to be able to. I don't think so, if I am understanding the question right. It is forbidden by a constraint in 3.7.1. See footnote 76 on page 82. Walter Murray ----------
gwyn@smoke.BRL.MIL (Doug Gwyn) (09/07/89)
In article <660059@hpclwjm.HP.COM> walter@hpclwjm.HP.COM (Walter Murray) writes: >>> extern int example( MonadicStringFunction arg ); >>>Would I need to add the * to ensure the argument is treated as a function >>>pointer... >>I think so. You want a pointer to a function, you should declare it as such. >>The automatic conversion of identifier designating a function to a pointer >>occurs only in expressions, not in declarations. >As I read the dpANS, the * is not necessary. There is an adjustment that >occurs in function declarations and definitions, analogous to the >automatic conversion that occurs in expressions. See 3.5.4.3 and 3.7.1. >(In the dpANS of 12/7/88, see page 69, lines 22-24, and page 83, >lines 23-26.) It's true that in 3.7.1 it's made clear that when a function is called with an argument of function type, the argument is converted to pointer to function. That makes Walter's interpretation a consistent one. All that 3.5.4.3 covers is when two function types are compatible, which doesn't so far as I can see cover the question. However, I'm willing to take 3.7.1 as providing a sufficient "as if" constraint to make what I would consider the "wrong" declaration completely interchangeable with the "right" one. Even if the * is not necessary, it is allowed and I think more clearly documents the interface. >>>Can I also use the typedef in a *definition*: >>> MonadicStringFunction boring( char *arg ) { return arg; } >>With the first (non-pointer) typedef, you're supposed to be able to. >I don't think so, if I am understanding the question right. It is >forbidden by a constraint in 3.7.1. See footnote 76 on page 82. I agree with this; I missed the constraint Walter mentions. The key is that in the syntax function_definition ::= declaration_specifiers{opt} declarator declaration_list{opt} compound_statement the declaration_specifiers are entirely associated with the function return type, so the above example would be an attempt to declare a function that returns a MonadicStringFunction, which is of course illegal. The "declarator" is basically constrained to include one identifier (the name of the function), a bunch of parentheses, possibly parameter list, *s, etc. but no place to introduce the desired typedef. The optional declaration_list is for old-style parameter declarations. Thus there's no place that you could use a typedef for the actual function type. You could use one for the function return type (only).