6

I am implementing a generic singly linked list where list nodes store a pointer to their data.

typedef struct sll_node
{   
    void *data;
    struct sll_node *next;
} sll_node;

To implement a generic find subroutine that works with any kind of data, I wrote it so that it takes as an argument a function pointer to the comparison function as follows:

/* eq() must take 2 arguments. ex: strcmp(char *, char *) */
sll_node *sll_find(void *data, int (*eq)(), sll_node *root);

You can pass the appropriate function pointer that works with the data type at hand.. So if you store strings in the list nodes, you can pass strcmp as the eq() function, and so on. It works but I'm still not satisfied..

Is there a way to explicitly specify the number of comparison function parameters without giving up its generality?

I tried this at first:

sll_node *sll_find(void *data, int (*eq)(void *, void *), sll_node *root);

I expected it to work. But no (edit: it compiles with a warning but I have -Werror on!), I had to write a wrapper function around strcmp to make it conform to the eq prototype.

I then tried:

sll_node *sll_find(void *data, int (*eq)(a, b), sll_node *root);

or:

typedef int (*equality_fn)(a, b);
sll_node *sll_find(void *data, equality_fn eq, sll_node *root);

which both wouldn't compile since: "a parameter list without types is only allowed in a function definition"

Osama Arafa
  • 63
  • 5
  • 2
    Comparison functions are typically declared with the `const` keyword, e.g. `int (*eq)(const void *, const void *)`. Does that fix the problem with `strcmp` ? – user3386109 Feb 12 '15 at 23:39
  • Casting the type of the pointer requires a parameter; in your case, perhaps try looping til NULL? –  Feb 12 '15 at 23:39
  • 1
    @user3386109 you're right about the **const** keyword (from the idiomatic point of view), but it still gives the same warning: **warning: incompatible pointer types passing 'int (const char *, const char *)' to parameter of type 'int (*)(void *, void *)' [-Wincompatible-pointer-types]** (I edited the question to clarify) – Osama Arafa Feb 12 '15 at 23:58
  • 1
    @concacid I tried the code while waiting for your reply. In order to use `strcmp` without a wrapper, you need to match the `strcmp` exactly, which means using `const char *` for the arguments. You might also be able to cast `strcmp`. I'll try that and add it to my answer below if it works. – user3386109 Feb 13 '15 at 00:01
  • 1
    @concacid Casting `strcmp` to the appropriate type *can* work. I've added that to my answer. – user3386109 Feb 13 '15 at 00:10
  • having to match strcmp exactly means the answer to my question is NO. Casting strcmp however sounds cool to me! Is it possible though? – Osama Arafa Feb 13 '15 at 00:12
  • @concacid Yes, see my answer below. However, there is one little problem. `strcmp` returns 0 when equal, and non-zero if not equal. So that's pretty much the opposite of what I would expect a `eq` function to return. So I'm afraid that you're stuck with a wrapper for that reason. – user3386109 Feb 13 '15 at 00:19
  • @user3386109 Oh! actually not, eq was a bad name choice, I should change that to cmp, you're right again! – Osama Arafa Feb 13 '15 at 00:37

3 Answers3

2

To use strcmp without a wrapper or a cast, the declaration needs to be 

sll_node *findNode(void *data, int (*eq)(const char *, const char *), sll_node *root);

On the other hand, if you declare the args as const void *, then you can avoid the wrapper by casting strcmp to the appropriate type.

Method 1: direct cast, messy but effective

    result = findNode( "hello", (int(*)(const void *, const void *))strcmp, root );

Method 2: typedef the comparison function, and then use it to cast

typedef int (*cmpfunc)(const void *, const void *);
result = findNode( "world", (cmpfunc)strcmp, root );

Edit: After reading this post that @WilburVandrsmith linked, I've decided to leave this answer as is. I leave it up to the reader to decide whether the proposed cast violates the following paragraph from the specification:

If a converted pointer is used to call a function whose type is not compatible with the pointed-to type, the behavior is undefined.

Compatible or not compatible, that is the question, you decide.

user3386109
  • 34,287
  • 7
  • 49
  • 68
  • 2
    Even though casting the function pointer will usually work, [it's still technically undefined behavior](https://stackoverflow.com/questions/559581/casting-a-function-pointer-to-another-type), unfortunately. – Wilbur Vandrsmith Feb 13 '15 at 00:18
  • @WilburVandrsmith Good point. As it turns out, `strcmp` probably needs a wrapper anyways because it returns 0 for equal, which isn't what one would expect from an `eq` function. I'll be changing the answer soon. – user3386109 Feb 13 '15 at 00:22
  • Thanks a lot! That's the answer I was looking for. I'm still learning C and I had no idea you could cast function pointers like that. I guess that still means that the caller is the one responsible for casting the comparison function while plugging it into findNode(), but that's much better than a wrapper function or an underspecified prototype. As a side not, after looking at [this](http://stackoverflow.com/questions/559581/casting-a-function-pointer-to-another-type), I'm still intrigued to research this further to understand which cases can result in undefined behaviour. – Osama Arafa Feb 13 '15 at 00:31
  • 1
    @concacid tl;dr: if you are using prototypes then it must match exactly; if you are using K&R style function declarations then there's a whole bunch of weird rules designed to basically allow code that appeared in the K&R book and disallow anything else. :) – M.M Feb 13 '15 at 00:45
0

Your last attempted solution is the closest to being correct. The parameters in your defined-type function pointer need to be declared with their data types, just like you would with a regular function declaration, like so:

typedef int (*equality_fn)(char *a, char *b);
sll_node *sll_find(void *data, equality_fn eq, sll_node *root);

UPDATE

To make it more generic use void pointers, and then type cast the passed void pointers to the needed data type in the matching function definition for equality_fn:

typedef int (*equality_fn)(void *a, void *b);
sll_node *sll_find(void *data, equality_fn eq, sll_node *root);

Something else important to remember is that a pointer is a pointer is a pointer, regardless of what it's pointing at or how it was originally defined. So, you can have some function pointer, or a void pointer, or a pointer to a byte, a char, an int--anything--as long as you handle it properly in your code and cast it back to a valid type before attempting to use it.

Something else that most coders don't take much advantage of in C is that function names themselves are really just addresses that are called at run-time, and so they are also pointers. ;)

Jim Fell
  • 13,750
  • 36
  • 127
  • 202
  • Well, but it wouldn't be generic anymore! – Osama Arafa Feb 13 '15 at 00:14
  • @concacid I updated my answer with additional info for you. :) – Jim Fell Feb 13 '15 at 00:28
  • 1
    There actually are platforms (for example, Harvard architecture devices) where data pointers point to data, function pointers point to functions, and never the twain shall meet. It's actually an error to cast function pointers to/from void * on such platforms. Thankfully, the popular platforms like Intel and ARM are not among these. – Lee Daniel Crocker Feb 13 '15 at 00:38
0

My solution to this conundrum would be (avoiding pointer typedefs, incidentally):

typedef int equality_fn(const void *a, const void *b);

sll_node *sll_find(void *data, equality_fn *eq, sll_node *root);

Then make all your comparators be of type equality_fn. If you need to actually have a function then so be it:

equality_fn eq_strcmp;  // a prototype

// ...

int eq_strcmp(const void *a, const void *b) { return strcmp(a, b); }

Gain lots of type safety in exchange for a potential picosocopic runtime penalty - which end of this trade you want to be on depends on your application.

M.M
  • 138,810
  • 21
  • 208
  • 365