Logo Search packages:      
Sourcecode: ragel version File versions

fsmstate.cpp

/*
 *  Copyright 2002 Adrian Thurston <adriant@ragel.ca>
 */

/*  This file is part of Ragel.
 *
 *  Ragel is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 * 
 *  Ragel is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 * 
 *  You should have received a copy of the GNU General Public License
 *  along with Ragel; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA 
 */

#include <string.h>
#include <assert.h>
#include "fsmgraph.h"

#include <iostream>
using namespace std;

/* Return and re-entry for the co-routine iterators. This should ALWAYS be
 * used inside of a block. */
#define CO_RETURN(label) \
      itState = label; \
      return; \
      entry##label: backIn = true

/* Return and re-entry for the co-routine iterators. This should ALWAYS be
 * used inside of a block. */
#define CO_RETURN2(label, uState) \
      itState = label; \
      userState = uState; \
      return; \
      entry##label: backIn = true

/* Construct a mark index for a specified number of states. Must new up
 * an array that is states^2 in size. */
MarkIndex::MarkIndex( int states ) : numStates(states)
{
      /* Total pairs is states^2. Actually only use half of these, but we allocate
       * them all to make indexing into the array easier. */
      int total = states * states;

      /* New up chars so that individual DListEl constructors are
       * not called. Zero out the mem manually. */
      array = new bool[total];
      memset( array, 0, sizeof(bool) * total );
}

/* Free the array used to store state pairs. */
MarkIndex::~MarkIndex()
{
      delete[] array;
}

/* Mark a pair of states. States are specified by their number. The
 * marked states are moved from the unmarked list to the marked list. */
void MarkIndex::markPair(int state1, int state2)
{
      int pos = ( state1 >= state2 ) ?
            ( state1 * numStates ) + state2 :
            ( state2 * numStates ) + state1;

      array[pos] = true;
}

/* Returns true if the pair of states are marked. Returns false otherwise.
 * Ordering of states given does not matter. */
bool MarkIndex::isPairMarked(int state1, int state2)
{
      int pos = ( state1 >= state2 ) ?
            ( state1 * numStates ) + state2 :
            ( state2 * numStates ) + state1;

      return array[pos];
}

/*
 * FsmKeySet
 */

/* Return a pointer to the item in the set on success. */
long *KeySet::insert( long key, KeyOps *keyOps )
{
      long *lower, *upper;
      int dataLen = size();
      if ( dataLen == 0 ) {
            lower = data;
            goto insert;
      }

      lower = data;
      upper = data + dataLen - 1;
      while ( true ) {
            /* Not found, insert location is lower. */
            if ( upper < lower )
                  goto insert;

            long *mid = lower + ((upper-lower)>>1);
            if ( keyOps->lt( key, *mid ) )
                  upper = mid - 1;
            else if ( keyOps->gt( key, *mid ) )
                  lower = mid + 1;
            else {
                  /* The key was found, return failure. */
                  return 0;
            }
      }
insert:
      /* Get the insert pos. */
      int insertPos = lower - data;

      /* Do the insert. After makeRawSpaceFor, lower pointer is no good. */
      makeRawSpaceFor( insertPos, 1 );
      data[insertPos] = key;

      /* Return the new element. */
      return data + insertPos;
}

/* Create a new fsm state. State has not out transitions or in transitions, not
 * out out transition data and not number. */
StateAp::StateAp()
:
      /* No out transitions. */
      outList(),
      outDefault(0),

      /* No in transitions. */
      inRange(),
      inDefault(),

      /* No entry points, or epsilon trans. */
      entryIds(),
      epsilonTrans(),
      contextSet(),

      /* No transitions in from other states. */
      foreignInTrans(0),

      /* Only used during merging. Normally null. */
      stateDictEl(0),
      eptVect(0),

      /* No state identification bits. */
      stateBits(0),

      /* No out action/priority data. */
      outActionTable(),
      outPriorTable(),
      errActionTable(),
      eofActionTable()
{
}

/* Copy everything except actual the transitions. That is left up to the
 * FsmAp copy constructor. */
