views:

142

answers:

2

I'm a bit confused about how to implement my state machine.
I already know it's hierarchical since some states share the same action.
I determine what I need to do by these parameters:

  • Class (Values are: Base, Derived, Specific)
  • OpCode
  • Parameter 1 - optional
  • Parameter 2 - optional

My hierarchy is determined by the Class and the OpCode represents the action.
Derived can use the OpCodes of Base and Specific can use OpCodes of both Base and Derived.
The naive implementation is the following:

void (*const state_table [MAX_CLASSES][MAX_OPCODES]) (state *) {
  {base_state1, base_state2, NULL, NULL},
  {base_state1, base_state2, derived_state1, NULL},
  {base_state1,base_state2, derived_state1, specific_state3},
};

void dispatch(state *s)
{
  if (state_table[s->Class][s->OpCode] != NULL)
    state_table[s->Class][s->OpCode](s);
}

This will turn unmaintainable really quick.
Is there another way to map the state to a superclass?

EDIT:
Further calcualtion leads me to think that I'll probably use most if not all OpCodes but I will not use all of the Classes available to me.
Another clarification:
Some OpCodes might be shared through multiple derived and base Classes.
For example:

  • I have a Class called Any which is a Base class. It has the OpCodes: STATE_ON, STATE_OFF, STATE_SET.
  • I have another Class called MyGroup which is a Derived class. It has the OpCodes: STATE_FLIP, STATE_FLOP.

  • The third Class is a Specific class called ThingInMyGroup which has the OpCode: STATE_FLIP_FLOP_AND_FLOOP.

So a message with class Any is sent from the server, recieved in all clients and processed.

A message with class MyGroup is sent from the server, recieved in all clients and processed only on clients that belong to MyGroup, any OpCodes that are valid for the Any class are valid for the MyGroup class.

A message with class ThingInMyGroup is sent from the server, recieved in all clients and processed only on clients that belong to MyGroup and are a ThingInMyGroup*, any **OpCodes that are valid for the Any class and MyGroup class are valid for the ThingInMyGroup class.

After a message is received the client will ACK/NACK accordingly.

I prefer not to use switch cases or const arrays as they will become unmaintainable when they get bigger.
I need a flexible design that allows me:

  1. To specify which OpCodes are available for each Class.
  2. To specify a superclass for each Class and through that specification to allow me to call the function pointer that is represented by the current OpCode.
+1  A: 

I wrote a little tool that generates code similar to your naive implementation based on a mini-language. The language just specified the state-opcode-action relationships, all of the actions were just C functions conforming to a typedef.

It didn't handle the HSM aspect, but this would be relatively easy to add to a language.

I'd recommend taking this approach -- create a little language that gives you a clean way to describe the state machine, and then generate code based on that machine description. That way when you need to insert a new state a month from now, the whole thing isn't a tangled mess to edit.

Let me know if you want the code and I'll make sure it's still available somewhere.

bstpierre
The problem is that this state table doesn't really fit my needs because in reality I have to translate the **Class** and the **OpCode** to the index of the function since both doesn't start from 0, therefor I still need to map it with a switch case or some calculation in order to access the state_table.I have found this link http://www.accu-usa.org/Slides/samek0311.pdf but the code in it doesn't suit my needs. I actually need something simpler. Got any idea?
the_drow
Are your state tables huge? How many opcodes, classes, states?
bstpierre
**sizeof(OpCode)** = 8**sizeof(Class)** = 16That's a maximum of 16711425 possible states.Since there is overlapping there might be less.Basically the **OpCode** and the **Class** are the state, sometimes they have parameters, sometimes they don't.
the_drow
@bstpierre: see edit for more details.
the_drow
+1  A: 

There are several ways to deal with this. Here is one:

edit -- with general purpose hierarchy added

typedef unsigned op_code_type;
typedef void (*dispatch_type)(op_code_type);
typedef struct hierarchy_stack hierarchy_stack;
struct hierarchy_stack {
       dispatch_type func;
       hierarchy_stack *tail;
};

void dispatch(state *s, hierarchy_stack *stk) {
    if (!stk) {
          printf("this shouldn't have happened");
    } else {
          stk->func(s, stk->tail);
    }
}

void Base(state *s, hierarchy_stack *stk ) {
    switch (s->OpCode) {
          case bstate1:
               base_state1(s);
               break;
          case bstate2:
               base_state(2);
               break;
          default:
               dispatch(s, stk);
    }
}
void Derived(state *s, hierarchy_stack *stk ) {
    switch(s->opcode) {
           case dstate1:
                deriveds_state1(s);
                break;
           default:
                dispatch(s, stk);
    }
}
... 

NOTE : All function calls are tail calls.

This localizes your "class"es a good bit so that if you decide that Derived needs 100 more methods/opcodes then you only have to edit methods and the enum (or whatever) that you use to define opcodes.

Another, more dynamic way, to deal with this would be to have a parent pointer within each "class" that pointed to the "class" that would handle anything that it could not handle.

The 2D table approach is fast and flexible (Derived could have a different handler than Base for opcode 0), but it grows fast.

nategoose
Your first approach isn't hierarchical at all. It's just a plain state machine.
the_drow
It fits the example given (when I wrote it), but if you replace the direct call on the `default` case with a call by pointer you can easily make it hierarchical. You just need to keep up with parent states, or the hierarchy could be passed as an additional parameter (a list), which the default case passes to a dispatcher, who removes the hierarchy's head, uses that to call another handler, and passes the state event and the tail of the hierarchy to.
nategoose
My problem with it is the switch case.It will grow huge.I also don't get the purpose of hierarchy_stack.See this: http://www.accu-usa.org/Slides/samek0311.pdfIt's implemented using a for loop, the problem is that I don't really get it.Another problem is that I need something less flexible.I only need to share actions between states and allow the actions the return replys
the_drow