CODEWITHSUNDEEP
cfunction-pointersfsm
John Rivers
John Rivers

Reputation: 1307

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.

Upvotes: 1

Views: 8055

Answers (5)

Tom
Tom

Reputation: 1

In case others want use a free framework for an fsm, please have a look at http://www.block-net.de/Programmierung/cpp/fsm/fsm.html There is a C and C++ finite state machine framework including state chart generator with PlantUML.

Upvotes: 0

Vaclav Cechticky
Vaclav Cechticky

Reputation: 31

Here you might find an answer on your question: http://code.google.com/p/fwprofile/

It's an open source version (GNU GPLv3) of the state machine implemented in C. The concept and implementation is well-suited for use in mission-critical applications. There are deployments in industrial applications.

Upvotes: 3

caf
caf

Reputation: 239011

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();
}

Upvotes: 3

R.. GitHub STOP HELPING ICE
R.. GitHub STOP HELPING ICE

Reputation: 215193

It's impossible in C to declare a function which returns a pointer to a function of its own type. Moreover, you cannot use void * because C does not allow conversion between function and object pointers. Instead you can use:

typedef void (*generic_func_ptr)(void);
typedef generic_func_ptr (*state_func_ptr)(void);
generic_func_ptr state1(void), state2(void), state3(void);
state_func_ptr fp;

while(fp)
    fp = (state_func_ptr)fp();

Ugly, but it works. Instead, I would consider using a switch statement. It's a lot cleaner for implementing state machines.

Upvotes: 1

Keith Nicholas
Keith Nicholas

Reputation: 44288

1) typedef void(*state_fp)(void); 

state_fp state1(void) { }

2) depends, a small loop with the code built into the function will be faster than making function calls. eg, a switch statement where each state is implemented in the switch statement, however, if there is too many case statements, this will degrade below function calls

Upvotes: 0

Related Questions