Newsgroup: it.comp.lang.c++
Titolo: Schema per una FSM

Salve a tutti,
mi trovo a dover scrivere una FSM un po' corposa (diciamo qualche
decina di stati e fino ad un centinaio di eventi da gestire) ma
semplice, con poche transizioni.  Inoltre le mie capacita' di C++ sono
limitate, ho visto in giro cose come State Pattern ed chemi di
ereditarieta' vari e altre cose complesse che sono completamente al di
fuori della mia portata.
Pensandoci un po' (e' la prima volta che scrivo una FSM in software,
l'ho sempre fatto in hardware) mi sembra di poterla ridurre
semplicemente ad una dispatch table in cui la chiave e' un ID unico
che caratterizza la combinazione stato/evento, e il valore e' il
puntatore a funzione membro che gestisce quell'evento in quello stato.
Ho buttato giu' una cosa del genere, vi sembra ragionevole?  Visto che
le transizioni sono poche, c'e' poco da mettere nella mappa quindi il
tempo di accesso e la dimensione della struttura sono contenute al
minimo (mi importa perche' deve girare su un ARM embedded), se quando
accedo alla mappa ottengo un iterator einvalido, e' segno che devo
ignorare l'evento.
Questo e' solo uno scheletro, in realta' poi gli eventi saranno
puntatori a oggetti che derivano da una classe base Event.
Thx.
<<<<<<<<<<<<<<<<<<   fsm.h   >>>>>>>>>>>>>>>>>>>>>>>
#include <map>
#include <iostream>
using namespace std;
enum State {STATE_IDLE, STATE_ONE, STATE_TWO, STATE_THREE,
NUMBER_OF_STATES};
enum Event {EVENT1, EVENT2, EVENT3, NUMBER_OF_EVENTS};
class Fsm
{
public:
    Fsm();
    ~Fsm();
    void feedEvent(Event event);
private:
    typedef void (Fsm::*EventHandler)(Event);   // puntatori ai metodi
di gestione degli eventi
    State state_;
    map<int,EventHandler> eventDispatchTable;
    void handleEvent1(Event event);
    void handleEvent2(Event event);
    void handleEvent3(Event event);
    int getStateEventCombinationId(State state, Event event)
{ return (state * NUMBER_OF_EVENTS + event); }
};
<<<<<<<<<<<<<<<<<<   fsm.cpp   >>>>>>>>>>>>>>>>>>>>>>>
#include "fsm.h"
Fsm::Fsm() :
    state_(STATE_IDLE)
{
    // crea mappa delle transizioni
 
eventDispatchTable.insert( make_pair(getStateEventCombinationId(STATE_IDLE,
EVENT1), &Fsm::handleEvent1) );
 
eventDispatchTable.insert( make_pair(getStateEventCombinationId(STATE_ONE,
EVENT2), &Fsm::handleEvent2) );
 
eventDispatchTable.insert( make_pair(getStateEventCombinationId(STATE_TWO,
EVENT3), &Fsm::handleEvent3) );
}
Fsm::~Fsm()
{}
void Fsm::feedEvent(Event event)
{
    int stateEventCombinationId = getStateEventCombinationId(state_,
event);
    map<int,EventHandler>::const_iterator i =
eventDispatchTable.find( stateEventCombinationId );
    if( i == eventDispatchTable.end() ) {
        cout << "Evento ignorato: state_ = " << state_ << ", event = "
<< event << endl;
    }
    else {
        (this->*(i->second))(event);
    }
}
void Fsm::handleEvent1(Event event)
{
    state_ = STATE_ONE;
    cout << "[Fsm::handleEvent1] event = " << event << ", next state =
STATE_ONE" << endl;
}
void Fsm::handleEvent2(Event event)
{
    state_ = STATE_TWO;
    cout << "[Fsm::handleEvent2] event = " << event << ", next state =
STATE_TWO" << endl;
}
void Fsm::handleEvent3(Event event)
{
    state_ = STATE_THREE;
    cout << "[Fsm::handleEvent2] event = " << event << ", next state =
STATE_THREE" << endl;
}

 semplice, con poche transizioni.
 > Pensandoci un po' (e' la prima volta che scrivo una FSM in software,
 > l'ho sempre fatto in hardware) mi sembra di poterla ridurre
 > semplicemente ad una dispatch table in cui la chiave e' un ID unico
 > che caratterizza la combinazione stato/evento, e il valore e' il
 > puntatore a funzione membro che gestisce quell'evento in quello stato.
Penso sia meglio usare un array bidimensionale:
   EventHandler eventDispatchTable[NUMBER_OF_STATES][NUMBER_OF_EVENTS];
L'array e' piu' veloce della mappa e, a meno che la grande maggioranza 
dei combinazioni stato-evento siano irraggiungibili (cioe' nel caso di 
matrice sparsa), e' anche piu' compatto. Ha i difetto che i numero degli 
stati e il numero degli eventi devono essere noti al compilatore, ma nel 
tuo caso mi sembra accettabile.
Alternativamente si puo' usare un array bidimensionale dinamico 
implementato usando un vector.
Volendo proprio usare una mappa, il codice risulta più leggibile, anche 
se meno efficiente, se si definisce come:
   map<std::pair<int,int>,EventHandler> eventDispatchTable;
che invece di essere acceduto con:
   int stateEventCombinationId = getStateEventCombinationId(
     state_,event);
   map<int,EventHandler>::const_iterator i =
     eventDispatchTable.find( stateEventCombinationId );
viene acceduto con:
   map<int,EventHandler>::const_iterator i =
     eventDispatchTable.find(make_pair(state_,event));
--
Carlo Milanesi

 se meno efficiente, se si definisce come:
[cut]
Si' e' vero, la mia "getStateEventCombinationId()" non piaceva nemmeno
a me, ma tanto sono solo un paio di linee che scrivo una volta sola e
poi mai piu', quindi non mi sembrava un grosso handicap.
Cmq ci penso su.
Grazie dei suggerimenti,
Pleg

 oltre sono NULL), che e' piu' della mia cache L1 :)
Mi sembrava poco plausibile che una FSM avesse meno del 30% di 
riempimento :)
Comunque c'e' un'altra tecnica che forse e' applicabile.
Memorizzare i puntatori a funzione in un array.
E memorizzare nella matrice gli indici di elementi di tale array.
In tal, al costo di introdurre un livello di indirettezza, si risparmia 
memoria, in quanto, se si puo' essere certi che le funzioni non sono 
piu' di 256, la matrice contiene singoli byte invece di puntatori a 32 
bit. Altrimenti, si dovrebbero usare word di 16 bit, che sono comunque 
piu' corte dei puntatori.
--
Carlo Milanesi

 piu' corte dei puntatori.
Si' avevo pensato anche a questo, e' una soluzione, risparmia memoria
e fa solo 3 accessi alla memoria (array -> vettore -> funzione).
Grazie dei suggerimenti,
Pleg