"Fossies" - the Fresh Open Source Software Archive

Member "ragel-6.10/ragel/cdtable.cpp" (24 Mar 2017, 27630 Bytes) of package /linux/misc/ragel-6.10.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "cdtable.cpp" see the Fossies "Dox" file reference documentation and the latest Fossies "Diffs" side-by-side code changes report: 6.9_vs_6.10.

    1 /*
    2  *  Copyright 2001-2006 Adrian Thurston <thurston@complang.org>
    3  *            2004 Erich Ocean <eric.ocean@ampede.com>
    4  *            2005 Alan West <alan@alanz.com>
    5  */
    6 
    7 /*  This file is part of Ragel.
    8  *
    9  *  Ragel is free software; you can redistribute it and/or modify
   10  *  it under the terms of the GNU General Public License as published by
   11  *  the Free Software Foundation; either version 2 of the License, or
   12  *  (at your option) any later version.
   13  * 
   14  *  Ragel is distributed in the hope that it will be useful,
   15  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
   16  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   17  *  GNU General Public License for more details.
   18  * 
   19  *  You should have received a copy of the GNU General Public License
   20  *  along with Ragel; if not, write to the Free Software
   21  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA 
   22  */
   23 
   24 #include "ragel.h"
   25 #include "cdtable.h"
   26 #include "redfsm.h"
   27 #include "gendata.h"
   28 
   29 /* Determine if we should use indicies or not. */
   30 void TabCodeGen::calcIndexSize()
   31 {
   32     int sizeWithInds = 0, sizeWithoutInds = 0;
   33 
   34     /* Calculate cost of using with indicies. */
   35     for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
   36         int totalIndex = st->outSingle.length() + st->outRange.length() + 
   37                 (st->defTrans == 0 ? 0 : 1);
   38         sizeWithInds += arrayTypeSize(redFsm->maxIndex) * totalIndex;
   39     }
   40     sizeWithInds += arrayTypeSize(redFsm->maxState) * redFsm->transSet.length();
   41     if ( redFsm->anyActions() )
   42         sizeWithInds += arrayTypeSize(redFsm->maxActionLoc) * redFsm->transSet.length();
   43 
   44     /* Calculate the cost of not using indicies. */
   45     for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
   46         int totalIndex = st->outSingle.length() + st->outRange.length() + 
   47                 (st->defTrans == 0 ? 0 : 1);
   48         sizeWithoutInds += arrayTypeSize(redFsm->maxState) * totalIndex;
   49         if ( redFsm->anyActions() )
   50             sizeWithoutInds += arrayTypeSize(redFsm->maxActionLoc) * totalIndex;
   51     }
   52 
   53     /* If using indicies reduces the size, use them. */
   54     useIndicies = sizeWithInds < sizeWithoutInds;
   55 }
   56 
   57 std::ostream &TabCodeGen::TO_STATE_ACTION( RedStateAp *state )
   58 {
   59     int act = 0;
   60     if ( state->toStateAction != 0 )
   61         act = state->toStateAction->location+1;
   62     out << act;
   63     return out;
   64 }
   65 
   66 std::ostream &TabCodeGen::FROM_STATE_ACTION( RedStateAp *state )
   67 {
   68     int act = 0;
   69     if ( state->fromStateAction != 0 )
   70         act = state->fromStateAction->location+1;
   71     out << act;
   72     return out;
   73 }
   74 
   75 std::ostream &TabCodeGen::EOF_ACTION( RedStateAp *state )
   76 {
   77     int act = 0;
   78     if ( state->eofAction != 0 )
   79         act = state->eofAction->location+1;
   80     out << act;
   81     return out;
   82 }
   83 
   84 
   85 std::ostream &TabCodeGen::TRANS_ACTION( RedTransAp *trans )
   86 {
   87     /* If there are actions, emit them. Otherwise emit zero. */
   88     int act = 0;
   89     if ( trans->action != 0 )
   90         act = trans->action->location+1;
   91     out << act;
   92     return out;
   93 }
   94 
   95 std::ostream &TabCodeGen::TO_STATE_ACTION_SWITCH()
   96 {
   97     /* Walk the list of functions, printing the cases. */
   98     for ( GenActionList::Iter act = actionList; act.lte(); act++ ) {
   99         /* Write out referenced actions. */
  100         if ( act->numToStateRefs > 0 ) {
  101             /* Write the case label, the action and the case break. */
  102             out << "\tcase " << act->actionId << ":\n";
  103             ACTION( out, act, 0, false, false );
  104             out << "\tbreak;\n";
  105         }
  106     }
  107 
  108     genLineDirective( out );
  109     return out;
  110 }
  111 
  112 std::ostream &TabCodeGen::FROM_STATE_ACTION_SWITCH()
  113 {
  114     /* Walk the list of functions, printing the cases. */
  115     for ( GenActionList::Iter act = actionList; act.lte(); act++ ) {
  116         /* Write out referenced actions. */
  117         if ( act->numFromStateRefs > 0 ) {
  118             /* Write the case label, the action and the case break. */
  119             out << "\tcase " << act->actionId << ":\n";
  120             ACTION( out, act, 0, false, false );
  121             out << "\tbreak;\n";
  122         }
  123     }
  124 
  125     genLineDirective( out );
  126     return out;
  127 }
  128 
  129 std::ostream &TabCodeGen::EOF_ACTION_SWITCH()
  130 {
  131     /* Walk the list of functions, printing the cases. */
  132     for ( GenActionList::Iter act = actionList; act.lte(); act++ ) {
  133         /* Write out referenced actions. */
  134         if ( act->numEofRefs > 0 ) {
  135             /* Write the case label, the action and the case break. */
  136             out << "\tcase " << act->actionId << ":\n";
  137             ACTION( out, act, 0, true, false );
  138             out << "\tbreak;\n";
  139         }
  140     }
  141 
  142     genLineDirective( out );
  143     return out;
  144 }
  145 
  146 
  147 std::ostream &TabCodeGen::ACTION_SWITCH()
  148 {
  149     /* Walk the list of functions, printing the cases. */
  150     for ( GenActionList::Iter act = actionList; act.lte(); act++ ) {
  151         /* Write out referenced actions. */
  152         if ( act->numTransRefs > 0 ) {
  153             /* Write the case label, the action and the case break. */
  154             out << "\tcase " << act->actionId << ":\n";
  155             ACTION( out, act, 0, false, false );
  156             out << "\tbreak;\n";
  157         }
  158     }
  159 
  160     genLineDirective( out );
  161     return out;
  162 }
  163 
  164 std::ostream &TabCodeGen::COND_OFFSETS()
  165 {
  166     out << "\t";
  167     int totalStateNum = 0, curKeyOffset = 0;
  168     for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
  169         /* Write the key offset. */
  170         out << curKeyOffset;
  171         if ( !st.last() ) {
  172             out << ", ";
  173             if ( ++totalStateNum % IALL == 0 )
  174                 out << "\n\t";
  175         }
  176 
  177         /* Move the key offset ahead. */
  178         curKeyOffset += st->stateCondList.length();
  179     }
  180     out << "\n";
  181     return out;
  182 }
  183 
  184 std::ostream &TabCodeGen::KEY_OFFSETS()
  185 {
  186     out << "\t";
  187     int totalStateNum = 0, curKeyOffset = 0;
  188     for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
  189         /* Write the key offset. */
  190         out << curKeyOffset;
  191         if ( !st.last() ) {
  192             out << ", ";
  193             if ( ++totalStateNum % IALL == 0 )
  194                 out << "\n\t";
  195         }
  196 
  197         /* Move the key offset ahead. */
  198         curKeyOffset += st->outSingle.length() + st->outRange.length()*2;
  199     }
  200     out << "\n";
  201     return out;
  202 }
  203 
  204 
  205 std::ostream &TabCodeGen::INDEX_OFFSETS()
  206 {
  207     out << "\t";
  208     int totalStateNum = 0, curIndOffset = 0;
  209     for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
  210         /* Write the index offset. */
  211         out << curIndOffset;
  212         if ( !st.last() ) {
  213             out << ", ";
  214             if ( ++totalStateNum % IALL == 0 )
  215                 out << "\n\t";
  216         }
  217 
  218         /* Move the index offset ahead. */
  219         curIndOffset += st->outSingle.length() + st->outRange.length();
  220         if ( st->defTrans != 0 )
  221             curIndOffset += 1;
  222     }
  223     out << "\n";
  224     return out;
  225 }
  226 
  227 std::ostream &TabCodeGen::COND_LENS()
  228 {
  229     out << "\t";
  230     int totalStateNum = 0;
  231     for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
  232         /* Write singles length. */
  233         out << st->stateCondList.length();
  234         if ( !st.last() ) {
  235             out << ", ";
  236             if ( ++totalStateNum % IALL == 0 )
  237                 out << "\n\t";
  238         }
  239     }
  240     out << "\n";
  241     return out;
  242 }
  243 
  244 
  245 std::ostream &TabCodeGen::SINGLE_LENS()
  246 {
  247     out << "\t";
  248     int totalStateNum = 0;
  249     for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
  250         /* Write singles length. */
  251         out << st->outSingle.length();
  252         if ( !st.last() ) {
  253             out << ", ";
  254             if ( ++totalStateNum % IALL == 0 )
  255                 out << "\n\t";
  256         }
  257     }
  258     out << "\n";
  259     return out;
  260 }
  261 
  262 std::ostream &TabCodeGen::RANGE_LENS()
  263 {
  264     out << "\t";
  265     int totalStateNum = 0;
  266     for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
  267         /* Emit length of range index. */
  268         out << st->outRange.length();
  269         if ( !st.last() ) {
  270             out << ", ";
  271             if ( ++totalStateNum % IALL == 0 )
  272                 out << "\n\t";
  273         }
  274     }
  275     out << "\n";
  276     return out;
  277 }
  278 
  279 std::ostream &TabCodeGen::TO_STATE_ACTIONS()
  280 {
  281     out << "\t";
  282     int totalStateNum = 0;
  283     for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
  284         /* Write any eof action. */
  285         TO_STATE_ACTION(st);
  286         if ( !st.last() ) {
  287             out << ", ";
  288             if ( ++totalStateNum % IALL == 0 )
  289                 out << "\n\t";
  290         }
  291     }
  292     out << "\n";
  293     return out;
  294 }
  295 
  296 std::ostream &TabCodeGen::FROM_STATE_ACTIONS()
  297 {
  298     out << "\t";
  299     int totalStateNum = 0;
  300     for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
  301         /* Write any eof action. */
  302         FROM_STATE_ACTION(st);
  303         if ( !st.last() ) {
  304             out << ", ";
  305             if ( ++totalStateNum % IALL == 0 )
  306                 out << "\n\t";
  307         }
  308     }
  309     out << "\n";
  310     return out;
  311 }
  312 
  313 std::ostream &TabCodeGen::EOF_ACTIONS()
  314 {
  315     out << "\t";
  316     int totalStateNum = 0;
  317     for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
  318         /* Write any eof action. */
  319         EOF_ACTION(st);
  320         if ( !st.last() ) {
  321             out << ", ";
  322             if ( ++totalStateNum % IALL == 0 )
  323                 out << "\n\t";
  324         }
  325     }
  326     out << "\n";
  327     return out;
  328 }
  329 
  330 std::ostream &TabCodeGen::EOF_TRANS()
  331 {
  332     out << "\t";
  333     int totalStateNum = 0;
  334     for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
  335         /* Write any eof action. */
  336         long trans = 0;
  337         if ( st->eofTrans != 0 ) {
  338             assert( st->eofTrans->pos >= 0 );
  339             trans = st->eofTrans->pos+1;
  340         }
  341         out << trans;
  342 
  343         if ( !st.last() ) {
  344             out << ", ";
  345             if ( ++totalStateNum % IALL == 0 )
  346                 out << "\n\t";
  347         }
  348     }
  349     out << "\n";
  350     return out;
  351 }
  352 
  353 
  354 std::ostream &TabCodeGen::COND_KEYS()
  355 {
  356     out << '\t';
  357     int totalTrans = 0;
  358     for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
  359         /* Loop the state's transitions. */
  360         for ( GenStateCondList::Iter sc = st->stateCondList; sc.lte(); sc++ ) {
  361             /* Lower key. */
  362             out << KEY( sc->lowKey ) << ", ";
  363             if ( ++totalTrans % IALL == 0 )
  364                 out << "\n\t";
  365 
  366             /* Upper key. */
  367             out << KEY( sc->highKey ) << ", ";
  368             if ( ++totalTrans % IALL == 0 )
  369                 out << "\n\t";
  370         }
  371     }
  372 
  373     /* Output one last number so we don't have to figure out when the last
  374      * entry is and avoid writing a comma. */
  375     out << 0 << "\n";
  376     return out;
  377 }
  378 
  379 std::ostream &TabCodeGen::COND_SPACES()
  380 {
  381     out << '\t';
  382     int totalTrans = 0;
  383     for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
  384         /* Loop the state's transitions. */
  385         for ( GenStateCondList::Iter sc = st->stateCondList; sc.lte(); sc++ ) {
  386             /* Cond Space id. */
  387             out << sc->condSpace->condSpaceId << ", ";
  388             if ( ++totalTrans % IALL == 0 )
  389                 out << "\n\t";
  390         }
  391     }
  392 
  393     /* Output one last number so we don't have to figure out when the last
  394      * entry is and avoid writing a comma. */
  395     out << 0 << "\n";
  396     return out;
  397 }
  398 
  399 std::ostream &TabCodeGen::KEYS()
  400 {
  401     out << '\t';
  402     int totalTrans = 0;
  403     for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
  404         /* Loop the singles. */
  405         for ( RedTransList::Iter stel = st->outSingle; stel.lte(); stel++ ) {
  406             out << KEY( stel->lowKey ) << ", ";
  407             if ( ++totalTrans % IALL == 0 )
  408                 out << "\n\t";
  409         }
  410 
  411         /* Loop the state's transitions. */
  412         for ( RedTransList::Iter rtel = st->outRange; rtel.lte(); rtel++ ) {
  413             /* Lower key. */
  414             out << KEY( rtel->lowKey ) << ", ";
  415             if ( ++totalTrans % IALL == 0 )
  416                 out << "\n\t";
  417 
  418             /* Upper key. */
  419             out << KEY( rtel->highKey ) << ", ";
  420             if ( ++totalTrans % IALL == 0 )
  421                 out << "\n\t";
  422         }
  423     }
  424 
  425     /* Output one last number so we don't have to figure out when the last
  426      * entry is and avoid writing a comma. */
  427     out << 0 << "\n";
  428     return out;
  429 }
  430 
  431 std::ostream &TabCodeGen::INDICIES()
  432 {
  433     int totalTrans = 0;
  434     out << '\t';
  435     for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
  436         /* Walk the singles. */
  437         for ( RedTransList::Iter stel = st->outSingle; stel.lte(); stel++ ) {
  438             out << stel->value->id << ", ";
  439             if ( ++totalTrans % IALL == 0 )
  440                 out << "\n\t";
  441         }
  442 
  443         /* Walk the ranges. */
  444         for ( RedTransList::Iter rtel = st->outRange; rtel.lte(); rtel++ ) {
  445             out << rtel->value->id << ", ";
  446             if ( ++totalTrans % IALL == 0 )
  447                 out << "\n\t";
  448         }
  449 
  450         /* The state's default index goes next. */
  451         if ( st->defTrans != 0 ) {
  452             out << st->defTrans->id << ", ";
  453             if ( ++totalTrans % IALL == 0 )
  454                 out << "\n\t";
  455         }
  456     }
  457 
  458     /* Output one last number so we don't have to figure out when the last
  459      * entry is and avoid writing a comma. */
  460     out << 0 << "\n";
  461     return out;
  462 }
  463 
  464 std::ostream &TabCodeGen::TRANS_TARGS()
  465 {
  466     int totalTrans = 0;
  467     out << '\t';
  468     for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
  469         /* Walk the singles. */
  470         for ( RedTransList::Iter stel = st->outSingle; stel.lte(); stel++ ) {
  471             RedTransAp *trans = stel->value;
  472             out << trans->targ->id << ", ";
  473             if ( ++totalTrans % IALL == 0 )
  474                 out << "\n\t";
  475         }
  476 
  477         /* Walk the ranges. */
  478         for ( RedTransList::Iter rtel = st->outRange; rtel.lte(); rtel++ ) {
  479             RedTransAp *trans = rtel->value;
  480             out << trans->targ->id << ", ";
  481             if ( ++totalTrans % IALL == 0 )
  482                 out << "\n\t";
  483         }
  484 
  485         /* The state's default target state. */
  486         if ( st->defTrans != 0 ) {
  487             RedTransAp *trans = st->defTrans;
  488             out << trans->targ->id << ", ";
  489             if ( ++totalTrans % IALL == 0 )
  490                 out << "\n\t";
  491         }
  492     }
  493 
  494     /* Add any eof transitions that have not yet been written out above. */
  495     for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
  496         if ( st->eofTrans != 0 ) {
  497             RedTransAp *trans = st->eofTrans;
  498             trans->pos = totalTrans;
  499             out << trans->targ->id << ", ";
  500             if ( ++totalTrans % IALL == 0 )
  501                 out << "\n\t";
  502         }
  503     }
  504 
  505 
  506     /* Output one last number so we don't have to figure out when the last
  507      * entry is and avoid writing a comma. */
  508     out << 0 << "\n";
  509     return out;
  510 }
  511 
  512 
  513 std::ostream &TabCodeGen::TRANS_ACTIONS()
  514 {
  515     int totalTrans = 0;
  516     out << '\t';
  517     for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
  518         /* Walk the singles. */
  519         for ( RedTransList::Iter stel = st->outSingle; stel.lte(); stel++ ) {
  520             RedTransAp *trans = stel->value;
  521             TRANS_ACTION( trans ) << ", ";
  522             if ( ++totalTrans % IALL == 0 )
  523                 out << "\n\t";
  524         }
  525 
  526         /* Walk the ranges. */
  527         for ( RedTransList::Iter rtel = st->outRange; rtel.lte(); rtel++ ) {
  528             RedTransAp *trans = rtel->value;
  529             TRANS_ACTION( trans ) << ", ";
  530             if ( ++totalTrans % IALL == 0 )
  531                 out << "\n\t";
  532         }
  533 
  534         /* The state's default index goes next. */
  535         if ( st->defTrans != 0 ) {
  536             RedTransAp *trans = st->defTrans;
  537             TRANS_ACTION( trans ) << ", ";
  538             if ( ++totalTrans % IALL == 0 )
  539                 out << "\n\t";
  540         }
  541     }
  542 
  543     /* Add any eof transitions that have not yet been written out above. */
  544     for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
  545         if ( st->eofTrans != 0 ) {
  546             RedTransAp *trans = st->eofTrans;
  547             TRANS_ACTION( trans ) << ", ";
  548             if ( ++totalTrans % IALL == 0 )
  549                 out << "\n\t";
  550         }
  551     }
  552 
  553 
  554     /* Output one last number so we don't have to figure out when the last
  555      * entry is and avoid writing a comma. */
  556     out << 0 << "\n";
  557     return out;
  558 }
  559 
  560 std::ostream &TabCodeGen::TRANS_TARGS_WI()
  561 {
  562     /* Transitions must be written ordered by their id. */
  563     RedTransAp **transPtrs = new RedTransAp*[redFsm->transSet.length()];
  564     for ( TransApSet::Iter trans = redFsm->transSet; trans.lte(); trans++ )
  565         transPtrs[trans->id] = trans;
  566 
  567     /* Keep a count of the num of items in the array written. */
  568     out << '\t';
  569     int totalStates = 0;
  570     for ( int t = 0; t < redFsm->transSet.length(); t++ ) {
  571         /* Record the position, need this for eofTrans. */
  572         RedTransAp *trans = transPtrs[t];
  573         trans->pos = t;
  574 
  575         /* Write out the target state. */
  576         out << trans->targ->id;
  577         if ( t < redFsm->transSet.length()-1 ) {
  578             out << ", ";
  579             if ( ++totalStates % IALL == 0 )
  580                 out << "\n\t";
  581         }
  582     }
  583     out << "\n";
  584     delete[] transPtrs;
  585     return out;
  586 }
  587 
  588 
  589 std::ostream &TabCodeGen::TRANS_ACTIONS_WI()
  590 {
  591     /* Transitions must be written ordered by their id. */
  592     RedTransAp **transPtrs = new RedTransAp*[redFsm->transSet.length()];
  593     for ( TransApSet::Iter trans = redFsm->transSet; trans.lte(); trans++ )
  594         transPtrs[trans->id] = trans;
  595 
  596     /* Keep a count of the num of items in the array written. */
  597     out << '\t';
  598     int totalAct = 0;
  599     for ( int t = 0; t < redFsm->transSet.length(); t++ ) {
  600         /* Write the function for the transition. */
  601         RedTransAp *trans = transPtrs[t];
  602         TRANS_ACTION( trans );
  603         if ( t < redFsm->transSet.length()-1 ) {
  604             out << ", ";
  605             if ( ++totalAct % IALL == 0 )
  606                 out << "\n\t";
  607         }
  608     }
  609     out << "\n";
  610     delete[] transPtrs;
  611     return out;
  612 }
  613 
  614 void TabCodeGen::LOCATE_TRANS()
  615 {
  616     out <<
  617         "   _keys = " << ARR_OFF( K(), KO() + "[" + vCS() + "]" ) << ";\n"
  618         "   _trans = " << IO() << "[" << vCS() << "];\n"
  619         "\n"
  620         "   _klen = " << SL() << "[" << vCS() << "];\n"
  621         "   if ( _klen > 0 ) {\n"
  622         "       " << PTR_CONST() << WIDE_ALPH_TYPE() << PTR_CONST_END() << POINTER() << "_lower = _keys;\n"
  623         "       " << PTR_CONST() << WIDE_ALPH_TYPE() << PTR_CONST_END() << POINTER() << "_mid;\n"
  624         "       " << PTR_CONST() << WIDE_ALPH_TYPE() << PTR_CONST_END() << POINTER() << "_upper = _keys + _klen - 1;\n"
  625         "       while (1) {\n"
  626         "           if ( _upper < _lower )\n"
  627         "               break;\n"
  628         "\n"
  629         "           _mid = _lower + ((_upper-_lower) >> 1);\n"
  630         "           if ( " << GET_WIDE_KEY() << " < *_mid )\n"
  631         "               _upper = _mid - 1;\n"
  632         "           else if ( " << GET_WIDE_KEY() << " > *_mid )\n"
  633         "               _lower = _mid + 1;\n"
  634         "           else {\n"
  635         "               _trans += " << CAST(UINT()) << "(_mid - _keys);\n"
  636         "               goto _match;\n"
  637         "           }\n"
  638         "       }\n"
  639         "       _keys += _klen;\n"
  640         "       _trans += _klen;\n"
  641         "   }\n"
  642         "\n"
  643         "   _klen = " << RL() << "[" << vCS() << "];\n"
  644         "   if ( _klen > 0 ) {\n"
  645         "       " << PTR_CONST() << WIDE_ALPH_TYPE() << PTR_CONST_END() << POINTER() << "_lower = _keys;\n"
  646         "       " << PTR_CONST() << WIDE_ALPH_TYPE() << PTR_CONST_END() << POINTER() << "_mid;\n"
  647         "       " << PTR_CONST() << WIDE_ALPH_TYPE() << PTR_CONST_END() << POINTER() << "_upper = _keys + (_klen<<1) - 2;\n"
  648         "       while (1) {\n"
  649         "           if ( _upper < _lower )\n"
  650         "               break;\n"
  651         "\n"
  652         "           _mid = _lower + (((_upper-_lower) >> 1) & ~1);\n"
  653         "           if ( " << GET_WIDE_KEY() << " < _mid[0] )\n"
  654         "               _upper = _mid - 2;\n"
  655         "           else if ( " << GET_WIDE_KEY() << " > _mid[1] )\n"
  656         "               _lower = _mid + 2;\n"
  657         "           else {\n"
  658         "               _trans += " << CAST(UINT()) << "((_mid - _keys)>>1);\n"
  659         "               goto _match;\n"
  660         "           }\n"
  661         "       }\n"
  662         "       _trans += _klen;\n"
  663         "   }\n"
  664         "\n";
  665 }
  666 
  667 void TabCodeGen::GOTO( ostream &ret, int gotoDest, bool inFinish )
  668 {
  669     ret << "{";
  670     
  671     ret << vCS() << " = " << gotoDest << ";";
  672 
  673     if ( inFinish && !noEnd )
  674         EOF_CHECK( ret );
  675 
  676     ret << CTRL_FLOW() << "goto _again;";
  677 
  678     ret << "}";
  679 }
  680 
  681 void TabCodeGen::GOTO_EXPR( ostream &ret, GenInlineItem *ilItem, bool inFinish )
  682 {
  683     ret << "{";
  684     ret << vCS() << " = (";
  685     INLINE_LIST( ret, ilItem->children, 0, inFinish, false );
  686     ret << "); ";
  687 
  688     if ( inFinish && !noEnd )
  689         EOF_CHECK( ret );
  690 
  691     ret << CTRL_FLOW() << "goto _again;";
  692 
  693     ret << "}";
  694 }
  695 
  696 void TabCodeGen::CURS( ostream &ret, bool inFinish )
  697 {
  698     ret << "(_ps)";
  699 }
  700 
  701 void TabCodeGen::TARGS( ostream &ret, bool inFinish, int targState )
  702 {
  703     ret << "(" << vCS() << ")";
  704 }
  705 
  706 void TabCodeGen::NEXT( ostream &ret, int nextDest, bool inFinish )
  707 {
  708     ret << vCS() << " = " << nextDest << ";";
  709 }
  710 
  711 void TabCodeGen::NEXT_EXPR( ostream &ret, GenInlineItem *ilItem, bool inFinish )
  712 {
  713     ret << vCS() << " = (";
  714     INLINE_LIST( ret, ilItem->children, 0, inFinish, false );
  715     ret << ");";
  716 }
  717 
  718 void TabCodeGen::CALL( ostream &ret, int callDest, int targState, bool inFinish )
  719 {
  720     if ( prePushExpr != 0 ) {
  721         ret << "{";
  722         INLINE_LIST( ret, prePushExpr, 0, false, false );
  723     }
  724 
  725     ret << "{" << STACK() << "[" << TOP() << "++] = " << vCS() << "; " << vCS() << " = " << callDest << ";";
  726 
  727     if ( inFinish && !noEnd )
  728         EOF_CHECK( ret );
  729 
  730     ret << CTRL_FLOW() << "goto _again;";
  731 
  732     ret << "}";
  733 
  734     if ( prePushExpr != 0 )
  735         ret << "}";
  736 }
  737 
  738 void TabCodeGen::CALL_EXPR( ostream &ret, GenInlineItem *ilItem, int targState, bool inFinish )
  739 {
  740     if ( prePushExpr != 0 ) {
  741         ret << "{";
  742         INLINE_LIST( ret, prePushExpr, 0, false, false );
  743     }
  744 
  745     ret << "{";
  746 
  747     ret << STACK() << "[" << TOP() << "++] = " << vCS() << "; " << vCS() << " = (";
  748     INLINE_LIST( ret, ilItem->children, targState, inFinish, false );
  749     ret << ");";
  750 
  751     if ( inFinish && !noEnd )
  752         EOF_CHECK( ret );
  753 
  754     ret << CTRL_FLOW() << "goto _again;";
  755 
  756     ret << "}";
  757 
  758     if ( prePushExpr != 0 )
  759         ret << "}";
  760 }
  761 
  762 void TabCodeGen::RET( ostream &ret, bool inFinish )
  763 {
  764     ret << "{" << vCS() << " = " << STACK() << "[--" << 
  765             TOP() << "]; ";
  766 
  767     if ( postPopExpr != 0 ) {
  768         ret << "{";
  769         INLINE_LIST( ret, postPopExpr, 0, false, false );
  770         ret << "}";
  771     }
  772 
  773     if ( inFinish && !noEnd )
  774         EOF_CHECK( ret );
  775 
  776     ret << CTRL_FLOW() <<  "goto _again;";
  777 
  778     ret << "}";
  779 }
  780 
  781 void TabCodeGen::BREAK( ostream &ret, int targState, bool csForced )
  782 {
  783     outLabelUsed = true;
  784     ret << "{" << P() << "++; " << CTRL_FLOW() << "goto _out; }";
  785 }
  786 
  787 void TabCodeGen::writeData()
  788 {
  789     /* If there are any transtion functions then output the array. If there
  790      * are none, don't bother emitting an empty array that won't be used. */
  791     if ( redFsm->anyActions() ) {
  792         OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActArrItem), A() );
  793         ACTIONS_ARRAY();
  794         CLOSE_ARRAY() <<
  795         "\n";
  796     }
  797 
  798     if ( redFsm->anyConditions() ) {
  799         OPEN_ARRAY( ARRAY_TYPE(redFsm->maxCondOffset), CO() );
  800         COND_OFFSETS();
  801         CLOSE_ARRAY() <<
  802         "\n";
  803 
  804         OPEN_ARRAY( ARRAY_TYPE(redFsm->maxCondLen), CL() );
  805         COND_LENS();
  806         CLOSE_ARRAY() <<
  807         "\n";
  808 
  809         OPEN_ARRAY( WIDE_ALPH_TYPE(), CK() );
  810         COND_KEYS();
  811         CLOSE_ARRAY() <<
  812         "\n";
  813 
  814         OPEN_ARRAY( ARRAY_TYPE(redFsm->maxCondSpaceId), C() );
  815         COND_SPACES();
  816         CLOSE_ARRAY() <<
  817         "\n";
  818     }
  819 
  820     OPEN_ARRAY( ARRAY_TYPE(redFsm->maxKeyOffset), KO() );
  821     KEY_OFFSETS();
  822     CLOSE_ARRAY() <<
  823     "\n";
  824 
  825     OPEN_ARRAY( WIDE_ALPH_TYPE(), K() );
  826     KEYS();
  827     CLOSE_ARRAY() <<
  828     "\n";
  829 
  830     OPEN_ARRAY( ARRAY_TYPE(redFsm->maxSingleLen), SL() );
  831     SINGLE_LENS();
  832     CLOSE_ARRAY() <<
  833     "\n";
  834 
  835     OPEN_ARRAY( ARRAY_TYPE(redFsm->maxRangeLen), RL() );
  836     RANGE_LENS();
  837     CLOSE_ARRAY() <<
  838     "\n";
  839 
  840     OPEN_ARRAY( ARRAY_TYPE(redFsm->maxIndexOffset), IO() );
  841     INDEX_OFFSETS();
  842     CLOSE_ARRAY() <<
  843     "\n";
  844 
  845     if ( useIndicies ) {
  846         OPEN_ARRAY( ARRAY_TYPE(redFsm->maxIndex), I() );
  847         INDICIES();
  848         CLOSE_ARRAY() <<
  849         "\n";
  850 
  851         OPEN_ARRAY( ARRAY_TYPE(redFsm->maxState), TT() );
  852         TRANS_TARGS_WI();
  853         CLOSE_ARRAY() <<
  854         "\n";
  855 
  856         if ( redFsm->anyActions() ) {
  857             OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActionLoc), TA() );
  858             TRANS_ACTIONS_WI();
  859             CLOSE_ARRAY() <<
  860             "\n";
  861         }
  862     }
  863     else {
  864         OPEN_ARRAY( ARRAY_TYPE(redFsm->maxState), TT() );
  865         TRANS_TARGS();
  866         CLOSE_ARRAY() <<
  867         "\n";
  868 
  869         if ( redFsm->anyActions() ) {
  870             OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActionLoc), TA() );
  871             TRANS_ACTIONS();
  872             CLOSE_ARRAY() <<
  873             "\n";
  874         }
  875     }
  876 
  877     if ( redFsm->anyToStateActions() ) {
  878         OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActionLoc), TSA() );
  879         TO_STATE_ACTIONS();
  880         CLOSE_ARRAY() <<
  881         "\n";
  882     }
  883 
  884     if ( redFsm->anyFromStateActions() ) {
  885         OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActionLoc), FSA() );
  886         FROM_STATE_ACTIONS();
  887         CLOSE_ARRAY() <<
  888         "\n";
  889     }
  890 
  891     if ( redFsm->anyEofActions() ) {
  892         OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActionLoc), EA() );
  893         EOF_ACTIONS();
  894         CLOSE_ARRAY() <<
  895         "\n";
  896     }
  897 
  898     if ( redFsm->anyEofTrans() ) {
  899         OPEN_ARRAY( ARRAY_TYPE(redFsm->maxIndexOffset+1), ET() );
  900         EOF_TRANS();
  901         CLOSE_ARRAY() <<
  902         "\n";
  903     }
  904 
  905     STATE_IDS();
  906 }
  907 
  908 void TabCodeGen::COND_TRANSLATE()
  909 {
  910     out << 
  911         "   _widec = " << GET_KEY() << ";\n"
  912         "   _klen = " << CL() << "[" << vCS() << "];\n"
  913         "   _keys = " << ARR_OFF( CK(), "(" + CO() + "[" + vCS() + "]*2)" ) << ";\n"
  914         "   if ( _klen > 0 ) {\n"
  915         "       " << PTR_CONST() << WIDE_ALPH_TYPE() << PTR_CONST_END() << POINTER() << "_lower = _keys;\n"
  916         "       " << PTR_CONST() << WIDE_ALPH_TYPE() << PTR_CONST_END() << POINTER() << "_mid;\n"
  917         "       " << PTR_CONST() << WIDE_ALPH_TYPE() << PTR_CONST_END() << POINTER() << "_upper = _keys + (_klen<<1) - 2;\n"
  918         "       while (1) {\n"
  919         "           if ( _upper < _lower )\n"
  920         "               break;\n"
  921         "\n"
  922         "           _mid = _lower + (((_upper-_lower) >> 1) & ~1);\n"
  923         "           if ( " << GET_WIDE_KEY() << " < _mid[0] )\n"
  924         "               _upper = _mid - 2;\n"
  925         "           else if ( " << GET_WIDE_KEY() << " > _mid[1] )\n"
  926         "               _lower = _mid + 2;\n"
  927         "           else {\n"
  928         "               switch ( " << C() << "[" << CO() << "[" << vCS() << "]"
  929                             " + ((_mid - _keys)>>1)] ) {\n";
  930 
  931     for ( CondSpaceList::Iter csi = condSpaceList; csi.lte(); csi++ ) {
  932         GenCondSpace *condSpace = csi;
  933         out << "    case " << condSpace->condSpaceId << ": {\n";
  934         out << TABS(2) << "_widec = " << CAST(WIDE_ALPH_TYPE()) << "(" <<
  935                 KEY(condSpace->baseKey) << " + (" << GET_KEY() << 
  936                 " - " << KEY(keyOps->minKey) << "));\n";
  937 
  938         for ( GenCondSet::Iter csi = condSpace->condSet; csi.lte(); csi++ ) {
  939             out << TABS(2) << "if ( ";
  940             CONDITION( out, *csi );
  941             Size condValOffset = ((1 << csi.pos()) * keyOps->alphSize());
  942             out << " ) _widec += " << condValOffset << ";\n";
  943         }
  944 
  945         out << 
  946             "       break;\n"
  947             "   }\n";
  948     }
  949 
  950     SWITCH_DEFAULT();
  951 
  952     out << 
  953         "               }\n"
  954         "               break;\n"
  955         "           }\n"
  956         "       }\n"
  957         "   }\n"
  958         "\n";
  959 }
  960 
  961 void TabCodeGen::writeExec()
  962 {
  963     testEofUsed = false;
  964     outLabelUsed = false;
  965 
  966     out <<
  967         "   {\n"
  968         "   int _klen";
  969 
  970     if ( redFsm->anyRegCurStateRef() )
  971         out << ", _ps";
  972 
  973     out << 
  974         ";\n"
  975         "   " << UINT() << " _trans;\n";
  976 
  977     if ( redFsm->anyConditions() )
  978         out << "    " << WIDE_ALPH_TYPE() << " _widec;\n";
  979 
  980     if ( redFsm->anyToStateActions() || redFsm->anyRegActions() 
  981             || redFsm->anyFromStateActions() )
  982     {
  983         out << 
  984             "   " << PTR_CONST() << ARRAY_TYPE(redFsm->maxActArrItem) << PTR_CONST_END() << 
  985                     POINTER() << "_acts;\n"
  986             "   " << UINT() << " _nacts;\n";
  987     }
  988 
  989     out <<
  990         "   " << PTR_CONST() << WIDE_ALPH_TYPE() << PTR_CONST_END() << POINTER() << "_keys;\n"
  991         "\n";
  992 
  993     if ( !noEnd ) {
  994         testEofUsed = true;
  995         out << 
  996             "   if ( " << P() << " == " << PE() << " )\n"
  997             "       goto _test_eof;\n";
  998     }
  999 
 1000     if ( redFsm->errState != 0 ) {
 1001         outLabelUsed = true;
 1002         out << 
 1003             "   if ( " << vCS() << " == " << redFsm->errState->id << " )\n"
 1004             "       goto _out;\n";
 1005     }
 1006 
 1007     out << "_resume:\n";
 1008 
 1009     if ( redFsm->anyFromStateActions() ) {
 1010         out <<
 1011             "   _acts = " << ARR_OFF( A(),  FSA() + "[" + vCS() + "]" ) << ";\n"
 1012             "   _nacts = " << CAST(UINT()) << " *_acts++;\n"
 1013             "   while ( _nacts-- > 0 ) {\n"
 1014             "       switch ( *_acts++ ) {\n";
 1015             FROM_STATE_ACTION_SWITCH();
 1016             SWITCH_DEFAULT() <<
 1017             "       }\n"
 1018             "   }\n"
 1019             "\n";
 1020     }
 1021 
 1022     if ( redFsm->anyConditions() )
 1023         COND_TRANSLATE();
 1024 
 1025     LOCATE_TRANS();
 1026 
 1027     out << "_match:\n";
 1028 
 1029     if ( useIndicies )
 1030         out << "    _trans = " << I() << "[_trans];\n";
 1031     
 1032     if ( redFsm->anyEofTrans() )
 1033         out << "_eof_trans:\n";
 1034 
 1035     if ( redFsm->anyRegCurStateRef() )
 1036         out << "    _ps = " << vCS() << ";\n";
 1037 
 1038     out <<
 1039         "   " << vCS() << " = " << TT() << "[_trans];\n"
 1040         "\n";
 1041 
 1042     if ( redFsm->anyRegActions() ) {
 1043         out <<
 1044             "   if ( " << TA() << "[_trans] == 0 )\n"
 1045             "       goto _again;\n"
 1046             "\n"
 1047             "   _acts = " << ARR_OFF( A(), TA() + "[_trans]" ) << ";\n"
 1048             "   _nacts = " << CAST(UINT()) << " *_acts++;\n"
 1049             "   while ( _nacts-- > 0 )\n    {\n"
 1050             "       switch ( *_acts++ )\n       {\n";
 1051             ACTION_SWITCH();
 1052             SWITCH_DEFAULT() <<
 1053             "       }\n"
 1054             "   }\n"
 1055             "\n";
 1056     }
 1057 
 1058     if ( redFsm->anyRegActions() || redFsm->anyActionGotos() || 
 1059             redFsm->anyActionCalls() || redFsm->anyActionRets() )
 1060         out << "_again:\n";
 1061 
 1062     if ( redFsm->anyToStateActions() ) {
 1063         out <<
 1064             "   _acts = " << ARR_OFF( A(), TSA() + "[" + vCS() + "]" ) << ";\n"
 1065             "   _nacts = " << CAST(UINT()) << " *_acts++;\n"
 1066             "   while ( _nacts-- > 0 ) {\n"
 1067             "       switch ( *_acts++ ) {\n";
 1068             TO_STATE_ACTION_SWITCH();
 1069             SWITCH_DEFAULT() <<
 1070             "       }\n"
 1071             "   }\n"
 1072             "\n";
 1073     }
 1074 
 1075     if ( redFsm->errState != 0 ) {
 1076         outLabelUsed = true;
 1077         out << 
 1078             "   if ( " << vCS() << " == " << redFsm->errState->id << " )\n"
 1079             "       goto _out;\n";
 1080     }
 1081 
 1082     if ( !noEnd ) {
 1083         out << 
 1084             "   if ( ++" << P() << " != " << PE() << " )\n"
 1085             "       goto _resume;\n";
 1086     }
 1087     else {
 1088         out << 
 1089             "   " << P() << " += 1;\n"
 1090             "   goto _resume;\n";
 1091     }
 1092     
 1093     if ( testEofUsed )
 1094         out << "    _test_eof: {}\n";
 1095     
 1096     if ( redFsm->anyEofTrans() || redFsm->anyEofActions() ) {
 1097         out << 
 1098             "   if ( " << P() << " == " << vEOF() << " )\n"
 1099             "   {\n";
 1100 
 1101         if ( redFsm->anyEofTrans() ) {
 1102             out <<
 1103                 "   if ( " << ET() << "[" << vCS() << "] > 0 ) {\n"
 1104                 "       _trans = " << ET() << "[" << vCS() << "] - 1;\n"
 1105                 "       goto _eof_trans;\n"
 1106                 "   }\n";
 1107         }
 1108 
 1109         if ( redFsm->anyEofActions() ) {
 1110             out <<
 1111                 "   " << PTR_CONST() << ARRAY_TYPE(redFsm->maxActArrItem) << PTR_CONST_END() << 
 1112                         POINTER() << "__acts = " << 
 1113                         ARR_OFF( A(), EA() + "[" + vCS() + "]" ) << ";\n"
 1114                 "   " << UINT() << " __nacts = " << CAST(UINT()) << " *__acts++;\n"
 1115                 "   while ( __nacts-- > 0 ) {\n"
 1116                 "       switch ( *__acts++ ) {\n";
 1117                 EOF_ACTION_SWITCH();
 1118                 SWITCH_DEFAULT() <<
 1119                 "       }\n"
 1120                 "   }\n";
 1121         }
 1122         
 1123         out << 
 1124             "   }\n"
 1125             "\n";
 1126     }
 1127 
 1128     if ( outLabelUsed )
 1129         out << "    _out: {}\n";
 1130 
 1131     out << "    }\n";
 1132 }