|
Finite-state machines occur all over the place. A reusable base class can capture code that's common to many FSM applications.
February 01, 1998
URL:http://www.drdobbs.com/object-oriented-finite-state-machines/184403458
Finite-state machines occur all over the place. A reusable base class can capture code that's common to many FSM applications.
We present an object-oriented, yet simple and practical, implementation of a finite-state machine (FSM). We designed it as a plug-in component, ready to use and adaptable to a particular application by altering just one derived class.
FSM is a modelling concept used in such varied technical fields as telecommunications protocols, telephone calls processing, digital hardware design, virtual memory management in operating systems, and so forth [1]. But its software implementations tend to be complex and offer small code reuse. To achieve greater reuse here, we employed a bridge design pattern. The principal classes remain unchanged, while application-specific behavior is introduced through inheritance.
We developed this implementation as a part of an OSI communications stack software package. We have reused it successfully in call-processing software based on Dialogic voice processing boards. It is portable across various operating systems. Since it does not use very recent C++ features, it should compile with any standard C++ compiler.
An FSM implementation tends to be complex, with little opportunity for reuse, because it is so intimately entwined with application-specific behavior. To make matters worse, a classic FSM implementation is often sprinkled throughout the program, making it difficult to find a clear boundary between the functionality of the application and the FSM itself. A programmer who inherits this kind of program and has to modify the FSM behaviour — to add new transitions, for example — faces two options:
1) To dig through existing code and figure out how it works.
2) To rewrite it from scratch.
The second alternative is particularly tempting if a design is too complex, with a lot of states, events, and transitions.
By contrast, maintenance is quite easy with our approach. The FSM core is placed in the initialization part of a main function. You specify the FSM here and then just call one control function to process an event. We needed the FSM core in the form of an object-oriented software component for several applications based on the OSI protocol state machines. The result of our effort was a plug-in component, usable in different applications.
It is a simple and practical implementation. The FSM has states, events, and transitions. When an event is received in a source state, a transition is triggered and a set of associated actions is executed. The FSM then passes to the destination state, or remains in the current one and waits for another event.
We avoid the use of switch statements. We feel they obscure the flow of program execution and make debugging more difficult. At the same time, we paid careful attention to run-time efficiency and small size, as we use the FSM code often in real-time systems. And, of course, we strove for portability across different operating systems and C++ compilers.
The design of the FSM is based on a bridge design pattern [2]. A client class FSM contains a reference to an abstract server class ABSEventHandler and invokes its methods. The FSM class is completely independent of the server class implementation, thus is reusable in different contexts.
Listings 1 and 2 show these classes in their entirety. The FSM class keeps a private table (myptrArrayTrans) of transitions, where each element is basically a pointer to a TransitionType object. The structure TransitionType is nested in the FSM class and is defined as:
typedef struct
{
int source_state;
int destination_state;
int event;
int index;
} TransitionType;
This table is filled in by successive calls to a defineTransition member function when you encode the machine's behavior. Its size is determined by a private member myMaxNumTransitions. In addition, the FSM class contains another interesting private member, myCurrentState, which holds the current state. It also maintains a queue object needed to store received events.
The last private member is myptrHandler, a pointer to an object of a type derived from ABSEventHandler, as mentioned above. Given this pointer, an FSM object invokes an event handler, stored as a function pointer in an ABSEventHandler array functions.
We supply a very small public interface — only three functions besides a constructor are needed to manipulate the automaton. The constructor expects three arguments:
The cornerstone of this class is the defineTransition method, which lets you to give shape to your FSM. You define a particular transition, passing it a source state, a destination state (which may be the same as the source), the event id that triggers the transition, and a corresponding event handler index:
int FSM::defineTransition(
int inSourceState,
int inDestinationState,
int inEvent,
int inIndex )
{
int index;
// Search free position in the table of transitions
index = hash(inSourceState, inEvent);
if ( index != -1 )
{
myptrArrayTrans[index].source_state =
inSourceState;
myptrArrayTrans[index].destination_state =
inDestinationState;
myptrArrayTrans[index].event = inEvent;
myptrArrayTrans[index].index = inIndex;
}
return index;
}
Notice that a free position is located through an efficient hash method. If it is found, input parameters are mapped into a TransitionType structure members, otherwise the error value -1 is returned, indicating that the table is full.
During program execution you just call the method control, which looks up the user-defined event handler according to the event id and the current state. Next, the found event handler executes actions associated with a transition. No more nested switch statements, no more chains of case labels. Moreover, you can pass an arbitrary parameter that you can process in the event handler function. In our optimized implementation there is only one table lookup based on hash techniques. We also found a generateEvent method to be useful under some circumstances. For instance, we used it to generate an internal error event for missing transitions.
The constructor for ABSEventHandler takes a parameter indicating the size of an array of pointers to event handlers. Each element of this array stores a pointer to a function which handles a particular event. You need to define the method FillHandlersArray in a derived class to fill in this array. It is a pure virtual function. The abstract base class ABSEventHandler does not know how to do it, of course, so it delegates this task to a derived application-specific class.
Figure 1 shows the object model of the FSM framework presented here, together with a derived class Filter_EventHandler used in an example. We have used the Object Modeling Technique (OMT) developed by James Rumbaugh and others[3] to set up our analysis and design.
Now let's look at the steps you must follow to use the framework:
1) Define all states and events needed for your application as an enumeration. Add indexes that will correspond to event handlers as shown in Listing 3. We defined this stuff together with a derived class Filter_EventHandler in separate files.
2) Derive a class from the abstract server class ABSEventHandler and define the pure virtual function FillHandlersArray of class ABSEventHandler. The purpose of FillHandlersArray is to fill in the array of pointers to event-handler functions. Define event-handler functions as member functions of a derived class for all events that need to be handled. You might need to define one event handler for each transition, or only a few handlers might do.
3) You still need to initialize the FSM with all possible transitions. As mentioned previously, this task is accomplished by succesive calls to defineTransition, passing it the source state, the destination state, the expected event, and the index in the array of event handlers. You will normally place this initialization somewhere in the beginning of a program.
4) Invoke the method control of the client class FSM upon reception of each event, passing it an event identifier and its associated parameters.
Listing 4 shows a C/C++ comment-filtering program that demonstrates how the framework is used. It takes two file names as command-line arguments, reads a C or C++ source file from the standard input stream, discards comments, and writes the rest of the input file to the output file. We left out error handling to keep the example as simple as possible.
Following the cook-book code, we define first events, states, and indexes. We could have used a series of macros, but standard C enumerations are far superior. For example, we defined the following enumeration for states:
enum Filter_states
{
VALID = 0,
WAIT_COMMENT,
GARBAGE1,
GARBAGE2,
WAIT_END_COMMENT
};
Five states will do. An initial state is VALID, where each character read from the input file is written to the output file. Reception of a slash character puts the machine into the WAIT_COMMENT state. From here it is possible to make a transition back to the VALID state, or go on to the GARBAGE1 and GARBAGE2 states. GARBAGE1 corresponds to the inside of a C++ comment, and GARBAGE2 to the inside of a C comment.
Inside comments, characters are thrown away until the end of comment is found, which can be a newline character for a C++ comment, or an asterisk followed by a slash character for a C style comment, respectively. In the case of a C comment, the intermediate state WAIT_END_COMMENT is necessary to get back to the VALID state.
Figure 2 shows a complete dynamic model of the C/C++ comment filtering application.
In the second step, we derived a Filter_EventHandler class from abstract ABSEventHandler class and encapsulated file handling inside this class for the sake of simplicity. You would normally put system resources into a separate class. The derived class would contain just a reference to it, as shown in Figure 1. The main function first instantiates this class, passing it a maximal number of transitions and file names as parameters. The Filter_EventHandler constructor fills in the array of event-handler functionss and opens the files:
Filter_EventHandler::Filter_EventHandler(
int inNumberTransitions,
char* inputFile,
char* outputFile )
: ABSEventHandler(inNumberTransitions)
{
// Call this function from the constructor
FillHandlersArray();
// Open input and output file
...
}
A Filter_EventHandler pointer is passed to the FSM constructor, along with the maximum number of transitions and an initial state. The next step is to define the FSM's behaviour. This is the crucial part of the program, because we model our filtering machine primarily by means of a set of defineTransition calls. If you detect some missing transition, you just add a new defineTransition call for that event.
There is the potential danger of an infinite loop, if the machine receives an event that has no defined handler. The FSM then generates an internal error event. The application should define an internal error handler to gracefully handle this situation. So if you cannot figure out all transitions, add one internal error transition for each state. We added only one, by way of illustration — a transition for the state GARBAGE1.
Now that we have defined a filter machine, the rest is easy. A while loop reads each character from the source file, converts it to an event, and calls control, passing it the event and read character. The event handlers writeChar and writeSlash use a cast from void* to int* to get a character and write it to the output file. If some error occurs, control returns false and the loop is terminated. The Filter_EventHandler destructor takes care of cleaning up and releasing resources.
The complete listing, together with an example is available electronically. See p. 3 for details.
We ended up with a simple plug-in FSM component that is portable across many platforms and is optimized for execution speed. Getting rid of ugly looking nested switch statements greatly improves the design of state-machine based programs. The basic component relies on a third-party list class to implement the event queue. You can use any commercial list implementation, or the STL queue template.
We initially developed this implementation on several flavors of UNIX (HP-UX V9.05, V10.10, Sun Solaris V2.3, Linux V1.2.13), then ported it to Windows NT V4.0 (Borland C++ V5.0 and Microsoft Visual C++ V4.1).
[1] Aamod Sane. Object-Oriented State Machines: Subclassing, Composition, Delegation, and Genericity. University of Illinois at Urbana-Champaign Department of Computer Science. 1994.
[2] Robert C. Martin. Designing Object-Oriented C++ Applications Using the Booch Method (Prentice Hall, Englewood Cliffs, NJ, 1995).
[3] James Rumbaugh. "OMT: The object model." Journal of Object Oriented Programming, January 1995.
Frantisek Kaduch was a software engineer with Marben, a company based in Madrid, Spain, specializing in OSI software. He has a degree in Electronic Engineering from Slovak Technical University, Slovakia. He has been developing telecommunications software for the past four years using C++ and object-oriented design. He is now working for Qualcomm, San Diego, and may be reached at [email protected].
Damian Jan is an OSI and TMN consultant. A former Marben employee, he now runs his own company, DEJ Consulting, based in Madrid, Spain and Vancouver, Canada. He has a degree in physics from UNCPBA University, Argentina, and has been involved in many telecommunications projects. He can be reached at [email protected].
Purificacion Vidal works for Kilowatt S.A., a Madrid, Spain based company, specializing in cellular telephony and CTI. She holds a Technical Engineer degree in Computer Science from the Polytechnic University of Madrid, Spain. She specializes in cellular telephony measurement systems software using OO architecture. She can be reached at [email protected].
//----------- FSM declaration ------------
#include "ABS_eventhandler.h"
#include "list.h"
typedef struct StructEvent
{
// event identifier
int Id;
// event parameters
void *parameters;
} STRUCT_EVENT;
Makelista(STRUCT_EVENT);
class FSM
{
private :
typedef struct
{
int source_state;
int destination_state;
int event;
int index;
} TransitionType;
TransitionType* myptrArrayTrans; // a pointer to the
// array of transitions
int myMaxNumTransitions; // max transitions supported
int myCurrentState; // current state of the FSM
// an event queue
STRUCT_EVENTlista myList;
ABSEventHandler* myptrHandler; // a pointer to the
// abstract server class
void insertInQueue(int inEvent, void *inParameters );
// Search using hash functions
int hash(int inSourceState, int inEvent);
int hash(int inEvent);
public :
// Constructor
FSM(ABSEventHandler *inTrans, int inMaxNumTransitions,
int inInitialState );
// Destructor
~FSM( void );
void defineTransition(int inSourceState, int inDestinationState,
int inEvent, int inIndex);
int control(int inEvent, void *inParameters = NULL );
void generateEvent(int inEvent, void *inParameters = NULL );
};
//----------- FSM definition ------------
#include <memory.h>
#include <stdlib.h>
#include "FSM.h"
FSM::FSM(ABSEventHandler *inTrans, int inMaxNumTransitions,
int inInitialState)
{
myptrHandler = inTrans;
// Initialize the maximal number of transitions
myMaxNumTransitions = inMaxNumTransitions;
// Initialize the current state
myCurrentState = inInitialState;
// Initialize the array of transitions
myptrArrayTrans = 0;
myptrArrayTrans = new TransitionType[myMaxNumTransitions];
memset(myptrArrayTrans, -1,
myMaxNumTransitions * sizeof(TransitionType));
}
FSM::~FSM()
{
if ( myptrArrayTrans )
delete []myptrArrayTrans;
}
void FSM::insertInQueue(int inEvent, void *inParametros)
// not shown
int FSM::hash(int inSourceState, int inEvent)
{
int i = 0;
int where = ((inEvent << 8) + inSourceState) % myMaxNumTransitions;
// Look for the first available position
while((myptrArrayTrans[(where + i)%myMaxNumTransitions].index != -1)
&& (i < myMaxNumTransitions))
i++;
// Return negative value if the table is full
if ( i >= myMaxNumTransitions )
return -1;
else // Return free position?s index
return ((where + i) % myMaxNumTransitions);
}
int FSM::hash( int inEvent )
{
int i = 0;
int where = ((inEvent << 8) + myCurrentState) % myMaxNumTransitions;
// rest the same as above
}
int FSM::defineTransition(int inSourceState, int inDestinationState,
int inEvent, int inIndex)
{
int index;
// Search free position in the table of transitions
index = hash(inSourceState, inEvent);
if ( index != -1 )
{
myptrArrayTrans[index].source_state = inSourceState;
myptrArrayTrans[index].destination_state = inDestinationState;
myptrArrayTrans[index].event = inEvent;
myptrArrayTrans[index].index = inIndex;
}
return index;
}
int FSM::control( int inEvent, void *inParametros )
{
int result = FALSE;
int trans_num;
StructEvent* anEvent = NULL;
// Insert the received event in the queue
insertInQueue(inEvent, inParametros);
anEvent = myList.first();
while ( anEvent )
{
// check if it is valid transition
if ((trans_num = hash(anEvent->Id)) >= 0)
{
if (myptrArrayTrans[trans_num].index == -1)
{
// Missing transition - generate an internal error event
generateEvent(INTERNAL_ERROR);
}
else
{
// Execute an event handler
result = (myptrHandler->*myptrHandler->
functions[myptrArrayTrans[trans_num].index])
(anEvent->parameters);
// Change the FSM's state
myCurrentState =
myptrArrayTrans[trans_num].destination_state;
}
}
// Missing transition - generate an internal error event
else
{
generateEvent(INTERNAL_ERROR);
}
// Remove the processed event
myList.remove(anEvent);
// pull the next event
// from the queue
anEvent = myList.next();
}
return result;
}
void FSM::generateEvent(int inEvent, void *inParametros )
{
insertInQueue(inEvent, inParametros);
}
//End of File
// Internal error event
#define INTERNAL_ERROR 0
// Boolean values definitions
#define FALSE 0
#define TRUE 1
typedef int Bool;
class ABSEventHandler;
// A typedef for a pointer to an event handler function
typedef Bool (ABSEventHandler::*FuncABSTransition )( void* );
class ABSEventHandler
{
friend class FSM;
public :
ABSEventHandler(int inNumberTransitions)
{functions = new FuncABSTransition[inNumberTransitions];}
virtual ~ABSEventHandler(void) {};
protected:
// A pointer to an array of event handler pointers
FuncABSTransition* functions;
// Pure virtual function to redefine in derived class
virtual void FillHandlersArray( void ) = 0;
};
//End of File
//--- Filter_eventhandler declaration ---
#include "ABS_eventhandler.h"
#include <stdio.h>
// Define list of possible states
enum Filter_states
{
VALID = 0,
WAIT_COMMENT,
GARBAGE1,
GARBAGE2,
WAIT_END_COMMENT
};
// Define list of possible events
enum Filter_events
{
SLASH ='/',
ASTERISK ='*',
NEWLINE ='\n',
OTHER
};
// Event handlers indexes
enum Handler_indexes
{
Ind_InternalError,
Ind_ignoreChar,
Ind_writeChar,
Ind_writeSlash
};
// A class derived from an abstract event handler class
class Filter_EventHandler : public ABSEventHandler
{
public :
// Constructor
Filter_EventHandler(int inNumberTransitions, char* inputFile,
char* outputFile );
// Destructor
~Filter_EventHandler( void );
// Get a character from the input file
int getCharacter();
private :
FILE* fi; // Input file handle
FILE* fo; // Output file handle
// Redefinition of the abstract base class's
// pure virtual function
void FillHandlersArray( void );
// Event handlers - make some actions
// associated with a transition
Bool handleInternalError( void* );
Bool ignoreChar( void* );
Bool writeChar( void* );
Bool writeSlash( void* );
};
//--- Filter_eventhandler definition ---
#include <stdio.h>
#include <stdlib.h>
#include <iostream.h>
#include "Filter_eventhandler.h"
Filter_EventHandler::Filter_EventHandler(int inNumberTransitions,
char* inputFile, char* outputFile )
: ABSEventHandler(inNumberTransitions)
{
// Call this function from the constructor
FillHandlersArray();
// Open input and output file -- not shown
}
Filter_EventHandler::getCharacter()
{
// read a character from the input file and return it
return fgetc(fi);
}
Filter_EventHandler::~Filter_EventHandler( void )
{
// Close the files
fclose(fi);
fclose(fo);
}
void Filter_EventHandler::FillHandlersArray( void )
{
functions[Ind_InternalError]
= (FuncABSTransition)
&Filter_EventHandler::handleInternalError;
functions[Ind_ignoreChar]
= (FuncABSTransition)
&Filter_EventHandler::ignoreChar;
functions[Ind_writeChar]
= (FuncABSTransition)
&Filter_EventHandler::writeChar;
functions[Ind_writeSlash]
= (FuncABSTransition)
&Filter_EventHandler::writeSlash;
}
Bool Filter_EventHandler::handleInternalError( void* )
{
cout << "Handle internal error." << endl;
return FALSE;
}
Bool Filter_EventHandler::ignoreChar( void* )
{
// do nothing
return TRUE;
}
Bool Filter_EventHandler::writeChar( void* inChar )
{
// Print a character into the output file
fputc(*(int *) inChar, fo);
return TRUE;
}
Bool Filter_EventHandler::writeSlash( void* inChar )
{
// Print a slash and a character into the output file
fputc(SLASH, fo);
fputc(*(int *) inChar, fo);
return TRUE;
}
//End of File
#include <stdio.h>
#include <iostream.h>
#include "FSM.h"
#include "Filter_eventhandler.h"
// Maximal number of transitions
const int MaxNumTransitions = 20;
int main( int argc, char *argv[] )
{
// Check the input arguments
// not shown
// Create an instance of a filter
// events handler (without error handling)
Filter_EventHandler *ptrHandler = 0;
ptrHandler = new Filter_EventHandler(MaxNumTransitions,
argv[1],
argv[2]);
// Create an instance of the FSM
FSM myFSM(ptrHandler, MaxNumTransitions, VALID);
// Define the FSM's transitions
myFSM.defineTransition(VALID, VALID, OTHER, Ind_writeChar);
myFSM.defineTransition(VALID, VALID, NEWLINE, Ind_writeChar);
myFSM.defineTransition(VALID, VALID, ASTERISK, Ind_writeChar);
myFSM.defineTransition(VALID, WAIT_COMMENT, SLASH, Ind_ignoreChar);
myFSM.defineTransition(WAIT_COMMENT, VALID, OTHER, Ind_writeSlash);
myFSM.defineTransition(WAIT_COMMENT, GARBAGE1, SLASH,
Ind_ignoreChar);
myFSM.defineTransition(GARBAGE1, VALID, INTERNAL_ERROR,
Ind_InternalError);
// not shown: the rest of
// the define Transition() calls
...
int char_read, event;
char_read = ptrHandler->getCharacter();
while (char_read != EOF)
{
// Convert a character into an event
switch (char_read)
{
case SLASH:
case ASTERISK:
case NEWLINE: event = char_read;
break;
default: event = OTHER;
}
// execute transition and
// associated actions
if (myFSM.control(event, (void *)&char_read) == FALSE)
break;
// Read a character from an input file
char_read = ptrHandler->getCharacter();
}
// Clean up ...
if ( ptrHandler )
delete ptrHandler;
return(0);
}
//End of File
Terms of Service | Privacy Statement | Copyright © 2024 UBM Tech, All rights reserved.