September 28, 2024

C言語でのState Machine実装

Table of Contents

C言語でステートマシンを実装する場合、どのような実装が考えられるだろうか。文法a(bc|d)を受理するステートマシンについて switch case文と構造体を使う実装を比較してみよう。

switch case文を使う実装

最も原始的な実装としてswitch caseとenumを組み合わせた方法が挙げられる。

typedef enum state{STATE_INIT,STATE_A,STATE_B,STATE_COMPLETE,STATE_ERROR}state_t;

state_t state_next(state_t s, char c){
  switch (c){
    case STATE_INIT:
      return c=='a'?STATE_A:STATE_ERROR;
    case STATE_A:
      return c=='b'?STATE_B:
             c=='d'?STATE_COMPLETE:STATE_ERROR;
    case STATE_B:
      return c=='c'?STATE_COMPLETE:STATE_ERROR;
    default:
      return STATE_ERROR:
  }
}

これの呼び出し例は次のようになる。

void demo(){
  const char *str="abc";
  state_t s=STATE_INIT;
  for (;*str;str++){
    s=state_next(*str);
    if (s==STATE_ERROR)break;
    if (s==STATE_COMPLETE){
      puts("complete!!");
      break;
    }
  }
}

この方法では、状態が少ないうちは容易な記述で比較的わかりやすいが状態が増えてくるとswitch case文が肥大化してしまう。更によくステートマシンの実装で使われるaction,enter,exitも実装すると肥大化したswitch case文が散逸してしまう。

そして、状態遷移を示す関数を実装するときに状態が既知でないと実装できない。

構造体を使った実装

構造体を用いた実装を考えてみよう。まず、状態を保存する構造体は次のように書ける。

struct state{
  const char *name;//デバック用に名前をつけておくことをおすすめする。
  void (*action)(void*context);//今回は使わない
  state_t* (*next)(void*context,char);//次のstateを返す(nullable)
  // NOTE: 今回は文字を受理するステートマシンとして書いているため
  // 第二引数をcharにしているがより汎用的に書くならばvoid*にするとよい。
  void (*enter)(void*context);//stateが開始するときに呼び出される(nullable)
  void (*exit)(void*context);//stateが終了するときに呼び出される(nullable)
  void *context;//これをいれることでstate machineの入れ子を実現できる(nullable)
}state_t;

次に、文法a(bc|d)を受理するステートマシンの状態遷移を示す。

#include <stdio.h>

// 構造体を前方宣言しておく
const extern state_t state_init, state_a, state_b, state_c, state_complete;

// 構造体とそこで使う関数を定義する
static state_t *state_init_next(void*,char c){
  return c=='a'?&state_a:NULL;
}
const state_t state_init={.name="init",.next=state_init_next};

static state_t *state_a_next(void*,char c){
  return c=='b'?&state_a:
         c=='d'?&state_complete:NULL;
}
const state_t state_a={.name="a",.next=state_a_next};

static state_t *state_b_next(void*,char c){
  return c=='c'?&state_complete:NULL;
}
const state_t state_b={.name="b",.next=state_b_next};

#define CAST_CALLBACK(x) (((void)(*)(const char*))(x))
const state_t state_complete={
  .name="complete",.enter=CAST_CALLBACK(puts),.context="complete!!"
  // enterがただのコールバック関数なので標準出力へ出力するputsを使ってしまう
};

Note

前方宣言をすることでnextと構造体の循環参照を解消しています。

そして状態を変化させる関数を示します。

state_t *state_next(state_t* now, char c){
  if (!now)return NULL;

  state_t *const next= now->next?now->next(now->context):NULL;
  if (now!=next){
    if (now->exit){now->exit(now->context);}
    if (next->enter){next->emter(next->context);}
  }
  
  return next;
}

void state_action(state_t*s){
  if (!s){return;}
  s->action(s->context);
}

最後に呼び出し例を示す。

void demo(){
  const char *str="abc";
  state_t* s=&state_init;
  for (;*str;str++){
    s=state_next(s,*str);
    if (!s||s==&state_complete)break;
    state_action(s);
  }
}

この方法では、構造体を使うことで状態が増えても状態を変化させる関数state_nextを変化させることなく実装させることができる。ただし流れを追うときに、一つずつコールバックされる関数を読む必要があり可読性になんがある点に注意したい。