StateAp::StateAp(const StateAp &other)
:
      /* All lists are cleared. They will be filled in when the
       * individual transitions are duplicated and attached. */
      outList(),
      outDefault(0),
      inRange(),
      inDefault(),

      /* Duplicate the entry id set, epsilon transitions and context sets. These
       * are sets of integers and as such need no fixing. */
      entryIds(other.entryIds),
      epsilonTrans(other.epsilonTrans),
      contextSet(other.contextSet),

      /* No transitions in from other states. */
      foreignInTrans(0),

      /* This is only used during merging. Normally null. */
      stateDictEl(0),
      eptVect(0),

      /* Fsm state data. */
      stateBits(other.stateBits),

      /* Fsm state data. */
      outActionTable(other.outActionTable),
      outPriorTable(other.outPriorTable),
      errActionTable(other.errActionTable),
      eofActionTable(other.eofActionTable)
{
      /* Duplicate all the transitions. */
      for ( TransList::Iter trans = other.outList; trans.lte(); trans++ ) {
            /* Dupicate and store the orginal target in the transition. This will
             * be corrected once all the states have been created. */
            TransAp *newTrans = new TransAp(*trans);
            newTrans->toState = trans->toState;
            outList.append( newTrans );
      }

      /* Duplicate the default transition if it is there. */
      outDefault = 0;
      if ( other.outDefault != 0 ) {
            /* Duplicate and store the original target. */
            outDefault = new TransAp(*other.outDefault);
            outDefault->toState = other.outDefault->toState;
      }
}


/* Compare two states using pointers to the states. With the approximate
 * compare the idea is that if the compare finds them the same, they can
 * immediately be merged. */
int ApproxCompare::compare( const StateAp *state1 , const StateAp *state2 )
{
      int compareRes;

      /* Test final state status. */
      if ( (state1->stateBits & SB_ISFINAL) && !(state2->stateBits & SB_ISFINAL) )
            return -1;
      else if ( !(state1->stateBits & SB_ISFINAL) && (state2->stateBits & SB_ISFINAL) )
            return 1;
      
      /* Test epsilon transition sets. */
      compareRes = CmpEpsilonTrans::compare( state1->epsilonTrans, 
                  state2->epsilonTrans );
      if ( compareRes != 0 )
            return compareRes;
      
      /* Test context sets. */
      compareRes = CmpContextSets::compare( state1->contextSet, 
                  state2->contextSet );
      if ( compareRes != 0 )
            return compareRes;
      
      /* Compare the out transitions. */
      compareRes = FsmAp::compareStateData( state1, state2 );
      if ( compareRes != 0 )
            return compareRes;

      /* Test default transitions. */
      compareRes = FsmAp::compareFullPtr( state1->outDefault, 
                  state2->outDefault );
      if ( compareRes != 0 )
            return compareRes;

      /* Use a pair iterator to get the transition pairs. */
      PairIter outPair( state1, state2, keyOps, false );
      while ( ! outPair.end() ) {
            switch ( outPair.userState ) {

            case PairIter::RangeInS1:
                  compareRes = FsmAp::compareFullPtr( 
                              outPair.s1Tel.trans, state2->outDefault );
                  if ( compareRes != 0 )
                        return compareRes;
                  break;

            case PairIter::RangeInS2:
                  compareRes = FsmAp::compareFullPtr( 
                              state1->outDefault, outPair.s2Tel.trans );
                  if ( compareRes != 0 )
                        return compareRes;
                  break;

            case PairIter::RangeOverlap:
                  compareRes = FsmAp::compareFullPtr( 
                              outPair.s1Tel.trans, outPair.s2Tel.trans );
                  if ( compareRes != 0 )
                        return compareRes;
                  break;

            case PairIter::BreakS1:
            case PairIter::BreakS2:
                  break;
            }
            outPair++;
      }

      /* Got through the entire state comparison, deem them equal. */
      return 0;
}

