Dynamic method dispatching in C

As others have noted, it is certainly possible to implement this in C. Not only is it possible, it is a fairly common mechanism. The most commonly used example is probably the file descriptor interface in UNIX. A read() call on a file descriptor will dispatch to a read function specific to the device or service that provided that file descriptor (was it a file? was it a socket? was it some other kind of device?).

The only trick is to recover the pointer to the concrete type from the abstract type. For file descriptors, UNIX uses a lookup table that contains information specific to that descriptor. If you are using a pointer to an object, the pointer held by the user of the interface is the “base” type, not the “derived” type. C doesn’t have inheritance per se, but it does guarantee that the pointer to the first element of a struct is equal to the pointer of the containing struct. So you can use this to recover the “derived” type by making the instance of the “base” be the first member of the “derived”.

Here’s a simple example with a stack:

struct Stack {
    const struct StackInterface * const vtable;
};

struct StackInterface {
    int (*top)(struct Stack *);
    void (*pop)(struct Stack *);
    void (*push)(struct Stack *, int);
    int (*empty)(struct Stack *);
    int (*full)(struct Stack *);
    void (*destroy)(struct Stack *);
};

inline int stack_top (struct Stack *s) { return s->vtable->top(s); }
inline void stack_pop (struct Stack *s) { s->vtable->pop(s); }
inline void stack_push (struct Stack *s, int x) { s->vtable->push(s, x); }
inline int stack_empty (struct Stack *s) { return s->vtable->empty(s); }
inline int stack_full (struct Stack *s) { return s->vtable->full(s); }
inline void stack_destroy (struct Stack *s) { s->vtable->destroy(s); }

Now, if I wanted to implement a stack using a fixed sized array, I could do something like this:

struct StackArray {
    struct Stack base;
    int idx;
    int array[STACK_ARRAY_MAX];
};
static int stack_array_top (struct Stack *s) { /* ... */ }
static void stack_array_pop (struct Stack *s) { /* ... */ }
static void stack_array_push (struct Stack *s, int x) { /* ... */ }
static int stack_array_empty (struct Stack *s) { /* ... */ }
static int stack_array_full (struct Stack *s) { /* ... */ }
static void stack_array_destroy (struct Stack *s) { /* ... */ }
struct Stack * stack_array_create () {
    static const struct StackInterface vtable = {
        stack_array_top, stack_array_pop, stack_array_push,
        stack_array_empty, stack_array_full, stack_array_destroy
    };
    static struct Stack base = { &vtable };
    struct StackArray *sa = malloc(sizeof(*sa));
    memcpy(&sa->base, &base, sizeof(base));
    sa->idx = 0;
    return &sa->base;
}

And if I wanted to implement a stack using a list instead:

struct StackList {
    struct Stack base;
    struct StackNode *head;
};
struct StackNode {
    struct StackNode *next;
    int data;
};
static int stack_list_top (struct Stack *s) { /* ... */ }
static void stack_list_pop (struct Stack *s) { /* ... */ }
static void stack_list_push (struct Stack *s, int x) { /* ... */ }
static int stack_list_empty (struct Stack *s) { /* ... */ }
static int stack_list_full (struct Stack *s) { /* ... */ }
static void stack_list_destroy (struct Stack *s) { /* ... */ }
struct Stack * stack_list_create () {
    static const struct StackInterface vtable = {
        stack_list_top, stack_list_pop, stack_list_push,
        stack_list_empty, stack_list_full, stack_list_destroy
    };
    static struct Stack base = { &vtable };
    struct StackList *sl = malloc(sizeof(*sl));
    memcpy(&sl->base, &base, sizeof(base));
    sl->head = 0;
    return &sl->base;
}

The implementations of the stack operations would simply cast the struct Stack * to what it knows it should be. For example:

static int stack_array_empty (struct Stack *s) {
    struct StackArray *sa = (void *)s;
    return sa->idx == 0;
}

static int stack_list_empty (struct Stack *s) {
    struct StackList *sl = (void *)s;
    return sl->head == 0;
}

When a user of a stack invokes a stack operation on the stack instance, the operation will dispatch to the corresponding operation in the vtable. This vtable is initialized by the creation function with the functions that correspond to its particular implementation. So:

Stack *s1 = stack_array_create();
Stack *s2 = stack_list_create();

stack_push(s1, 1);
stack_push(s2, 1);

stack_push() is called on both s1 and s2. But, for s1, it will dispatch to stack_array_push(), while for s2, it will dispatch to stack_list_push().