일반적인 상태 머신 구현 패턴이 있습니까?
https://stackoverflow.com/questions/133214
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
우리는 간단한 상태 머신을 구현해야 합니다. 씨.
표준 스위치 문이 가장 좋은 방법입니까?
현재 상태(state)와 전환에 대한 트리거가 있습니다.
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
이제 두 가지 유형의 전환이 있습니다. 하나는 상태로 가서 새로운 캐릭터를 읽고 다른 하나는 입력을 소비하지 않고 상태로갑니다.
다음과 같은 것과 함께 EOF 처리를 자동화 할 수도 있습니다.
#define STATE(x) s_##x : if ((FSMCHR = fgetc(FSMFILE) == EOF)\
goto sx_endfsm;\
sn_##x :
#define ENDFSM sx_endfsm:
이 접근법의 좋은 점은 작업 코드로 그린 상태 다이어그램을 직접 변환 할 수 있으며 반대로 코드에서 상태 다이어그램을 쉽게 그릴 수 있다는 것입니다.
FSM을 구현하기위한 다른 기술에서 전이의 구조는 제어 구조에 묻히고 (wew, if, switch ...) 변수 값 (팁으로 A state 변수) 및 NICE 다이어그램을 복잡한 코드와 관련시키는 것은 복잡한 작업 일 수 있습니다.
나는 불행히도 더 이상 출판되지 않은 Great "Computer Language"잡지에 나온 기사 에서이 기술을 배웠습니다.
나는 또한 테이블 접근 방식을 사용했습니다.그러나 오버헤드가 있습니다.두 번째 포인터 목록을 저장하는 이유는 무엇입니까?()가 없는 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 문 전후에 실행될 수 있습니다.
단점:
- 하나의 함수 호출로 여러 상태를 실행할 수 있습니다.
- 모든 상태에 공통된 코드는 switch 문 전후에 실행될 수 있습니다.
- 스위치 구현이 느려질 수 있음
찬반 양론인 두 가지 속성에 주목하세요.저는 전환이 상태 간에 너무 많은 공유 기회를 허용하고 상태 간의 상호의존성을 관리하기 어렵게 만들 수 있다고 생각합니다.그러나 소수의 상태에서는 가장 읽기 쉽고 유지 관리가 용이할 수 있습니다.
간단한 상태 머신의 경우 스위치 명령문과 주에 열거 된 유형을 사용하십시오. 입력을 기반으로 스위치 명령문 내에서 전환을 수행하십시오. 실제 프로그램에서는 전환 지점을 확인하기 위해 "if (입력)"를 분명히 변경합니다. 도움이 되었기를 바랍니다.
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;
}
...
}
또한있다 논리 그리드 상태 머신이 커질수록 유지 관리가 더 쉬워집니다.
~ 안에 마틴 파울러의 UML이 증류되었습니다, 그는 10 장 State Machine Diagrams (강조 광산)에서 다음과 같이 말합니다.
상태 다이어그램은 세 가지 주요 방법으로 구현할 수 있습니다. 중첩 스위치,, 상태 패턴, 그리고 상태 테이블.
휴대폰 디스플레이 상태의 단순화 된 예를 사용해 봅시다.
중첩 스위치
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 상태 패턴과 함께 내 예제를 구현했습니다.
상태 테이블
Fowler에서 영감을 얻은 다음 내 예를위한 테이블이 있습니다.
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
비교
중첩 스위치는 모든 논리를 한 지점에 유지하지만 많은 상태와 전환이있을 때 코드를 읽기가 어려울 수 있습니다. 다른 접근법 (다형성이나 해석 없음)보다 더 안전하고 검증하는 것이 더 안전하고 쉽습니다.
상태 패턴 구현은 잠재적으로 여러 개의 별도 클래스에 대한 논리를 퍼 뜨리므로 전체 문제로 이해할 수 있습니다. 반면에 작은 수업은 별도로 이해하기 쉽습니다. 전환을 추가하거나 제거하여 동작을 변경하거나 제거하면 디자인이 특히 깨지기 쉽습니다. 작은 인터페이스의 디자인 원칙에 따라 살고 있다면이 패턴이 실제로 그렇게 잘되지 않는다는 것을 알 수 있습니다. 그러나 상태 기계가 안정적이면 그러한 변경이 필요하지 않습니다.
State Tables 접근 방식은 콘텐츠에 대해 어떤 종류의 통역사를 작성해야합니다 (사용중인 언어에 반영되는 경우 더 쉬울 수 있음). Fowler가 지적한 것처럼 테이블이 코드와 분리되어 있으면 다시 컴파일하지 않고 소프트웨어의 동작을 수정할 수 있습니다. 그러나 이것은 몇 가지 보안 영향을 미칩니다. 소프트웨어는 외부 파일의 내용을 기반으로 작동합니다.
편집 (실제로 C 언어가 아님)
유창한 인터페이스 (일명 내부 도메인 별 언어) 접근법도 있으며, 아마도 언어로 촉진 될 수 있습니다. 일류 기능. 그만큼 무국적 도서관 존재하며 해당 블로그는 코드가있는 간단한 예를 보여줍니다. ㅏ Java 구현 (Pre 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에서 상태 머신을 구현하는 강력하고 표준적인 방법이지만 많은 상태가 있으면 유지 관리 가능성을 줄일 수 있습니다. 또 다른 일반적인 방법은 기능 포인터를 사용하여 다음 상태를 저장하는 것입니다. 이 간단한 예제는 Set/Reset Flip-Flop을 구현합니다.
/* 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;
}
Edx.org 코스 임베디드 시스템에서 Moore FSM의 정말로 매끄러운 C 구현을 발견했습니다. Jonathan Valvano와 Ramesh Yerraballi의 World the World Utaustinx -UT.6.02X, 10 장 ....
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 및 기타 여러에 대한 코드를 생성 할 수 있습니다. 출처와 바이너리 Imatix
이 기사 상태 패턴에 적합합니다 (특히 C가 아닌 C ++이지만).
책에 손을 대면 "첫 번째 디자인 패턴을 헤드하십시오", 설명과 예는 매우 분명합니다.
내가 가장 좋아하는 패턴 중 하나는 상태 디자인 패턴입니다. 주어진 입력 세트에 다르게 응답하거나 행동합니다.
상태 머신에 스위치/케이스 명령문을 사용하는 데있어 문제 중 하나는 더 많은 상태를 만들면 스위치/케이스가 읽기/유지하기가 어려워지고 조직화되지 않은 스파게티 코드를 촉진하며 무언가를 깨지 않고 변경하기가 점점 어려워지는 것입니다. 디자인 패턴을 사용하면 데이터를 더 잘 정리하는 데 도움이됩니다. 이는 추상화의 요점입니다. 당신이 온 상태를 중심으로 주 코드를 설계하는 대신, 새로운 상태를 입력 할 때 상태를 기록하도록 코드를 구조화하십시오. 그렇게하면 이전 상태의 기록을 효과적으로 얻습니다. 나는 @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);
statectxt.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;
}
대부분의 주 머신의 경우, esp. 유한 상태 기계, 각주는 다음 상태가 무엇인지, 다음 상태로 전환하기위한 기준을 알게 될 것입니다. 느슨한 상태 설계의 경우 그렇지 않을 수 있으므로 전환 상태를위한 API를 노출시키는 옵션입니다. 더 많은 추상화를 원한다면 각 상태 핸들러는 자체 파일로 분리 될 수 있으며,이 파일은 GOF 책의 콘크리트 상태 처리기와 동일합니다. 몇 개의 상태만으로 디자인이 간단한 경우 STATECTXT.C와 StateHandlers.c를 모두 단순성을 위해 단일 파일로 결합 할 수 있습니다.
'스위치'진술을 사용한 경험에 따르면 여러 상태를 처리하는 표준 방법입니다. 비록 당신이 주당 처리에 전환 값을 전달하고 있다는 사실에 대해서는 언급되어 있습니다. 상태 기계의 요점은 각 주가 단일 행동을 수행했다는 것입니다. 그런 다음 다음 조치/입력은 전환 할 새로운 상태를 결정합니다. 따라서 각 상태 처리 기능이 상태로 들어가는 데 고정 된 모든 것을 즉시 수행 할 것으로 예상 한 다음 나중에 다른 상태로의 전환이 필요한지 결정했습니다.
제목의 책이 있습니다 C/C ++의 실용적인 statecharts. 그러나 그것은입니다 방법 우리가 필요로하는 것에 너무 헤비급.
지원하는 컴파일러 용 __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에서 볼 수 있습니다. Janusz Dobrowolski
C에서는 간단한 기계의 경우 이와 같은 것이 일반적으로 사용하게됩니다.
이벤트 중심의 FSM은 동작 (FSMACTION) 및 현재 상태 및 이벤트로 정의 된 전환 (FSMEDGE)과 관련된 상태 객체 (FSMSTATE)에 의해 설명됩니다.
또한 FSM 및 사용자 데이터를 모두 저장 및 전달하여 FSM 중심 및 사용자가 결합한 정보를 분리하고 동일한 FSM의 여러 인스턴스를 허용합니다 (즉, 동일한 설명을 사용하지만 다른 사용자 데이터를 전달합니다).
이벤트는 정수 유형 (fsmevent)으로 표시됩니다. 음수 값은 구현에 의해 예약되어 특별 공통 이벤트 (재설정, 없음, 공급, 끝). 음이 아닌 이벤트는 사용자 정의입니다.
단순화를 위해, 전환은 배열에 나열되며 일치하는 것은 배열 순서에 시도되며 본질적으로 전환 우선 순위를 제공합니다. 그들은 선택적인 가드 기능을 가지고 있습니다. 다음 상태는 전환 목록에 직접 또는 점프 함수로 직접 표시 될 수 있으며, 이러한 방식으로 동적 FSM 동작을 가능하게하는 유연성을 제공합니다.
전환 설명에서, null 전류 상태는 모든 상태와 일치하며 와일드 카드 이벤트 (모든)는 모든 이벤트와 일치합니다. 어쨌든, 전환을 유발 한 이벤트의 실제 값은 점프 및 가드 기능으로 전달됩니다.
복잡한 FSM의 경우 간단한 에지 어레이 솔루션이 너무 비효율적 일 수 있습니다. 이 경우 에지 어레이 및 전환 행렬 또는 상태 인접력 목록으로 변환 된 이벤트 항목을 사용하여 올바른 점프 함수를 구현할 수 있습니다.
상태 조치는 상태 입력 (ENTER), 상태 출구 (LEFFE) 및 주 내 (주) 운영을 구별하는 재진입 기능으로 구현되어야합니다. 이러한 방식으로 국소 상태 정보는 정적 함수 변수로 캡슐화되고 보존 될 수 있습니다.
일반적으로 상태 입력 및 종료 조치는 눈에 띄게 실행되며 새로운 이벤트 (없음)를 반환하지 않습니다. 그렇지 않은 경우 새 이벤트가 갇히고 즉시 반환됩니다. 이것은 현재 상태를 종료 할 때 발생하는 경우를 대비하여 효과적으로 전환을 방지합니다.
FSMSTEP (FSM STEP 함수)는 새로운 이벤트를 사용하여 전환을 트리거하거나 현재 상태의 상태 내 동작을 실행하기위한 이벤트 (없음)를 사용하여 FSM의 단일 단계를 수행합니다. 단계 함수는 FSM으로 처리하거나 다시 공급할 수있는 새로운 방출 된 이벤트를 반환합니다. 또는 이벤트가없는 경우, 비어 있고 끝이없고, 전환이 발견되지 않거나 종료 상태에 각각 도달하지 못합니다.
#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에는 STATECHART 라이브러리가 있습니다. http://www.boost.org/doc/libs/1_36_0/libs/statechart/doc/index.html
그래도 나는 그것의 사용에 대해 말할 수 없습니다. 직접 사용하지 않음 (아직)