/* Compare class for the sort that does the intial partition of compaction. */
int InitPartitionCompare::compare( const StateAp *state1 , const StateAp *state2 )
{
      int compareRes;

      /* Test final state status. */
      if ( (state1->stateBits & SB_ISFINAL) && !(state2->stateBits & SB_ISFINAL) )
            return -1;
      else if ( !(state1->stateBits & SB_ISFINAL) && (state2->stateBits & SB_ISFINAL) )
            return 1;

      /* Test epsilon transition sets. */
      compareRes = CmpEpsilonTrans::compare( state1->epsilonTrans, 
                  state2->epsilonTrans );
      if ( compareRes != 0 )
            return compareRes;

      /* Test context sets. */
      compareRes = CmpContextSets::compare( state1->contextSet, 
                  state2->contextSet );
      if ( compareRes != 0 )
            return compareRes;

      /* Compare the out transitions. */
      compareRes = FsmAp::compareStateData( state1, state2 );
      if ( compareRes != 0 )
            return compareRes;

      /* Test default transitions. */
      compareRes = FsmAp::compareDataPtr( state1->outDefault, 
                  state2->outDefault );
      if ( compareRes != 0 )
            return compareRes;

      /* Use a pair iterator to get the transition pairs. */
      PairIter outPair( state1, state2, keyOps, false );
      while ( ! outPair.end() ) {
            switch ( outPair.userState ) {

            case PairIter::RangeInS1:
                  compareRes = FsmAp::compareDataPtr( 
                              outPair.s1Tel.trans, state2->outDefault );
                  if ( compareRes != 0 )
                        return compareRes;
                  break;

            case PairIter::RangeInS2:
                  compareRes = FsmAp::compareDataPtr( 
                              state1->outDefault, outPair.s2Tel.trans );
                  if ( compareRes != 0 )
                        return compareRes;
                  break;

            case PairIter::RangeOverlap:
                  compareRes = FsmAp::compareDataPtr( 
                              outPair.s1Tel.trans, outPair.s2Tel.trans );
                  if ( compareRes != 0 )
                        return compareRes;
                  break;

            case PairIter::BreakS1:
            case PairIter::BreakS2:
                  break;
            }
            outPair++;
      }

      return 0;
}

/* Compare class for the sort that does the partitioning. */
int PartitionCompare::compare( const StateAp *state1, const StateAp *state2 )
{
      int compareRes;

      /* Test default transitions. */
      compareRes = FsmAp::comparePartPtr( state1->outDefault, state2->outDefault );
      if ( compareRes != 0 )
            return compareRes;

      /* Use a pair iterator to get the transition pairs. */
      PairIter outPair( state1, state2, keyOps, false );
      while ( ! outPair.end() ) {
            switch ( outPair.userState ) {

            case PairIter::RangeInS1:
                  compareRes = FsmAp::comparePartPtr( 
                              outPair.s1Tel.trans, state2->outDefault );
                  if ( compareRes != 0 )
                        return compareRes;
                  break;

            case PairIter::RangeInS2:
                  compareRes = FsmAp::comparePartPtr( 
                              state1->outDefault, outPair.s2Tel.trans );
                  if ( compareRes != 0 )
                        return compareRes;
                  break;

            case PairIter::RangeOverlap:
                  compareRes = FsmAp::comparePartPtr( 
                              outPair.s1Tel.trans, outPair.s2Tel.trans );
                  if ( compareRes != 0 )
                        return compareRes;
                  break;

            case PairIter::BreakS1:
            case PairIter::BreakS2:
                  break;
            }
            outPair++;
      }

      return 0;
}

/* Compare class for the sort that does the partitioning. */
bool MarkCompare::shouldMark( MarkIndex &markIndex, const StateAp *state1, 
                  const StateAp *state2 )
{
      /* Test default transitions. */
      if ( FsmAp::shouldMarkPtr( markIndex, state1->outDefault, 
                  state2->outDefault ) )
            return true;

      /* Use a pair iterator to get the transition pairs. */
      PairIter outPair( state1, state2, keyOps, false );
      while ( ! outPair.end() ) {
            switch ( outPair.userState ) {

            case PairIter::RangeInS1:
                  if ( FsmAp::shouldMarkPtr( markIndex, 
                              outPair.s1Tel.trans, state2->outDefault ) )
                        return true;
                  break;

            case PairIter::RangeInS2:
                  if ( FsmAp::shouldMarkPtr( markIndex,
                              state1->outDefault, outPair.s2Tel.trans ) )
                        return true;
                  break;

            case PairIter::RangeOverlap:
                  if ( FsmAp::shouldMarkPtr( markIndex,
                              outPair.s1Tel.trans, outPair.s2Tel.trans ) )
                        return true;
                  break;

            case PairIter::BreakS1:
            case PairIter::BreakS2:
                  break;
            }
            outPair++;
      }

      return false;
}


/* Init the iterator by advancing to the first item. */
OutIter::OutIter( StateAp *state )
:
      state(state),
      itState(Begin)
{
      findNext();
}

/* Postfix operator. Save result for return then increment. */
TransAp *OutIter::operator++(int)
{
      TransAp *retVal = trans;
      findNext();
      return retVal;
}

/* Prefix operator. Icrement first, then return result. */
TransAp *OutIter::operator++()
{
      findNext();
      return trans;
}

/* Advance to the next transition. When returns, trans points to the next
 * transition, unless there are no more, in which case end() returns true. */
