#include <FiniteStateAutomaton.hh>

Inheritance diagram for FiniteStateAutomaton:

Collaboration diagram for FiniteStateAutomaton:

Public Types
typedef int	FSAStateTransitionIndex
	Type used for indexing the transitions. More...

typedef int	FSAStateIndex
	Type used for indexing the states. More...

typedef std::set< FSAStateIndex >	FSAStateIndexSet
	Type for a set of state indices. More...

Public Member Functions
	FiniteStateAutomaton (FSAStateTransitionIndex defaultState=ILLEGAL_STATE, int transitionCount=0)

virtual	~FiniteStateAutomaton ()

virtual const std::string &	transitionName (FSAStateTransitionIndex transition) const

virtual std::string	stateName (FSAStateIndex state) const

virtual FSAStateTransitionIndex	transitionIndex (const std::string &transitionName) const

virtual FSAStateIndex	destinationState (FSAStateIndex source, FSAStateTransitionIndex transition)

virtual bool	isLegalTransition (FSAStateIndex source, FSAStateTransitionIndex transition)

virtual FSAStateIndex	addState ()

virtual FSAStateTransitionIndex	addTransitionType (const std::string &name)

virtual void	setTransitionName (FSAStateTransitionIndex transition, const std::string &name)

virtual void	setTransition (FSAStateIndex source, FSAStateIndex destination, FSAStateTransitionIndex transition)

virtual std::string	toDotString () const

virtual FSAStateIndex	startState () const

Static Public Attributes
static const FSAStateIndex	ILLEGAL_STATE = -1
	A state id which denotes an illegal state. More...

static const FSAStateIndex	UNKNOWN_STATE = -2
	A state id which denotes an unknown (unresolved) state. Used for lazy construction of states. More...

Protected Types
typedef std::vector< FSAStateIndex >	TransitionVector
	Vector which stores the target states of for each transition type. More...

typedef std::vector< TransitionVector >	TransitionMap
	Type for storing the transitions of each state. The vector stores for each state (indexed from 0) a vector with elements as many there are transitions. The value of the element is the target state to which the transition leads to, or ILLEGAL_STATE_INDEX if there is no transition for that transition type from that state. Using this structure it's possible to find the target state using two table (vector) lookups. More...

Protected Attributes
TransitionMap	transitions_
	The state transitions. In protected to allow fast access from derived classes. More...

Private Types
typedef std::map< std::string, FSAStateTransitionIndex >	TransitionNameIndex
	Type for finding the index for a transition using its name. More...

Private Attributes
int	stateCount_
	Count of states in the automaton. More...

int	transitionTypeCount_
	Count of different transition types in the automaton. More...

std::vector< std::string >	transitionNames_
	Names of the state transitions types (indexed from 0). More...

TransitionNameIndex	transitionIndices_
	Indices of the state transition types. More...

const FSAStateTransitionIndex	defaultState_
	The default target state for state transitions. More...

Friends
class	FSAFUResourceConflictDetector
	Friend due to highly optimized compiled simulation versions of the conflict detection functions. More...

Detailed Description

Generic finite state automaton (FSA).

This is a generic structure for FSA. The building and initialization of the states is the responsibility of derived classes.

Definition at line 49 of file FiniteStateAutomaton.hh.

Member Typedef Documentation

◆ FSAStateIndex

typedef int FiniteStateAutomaton::FSAStateIndex

Type used for indexing the states.

Definition at line 57 of file FiniteStateAutomaton.hh.

◆ FSAStateIndexSet

typedef std::set<FSAStateIndex> FiniteStateAutomaton::FSAStateIndexSet

Type for a set of state indices.

Definition at line 59 of file FiniteStateAutomaton.hh.

◆ FSAStateTransitionIndex

typedef int FiniteStateAutomaton::FSAStateTransitionIndex

Type used for indexing the transitions.

Definition at line 55 of file FiniteStateAutomaton.hh.

◆ TransitionMap

typedef std::vector<TransitionVector> FiniteStateAutomaton::TransitionMap

protected

Type for storing the transitions of each state. The vector stores for each state (indexed from 0) a vector with elements as many there are transitions. The value of the element is the target state to which the transition leads to, or ILLEGAL_STATE_INDEX if there is no transition for that transition type from that state. Using this structure it's possible to find the target state using two table (vector) lookups.

Definition at line 116 of file FiniteStateAutomaton.hh.

◆ TransitionNameIndex

typedef std::map<std::string, FSAStateTransitionIndex> FiniteStateAutomaton::TransitionNameIndex

private

Type for finding the index for a transition using its name.

Definition at line 126 of file FiniteStateAutomaton.hh.

◆ TransitionVector

typedef std::vector<FSAStateIndex> FiniteStateAutomaton::TransitionVector

protected

