Search code examples
cfunction-pointersfsm

Finite-State Machine implementation

I'm trying to implement Finite-State Machine in C and need it to be very fast. So I decided to use function pointers as "states":

void *state1(void){ /* function body here */ }
void *state2(void){ /* ... */ }
void *state3(void){ /* ... */ }

Then, main FSM loop can be very simple:

void *(*fp)(void);
fp = state1;

while(fp)
    fp = fp();

There is a questions:

1) Is it possible to avoid using void pointer in function return types? Ideally state functions should have some typedef'ed type to ensure that in FSM will be used only functions with this type.

2) Traditional approach of implementing FSM in C is using enum for states and switch-based dispatcher loop, so comparing with function-pointers based implementation there is will be one indirection level.
But I'm not sure, can there some issues with instruction-cache or branch prediction have a place? In other words, can there exist implementation that can outperform my solution?

Thanks.

Solution

  • To create a recursive type definition like this in C you need to use a struct somewhere along the line, because you can't "forward declare" typedefs. For example, you can wrap the function pointer within a struct:

    struct state {
    struct state (*func)(void);
};

    Then in the loop:

    struct state state = { state1 };

while (state.func) {
    state = state.func();
}