I have a state machine that looks like this:

           G--H
          /
A--B--C--D--E--F

I want to have a function, goToState(target) that has as an input argument the target state, and then the function will execute all the transitions starting from the current state until it reaches the target state.

For example, let's say that the current state is B and we call goToState(F). Then the function will do the following state transitions B->C, C->D, D->E, E->F.

The transitions work both ways so if current state is F and we call goToState(G), then the function will do F->E, E->D, D->G.

If we had a linear state machine (eg, no branch G--H), then I would just do an array of functions for each transition, in the legal order, and then find the index for current state and the index for the target state and call all the transition function in between those two indexes in a for loop.

However now that I have a branch, this method would not work. What would be the most efficient way to encode the legal transitions and to implement a function that executes them in the right order based on the target state in C?

CodePudding user response：

You can model the states as an array of structs, each of which contains a function pointer for the transition and an array of possible destination states.

Then, create a function that takes the current and destination state and have it loop through the list of possible states. If one matches the destination, put that at the start of an empty list of states and return the list. If not, recurse through each possible intermediate state until either one returns a nonempty list and add the current state to the front of the list.

After the recursive function returns, you can iterate through the list running the transitions.

(note: untested code)

typedef void (*func)(void);    // modify as needed
typedef enum { NONE=-1, A, B, C, D, E, F, G } states;
#define MAX_STATES 7

struct transitions {
    func transition;
    states slist[MAX_STATES];
};

struct tlist {
    struct transitions *trans;
    struct tlist *next;
};

struct transitions transitions[] = {
    { trans_a, { B, NONE } },
    { trans_b, { A, C, NONE } },
    { trans_c, { B, D, NONE } },
    { trans_d, { C, G, E, NONE } },
    { trans_e, { D, F, NONE } },
    { trans_f, { E, NONE } },
    { trans_g, { D, H, NONE } },
    { trans_h, { G, NONE } }
};

struct tlist *getStates(state start, state end)
{
    int i;
    for (i = 0; transitions[start].slist[i] != NONE; i  ) {
        if (transitions[start].slist[i] == end) {
            struct tlist *entry = malloc(sizeof *entry);
            entry->trans = transitions   start;
            entry->next = NULL;
            return entry;
        }

        struct tlist *list = getStates(transitions[start].slist[i], end);
        if (list) {
            struct tlist *entry = malloc(sizeof *entry);
            entry->trans = transitions   start;
            entry->next = list;
            return entry;
        }
    }
    return NULL;
}

CodePudding user response：

No matter the state machine, you'll want to avoid "stateghetti", which is what happens when each and every state makes multiple, local decisions on what state to execute next.

Instead, have each state return a result code. You can still have an array of function pointers no matter. Then at the top level of the program, write something along the lines of this pseudo:

while(...)
{
  result = state_machine[current_state]();
  current_state = evaluate(current_state, result);
}

The function evaluate() is the only place in your code where state transitions are allowed. Optionally it can double as your top-level error handler.

Then simply code down all dependencies you need inside this function:

...
if(state==C && result==OK)
  return D;

if(state==D)
{
  if(result==OK)
    return E;
  else
    return G;
}
...