Vector which stores the target states of for each transition type.

Definition at line 107 of file FiniteStateAutomaton.hh.

Constructor & Destructor Documentation

◆ FiniteStateAutomaton()

FiniteStateAutomaton::FiniteStateAutomaton	(	FSAStateTransitionIndex	defaultState = `ILLEGAL_STATE`,
		int	transitionCount = `0`
	)

Constructor.

Parameters

defaultState	The default state for state transitions (either ILLEGAL_STATE or UNKNOWN_STATE, as no other states are known at this point).
transitionCount	The initial count of transitions.

Definition at line 55 of file FiniteStateAutomaton.cc.

                          : 
     stateCount_(0), 
     transitionTypeCount_(transitionCount), transitionNames_(transitionCount),
     defaultState_(defaultState) {
 }

◆ ~FiniteStateAutomaton()

FiniteStateAutomaton::~FiniteStateAutomaton ( )

virtual

Destructor.

Definition at line 66 of file FiniteStateAutomaton.cc.

                                             {
 #if 0
     Application::logStream() << stateCount_ << " states" << std::endl;
 #endif
 }

References Application::logStream(), and stateCount_.

Here is the call graph for this function:

Member Function Documentation

◆ addState()

FiniteStateAutomaton::FSAStateIndex FiniteStateAutomaton::addState ( )

virtual

Adds a new state to the automaton.

Returns: Returns the index of the new state. Indexing starts from 0.

Definition at line 178 of file FiniteStateAutomaton.cc.

                                {
     // add transition vector with no transitions for the new state
     transitions_.push_back(
         TransitionVector(transitionTypeCount_, defaultState_));
     return stateCount_++;
 }

References defaultState_, stateCount_, transitions_, and transitionTypeCount_.

Referenced by FUFiniteStateAutomaton::FUFiniteStateAutomaton(), and FUFiniteStateAutomaton::resolveState().

◆ addTransitionType()

FiniteStateAutomaton::FSAStateTransitionIndex FiniteStateAutomaton::addTransitionType ( const std::string & name )

virtual

Adds a new transition type to the automaton.

Parameters

name	Name of the transition type. Must be unique within all transition types.

Returns: Returns the index of the new transition type. Indexing starts from 0.

Definition at line 194 of file FiniteStateAutomaton.cc.

                                                              {    
  
     transitionNames_.push_back(name.c_str());
     transitionIndices_.insert(
         TransitionNameIndex::value_type(name, transitionTypeCount_));
  
     // increment the size of each state's transition vectors to
     // match the new count of transition types
     for (TransitionMap::iterator i = transitions_.begin(); 
          i != transitions_.end(); ++i) {
         TransitionVector& vec = *i;
         vec.resize(transitionTypeCount_ + 1, defaultState_);
     }
  
     return transitionTypeCount_++;
 }

References defaultState_, transitionIndices_, transitionNames_, transitions_, and transitionTypeCount_.

◆ destinationState()

FiniteStateAutomaton::FSAStateIndex FiniteStateAutomaton::destinationState	(	FSAStateIndex	source,
		FSAStateTransitionIndex	transition
	)

virtual

Returns the index of the state resulting from the given transition from the given source state.

This method is called often, thus should be as fast as possible. Therefore, all range checking etc. is disabled. Method is not const due to possibility of lazy initialization of states in derived classes.

Parameters

source	The source state.
transition	The transition.

Returns: The index of the destination state.

Reimplemented in FUFiniteStateAutomaton.

Definition at line 146 of file FiniteStateAutomaton.cc.

                                                               {
     return transitions_[source][transition];    
 }

References transitions_.

◆ isLegalTransition()

bool FiniteStateAutomaton::isLegalTransition	(	FSAStateIndex	source,
		FSAStateTransitionIndex	transition
	)

virtual

Returns true in case the given transition is legal (accepted by the state machine) from the given state.

This method is called often, thus should be as fast as possible. Therefore, all range checking etc. is disabled. Method is not const due to possibility of lazy initialization of states in derived classes.

Parameters

source	The source state.
transition	The transition.

Returns: True in case the transition is legal.

Reimplemented in FUFiniteStateAutomaton.

Definition at line 165 of file FiniteStateAutomaton.cc.

                                         {
     return transitions_[source][transition] != ILLEGAL_STATE;
 }

References ILLEGAL_STATE, and transitions_.

◆ setTransition()

void FiniteStateAutomaton::setTransition	(	FSAStateIndex	source,
		FSAStateIndex	destination,
		FSAStateTransitionIndex	transition
	)

virtual

Set a transition between two states.

Parameters

source	The source state.
destination	The destination state.
transition	The type of transition.

Definition at line 219 of file FiniteStateAutomaton.cc.

                                         {
  
     transitions_.at(source).at(transition) = destination;
 }

