480 lines
18 KiB
C++
480 lines
18 KiB
C++
// Copyright 2010 Christophe Henry
|
|
// henry UNDERSCORE christophe AT hotmail DOT com
|
|
// This is an extended version of the state machine available in the boost::mpl library
|
|
// Distributed under the same license as the original.
|
|
// Copyright for the original version:
|
|
// Copyright 2005 David Abrahams and Aleksey Gurtovoy. Distributed
|
|
// under the Boost Software License, Version 1.0. (See accompanying
|
|
// file LICENSE_1_0.txt or copy at
|
|
// http://www.boost.org/LICENSE_1_0.txt)
|
|
|
|
#define FUSION_MAX_VECTOR_SIZE 20
|
|
|
|
#include <boost/msm/back/state_machine.hpp>
|
|
#include "char_event_dispatcher.hpp"
|
|
#include <boost/msm/front/state_machine_def.hpp>
|
|
#include <boost/msm/front/functor_row.hpp>
|
|
#include <boost/timer.hpp>
|
|
|
|
namespace msm = boost::msm;
|
|
namespace mpl = boost::mpl;
|
|
using namespace msm::front;
|
|
|
|
#include <iostream>
|
|
#ifdef WIN32
|
|
#include "windows.h"
|
|
#else
|
|
#include <sys/time.h>
|
|
#endif
|
|
|
|
// events
|
|
struct end_sub {template <class Event> end_sub(Event const&){}};
|
|
struct other_char {};
|
|
struct default_char {};
|
|
struct eos {};
|
|
|
|
|
|
namespace test_fsm // Concrete FSM implementation
|
|
{
|
|
// Concrete FSM implementation
|
|
struct parsing_ : public msm::front::state_machine_def<parsing_>
|
|
{
|
|
// no need for exception handling or message queue
|
|
typedef int no_exception_thrown;
|
|
typedef int no_message_queue;
|
|
|
|
struct Waiting : public msm::front::state<>
|
|
{
|
|
// optional entry/exit methods
|
|
//template <class Event,class FSM>
|
|
//void on_entry(Event const&,FSM& ) {std::cout << "entering: Waiting" << std::endl;}
|
|
//template <class Event,class FSM>
|
|
//void on_exit(Event const&,FSM& ) {std::cout << "leaving: Waiting" << std::endl;}
|
|
};
|
|
struct Digit1 : public msm::front::state<>
|
|
{
|
|
// optional entry/exit methods
|
|
//template <class Event,class FSM>
|
|
//void on_entry(Event const&,FSM& ) {std::cout << "entering: Digit1" << std::endl;}
|
|
//template <class Event,class FSM>
|
|
//void on_exit(Event const&,FSM& ) {std::cout << "leaving: Digit1" << std::endl;}
|
|
};
|
|
struct Digit2 : public msm::front::state<>
|
|
{
|
|
// optional entry/exit methods
|
|
//template <class Event,class FSM>
|
|
//void on_entry(Event const&,FSM& ) {std::cout << "entering: Digit2" << std::endl;}
|
|
//template <class Event,class FSM>
|
|
//void on_exit(Event const&,FSM& ) {std::cout << "leaving: Digit2" << std::endl;}
|
|
};
|
|
struct Digit3 : public msm::front::state<>
|
|
{
|
|
// optional entry/exit methods
|
|
//template <class Event,class FSM>
|
|
//void on_entry(Event const&,FSM& ) {std::cout << "entering: Digit3" << std::endl;}
|
|
//template <class Event,class FSM>
|
|
//void on_exit(Event const&,FSM& ) {std::cout << "leaving: Digit3" << std::endl;}
|
|
};
|
|
struct Digit4 : public msm::front::state<>
|
|
{
|
|
// optional entry/exit methods
|
|
//template <class Event,class FSM>
|
|
//void on_entry(Event const&,FSM& ) {std::cout << "entering: Digit4" << std::endl;}
|
|
//template <class Event,class FSM>
|
|
//void on_exit(Event const&,FSM& ) {std::cout << "leaving: Digit4" << std::endl;}
|
|
};
|
|
struct MinusChar1 : public msm::front::state<>
|
|
{
|
|
// optional entry/exit methods
|
|
//template <class Event,class FSM>
|
|
//void on_entry(Event const&,FSM& ) {std::cout << "entering: MinusChar1" << std::endl;}
|
|
//template <class Event,class FSM>
|
|
//void on_exit(Event const&,FSM& ) {std::cout << "leaving: MinusChar1" << std::endl;}
|
|
};
|
|
struct Digit5 : public msm::front::state<>
|
|
{
|
|
// optional entry/exit methods
|
|
//template <class Event,class FSM>
|
|
//void on_entry(Event const&,FSM& ) {std::cout << "entering: Digit5" << std::endl;}
|
|
//template <class Event,class FSM>
|
|
//void on_exit(Event const&,FSM& ) {std::cout << "leaving: Digit5" << std::endl;}
|
|
};
|
|
struct Digit6 : public msm::front::state<>
|
|
{
|
|
// optional entry/exit methods
|
|
//template <class Event,class FSM>
|
|
//void on_entry(Event const&,FSM& ) {std::cout << "entering: Digit6" << std::endl;}
|
|
//template <class Event,class FSM>
|
|
//void on_exit(Event const&,FSM& ) {std::cout << "leaving: Digit6" << std::endl;}
|
|
};
|
|
struct Digit7 : public msm::front::state<>
|
|
{
|
|
// optional entry/exit methods
|
|
//template <class Event,class FSM>
|
|
//void on_entry(Event const&,FSM& ) {std::cout << "entering: Digit7" << std::endl;}
|
|
//template <class Event,class FSM>
|
|
//void on_exit(Event const&,FSM& ) {std::cout << "leaving: Digit7" << std::endl;}
|
|
};
|
|
struct Digit8 : public msm::front::state<>
|
|
{
|
|
// optional entry/exit methods
|
|
//template <class Event,class FSM>
|
|
//void on_entry(Event const&,FSM& ) {std::cout << "entering: Digit8" << std::endl;}
|
|
//template <class Event,class FSM>
|
|
//void on_exit(Event const&,FSM& ) {std::cout << "leaving: Digit8" << std::endl;}
|
|
};
|
|
struct MinusChar2 : public msm::front::state<>
|
|
{
|
|
// optional entry/exit methods
|
|
//template <class Event,class FSM>
|
|
//void on_entry(Event const&,FSM& ) {std::cout << "entering: MinusChar2" << std::endl;}
|
|
//template <class Event,class FSM>
|
|
//void on_exit(Event const&,FSM& ) {std::cout << "leaving: MinusChar2" << std::endl;}
|
|
};
|
|
struct Digit9 : public msm::front::state<>
|
|
{
|
|
// optional entry/exit methods
|
|
//template <class Event,class FSM>
|
|
//void on_entry(Event const&,FSM& ) {std::cout << "entering: Digit9" << std::endl;}
|
|
//template <class Event,class FSM>
|
|
//void on_exit(Event const&,FSM& ) {std::cout << "leaving: Digit9" << std::endl;}
|
|
};
|
|
struct Digit10 : public msm::front::state<>
|
|
{
|
|
// optional entry/exit methods
|
|
//template <class Event,class FSM>
|
|
//void on_entry(Event const&,FSM& ) {std::cout << "entering: Digit10" << std::endl;}
|
|
//template <class Event,class FSM>
|
|
//void on_exit(Event const&,FSM& ) {std::cout << "leaving: Digit10" << std::endl;}
|
|
};
|
|
struct Digit11 : public msm::front::state<>
|
|
{
|
|
// optional entry/exit methods
|
|
//template <class Event,class FSM>
|
|
//void on_entry(Event const&,FSM& ) {std::cout << "entering: Digit11" << std::endl;}
|
|
//template <class Event,class FSM>
|
|
//void on_exit(Event const&,FSM& ) {std::cout << "leaving: Digit11" << std::endl;}
|
|
};
|
|
struct Digit12 : public msm::front::state<>
|
|
{
|
|
// optional entry/exit methods
|
|
//template <class Event,class FSM>
|
|
//void on_entry(Event const&,FSM& ) {std::cout << "entering: Digit12" << std::endl;}
|
|
//template <class Event,class FSM>
|
|
//void on_exit(Event const&,FSM& ) {std::cout << "leaving: Digit12" << std::endl;}
|
|
};
|
|
struct MinusChar3 : public msm::front::state<>
|
|
{
|
|
// optional entry/exit methods
|
|
//template <class Event,class FSM>
|
|
//void on_entry(Event const&,FSM& ) {std::cout << "entering: MinusChar3" << std::endl;}
|
|
//template <class Event,class FSM>
|
|
//void on_exit(Event const&,FSM& ) {std::cout << "leaving: MinusChar3" << std::endl;}
|
|
};
|
|
struct Digit13 : public msm::front::state<>
|
|
{
|
|
// optional entry/exit methods
|
|
//template <class Event,class FSM>
|
|
//void on_entry(Event const&,FSM& ) {std::cout << "entering: Digit13" << std::endl;}
|
|
//template <class Event,class FSM>
|
|
//void on_exit(Event const&,FSM& ) {std::cout << "leaving: Digit13" << std::endl;}
|
|
};
|
|
struct Digit14 : public msm::front::state<>
|
|
{
|
|
// optional entry/exit methods
|
|
//template <class Event,class FSM>
|
|
//void on_entry(Event const&,FSM& ) {std::cout << "entering: Digit14" << std::endl;}
|
|
//template <class Event,class FSM>
|
|
//void on_exit(Event const&,FSM& ) {std::cout << "leaving: Digit14" << std::endl;}
|
|
};
|
|
struct Digit15 : public msm::front::state<>
|
|
{
|
|
// optional entry/exit methods
|
|
//template <class Event,class FSM>
|
|
//void on_entry(Event const&,FSM& ) {std::cout << "entering: Digit15" << std::endl;}
|
|
//template <class Event,class FSM>
|
|
//void on_exit(Event const&,FSM& ) {std::cout << "leaving: Digit15" << std::endl;}
|
|
};
|
|
//struct Start : public msm::front::state<> {};
|
|
struct Parsed : public msm::front::state<> {};
|
|
//struct Failed : public msm::front::state<> {};
|
|
|
|
// the initial state of the player SM. Must be defined
|
|
typedef Waiting initial_state;
|
|
// transition actions
|
|
struct test_fct
|
|
{
|
|
template <class FSM,class EVT,class SourceState,class TargetState>
|
|
void operator()(EVT const& ,FSM&,SourceState& ,TargetState& )
|
|
{
|
|
std::cout << "Parsed!" << std::endl;
|
|
}
|
|
};
|
|
|
|
// guard conditions
|
|
|
|
|
|
// Transition table for parsing_
|
|
struct transition_table : mpl::vector<
|
|
// Start Event Next Action Guard
|
|
// +-------------+-------------------+---------+---------------------+----------------------+
|
|
Row < Waiting , digit , Digit1 >,
|
|
Row < Digit1 , digit , Digit2 >,
|
|
Row < Digit2 , digit , Digit3 >,
|
|
Row < Digit3 , digit , Digit4 >,
|
|
Row < Digit4 , event_char<'-'> , MinusChar1 >,
|
|
Row < MinusChar1 , digit , Digit5 >,
|
|
Row < Digit5 , digit , Digit6 >,
|
|
Row < Digit6 , digit , Digit7 >,
|
|
Row < Digit7 , digit , Digit8 >,
|
|
Row < Digit8 , event_char<'-'> , MinusChar2 >,
|
|
Row < MinusChar2 , digit , Digit9 >,
|
|
Row < Digit9 , digit , Digit10 >,
|
|
Row < Digit10 , digit , Digit11 >,
|
|
Row < Digit11 , digit , Digit12 >,
|
|
Row < Digit12 , event_char<'-'> , MinusChar3 >,
|
|
Row < MinusChar3 , digit , Digit13 >,
|
|
Row < Digit13 , digit , Digit14 >,
|
|
Row < Digit14 , digit , Digit15 >,
|
|
Row < Digit15 , eos , Parsed >,
|
|
Row < Parsed , eos , Waiting >
|
|
// +---------+-------------+---------+---------------------+----------------------+
|
|
> {};
|
|
|
|
|
|
// Replaces the default no-transition response.
|
|
template <class FSM,class Event>
|
|
void no_transition(Event const& e, FSM&,int state)
|
|
{
|
|
std::cout << "no transition from state " << state
|
|
<< " on event " << typeid(e).name() << std::endl;
|
|
}
|
|
};
|
|
typedef msm::back::state_machine<parsing_> parsing;
|
|
}
|
|
|
|
#ifndef WIN32
|
|
long mtime(struct timeval& tv1,struct timeval& tv2)
|
|
{
|
|
return (tv2.tv_sec-tv1.tv_sec) *1000000 + ((tv2.tv_usec-tv1.tv_usec));
|
|
}
|
|
#endif
|
|
|
|
// This declares the statically-initialized char_event_dispatcher instance.
|
|
template <class Fsm>
|
|
const msm::back::char_event_dispatcher<Fsm>
|
|
msm::back::char_event_dispatcher<Fsm>::instance;
|
|
|
|
struct Parser
|
|
{
|
|
Parser():p(){p.start();}
|
|
void new_char(char c)
|
|
{
|
|
typedef msm::back::char_event_dispatcher<test_fsm::parsing> table;
|
|
table::instance.process_event(p,c);
|
|
}
|
|
void finish_string(){p.process_event(eos());}
|
|
void reinit(){p.process_event(eos());}
|
|
test_fsm::parsing p;
|
|
};
|
|
|
|
void msm_match(const char* input)
|
|
{
|
|
test_fsm::parsing p;
|
|
p.start();
|
|
|
|
int j=0;
|
|
while(input[j])
|
|
//for (size_t j=0;j<len;++j)
|
|
{
|
|
switch (input[j])
|
|
{
|
|
case '0':
|
|
p.process_event(char_0());
|
|
break;
|
|
case '1':
|
|
p.process_event(char_1());
|
|
break;
|
|
case '2':
|
|
p.process_event(char_2());
|
|
break;
|
|
case '3':
|
|
p.process_event(char_3());
|
|
break;
|
|
case '4':
|
|
p.process_event(char_4());
|
|
break;
|
|
case '5':
|
|
p.process_event(char_5());
|
|
break;
|
|
case '6':
|
|
p.process_event(char_6());
|
|
break;
|
|
case '7':
|
|
p.process_event(char_7());
|
|
break;
|
|
case '8':
|
|
p.process_event(char_8());
|
|
break;
|
|
case '9':
|
|
p.process_event(char_9());
|
|
break;
|
|
case '-':
|
|
p.process_event(event_char<'-'>());
|
|
break;
|
|
default:
|
|
p.process_event(default_char());
|
|
break;
|
|
}
|
|
++j;
|
|
}
|
|
p.process_event(eos());
|
|
p.process_event(eos());
|
|
}
|
|
|
|
double time_match(const char* text)
|
|
{
|
|
boost::timer tim;
|
|
int iter = 1;
|
|
int counter, repeats;
|
|
double result = 0;
|
|
double run;
|
|
do
|
|
{
|
|
tim.restart();
|
|
for(counter = 0; counter < iter; ++counter)
|
|
{
|
|
msm_match( text);
|
|
}
|
|
result = tim.elapsed();
|
|
iter *= 2;
|
|
} while(result < 0.5);
|
|
iter /= 2;
|
|
|
|
// repeat test and report least value for consistency:
|
|
for(repeats = 0; repeats < 10; ++repeats)
|
|
{
|
|
tim.restart();
|
|
for(counter = 0; counter < iter; ++counter)
|
|
{
|
|
msm_match( text);
|
|
}
|
|
run = tim.elapsed();
|
|
result = (std::min)(run, result);
|
|
}
|
|
return result / iter;
|
|
}
|
|
int main()
|
|
{
|
|
// for timing
|
|
#ifdef WIN32
|
|
LARGE_INTEGER res;
|
|
::QueryPerformanceFrequency(&res);
|
|
LARGE_INTEGER li,li2;
|
|
#else
|
|
struct timeval tv1,tv2;
|
|
gettimeofday(&tv1,NULL);
|
|
#endif
|
|
|
|
test_fsm::parsing p;
|
|
p.start();
|
|
const char* input = "1234-5678-1234-456";
|
|
size_t len = strlen(input);
|
|
// for timing
|
|
#ifdef WIN32
|
|
::QueryPerformanceCounter(&li);
|
|
#else
|
|
gettimeofday(&tv1,NULL);
|
|
#endif
|
|
for (int i=0;i<1000;++i)
|
|
{
|
|
int j=0;
|
|
while(input[j])
|
|
//for (size_t j=0;j<len;++j)
|
|
{
|
|
switch (input[j])
|
|
{
|
|
case '0':
|
|
p.process_event(char_0());
|
|
break;
|
|
case '1':
|
|
p.process_event(char_1());
|
|
break;
|
|
case '2':
|
|
p.process_event(char_2());
|
|
break;
|
|
case '3':
|
|
p.process_event(char_3());
|
|
break;
|
|
case '4':
|
|
p.process_event(char_4());
|
|
break;
|
|
case '5':
|
|
p.process_event(char_5());
|
|
break;
|
|
case '6':
|
|
p.process_event(char_6());
|
|
break;
|
|
case '7':
|
|
p.process_event(char_7());
|
|
break;
|
|
case '8':
|
|
p.process_event(char_8());
|
|
break;
|
|
case '9':
|
|
p.process_event(char_9());
|
|
break;
|
|
case '-':
|
|
p.process_event(event_char<'-'>());
|
|
break;
|
|
default:
|
|
p.process_event(default_char());
|
|
break;
|
|
}
|
|
++j;
|
|
}
|
|
p.process_event(eos());
|
|
p.process_event(eos());
|
|
}
|
|
#ifdef WIN32
|
|
::QueryPerformanceCounter(&li2);
|
|
#else
|
|
gettimeofday(&tv2,NULL);
|
|
#endif
|
|
#ifdef WIN32
|
|
std::cout << "msm(1) took in s:" << (double)(li2.QuadPart-li.QuadPart)/res.QuadPart <<"\n" <<std::endl;
|
|
#else
|
|
std::cout << "msm(1) took in us:" << mtime(tv1,tv2) <<"\n" <<std::endl;
|
|
#endif
|
|
|
|
Parser parse;
|
|
// for timing
|
|
#ifdef WIN32
|
|
::QueryPerformanceCounter(&li);
|
|
#else
|
|
gettimeofday(&tv1,NULL);
|
|
#endif
|
|
for (int i=0;i<1000;++i)
|
|
{
|
|
for (size_t j=0;j<len;++j)
|
|
{
|
|
parse.new_char(input[j]);
|
|
}
|
|
parse.finish_string();
|
|
parse.reinit();
|
|
}
|
|
#ifdef WIN32
|
|
::QueryPerformanceCounter(&li2);
|
|
#else
|
|
gettimeofday(&tv2,NULL);
|
|
#endif
|
|
#ifdef WIN32
|
|
std::cout << "msm(2) took in s:" << (double)(li2.QuadPart-li.QuadPart)/res.QuadPart <<"\n" <<std::endl;
|
|
#else
|
|
std::cout << "msm(2) took in us:" << mtime(tv1,tv2) <<"\n" <<std::endl;
|
|
#endif
|
|
std::cout << "msm(3) took in s:" << time_match(input) <<"\n" <<std::endl;
|
|
return 0;
|
|
}
|
|
|