void OutIter::findNext()
{
      /* This variable is used in dummy statements that follow the entry
       * goto labels. The compiler needs some statement to follow the label. */
      bool backIn;

      /* Jump into the iterator routine base on the iterator state. */
      switch ( itState ) {
            case Begin:     goto entryBegin;
            case Range:     goto entryRange;
            case Default:   goto entryDefault;
            case End:       goto entryEnd;
      }

      entryBegin:

      /* Loop over out list transitions. */
      trans = state->outList.head;
      while ( trans != 0 ) {
            /* Save the state of the iterator and return. */
            CO_RETURN( Range );
            trans = trans->next;
      }

      /* Process default transition. */
      if ( state->outDefault != 0 ) {
            /* Save the state of the iterator and return. */
            trans = state->outDefault;
            CO_RETURN( Default );
      }

      CO_RETURN( End );
}

/* Init the iterator by advancing to the first item. */
InIter::InIter( StateAp *state )
:
      state(state),
      itState(Begin)
{
      findNext();
}

/* Postfix operator. Save result for return then increment. */
TransAp *InIter::operator++(int)
{
      TransAp *retVal = trans;
      findNext();
      return retVal;
}

/* Prefix operator. Icrement first, then return result. */
TransAp *InIter::operator++()
{
      findNext();
      return trans;
}

/* Advance to the next transition. When returns, trans points to the next
 * transition, unless there are no more, in which case end() returns true. */
void InIter::findNext()
{
      /* This variable is used in dummy statements that follow the entry
       * goto labels. The compiler needs some statement to follow the label. */
      bool backIn;

      /* Jump into the iterator routine base on the iterator state. */
      switch ( itState ) {
            case Begin:     goto entryBegin;
            case Range:     goto entryRange;
            case Default:   goto entryDefault;
            case End:       goto entryEnd;
      }

      entryBegin:

      /* Loop over inRange transitions. */
      trans = state->inRange.head;
      while ( trans != 0 ) {
            /* Save the state of the iterator and return. */
            CO_RETURN( Range );

            /* Next transition. */
            trans = trans->ilnext;
      }

      /* Loop over the list of transitions at the default trans. */
      trans = state->inDefault.head;
      while ( trans != 0 ) {
            /* Save the state of the iterator and return. */
            CO_RETURN( Default );

            /* Next transition. */
            trans = trans->ilnext;
      }

      /* Done, go into end state. */
      CO_RETURN( End );
}

/* Init the iterator by advancing to the first item. */
PairIter::PairIter( const StateAp *state1, const StateAp *state2, 
            KeyOps *keyOps, bool wantBreaks )
:
      state1(state1),
      state2(state2),
      itState(Begin),
      keyOps(keyOps),
      wantBreaks(wantBreaks)
{
      findNext();
}

/* Advance to the next transition. When returns, trans points to the next
 * transition, unless there are no more, in which case end() returns true. */