References transitions_.

Referenced by FUFiniteStateAutomaton::resolveState().

◆ setTransitionName()

void FiniteStateAutomaton::setTransitionName	(	FSAStateTransitionIndex	transition,
		const std::string &	name
	)

virtual

Sets a name for the given transition.

Parameters

transition	The index of the transition of which name to return.
name	The name of the transition.

Definition at line 93 of file FiniteStateAutomaton.cc.

                                                                {
     transitionNames_.at(transition) = name;
     transitionIndices_[name] = transition;
 }

References transitionIndices_, and transitionNames_.

Referenced by FUFiniteStateAutomaton::FUFiniteStateAutomaton().

◆ startState()

FiniteStateAutomaton::FSAStateIndex FiniteStateAutomaton::startState ( ) const

virtual

Returns the starting state of the automaton.

By default the starting state is assumed to be the state 0.

Returns: The starting state.

Definition at line 282 of file FiniteStateAutomaton.cc.

                                        {
     return 0;
 }

Referenced by FSAFUResourceConflictDetector::isIdle(), and FSAFUResourceConflictDetector::reset().

◆ stateName()

std::string FiniteStateAutomaton::stateName ( FSAStateIndex state ) const

virtual

Returns the textual description of the state at the given index.

Parameters

state The index of the state of which name to return.

Returns: The name of the state.

Reimplemented in FUFiniteStateAutomaton.

Definition at line 106 of file FiniteStateAutomaton.cc.

                                                          {
     return Conversion::toString(state);
 }

References Conversion::toString().

Referenced by toDotString().

Here is the call graph for this function:

◆ toDotString()

std::string FiniteStateAutomaton::toDotString ( ) const

virtual

Creates a string that represents the FSA as a graph in GraphViz dot format.

This string can be rendered to a visual graph using the 'dot' tool.

Returns: The FSA in dot graph format.

Definition at line 235 of file FiniteStateAutomaton.cc.

                                         {
  
     std::ostringstream s;
     s << "digraph G {" << std::endl;
  
     // first print all the states as nodes
     for (int i = 0; i < stateCount_; ++i) {
         s << "\tS" << i << " [label=\"S" << i << "\\n" << stateName(i) 
           << "\"]; " << std::endl;
     }
  
     // print transitions as edges
     for (int i = 0; i < stateCount_; ++i) {
         const TransitionVector& vec = transitions_.at(i);
         for (int t = 0; t < transitionTypeCount_; ++t) {
             std::string edgeLabel = transitionName(t);
             if (edgeLabel == "")
                 edgeLabel = "[NOP]";
             edgeLabel = edgeLabel + " (" + Conversion::toString(t) + ")";
             switch (vec.at(t)) {
             case ILLEGAL_STATE:
                 s << "\t/* No transition " << edgeLabel << " from S" << i 
                   << " possible */" << std::endl;
                 break;
             case UNKNOWN_STATE:
                 s << "\t/* Transition " << edgeLabel << " from S" << i 
                   << " not initialized yet */" << std::endl;
                 break;
             default:
                 s << "\tS" << i << " -> " << "S" << vec.at(t) << "[label=\""
                   << edgeLabel << "\"];" << std::endl;
                 break;
             }
         }
     }
     s << "}" << std::endl;   
     return s.str();    
 }

References ILLEGAL_STATE, stateCount_, stateName(), Conversion::toString(), transitionName(), transitions_, transitionTypeCount_, and UNKNOWN_STATE.

Referenced by FSAFUResourceConflictDetector::writeToDotFile().

Here is the call graph for this function:

◆ transitionIndex()

FiniteStateAutomaton::FSAStateTransitionIndex FiniteStateAutomaton::transitionIndex ( const std::string & transitionName ) const

virtual

Returns the index of the transition with given name.

Returns the transition index for an operation in case of an FU FSA.

Parameters

transitionName The name of the transition of index to return.

Returns: The index.

Exceptions

KeyNotFound In case no transition with given is found.

Definition at line 120 of file FiniteStateAutomaton.cc.

                                                                            {
     TransitionNameIndex::const_iterator i = 
         transitionIndices_.find(transitionName);
  
     if (i == transitionIndices_.end())
         throw KeyNotFound(
             __FILE__, __LINE__, __func__, 
             (boost::format("No transition '%s'") % transitionName).str());
  
     return (*i).second;
 }

References __func__, transitionIndices_, and transitionName().

Referenced by FUFiniteStateAutomaton::operationCollisionMatrix(), and FSAFUResourceConflictDetector::operationID().

Here is the call graph for this function:

◆ transitionName()

const std::string & FiniteStateAutomaton::transitionName ( FSAStateTransitionIndex transition ) const

virtual

Returns the textual description of the transition at the given index.

For example, returns the name of the operation in case of an FU FSA.

