典型的なステート マシンの実装パターンはありますか?
https://stackoverflow.com/questions/133214
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
単純なステートマシンを実装する必要があります。 C.
標準の switch ステートメントが最善の方法でしょうか?
現在の状態 (状態) と遷移のトリガーがあります。
switch(state)
{
case STATE_1:
state = DoState1(transition);
break;
case STATE_2:
state = DoState2(transition);
break;
}
...
DoState2(int transition)
{
// Do State Work
...
if(transition == FROM_STATE_2) {
// New state when doing STATE 2 -> STATE 2
}
if(transition == FROM_STATE_1) {
// New State when moving STATE 1 -> STATE 2
}
return new_state;
}
もっと良い方法はありますか 単純なステートマシンの場合
編集：C++ の場合は、Boost だと思います ステートチャート 図書館が最適かもしれません。ただし、それは可能です ない Cを手伝ってください。C のユースケースに集中してみましょう。
解決
私は、ほとんどのステート マシンに対してテーブル駆動のアプローチを使用することを好みます。
typedef enum { STATE_INITIAL, STATE_FOO, STATE_BAR, NUM_STATES } state_t;
typedef struct instance_data instance_data_t;
typedef state_t state_func_t( instance_data_t *data );
state_t do_state_initial( instance_data_t *data );
state_t do_state_foo( instance_data_t *data );
state_t do_state_bar( instance_data_t *data );
state_func_t* const state_table[ NUM_STATES ] = {
do_state_initial, do_state_foo, do_state_bar
};
state_t run_state( state_t cur_state, instance_data_t *data ) {
return state_table[ cur_state ]( data );
};
int main( void ) {
state_t cur_state = STATE_INITIAL;
instance_data_t data;
while ( 1 ) {
cur_state = run_state( cur_state, &data );
// do other program logic, run other state machines, etc
}
}
もちろん、これを拡張して複数のステート マシンなどをサポートすることもできます。移行アクションにも対応できます。
typedef void transition_func_t( instance_data_t *data );
void do_initial_to_foo( instance_data_t *data );
void do_foo_to_bar( instance_data_t *data );
void do_bar_to_initial( instance_data_t *data );
void do_bar_to_foo( instance_data_t *data );
void do_bar_to_bar( instance_data_t *data );
transition_func_t * const transition_table[ NUM_STATES ][ NUM_STATES ] = {
{ NULL, do_initial_to_foo, NULL },
{ NULL, NULL, do_foo_to_bar },
{ do_bar_to_initial, do_bar_to_foo, do_bar_to_bar }
};
state_t run_state( state_t cur_state, instance_data_t *data ) {
state_t new_state = state_table[ cur_state ]( data );
transition_func_t *transition =
transition_table[ cur_state ][ new_state ];
if ( transition ) {
transition( data );
}
return new_state;
};
テーブル駆動のアプローチは、保守と拡張が容易で、状態図へのマッピングも簡単です。
他のヒント
FSM について言及した別の C の質問に対する私の回答を見たことがあるかもしれません。私のやり方は次のとおりです。
FSM {
STATE(x) {
...
NEXTSTATE(y);
}
STATE(y) {
...
if (x == 0)
NEXTSTATE(y);
else
NEXTSTATE(x);
}
}
以下のマクロを定義した状態で
#define FSM
#define STATE(x) s_##x :
#define NEXTSTATE(x) goto s_##x
これは、特定のケースに合わせて変更できます。たとえば、次のようなファイルがあるとします。 FSMFILE FSM を駆動したいので、次の文字を読み取るアクションをマクロ自体に組み込むことができます。
#define FSM
#define STATE(x) s_##x : FSMCHR = fgetc(FSMFILE); sn_##x :
#define NEXTSTATE(x) goto s_##x
#define NEXTSTATE_NR(x) goto sn_##x
これで 2 種類のトランジションができました。1 つはステートに移行して新しい文字を読み取り、もう 1 つは入力を消費せずにステートに移行します。
次のような方法で EOF の処理を自動化することもできます。
#define STATE(x) s_##x : if ((FSMCHR = fgetc(FSMFILE) == EOF)\
goto sx_endfsm;\
sn_##x :
#define ENDFSM sx_endfsm:
このアプローチの良い点は、描画した状態図を実際に動作するコードに直接変換でき、逆に、コードから状態図を簡単に描画できることです。
FSM を実装する他の手法では、遷移の構造は制御構造 (while、if、switch ...) に埋め込まれ、変数値 (通常は state 変数)、優れた図を複雑なコードに関連付けるのは複雑な作業になる可能性があります。
私はこのテクニックを、残念ながらもう廃刊になってしまった偉大な雑誌「Computer Language」に掲載された記事から学びました。
私もテーブルアプローチを使用しました。ただし、オーバーヘッドが発生します。なぜポインタの 2 番目のリストを保存するのでしょうか?() のない C の関数は const ポインターです。したがって、次のことができます。
struct state;
typedef void (*state_func_t)( struct state* );
typedef struct state
{
state_func_t function;
// other stateful data
} state_t;
void do_state_initial( state_t* );
void do_state_foo( state_t* );
void do_state_bar( state_t* );
void run_state( state_t* i ) {
i->function(i);
};
int main( void ) {
state_t state = { do_state_initial };
while ( 1 ) {
run_state( state );
// do other program logic, run other state machines, etc
}
}
もちろん、あなたの恐怖要因によって異なります（つまり、安全性と速度の比較)、有効なポインタを確認することをお勧めします。3 つ程度のステートを超えるステート マシンの場合、上記のアプローチは、同等のスイッチまたはテーブルのアプローチよりも命令が少なくなるはずです。次のようにマクロ化することもできます。
#define RUN_STATE(state_ptr_) ((state_ptr_)->function(state_ptr_))
また、OPの例から、ステートマシンを考える/設計するときに行うべき単純化があると感じます。遷移状態をロジックに使用するべきではないと思います。各状態関数は、過去の状態を明示的に知らなくても、指定された役割を実行できる必要があります。基本的には、現在の状態から別の状態に移行する方法を設計します。
最後に、「機能」境界に基づいてステート マシンの設計を開始するのではなく、そのためにサブ関数を使用します。代わりに、続行する前に何かが起こるまで待機する必要があるかどうかに基づいて状態を分割します。これにより、結果が得られるまでにステート マシンを実行する必要がある回数を最小限に抑えることができます。これは、I/O 関数または割り込みハンドラーを作成するときに重要になることがあります。
また、古典的な switch ステートメントの長所と短所もいくつか示します。
長所:
- 言語で書かれているので文書化されており、明確です
- 状態は呼び出された場所で定義されます
- 1 回の関数呼び出しで複数の状態を実行できる
- すべての状態に共通のコードは switch ステートメントの前後で実行できます。
短所:
- 1 回の関数呼び出しで複数の状態を実行できる
- すべての状態に共通のコードは switch ステートメントの前後で実行できます。
- スイッチの実装が遅くなる可能性がある
長所と短所の 2 つの属性に注目してください。この切り替えにより、州間で過度の共有が可能になり、州間の相互依存関係が管理不能になる可能性があると思います。ただし、少数の州では、これが最も読みやすく保守しやすい可能性があります。
単純なステート マシンの場合は、switch ステートメントと状態の enum 型を使用するだけです。入力に基づいて switch ステートメント内でトランジションを実行します。実際のプログラムでは、遷移点を確認するために「if(input)」を変更することになるのは明らかです。お役に立てれば。
typedef enum
{
STATE_1 = 0,
STATE_2,
STATE_3
} my_state_t;
my_state_t state = STATE_1;
void foo(char input)
{
...
switch(state)
{
case STATE_1:
if(input)
state = STATE_2;
break;
case STATE_2:
if(input)
state = STATE_3;
else
state = STATE_1;
break;
case STATE_3:
...
break;
}
...
}
もあります ロジックグリッド ステートマシンが大きくなるにつれて保守しやすくなります
で Martin Fowler の UML 蒸留, 、彼は第 10 章のステートマシン図で次のように述べています (冗談ではありません) (強調は私のものです)。
状態図は主に 3 つの方法で実装できます。 ネストされたスイッチ, 、 状態パターン, 、 そして 状態テーブル.
携帯電話のディスプレイの状態の簡略化された例を使用してみましょう。
ネストされたスイッチ
Fowler は C# コードの例を示しましたが、私はそれを私の例に適応させました。
public void HandleEvent(PhoneEvent anEvent) {
switch (CurrentState) {
case PhoneState.ScreenOff:
switch (anEvent) {
case PhoneEvent.PressButton:
if (powerLow) { // guard condition
DisplayLowPowerMessage(); // action
// CurrentState = PhoneState.ScreenOff;
} else {
CurrentState = PhoneState.ScreenOn;
}
break;
case PhoneEvent.PlugPower:
CurrentState = PhoneState.ScreenCharging;
break;
}
break;
case PhoneState.ScreenOn:
switch (anEvent) {
case PhoneEvent.PressButton:
CurrentState = PhoneState.ScreenOff;
break;
case PhoneEvent.PlugPower:
CurrentState = PhoneState.ScreenCharging;
break;
}
break;
case PhoneState.ScreenCharging:
switch (anEvent) {
case PhoneEvent.UnplugPower:
CurrentState = PhoneState.ScreenOff;
break;
}
break;
}
}
状態パターン
GoF State パターンを使用した例の実装は次のとおりです。
状態テーブル
ファウラーからインスピレーションを得て、私の例を表に示します。
Source State Target State Event Guard Action -------------------------------------------------------------------------------------- ScreenOff ScreenOff pressButton powerLow displayLowPowerMessage ScreenOff ScreenOn pressButton !powerLow ScreenOn ScreenOff pressButton ScreenOff ScreenCharging plugPower ScreenOn ScreenCharging plugPower ScreenCharging ScreenOff unplugPower
比較
ネストされたスイッチはすべてのロジックを 1 か所にまとめますが、状態や遷移が多数ある場合、コードが読みにくくなることがあります。おそらく、他のアプローチ (ポリモーフィズムや解釈なし) よりも安全で検証が簡単です。
State パターンの実装では、ロジックが複数の個別のクラスに分散される可能性があり、全体としての理解が困難になる可能性があります。一方、少人数クラスは個別に理解しやすいです。トランジションは階層内のメソッドであり、コードに多くの変更が加えられる可能性があるため、トランジションを追加または削除して動作を変更する場合、設計は特に脆弱になります。小さなインターフェイスの設計原則に従っている場合は、このパターンがあまりうまく機能しないことがわかるでしょう。ただし、ステート マシンが安定している場合は、そのような変更は必要ありません。
状態テーブルのアプローチでは、コンテンツに対して何らかのインタプリタを作成する必要があります (使用している言語にリフレクションがある場合は、これがより簡単になる可能性があります)。これは、事前に行う必要がある作業が多大になる可能性があります。Fowler 氏が指摘しているように、テーブルがコードから分離されている場合は、再コンパイルせずにソフトウェアの動作を変更できます。ただし、これにはセキュリティ上の影響がいくつかあります。ソフトウェアは外部ファイルの内容に基づいて動作します。
編集（実際にはC言語用ではありません）
流暢なインターフェイス (別名内部ドメイン固有言語) アプローチもあります。これはおそらく、次のような言語によって促進されます。 最高級の関数. 。の ステートレスライブラリ 存在しており、そのブログではコード付きの簡単な例が示されています。あ Java 実装 (Java8 以前) が議論されています。見せてもらいました GitHub の Python の例 同じように。
単純な場合には、スタイルを切り替える方法を使用できます。過去にうまく機能したと私が発見したのは、遷移にも対処することです。
static int current_state; // should always hold current state -- and probably be an enum or something
void state_leave(int new_state) {
// do processing on what it means to enter the new state
// which might be dependent on the current state
}
void state_enter(int new_state) {
// do processing on what is means to leave the current atate
// might be dependent on the new state
current_state = new_state;
}
void state_process() {
// switch statement to handle current state
}
boost ライブラリについては何も知りませんが、このタイプのアプローチは非常にシンプルで、外部依存関係を必要とせず、実装も簡単です。
switch() は C でステート マシンを実装する強力で標準的な方法ですが、多数のステートがある場合は保守性が低下する可能性があります。もう 1 つの一般的な方法は、関数ポインターを使用して次の状態を保存することです。この簡単な例は、セット/リセット フリップフロップを実装します。
/* Implement each state as a function with the same prototype */
void state_one(int set, int reset);
void state_two(int set, int reset);
/* Store a pointer to the next state */
void (*next_state)(int set, int reset) = state_one;
/* Users should call next_state(set, reset). This could
also be wrapped by a real function that validated input
and dealt with output rather than calling the function
pointer directly. */
/* State one transitions to state one if set is true */
void state_one(int set, int reset) {
if(set)
next_state = state_two;
}
/* State two transitions to state one if reset is true */
void state_two(int set, int reset) {
if(reset)
next_state = state_one;
}
Jonathan Valvano と Ramesh Yerraballi による edx.org コース「Embedded Systems - Shape the World UTAustinX - UT.6.02x」の第 10 章で、Moore FSM の非常に洗練された C 実装を見つけました。
struct State {
unsigned long Out; // 6-bit pattern to output
unsigned long Time; // delay in 10ms units
unsigned long Next[4]; // next state for inputs 0,1,2,3
};
typedef const struct State STyp;
//this example has 4 states, defining constants/symbols using #define
#define goN 0
#define waitN 1
#define goE 2
#define waitE 3
//this is the full FSM logic coded into one large array of output values, delays,
//and next states (indexed by values of the inputs)
STyp FSM[4]={
{0x21,3000,{goN,waitN,goN,waitN}},
{0x22, 500,{goE,goE,goE,goE}},
{0x0C,3000,{goE,goE,waitE,waitE}},
{0x14, 500,{goN,goN,goN,goN}}};
unsigned long currentState; // index to the current state
//super simple controller follows
int main(void){ volatile unsigned long delay;
//embedded micro-controller configuration omitteed [...]
currentState = goN;
while(1){
LIGHTS = FSM[currentState].Out; // set outputs lines (from FSM table)
SysTick_Wait10ms(FSM[currentState].Time);
currentState = FSM[currentState].Next[INPUT_SENSORS];
}
}
調べてみるとよいかもしれません リベロ FSM ジェネレーター ソフトウェア。状態記述言語や (Windows) 状態図エディタから、C、C++、Java などのコードを生成できます。さらに素晴らしいドキュメントと図も含まれています。ソースとバイナリのソース アイマティクス
この記事 これは状態パターンに適しています (ただし、これは C++ であり、特に C ではありません)。
本に手を出していただければ」ヘッドファーストのデザインパターン」の説明と例が非常にわかりやすいです。
私のお気に入りのパターンの 1 つは、州のデザイン パターンです。同じ与えられた入力セットに対して異なる応答または動作をします。
ステート マシンに switch/case ステートメントを使用する場合の問題の 1 つは、より多くのステートを作成するほど、switch/case の読み取り/保守が難しくなり、扱いにくくなり、整理されていないスパゲッティ コードが促進され、何かを壊すことなく変更することがますます困難になることです。デザイン パターンを使用すると、データをより適切に整理できることがわかりました。これが抽象化のポイントです。どの状態から来たのかに基づいて状態コードを設計するのではなく、新しい状態に入ったときにその状態を記録するようにコードを構造化します。こうすることで、以前の状態の記録を効果的に取得できます。私は @JoshPetit の答えが好きで、GoF 本からそのまま引用して、彼の解決策をさらに一歩進めました。
stateCtxt.h:
#define STATE (void *)
typedef enum fsmSignal
{
eEnter =0,
eNormal,
eExit
}FsmSignalT;
typedef struct fsm
{
FsmSignalT signal;
// StateT is an enum that you can define any which way you want
StateT currentState;
}FsmT;
extern int STATECTXT_Init(void);
/* optionally allow client context to set the target state */
extern STATECTXT_Set(StateT stateID);
extern void STATECTXT_Handle(void *pvEvent);
状態Ctxt.c:
#include "stateCtxt.h"
#include "statehandlers.h"
typedef STATE (*pfnStateT)(FsmSignalT signal, void *pvEvent);
static FsmT fsm;
static pfnStateT UsbState ;
int STATECTXT_Init(void)
{
UsbState = State1;
fsm.signal = eEnter;
// use an enum for better maintainability
fsm.currentState = '1';
(*UsbState)( &fsm, pvEvent);
return 0;
}
static void ChangeState( FsmT *pFsm, pfnStateT targetState )
{
// Check to see if the state has changed
if (targetState != NULL)
{
// Call current state's exit event
pFsm->signal = eExit;
STATE dummyState = (*UsbState)( pFsm, pvEvent);
// Update the State Machine structure
UsbState = targetState ;
// Call the new state's enter event
pFsm->signal = eEnter;
dummyState = (*UsbState)( pFsm, pvEvent);
}
}
void STATECTXT_Handle(void *pvEvent)
{
pfnStateT newState;
if (UsbState != NULL)
{
fsm.signal = eNormal;
newState = (*UsbState)( &fsm, pvEvent );
ChangeState( &fsm, newState );
}
}
void STATECTXT_Set(StateT stateID)
{
prevState = UsbState;
switch (stateID)
{
case '1':
ChangeState( State1 );
break;
case '2':
ChangeState( State2);
break;
case '3':
ChangeState( State3);
break;
}
}
statehandlers.h:
/* define state handlers */
extern STATE State1(void);
extern STATE State2(void);
extern STATE State3(void);
statehandlers.c:
#include "stateCtxt.h:"
/* Define behaviour to given set of inputs */
STATE State1(FsmT *fsm, void *pvEvent)
{
STATE nextState;
/* do some state specific behaviours
* here
*/
/* fsm->currentState currently contains the previous state
* just before it gets updated, so you can implement behaviours
* which depend on previous state here
*/
fsm->currentState = '1';
/* Now, specify the next state
* to transition to, or return null if you're still waiting for
* more stuff to process.
*/
switch (fsm->signal)
{
case eEnter:
nextState = State2;
break;
case eNormal:
nextState = null;
break;
case eExit:
nextState = State2;
break;
}
return nextState;
}
STATE State3(FsmT *fsm, void *pvEvent)
{
/* do some state specific behaviours
* here
*/
fsm->currentState = '2';
/* Now, specify the next state
* to transition to
*/
return State1;
}
STATE State2(FsmT *fsm, void *pvEvent)
{
/* do some state specific behaviours
* here
*/
fsm->currentState = '3';
/* Now, specify the next state
* to transition to
*/
return State3;
}
ほとんどのステート マシンでは、特に有限状態マシンである各状態は、次の状態がどうあるべきか、次の状態に移行するための基準を知っています。緩やかな状態設計の場合、これは当てはまらない可能性があるため、状態遷移用の API を公開するオプションが必要になります。さらに抽象化したい場合は、各状態ハンドラーを独自のファイルに分離できます。これは、GoF 本の具象状態ハンドラーと同等です。設計が少数の状態のみを含む単純な場合は、簡略化するために、stateCtxt.c と statehandlers.c の両方を 1 つのファイルに結合できます。
私の経験では、「switch」ステートメントを使用するのが、可能な複数の状態を処理する標準的な方法です。状態ごとの処理に遷移値を渡していることに驚きましたが。ステート マシンの要点は、各状態が 1 つのアクションを実行することだと考えていました。次に、次のアクション/入力によって、どの新しい状態に遷移するかが決まります。したがって、各状態処理関数が状態に入るために修正されたことをすべて即座に実行し、その後、別の状態への移行が必要かどうかを判断することを期待していました。
というタイトルの本があります C/C++ の実践的なステートチャート。ただし、それは 方法 私たちが必要とするものには重すぎます。
をサポートするコンパイラの場合 __COUNTER__ 、単純な (ただし大規模な) ステート マシンに使用できます。
#define START 0
#define END 1000
int run = 1;
state = START;
while(run)
{
switch (state)
{
case __COUNTER__:
//do something
state++;
break;
case __COUNTER__:
//do something
if (input)
state = END;
else
state++;
break;
.
.
.
case __COUNTER__:
//do something
if (input)
state = START;
else
state++;
break;
case __COUNTER__:
//do something
state++;
break;
case END:
//do something
run = 0;
state = START;
break;
default:
state++;
break;
}
}
使用する利点 __COUNTER__ ハードコード化された数字の代わりに、他の州の真ん中に状態を追加することができるということです。コンパイラがサポートしていない場合 __COUNTER__, 、限られた方法では、予防策を講じて使用することが可能です __LINE__
C++ では、次の点を考慮してください。 状態パターン.
あなたの質問は、「典型的なデータベース実装パターンはありますか?」に似ています。答えは、何を達成したいかによって異なります。より大きな決定論的ステート マシンを実装したい場合は、モデルとステート マシン ジェネレーターを使用できます。例は、www.StateSoft.org - SM Gallery でご覧いただけます。ヤヌシュ・ドブロヴォルスキ
C では、単純なマシンの場合、最終的には次のようなものを使用することがよくあります。
イベント駆動型 FSM は、アクション (FsmAction) に関連付けられた状態オブジェクト (FsmState)、および現在の状態とイベントによって定義された遷移 (FsmEdge) によって記述されます。
また、FSM とユーザー データの両方の保存と受け渡しを提供して、FSM にバインドされた情報とユーザーにバインドされた情報を分離し、同じ FSM の複数のインスタンスを許可します。同じ説明を使用しますが、異なるユーザー データを渡します)。
イベントは整数型 (FsmEvent) で表されます。負の値は、特別な共通イベント (Reset、None、Any、Empty、End) を許可するために実装によって予約されています。非ネガティブなイベントはユーザー定義です。
簡単にするために、遷移は配列にリストされ、配列の順序で照合が試行され、基本的に遷移の優先順位が提供されます。オプションのガード機能があります。次の状態は、遷移リスト内で直接指定することも、ジャンプ関数によって指定することもでき、これにより、動的な FSM 動作を可能にする柔軟性が向上します。
遷移の説明では、NULL の現在の状態は任意の状態に一致し、ワイルドカード イベント (Any) は任意のイベントに一致します。いずれにせよ、遷移をトリガーしたイベントの実際の値はジャンプ関数とガード関数に渡されます。
複雑な FSM の場合、単純なエッジ アレイ ソリューションでは非効率すぎる可能性があります。その場合、エッジ配列と遷移行列または状態隣接リストに変換されたイベント エントリを使用して、適切なジャンプ関数を実装できます。
ステート アクションは、ステートに入る (Enter)、ステートから出る (Leave)、およびステート内 (State) の操作を区別するリエントラント関数で実装されることを目的としています。このようにして、ローカル状態情報をカプセル化し、静的関数変数で保存できます。
通常、状態の開始および終了アクションは特に問題なく実行され、新しいイベントは返されません (None)。そうでない場合、新しいイベントはトラップされ、すぐに返されます。これにより、現在の状態を終了するときに遷移が発生した場合に効果的に遷移を防ぐことができます。
FSM ステップ関数 (fsmStep) は、新しいイベントを使用して遷移をトリガーするか、イベントなし (None) を使用して現在のステートのインステート アクションを実行して、FSM の単一ステップを実行します。ステップ関数は、処理または FSM に再供給できる、新しく発行されたイベントを返します。イベントがない場合、遷移が見つからない場合、または終了状態に到達した場合は、それぞれ「None」、「Empty」および「End」です。
#ifndef FSM_H_
#define FSM_H_
#include <stdbool.h>
#include <stdint.h>
/** FSM enum type */
typedef enum
{
// Events and return values
fsm_User = 0, ///< User events start with this id
fsm_Reset = -1, ///< Reset event
fsm_None = -2, ///< No event
fsm_Any = -3, ///< Any event, used as a wildcard
fsm_Empty = -4, ///< No transition found for event
fsm_End = -5, ///< Final state event generated when FSM reaches end state, or stop processing when used in transition
// Action types
fsm_Enter = 0, ///< Entry action
fsm_State, ///< In-state action
fsm_Leave ///< Exit action
} fsm_e;
typedef int FsmEvent; ///< Type for events
typedef struct FsmState FsmState; ///< Type for states
typedef struct FsmEdge FsmEdge; ///< Type for edges (transitions)
/** State action functor
@param state Pointer to this state
@param type Action type (Enter/State/Leave)
@param frto Pointer to from(Enter)/to(Leave) state, NULL otherwise
@param data User data
@return Event id in case of a new triggered event, fsm_None otherwise
*/
typedef FsmEvent (*FsmAction)(FsmState *state, fsm_e type, FsmState *frto, void *data);
/** FSM state object */
struct FsmState
{
FsmAction action; ///< Per-state action
void *data; ///< Per-state data
};
/** State jump functor
@param edge Pointer to this edge
@param state Pointer to the actual current state
@param event Event id that triggered the transition
@param data User data
@return Pointer to the next state and NULL for end state
*/
typedef FsmState *(*FsmJump)(FsmEdge *edge, FsmState *state, FsmEvent event, void *data);
/** Guard function
@param edge Pointer to this edge
@param state Pointer to the actual current state
@param event Event id that triggered the transition
@param data User data
@return Guard result
*/
typedef bool (*FsmGuard)(FsmEdge *edge, FsmState *state, FsmEvent event, void *data);
/** FSM edge transition */
struct FsmEdge
{
FsmState *state; ///< Matching current state pointer, or NULL to match any state
FsmEvent event; ///< Matching event id or fsm_Any for wildcard
void *next; ///< Next state pointer (FsmState *) or jump function (FsmJump)
FsmGuard guard; ///< Transition guard function
void *data; ///< Per-edge data
};
typedef struct Fsm Fsm;
struct Fsm
{
FsmState *state; ///< Pointer to the state array
size_t states; ///< Number of states
void **stateData; ///< Pointer to user state data array
FsmEdge *edge; ///< Pointer to the edge transitions array
size_t edges; ///< Number of edges
void **edgeData; ///< Pointer to user edge data array
FsmEvent event; ///< Current/last event
fsm_e type; ///< Current/last action type
FsmState *current; ///< Pointer to the current state
void *data; ///< Per-fsm data
};
#define fsm_INIT { 0 }
static inline FsmEvent
fsmStep(Fsm *f, FsmEvent e)
{
FsmState *cp = f->current; // Store current state
FsmEvent ne = fsm_None; // Next event
// User state data
void *us = (f->stateData && cp) ? f->stateData[cp - f->state] : NULL;
if (!cp && e == fsm_None)
e = fsm_Reset; // Inject reset into uninitialized FSM
f->event = e;
switch (e)
{
case fsm_Reset:
{
// Exit current state
if (cp && cp->action)
{
f->type = fsm_Leave, ne = cp->action(cp, fsm_Leave, f->state, us);
if (ne != fsm_None)
return ne; // Leave action emitted event
}
FsmState *ps = cp;
cp = f->current = f->state; // First state in array is entry state
if (!cp)
return fsm_End; // Null state machine
if (cp->action)
{
us = f->stateData ? f->stateData[0] : NULL;
f->type = fsm_Enter, ne = cp->action(cp, fsm_Enter, ps, us);
}
}
break;
case fsm_None: // No event, run in-state action
if (cp->action)
f->type = fsm_State, ne = cp->action(cp, fsm_State, NULL, us);
break;
default: // Process user transition event
ne = fsm_Empty; // Default return in case no transition is found
// Search transition in listing order
for (size_t i = 0; i < f->edges; ++i)
{
FsmEdge *ep = &f->edge[i];
// Check for state match (null edge state matches any state)
if (ep->state && ep->state != cp)
continue; // Not a match
// Check for stop processing filter
if (ep->event == fsm_End)
break;
ne = fsm_None; // Default return for a transition
// Check for event match
if (ep->event == e || ep->event == fsm_Any)
{
// User edge data
void *ue = f->edgeData ? f->edgeData[i] : NULL;
// Check transition guard
if (!ep->guard || ep->guard(ep, cp, e, ue))
{
// Resolve next state pointer (NULL, new state pointer or jump function)
FsmState *np = (!ep->next) ? NULL
: ((FsmState *)(ep->next) >= f->state && (FsmState *)(ep->next) < (f->state + f->states)) ? (FsmState *)(ep->next)
: ((FsmJump)(ep->next))(ep, cp, e, ue);
if (cp->action)
{
f->type = fsm_Leave, ne = cp->action(cp, fsm_Leave, np, us);
if (ne != fsm_None)
return ne; // Leave action emitted event
}
if (!np) // Final state reached if next state is NULL
ne = fsm_End;
else if (np->action)
{
us = f->stateData ? f->stateData[np - f->state] : NULL;
f->type = fsm_Enter, ne = np->action(np, fsm_Enter, cp, us);
}
cp = np; // New state value
// Transition executed, stop
break;
}
}
}
}
f->current = cp; // Commit current state
return ne; // Last event value
}
static inline FsmEvent
fsmReset(Fsm *f)
{
return fsmStep(f, fsm_Reset);
}
#endif // FSM_H_
以下に、FSM 実装を定義して使用する方法を理解するための非常に簡単なテストを示します。ユーザー定義のイベントはなく、FSM データ (文字列)、すべての状態に対する同じ状態アクション、および共有ジャンプ関数のみがあります。
#include <stdio.h>
#include "fsm.h"
// State action example
static FsmEvent
state_action(FsmState *s, fsm_e t, FsmState *ft, void *us)
{
FsmEvent e = fsm_None; // State event
const char *q = "?";
switch (t)
{
case fsm_Enter:
q = "enter";
break;
case fsm_Leave:
q = "leave";
break;
default /* fsm_State */:
q = "state";
}
printf("%s %s\n", (const char *)s->data, q);
return e;
}
// States
FsmState fs[] =
{
{ state_action, "S0" },
{ state_action, "S1" },
{ state_action, "S2" },
};
// Transition jump example
static FsmState *
state_jump(FsmEdge *t, FsmState *s, FsmEvent e, void *ue)
{
if (s == &fs[0])
return &fs[1];
if (s == &fs[2])
return NULL; // End state
return NULL; // Trap
}
// Transition guard example
static bool
count_attempt(FsmEdge *t, FsmState *s, FsmEvent e, void *ue)
{
static int c = 0;
++c;
bool b = c == 3;
printf("guard is %s\n", b ? "true" : "false");
return b;
}
// Transitions
FsmEdge fe[] =
{
{ &fs[0], fsm_Any, state_jump }, // Using jump function, no guard
{ &fs[1], fsm_Any, &fs[2], count_attempt }, // Using direct state and guard
{ &fs[2], fsm_Any, state_jump }, // Using jump function, no guard
};
int
main(int argc, char **argv)
{
Fsm f = { fs, 3, NULL, fe, 3, NULL, };
fsmReset(&f);
do
{
fsmStep(&f, fsm_None);
} while (fsmStep(&f, fsm_Any) != fsm_End);
return 0;
}
Boost にはステートチャート ライブラリがあります。 http://www.boost.org/doc/libs/1_36_0/libs/statechart/doc/index.html
ただし、その用途については話すことができません。私自身は（まだ）使っていません
