1 // Copyright 2010 Christophe Henry
2 // henry UNDERSCORE christophe AT hotmail DOT com
3 // This is an extended version of the state machine available in the boost::mpl library
4 // Distributed under the same license as the original.
5 // Copyright for the original version:
6 // Copyright 2005 David Abrahams and Aleksey Gurtovoy. Distributed
7 // under the Boost Software License, Version 1.0. (See accompanying
8 // file LICENSE_1_0.txt or copy at
9 // http://www.boost.org/LICENSE_1_0.txt)
10
11 #define FUSION_MAX_VECTOR_SIZE 20
12
13 #include <boost/msm/back/state_machine.hpp>
14 #include "char_event_dispatcher.hpp"
15 #include <boost/msm/front/state_machine_def.hpp>
16 #include <boost/msm/front/functor_row.hpp>
17 #include <boost/timer.hpp>
18
19 namespace msm = boost::msm;
20 namespace mpl = boost::mpl;
21 using namespace msm::front;
22
23 #include <iostream>
24 #ifdef WIN32
25 #include "windows.h"
26 #else
27 #include <sys/time.h>
28 #endif
29
30 // events
end_subend_sub31 struct end_sub {template <class Event> end_sub(Event const&){}};
32 struct other_char {};
33 struct default_char {};
34 struct eos {};
35
36
37 namespace test_fsm // Concrete FSM implementation
38 {
39 // Concrete FSM implementation
40 struct parsing_ : public msm::front::state_machine_def<parsing_>
41 {
42 // no need for exception handling or message queue
43 typedef int no_exception_thrown;
44 typedef int no_message_queue;
45
46 struct Waiting : public msm::front::state<>
47 {
48 // optional entry/exit methods
49 //template <class Event,class FSM>
50 //void on_entry(Event const&,FSM& ) {std::cout << "entering: Waiting" << std::endl;}
51 //template <class Event,class FSM>
52 //void on_exit(Event const&,FSM& ) {std::cout << "leaving: Waiting" << std::endl;}
53 };
54 struct Digit1 : public msm::front::state<>
55 {
56 // optional entry/exit methods
57 //template <class Event,class FSM>
58 //void on_entry(Event const&,FSM& ) {std::cout << "entering: Digit1" << std::endl;}
59 //template <class Event,class FSM>
60 //void on_exit(Event const&,FSM& ) {std::cout << "leaving: Digit1" << std::endl;}
61 };
62 struct Digit2 : public msm::front::state<>
63 {
64 // optional entry/exit methods
65 //template <class Event,class FSM>
66 //void on_entry(Event const&,FSM& ) {std::cout << "entering: Digit2" << std::endl;}
67 //template <class Event,class FSM>
68 //void on_exit(Event const&,FSM& ) {std::cout << "leaving: Digit2" << std::endl;}
69 };
70 struct Digit3 : public msm::front::state<>
71 {
72 // optional entry/exit methods
73 //template <class Event,class FSM>
74 //void on_entry(Event const&,FSM& ) {std::cout << "entering: Digit3" << std::endl;}
75 //template <class Event,class FSM>
76 //void on_exit(Event const&,FSM& ) {std::cout << "leaving: Digit3" << std::endl;}
77 };
78 struct Digit4 : public msm::front::state<>
79 {
80 // optional entry/exit methods
81 //template <class Event,class FSM>
82 //void on_entry(Event const&,FSM& ) {std::cout << "entering: Digit4" << std::endl;}
83 //template <class Event,class FSM>
84 //void on_exit(Event const&,FSM& ) {std::cout << "leaving: Digit4" << std::endl;}
85 };
86 struct MinusChar1 : public msm::front::state<>
87 {
88 // optional entry/exit methods
89 //template <class Event,class FSM>
90 //void on_entry(Event const&,FSM& ) {std::cout << "entering: MinusChar1" << std::endl;}
91 //template <class Event,class FSM>
92 //void on_exit(Event const&,FSM& ) {std::cout << "leaving: MinusChar1" << std::endl;}
93 };
94 struct Digit5 : public msm::front::state<>
95 {
96 // optional entry/exit methods
97 //template <class Event,class FSM>
98 //void on_entry(Event const&,FSM& ) {std::cout << "entering: Digit5" << std::endl;}
99 //template <class Event,class FSM>
100 //void on_exit(Event const&,FSM& ) {std::cout << "leaving: Digit5" << std::endl;}
101 };
102 struct Digit6 : public msm::front::state<>
103 {
104 // optional entry/exit methods
105 //template <class Event,class FSM>
106 //void on_entry(Event const&,FSM& ) {std::cout << "entering: Digit6" << std::endl;}
107 //template <class Event,class FSM>
108 //void on_exit(Event const&,FSM& ) {std::cout << "leaving: Digit6" << std::endl;}
109 };
110 struct Digit7 : public msm::front::state<>
111 {
112 // optional entry/exit methods
113 //template <class Event,class FSM>
114 //void on_entry(Event const&,FSM& ) {std::cout << "entering: Digit7" << std::endl;}
115 //template <class Event,class FSM>
116 //void on_exit(Event const&,FSM& ) {std::cout << "leaving: Digit7" << std::endl;}
117 };
118 struct Digit8 : public msm::front::state<>
119 {
120 // optional entry/exit methods
121 //template <class Event,class FSM>
122 //void on_entry(Event const&,FSM& ) {std::cout << "entering: Digit8" << std::endl;}
123 //template <class Event,class FSM>
124 //void on_exit(Event const&,FSM& ) {std::cout << "leaving: Digit8" << std::endl;}
125 };
126 struct MinusChar2 : public msm::front::state<>
127 {
128 // optional entry/exit methods
129 //template <class Event,class FSM>
130 //void on_entry(Event const&,FSM& ) {std::cout << "entering: MinusChar2" << std::endl;}
131 //template <class Event,class FSM>
132 //void on_exit(Event const&,FSM& ) {std::cout << "leaving: MinusChar2" << std::endl;}
133 };
134 struct Digit9 : public msm::front::state<>
135 {
136 // optional entry/exit methods
137 //template <class Event,class FSM>
138 //void on_entry(Event const&,FSM& ) {std::cout << "entering: Digit9" << std::endl;}
139 //template <class Event,class FSM>
140 //void on_exit(Event const&,FSM& ) {std::cout << "leaving: Digit9" << std::endl;}
141 };
142 struct Digit10 : public msm::front::state<>
143 {
144 // optional entry/exit methods
145 //template <class Event,class FSM>
146 //void on_entry(Event const&,FSM& ) {std::cout << "entering: Digit10" << std::endl;}
147 //template <class Event,class FSM>
148 //void on_exit(Event const&,FSM& ) {std::cout << "leaving: Digit10" << std::endl;}
149 };
150 struct Digit11 : public msm::front::state<>
151 {
152 // optional entry/exit methods
153 //template <class Event,class FSM>
154 //void on_entry(Event const&,FSM& ) {std::cout << "entering: Digit11" << std::endl;}
155 //template <class Event,class FSM>
156 //void on_exit(Event const&,FSM& ) {std::cout << "leaving: Digit11" << std::endl;}
157 };
158 struct Digit12 : public msm::front::state<>
159 {
160 // optional entry/exit methods
161 //template <class Event,class FSM>
162 //void on_entry(Event const&,FSM& ) {std::cout << "entering: Digit12" << std::endl;}
163 //template <class Event,class FSM>
164 //void on_exit(Event const&,FSM& ) {std::cout << "leaving: Digit12" << std::endl;}
165 };
166 struct MinusChar3 : public msm::front::state<>
167 {
168 // optional entry/exit methods
169 //template <class Event,class FSM>
170 //void on_entry(Event const&,FSM& ) {std::cout << "entering: MinusChar3" << std::endl;}
171 //template <class Event,class FSM>
172 //void on_exit(Event const&,FSM& ) {std::cout << "leaving: MinusChar3" << std::endl;}
173 };
174 struct Digit13 : public msm::front::state<>
175 {
176 // optional entry/exit methods
177 //template <class Event,class FSM>
178 //void on_entry(Event const&,FSM& ) {std::cout << "entering: Digit13" << std::endl;}
179 //template <class Event,class FSM>
180 //void on_exit(Event const&,FSM& ) {std::cout << "leaving: Digit13" << std::endl;}
181 };
182 struct Digit14 : public msm::front::state<>
183 {
184 // optional entry/exit methods
185 //template <class Event,class FSM>
186 //void on_entry(Event const&,FSM& ) {std::cout << "entering: Digit14" << std::endl;}
187 //template <class Event,class FSM>
188 //void on_exit(Event const&,FSM& ) {std::cout << "leaving: Digit14" << std::endl;}
189 };
190 struct Digit15 : public msm::front::state<>
191 {
192 // optional entry/exit methods
193 //template <class Event,class FSM>
194 //void on_entry(Event const&,FSM& ) {std::cout << "entering: Digit15" << std::endl;}
195 //template <class Event,class FSM>
196 //void on_exit(Event const&,FSM& ) {std::cout << "leaving: Digit15" << std::endl;}
197 };
198 //struct Start : public msm::front::state<> {};
199 struct Parsed : public msm::front::state<> {};
200 //struct Failed : public msm::front::state<> {};
201
202 // the initial state of the player SM. Must be defined
203 typedef Waiting initial_state;
204 // transition actions
205 struct test_fct
206 {
207 template <class FSM,class EVT,class SourceState,class TargetState>
operator ()test_fsm::parsing_::test_fct208 void operator()(EVT const& ,FSM&,SourceState& ,TargetState& )
209 {
210 std::cout << "Parsed!" << std::endl;
211 }
212 };
213
214 // guard conditions
215
216
217 // Transition table for parsing_
218 struct transition_table : mpl::vector<
219 // Start Event Next Action Guard
220 // +-------------+-------------------+---------+---------------------+----------------------+
221 Row < Waiting , digit , Digit1 >,
222 Row < Digit1 , digit , Digit2 >,
223 Row < Digit2 , digit , Digit3 >,
224 Row < Digit3 , digit , Digit4 >,
225 Row < Digit4 , event_char<'-'> , MinusChar1 >,
226 Row < MinusChar1 , digit , Digit5 >,
227 Row < Digit5 , digit , Digit6 >,
228 Row < Digit6 , digit , Digit7 >,
229 Row < Digit7 , digit , Digit8 >,
230 Row < Digit8 , event_char<'-'> , MinusChar2 >,
231 Row < MinusChar2 , digit , Digit9 >,
232 Row < Digit9 , digit , Digit10 >,
233 Row < Digit10 , digit , Digit11 >,
234 Row < Digit11 , digit , Digit12 >,
235 Row < Digit12 , event_char<'-'> , MinusChar3 >,
236 Row < MinusChar3 , digit , Digit13 >,
237 Row < Digit13 , digit , Digit14 >,
238 Row < Digit14 , digit , Digit15 >,
239 Row < Digit15 , eos , Parsed >,
240 Row < Parsed , eos , Waiting >
241 // +---------+-------------+---------+---------------------+----------------------+
242 > {};
243
244
245 // Replaces the default no-transition response.
246 template <class FSM,class Event>
no_transitiontest_fsm::parsing_247 void no_transition(Event const& e, FSM&,int state)
248 {
249 std::cout << "no transition from state " << state
250 << " on event " << typeid(e).name() << std::endl;
251 }
252 };
253 typedef msm::back::state_machine<parsing_> parsing;
254 }
255
256 #ifndef WIN32
mtime(struct timeval & tv1,struct timeval & tv2)257 long mtime(struct timeval& tv1,struct timeval& tv2)
258 {
259 return (tv2.tv_sec-tv1.tv_sec) *1000000 + ((tv2.tv_usec-tv1.tv_usec));
260 }
261 #endif
262
263 // This declares the statically-initialized char_event_dispatcher instance.
264 template <class Fsm>
265 const msm::back::char_event_dispatcher<Fsm>
266 msm::back::char_event_dispatcher<Fsm>::instance;
267
268 struct Parser
269 {
ParserParser270 Parser():p(){p.start();}
new_charParser271 void new_char(char c)
272 {
273 typedef msm::back::char_event_dispatcher<test_fsm::parsing> table;
274 table::instance.process_event(p,c);
275 }
finish_stringParser276 void finish_string(){p.process_event(eos());}
reinitParser277 void reinit(){p.process_event(eos());}
278 test_fsm::parsing p;
279 };
280
msm_match(const char * input)281 void msm_match(const char* input)
282 {
283 test_fsm::parsing p;
284 p.start();
285
286 int j=0;
287 while(input[j])
288 //for (size_t j=0;j<len;++j)
289 {
290 switch (input[j])
291 {
292 case '0':
293 p.process_event(char_0());
294 break;
295 case '1':
296 p.process_event(char_1());
297 break;
298 case '2':
299 p.process_event(char_2());
300 break;
301 case '3':
302 p.process_event(char_3());
303 break;
304 case '4':
305 p.process_event(char_4());
306 break;
307 case '5':
308 p.process_event(char_5());
309 break;
310 case '6':
311 p.process_event(char_6());
312 break;
313 case '7':
314 p.process_event(char_7());
315 break;
316 case '8':
317 p.process_event(char_8());
318 break;
319 case '9':
320 p.process_event(char_9());
321 break;
322 case '-':
323 p.process_event(event_char<'-'>());
324 break;
325 default:
326 p.process_event(default_char());
327 break;
328 }
329 ++j;
330 }
331 p.process_event(eos());
332 p.process_event(eos());
333 }
334
time_match(const char * text)335 double time_match(const char* text)
336 {
337 boost::timer tim;
338 int iter = 1;
339 int counter, repeats;
340 double result = 0;
341 double run;
342 do
343 {
344 tim.restart();
345 for(counter = 0; counter < iter; ++counter)
346 {
347 msm_match( text);
348 }
349 result = tim.elapsed();
350 iter *= 2;
351 } while(result < 0.5);
352 iter /= 2;
353
354 // repeat test and report least value for consistency:
355 for(repeats = 0; repeats < 10; ++repeats)
356 {
357 tim.restart();
358 for(counter = 0; counter < iter; ++counter)
359 {
360 msm_match( text);
361 }
362 run = tim.elapsed();
363 result = (std::min)(run, result);
364 }
365 return result / iter;
366 }
main()367 int main()
368 {
369 // for timing
370 #ifdef WIN32
371 LARGE_INTEGER res;
372 ::QueryPerformanceFrequency(&res);
373 LARGE_INTEGER li,li2;
374 #else
375 struct timeval tv1,tv2;
376 gettimeofday(&tv1,NULL);
377 #endif
378
379 test_fsm::parsing p;
380 p.start();
381 const char* input = "1234-5678-1234-456";
382 size_t len = strlen(input);
383 // for timing
384 #ifdef WIN32
385 ::QueryPerformanceCounter(&li);
386 #else
387 gettimeofday(&tv1,NULL);
388 #endif
389 for (int i=0;i<1000;++i)
390 {
391 int j=0;
392 while(input[j])
393 //for (size_t j=0;j<len;++j)
394 {
395 switch (input[j])
396 {
397 case '0':
398 p.process_event(char_0());
399 break;
400 case '1':
401 p.process_event(char_1());
402 break;
403 case '2':
404 p.process_event(char_2());
405 break;
406 case '3':
407 p.process_event(char_3());
408 break;
409 case '4':
410 p.process_event(char_4());
411 break;
412 case '5':
413 p.process_event(char_5());
414 break;
415 case '6':
416 p.process_event(char_6());
417 break;
418 case '7':
419 p.process_event(char_7());
420 break;
421 case '8':
422 p.process_event(char_8());
423 break;
424 case '9':
425 p.process_event(char_9());
426 break;
427 case '-':
428 p.process_event(event_char<'-'>());
429 break;
430 default:
431 p.process_event(default_char());
432 break;
433 }
434 ++j;
435 }
436 p.process_event(eos());
437 p.process_event(eos());
438 }
439 #ifdef WIN32
440 ::QueryPerformanceCounter(&li2);
441 #else
442 gettimeofday(&tv2,NULL);
443 #endif
444 #ifdef WIN32
445 std::cout << "msm(1) took in s:" << (double)(li2.QuadPart-li.QuadPart)/res.QuadPart <<"\n" <<std::endl;
446 #else
447 std::cout << "msm(1) took in us:" << mtime(tv1,tv2) <<"\n" <<std::endl;
448 #endif
449
450 Parser parse;
451 // for timing
452 #ifdef WIN32
453 ::QueryPerformanceCounter(&li);
454 #else
455 gettimeofday(&tv1,NULL);
456 #endif
457 for (int i=0;i<1000;++i)
458 {
459 for (size_t j=0;j<len;++j)
460 {
461 parse.new_char(input[j]);
462 }
463 parse.finish_string();
464 parse.reinit();
465 }
466 #ifdef WIN32
467 ::QueryPerformanceCounter(&li2);
468 #else
469 gettimeofday(&tv2,NULL);
470 #endif
471 #ifdef WIN32
472 std::cout << "msm(2) took in s:" << (double)(li2.QuadPart-li.QuadPart)/res.QuadPart <<"\n" <<std::endl;
473 #else
474 std::cout << "msm(2) took in us:" << mtime(tv1,tv2) <<"\n" <<std::endl;
475 #endif
476 std::cout << "msm(3) took in s:" << time_match(input) <<"\n" <<std::endl;
477 return 0;
478 }
479
480