void PairIter::findNext()
{
      /* This variable is used in dummy statements that follow the entry
       * goto labels. The compiler needs some statement to follow the label. */
      bool backIn;

      /* Jump into the iterator routine base on the iterator state. */
      switch ( itState ) {
            case Begin:              goto entryBegin;
            case ConsumeS1Range:     goto entryConsumeS1Range;
            case ConsumeS2Range:     goto entryConsumeS2Range;
            case OnlyInS1Range:      goto entryOnlyInS1Range;
            case OnlyInS2Range:      goto entryOnlyInS2Range;
            case S1SticksOut:        goto entryS1SticksOut;
            case S1SticksOutBreak:   goto entryS1SticksOutBreak;
            case S2SticksOut:        goto entryS2SticksOut;
            case S2SticksOutBreak:   goto entryS2SticksOutBreak;
            case S1DragsBehind:      goto entryS1DragsBehind;
            case S1DragsBehindBreak: goto entryS1DragsBehindBreak;
            case S2DragsBehind:      goto entryS2DragsBehind;
            case S2DragsBehindBreak: goto entryS2DragsBehindBreak;
            case ExactOverlap:       goto entryExactOverlap;
            case End:                goto entryEnd;
      }

entryBegin:
      /* Set up the next structs at the head of the transition lists. */
      s1Tel.set( state1->outList.head );
      s2Tel.set( state2->outList.head );

      /* Concurrently scan both out ranges. */
      while ( true ) {
            if ( s1Tel.trans == 0 ) {
                  /* We are at the end of state1's ranges. Process the rest of
                   * state2's ranges. */
                  while ( s2Tel.trans != 0 ) {
                        /* Range is only in s2. */
                        CO_RETURN2( ConsumeS2Range, RangeInS2 );
                        s2Tel.increment();
                  }
                  break;
            }
            else if ( s2Tel.trans == 0 ) {
                  /* We are at the end of state2's ranges. Process the rest of
                   * state1's ranges. */
                  while ( s1Tel.trans != 0 ) {
                        /* Range is only in s1. */
                        CO_RETURN2( ConsumeS1Range, RangeInS1 );
                        s1Tel.increment();
                  }
                  break;
            }
            /* Both state1's and state2's transition elements are good.
             * The signiture of no overlap is a back key being in front of a
             * front key. */
            else if ( keyOps->lt( s1Tel.highKey, s2Tel.lowKey ) ) {
                  /* A range exists in state1 that does not overlap with state2. */
                  CO_RETURN2( OnlyInS1Range, RangeInS1 );
                  s1Tel.increment();
            }
            else if ( keyOps->lt( s2Tel.highKey, s1Tel.lowKey ) ) {
                  /* A range exists in state2 that does not overlap with state1. */
                  CO_RETURN2( OnlyInS2Range, RangeInS2 );
                  s2Tel.increment();
            }
            /* There is overlap, must mix the ranges in some way. */
            else if ( keyOps->lt( s1Tel.lowKey, s2Tel.lowKey ) ) {
                  /* Range from state1 sticks out front. Must break it into
                   * non-overlaping and overlaping segments. */
                  bottomLow = s2Tel.lowKey;
                  bottomHigh = s1Tel.highKey;
                  s1Tel.highKey = s2Tel.lowKey;
                  keyOps->dec( s1Tel.highKey );
                  bottomTrans = s1Tel.trans;

                  if ( wantBreaks ) {
                        /* Notify the caller that we are breaking s1. This gives them a
                         * chance to duplicate s1Tel[0,1].value. */
                        CO_RETURN2( S1SticksOutBreak, BreakS1 );
                  }

                  /* Broken off range is only in s1. */
                  CO_RETURN2( S1SticksOut, RangeInS1 );

                  /* Advance over the part sticking out front. */
                  s1Tel.lowKey = bottomLow;
                  s1Tel.highKey = bottomHigh;
                  s1Tel.trans = bottomTrans;
            }
            else if ( keyOps->lt( s2Tel.lowKey, s1Tel.lowKey ) ) {
                  /* Range from state2 sticks out front. Must break it into
                   * non-overlaping and overlaping segments. */
                  bottomLow = s1Tel.lowKey;
                  bottomHigh = s2Tel.highKey;
                  s2Tel.highKey = s1Tel.lowKey;
                  keyOps->dec( s2Tel.highKey );
                  bottomTrans = s2Tel.trans;

                  if ( wantBreaks ) {
                        /* Notify the caller that we are breaking s2. This gives them a
                         * chance to duplicate s2Tel[0,1].value. */
                        CO_RETURN2( S2SticksOutBreak, BreakS2 );
                  }

                  /* Broken off range is only in s2. */
                  CO_RETURN2( S2SticksOut, RangeInS2 );

                  /* Advance over the part sticking out front. */
                  s2Tel.lowKey = bottomLow;
                  s2Tel.highKey = bottomHigh;
                  s2Tel.trans = bottomTrans;
            }
            /* Low ends are even. Are the high ends even? */
            else if ( keyOps->lt( s1Tel.highKey, s2Tel.highKey ) ) {
                  /* Range from state2 goes longer than the range from state1. We
                   * must break the range from state2 into an evenly overlaping
                   * segment. */
                  bottomLow = s1Tel.highKey;
                  keyOps->inc( bottomLow );
                  bottomHigh = s2Tel.highKey;
                  s2Tel.highKey = s1Tel.highKey;
                  bottomTrans = s2Tel.trans;

                  if ( wantBreaks ) {
                        /* Notify the caller that we are breaking s2. This gives them a
                         * chance to duplicate s2Tel[0,1].value. */
                        CO_RETURN2( S2DragsBehindBreak, BreakS2 );
                  }

                  /* Breaking s2 produces exact overlap. */
                  CO_RETURN2( S2DragsBehind, RangeOverlap );

                  /* Advance over the front we just broke off of range 2. */
                  s2Tel.lowKey = bottomLow;
                  s2Tel.highKey = bottomHigh;
                  s2Tel.trans = bottomTrans;

                  /* Advance over the entire s1Tel. We have consumed it. */
                  s1Tel.increment();
            }
            else if ( keyOps->lt( s2Tel.highKey, s1Tel.highKey ) ) {
                  /* Range from state1 goes longer than the range from state2. We
                   * must break the range from state1 into an evenly overlaping
                   * segment. */
                  bottomLow = s2Tel.highKey;
                  keyOps->inc( bottomLow );
                  bottomHigh = s1Tel.highKey;
                  s1Tel.highKey = s2Tel.highKey;
                  bottomTrans = s1Tel.trans;

                  if ( wantBreaks ) {
                        /* Notify the caller that we are breaking s1. This gives them a
                         * chance to duplicate s2Tel[0,1].value. */
                        CO_RETURN2( S1DragsBehindBreak, BreakS1 );
                  }

                  /* Breaking s1 produces exact overlap. */
                  CO_RETURN2( S1DragsBehind, RangeOverlap );

                  /* Advance over the front we just broke off of range 1. */
                  s1Tel.lowKey = bottomLow;
                  s1Tel.highKey = bottomHigh;
                  s1Tel.trans = bottomTrans;

                  /* Advance over the entire s2Tel. We have consumed it. */
                  s2Tel.increment();
            }
            else {
                  /* There is an exact overlap. */
                  CO_RETURN2( ExactOverlap, RangeOverlap );

                  s1Tel.increment();
                  s2Tel.increment();
            }
      }

      /* Done, go into end state. */
      CO_RETURN( End );
}

