Dynamic Dispatch in C using virtual method table

Question

I am hoping to find a hint (preferably by good example) for implementing dynamic dispatch in C.

I am learning C and as practice, I want to translate from Java to C using dynamic dispatch virtual method table.

for example I have a java code :

abstract class Foo {
    public abstract int val(); 
    public abstract Boolean error();
}

class Fail extends Foo {
    public int val(){ return 0;}
    public Boolean error(){return true;}
}

class IntFoo extends Foo {
    int v;
    public IntFoo(int value){this.value=v;}
    public int val(){ return v;}
    public Boolean error(){return False;}
}

and I could just translate some basic stuff like this:

typedef struct Foo{
    void(**vtable);
}Foo;

typedef struct Fail{
    void(**vtable);
    struct Foo inherited;
}Fail;

typedef struct IntFoo{
    void(**vtable);
    struct Foo inherited;
}IntFoo;

I am stuck while trying to complete this because I don't know:

1. How to define these methods in c.
2. Set the address of these methods in vtable so that the compiler recognizes the right method to call.
3. What else to define to make it work.

Answer 1

There is no simple way of doing this. Nevertheless you can do manually what the C++ compiler is doing. In your case this will look like:

typedef struct vtable_Fail
{
    int  (*val)(struct Fail *this_pointer);
    bool (*error)(struct Fail *this_pointer);
} vtable_Fail;

typedef struct vtable_IntFoo
{
    int  (*val)(struct IntFoo *this_pointer);
    bool (*error)(struct IntFoo *this_pointer);
} vtable_IntFoo;

int Fail_val(struct Fail *this_pointer)
{
    return 0;
}

...

void IntFoo_ctor(struct IntFoo *this_pointer, int value)
{
     this_pointer->v = value;
}

int IntFoo_val(struct IntFoo *this_pointer)
{
    return this_pointer->v;
}

...

struct Fail
{
    vtable_Fail *vtable;
};

struct IntFoo
{
    vtable_IntFoo *vtable;
    int v;
};

The idea is that each struct should have a companion vtable struct that stores pointers to all virtual methods that this struct implements. Vtable structs have only one instance each. They should reside in static memory and they should be inited with pointers to functions. These pointers should implement virtual methods in the way that is needed for each particular struct. The structs themselves can have many instances. Vtable data fiels in the instance should point to the static vtable struct of its class.

Parameter this_pointer passes the address of the instance. It should be passed manually. This is C at the end of the day.

Note you need to allocate vtable structures, init vtable pointers, etc. And you need to do all this manually with your own code.

Answer 2

The approach I would recommend is to look at some other C code that uses a dispatch table and see how it's structured. Specific examples that I'm aware of off the top of my head (perhaps not the best teaching examples, since they're just random free software I've worked on) are MIT Kerberos and Heimdal, both of which use dispatch tables all over the place and the Apache web server and how it handles dynamically loaded modules. None of these do inheritance, but inheritance is relatively straightforward to add: you see if the method you're trying to call is NULL, and if so, you check the parent dispatch table for that method.

The short version for how to handle a dispatch table in C in general is that you define a data structure akin to the C++ vtable, which holds function pointers and some way of figuring out which pointer to use. Something like:

typedef void (*dispatch_func)(void *);
struct dispatch {
    const char *command;
    dispatch_func callback;
};

is the super-generic version, which maps string method names to functions that take a single anonymous pointer as an argument. Your actual dispatch table will be an array of these, like this (a modified example taken from tinyleaf in the INN source):

const struct dispatch commands[] = {
    { "help",  command_help },
    { "ihave", command_ihave },
    { "quit",  command_quit }
};

Obviously, the more you know about the functions, the more specific you can make the prototype, and you can embed other selection criteria (such as the number of arguments) into the dispatch table. (The actual INN source has minimum and maximum argument counts, passes in a structure of arguments instead of just a void *, and includes a command description in the dispatch table.)

The basic code to search a dispatch table is pretty simple. Assuming you have an array of those dispatch struct entries in vtable and the length of the table in length, something like:

for (i = 0; i < length; i++)
    if (strcmp(command, vtable[i].command) == 0) {
        (*vtable[i].callback)(data);
        return;
    }

To implement inheritance, you would need the parent pointer, and if you fall off the end of the loop, you move up to the parent and repeat the logic. (Obviously, this may be a useful place for a recursive function.)