Parameters

transition The index of the transition of which name to return.

Returns: The name of the transition.

Definition at line 81 of file FiniteStateAutomaton.cc.

                                               {
     return transitionNames_.at(transition);
 }

References transitionNames_.

Referenced by FSAFUResourceConflictDetector::operationName(), toDotString(), and transitionIndex().

Friends And Related Function Documentation

◆ FSAFUResourceConflictDetector

friend class FSAFUResourceConflictDetector

friend

Friend due to highly optimized compiled simulation versions of the conflict detection functions.

Definition at line 53 of file FiniteStateAutomaton.hh.

Member Data Documentation

◆ defaultState_

const FSAStateTransitionIndex FiniteStateAutomaton::defaultState_

private

The default target state for state transitions.

Definition at line 136 of file FiniteStateAutomaton.hh.

Referenced by addState(), and addTransitionType().

◆ ILLEGAL_STATE

const FiniteStateAutomaton::FSAStateIndex FiniteStateAutomaton::ILLEGAL_STATE = -1

static

A state id which denotes an illegal state.

Definition at line 61 of file FiniteStateAutomaton.hh.

Referenced by FUFiniteStateAutomaton::buildStateMachine(), FUFiniteStateAutomaton::isLegalTransition(), isLegalTransition(), FSAFUResourceConflictDetector::issueOperationInline(), FSAFUResourceConflictDetector::issueOperationLazyInline(), FUFiniteStateAutomaton::resolveState(), and toDotString().

◆ stateCount_

int FiniteStateAutomaton::stateCount_

private

Count of states in the automaton.

Definition at line 128 of file FiniteStateAutomaton.hh.

Referenced by addState(), toDotString(), and ~FiniteStateAutomaton().

◆ transitionIndices_

TransitionNameIndex FiniteStateAutomaton::transitionIndices_

private

Indices of the state transition types.

Definition at line 134 of file FiniteStateAutomaton.hh.

Referenced by addTransitionType(), setTransitionName(), and transitionIndex().

◆ transitionNames_

std::vector<std::string> FiniteStateAutomaton::transitionNames_

private

Names of the state transitions types (indexed from 0).

Definition at line 132 of file FiniteStateAutomaton.hh.

Referenced by addTransitionType(), setTransitionName(), and transitionName().

◆ transitions_

TransitionMap FiniteStateAutomaton::transitions_

protected

The state transitions. In protected to allow fast access from derived classes.

Definition at line 120 of file FiniteStateAutomaton.hh.

Referenced by addState(), addTransitionType(), FSAFUResourceConflictDetector::advanceCycleLazyInline(), FUFiniteStateAutomaton::destinationState(), destinationState(), isLegalTransition(), FSAFUResourceConflictDetector::issueOperationInline(), FSAFUResourceConflictDetector::issueOperationLazyInline(), setTransition(), and toDotString().

◆ transitionTypeCount_

int FiniteStateAutomaton::transitionTypeCount_

private

Count of different transition types in the automaton.

Definition at line 130 of file FiniteStateAutomaton.hh.

Referenced by addState(), addTransitionType(), and toDotString().

◆ UNKNOWN_STATE

const FiniteStateAutomaton::FSAStateIndex FiniteStateAutomaton::UNKNOWN_STATE = -2

static

A state id which denotes an unknown (unresolved) state. Used for lazy construction of states.

Definition at line 64 of file FiniteStateAutomaton.hh.

Referenced by FSAFUResourceConflictDetector::advanceCycleLazyInline(), FUFiniteStateAutomaton::destinationState(), FSAFUResourceConflictDetector::issueOperationLazyInline(), and toDotString().

The documentation for this class was generated from the following files:

Public Types

Public Member Functions

Static Public Attributes

Protected Types

Protected Attributes

Private Types

Private Attributes

Friends

Detailed Description

Member Typedef Documentation

◆ FSAStateIndex

◆ FSAStateIndexSet

◆ FSAStateTransitionIndex

◆ TransitionMap

◆ TransitionNameIndex

◆ TransitionVector

Constructor & Destructor Documentation

◆ FiniteStateAutomaton()

◆ ~FiniteStateAutomaton()

Member Function Documentation

◆ addState()

◆ addTransitionType()

◆ destinationState()

◆ isLegalTransition()

◆ setTransition()

◆ setTransitionName()

◆ startState()

◆ stateName()

◆ toDotString()

◆ transitionIndex()

◆ transitionName()

Friends And Related Function Documentation

◆ FSAFUResourceConflictDetector

Member Data Documentation

◆ defaultState_

◆ ILLEGAL_STATE

◆ stateCount_

◆ transitionIndices_

◆ transitionNames_

◆ transitions_

◆ transitionTypeCount_

◆ UNKNOWN_STATE