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().

Yes. It can be easily achieved. You would use an array of function pointers, then use those function pointers to make the call. If you want to "override" a function, you just set the corresponding slot to point to the new function. This is exactly how C++ implements virtual functions.

C++ was (initially) built on top of C. The first C++ compilers were actually generating C as intermediary step. Ergo, yes it's possible.

Here's how C++ does things like this.

There's is plenty of solid information available online, more than we can type together here in a few minutes. "Google and you will find."

You said in a comment above:

Well someone would prefer that if they have something code written already in c but to add some functionality. instead of writing from scratch using OOlanguage.

To have functionality like this in C, you'll basically need to reimplement OO language features. Getting people to use this new OO method is the biggest factor against usability. In other words, by creating yet another method for reuse, you'll actually making things less reusable.

Dynamic method dispatching in C

Related

Recent Posts