6/01/2011 Delegates vs. Function Pointers, part 2: C

This is part 2 in a series about state and function pointers; part 1 is here.

Unlike most other languages, it is not possible to include any form of state in a function pointer in C.  Therefore, it is impossible to fully implement closures in C without the cooperation of the call-site and/or the compiler.

To illustrate what this means in practice, I will refer to my standard example, using a filter function to find all elements in an array that are greater than x.  Since C doesn’t have any such function, I’ll write one myself, inspired by qsort:

void* filter(void* base, 
             size_t count, 
             size_t elemSize, 
             int (*predicate)(const void *)) {
    //Magic...
}

With this function, one can easily find all elements that are greater than some constant:

int predicate(const void* item) {
        return *(int*)item > 2;
}

int arr[] = { 1, 2, 3, 4 };
filter(arr, 4, sizeof(int), &predicate);

However, if we want to replace the hard-coded 2 with a local variable, it becomes more complicated.  Since function pointers, unlike delegates, do not have state, there is no simple way to pass the local variable to the function.

The most obvious answer is to use a global variable:

static int minimum;
int predicate(const void* item) {
        return *(int*)item > minimum;
}

int arr[] = { 1, 2, 3, 4 };
minimum = x;
filter(arr, 4, sizeof(int), &predicate);

However, this code will fail horribly if it’s ever run on multiple threads.  In simple cases, you can work around that by storing the value in a global thread-local variable (or in fiber-local storage for code that uses fibers).   Because each thread will have its own global, the threads won’t conflict with each-other.  Obviously, this won’t work if the callback might be run on a different thread.

However, even if everything is running on one thread, this still isn’t enough if the code can be re-entrant, or if the callback might be called after the original function call finishes.  This technique assumes that exactly one callback (from a single call to the function that accepted the callback) will be used at any given time.  If the callback might be invoked later (eg, a timer, or a UI handler), this method will break down, since all of the callbacks will share the same global.

In these more complicated cases, one can only pass any state with the cooperation of the original function.  In this (overly simple) example, the filter method can be modified to take a context parameter and pass it to the predicate:

void* filter(void* base, 
             size_t count,
             size_t elemSize, 
             int (*predicate)(const void *, const void *), 
             const void* context) {
        //More magic...
}
int predicate(const void* item, const void* context) {
        return *(int*)item > *(int*)context;
}

int arr[] = { 1, 2, 3, 4 };
filter(arr, 4, sizeof(int), &predicate, &x);

To pass around more complicated state, one could pass a pointer to a struct as the context.

Next Time: C# 1.0