Function Pointers in C are Underrated

Thursday, March 22, 2012

The function pointer in C is, in my opinion, one of the most ignored gems of the language. It’s the kind of feature you rarely need, and then suddenly, one day, you find yourself in dire need of it, as evidenced by the use-case below.

If you don’t know what a function pointer is in the first place, here’s the meat of it: it gives you the ability to pass a function around like a normal variable. If you know Python / Ruby / Lisp, you might know it by the name ‘lambda’, or if you come from a JavaScript background, you might’ve used it under the name ‘anonymous function’. (UPDATE: a lot of people have pointed out that function pointers are not the same as closures, and they are correct. But the point here is to establish some semblance of familiarity for those who are new to function pointers in C).

The Why

Say we’re writing a library for linked list manipulation, as part of another application. Being the kind of programmers who see beauty in reusable code, we want the library to be completely generic and independent from the other modules in our application, so we can re-use it in other projects. To that end, first we define some basic structures for the list and its nodes:

struct list_entry_t {
    void * data;
    struct list_entry_t * next;
};

struct list_t {
    struct list_entry_t * head;
    unsigned int length;
};

Now let’s assume that, in our application, the data field in our linked list entries is meant to store a pointer to a structure of the following type:

struct mem_block {
    void * addr;
    unsigned int size;
};

Now if we want to search for a specific struct mem_block in our list, given the value of it’s addr field, how would we do it? (I encountered this exact same use-case when I had to write a memory manager for my last Operating Systems assignment).

We ideally shouldn’t make a public function in our generic linked list library (that’s meant to store any type of data), hard-wired just for this specific case (searching by the addr field of the struct mem_block), since that would make our library, well, not generic. Argh, the reusability-seeker within itches for a better solution! If you’ve so much as read the title of this post, you already know the answer: function pointers!

The How

Now let’s see how function pointers can help us here. First, we declare a public function in our linked list library with the following prototype:

/* get the data of the first element of list @l which passes the
 * comparison test implemented by the function @compar.
 *
 * @param l         the linked list to search
 * @param compar    the comparison function. The two parameters passed to
 *                  it are the element data, and @key, respectively. Must
 *                  return 1 for a success, else 0.
 * @param key       the search key passed as the second parameter to
 *                  @compar */

void * list_get_by_condition(struct list_t * l,
                             int (* compar) (void *, void *),
                             void * key);

And the function definition:

void * list_get_by_condition(struct list_t * l, int (* compar) (void *, void *), void * key) {
    struct list_entry_t * entry;

    for (entry = l->head; entry; entry = entry->next) {
        if (compar(entry->data, key)) {
            return entry->data;
        }
    }

    return NULL;
}

And our comparison function, in the application program:

/* comparison function to compare a block and an address; intended to be passed
 * to list_get_by_condition() */

int compar_addr(void * block, void * addr) {
    return (((struct mem_block *) block)->addr == addr);
}

Now let’s see how this helps us. We call list_get_by_condition() with our linked list, it traverses the list, and for each list entry, it passes the data (the struct mem_block) and the search key key to our comparison function compar_addr(). The comparison function in turn checks if its parameters satisfy our search criterion, and returns 1 or 0 to list_get_by_condition(), as appropriate. As soon as a match is found, the matching struct mem_block is returned, otherwise NULL is returned.

Notice how we separate the common parts from the use-case-specific parts using the function pointer compar. We put the common parts into our linked list library, and the small application-specific parts into our application. Now we can have several comparison functions testing various conditions, for different search criteria, and the sanctity of our linked list library remains preserved :)


blog comments powered by Disqus