ceph/src/boost/libs/msm/doc/PDF/examples/ParsingDigits.cpp

   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
  31 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>
 208             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>
 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
 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 {
 270     Parser():p(){p.start();}
 271     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     }
 276     void finish_string(){p.process_event(eos());}
 277     void reinit(){p.process_event(eos());}
 278     test_fsm::parsing p;
 279 };
 280
 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
 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 }
 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