/*
 * Transition Comparison.
 */

/* Compare target partitions. Either pointer may be null. */
int FsmAp::comparePartPtr( TransAp *trans1, TransAp *trans2 )
{
      if ( trans1 != 0 ) {
            /* If trans1 is set then so should trans2. The initial partitioning
             * guarantees this for us. */
            if ( trans1->toState == 0 && trans2->toState != 0 )
                  return -1;
            else if ( trans1->toState != 0 && trans2->toState == 0 )
                  return 1;
            else if ( trans1->toState != 0 ) {
                  /* Both of targets are set. */
                  return CmpOrd< MinPartition* >::compare( 
                        trans1->toState->alg.partition, trans2->toState->alg.partition );
            }
      }
      return 0;
}


/* Compares two transition pointers according to priority and functions.
 * Either pointer may be null. Does not consider to state or from state. */
int FsmAp::compareDataPtr( TransAp *trans1, TransAp *trans2 )
{
      if ( trans1 == 0 && trans2 != 0 )
            return -1;
      else if ( trans1 != 0 && trans2 == 0 )
            return 1;
      else if ( trans1 != 0 ) {
            /* Both of the transition pointers are set. */
            int compareRes = compareTransData( trans1, trans2 );
            if ( compareRes != 0 )
                  return compareRes;
      }
      return 0;
}

/* Compares two transitions according to target state, priority and functions.
 * Does not consider from state. Either of the pointers may be null. */
int FsmAp::compareFullPtr( TransAp *trans1, TransAp *trans2 )
{
      if ( (trans1 != 0) ^ (trans2 != 0) ) {
            /* Exactly one of the transitions is set. */
            if ( trans1 != 0 )
                  return -1;
            else
                  return 1;
      }
      else if ( trans1 != 0 ) {
            /* Both of the transition pointers are set. Test target state,
             * priority and funcs. */
            if ( trans1->toState < trans2->toState )
                  return -1;
            else if ( trans1->toState > trans2->toState )
                  return 1;
            else if ( trans1->toState != 0 ) {
                  /* Test transition data. */
                  int compareRes = compareTransData( trans1, trans2 );
                  if ( compareRes != 0 )
                        return compareRes;
            }
      }
      return 0;
}


bool FsmAp::shouldMarkPtr( MarkIndex &markIndex, TransAp *trans1, 
                        TransAp *trans2 )
{
      if ( (trans1 != 0) ^ (trans2 != 0) ) {
            /* Exactly one of the transitions is set. The initial mark round
             * should rule out this case. */
            assert( false );
      }
      else if ( trans1 != 0 ) {
            /* Both of the transitions are set. If the target pair is marked, then
             * the pair we are considering gets marked. */
            return markIndex.isPairMarked( trans1->toState->alg.stateNum, 
                        trans2->toState->alg.stateNum );
      }

      /* Neither of the transitiosn are set. */
      return false;
}



Generated by  Doxygen 1.6.0   Back to index