Browse Prior Art Database

C++ Data Structures to Support Finite State Machine

IP.com Disclosure Number: IPCOM000117102D
Original Publication Date: 1995-Dec-01
Included in the Prior Art Database: 2005-Mar-31
Document File: 8 page(s) / 280K

Publishing Venue

IBM

Related People

Dickson, DW: AUTHOR [+4]

Abstract

A Finite State Machine (FSM) alters its state in accordance with its State Transition Table (STT) in response to received events. The Moore state mode, as used by the Shlaer Mellor Object Oriented Analysis (OOA) methodology, demands that an action is executed when a new state is entered. In order to implement this in C++, data structures are required which efficiently hold the STT information and support a means of locating the appropriate action function.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 22% of the total text.

C++ Data Structures to Support Finite State Machine

      A Finite State Machine (FSM) alters its state in accordance
with its State Transition Table (STT) in response to received events.
The Moore state mode, as used by the Shlaer Mellor Object Oriented
Analysis (OOA) methodology, demands that an action is executed when a
new state is entered.  In order to implement this in C++, data
structures are required which efficiently hold the STT information
and support a means of locating the appropriate action function.

      Disclosed is a design which uses C++ statements to create, at
compile time, the required data structures with the required STT
information loaded.  The design takes into consideration the
efficiency of searching the data structures.  Also disclosed are C++
structures for traversing the data structures supporting the STT, and
a C++ function for calling the relating action function.

      In the Shlaer Mellow OOA Methodology, an active object is one
that undergoes state changes.  Its behavior is described by an FSM,
and valid state transitions of the FSM are defined in an STT.

      A particular class of active object, of which there may be any
number of instances, will use a particular STT.  Therefore, there is
only one STT needed per class, no matter how many instances there
are.  The STT, therefore, is class data.

      An STT is a tabular representation of a State Transition
Diagram (STD), an example of which is shown in Fig. 1.

      In an STD, the boxes represent states and the labelled arrows
represent allowed state transitions.  The labels on the arrows
identify the events which cause the state transitions.

      In an STT, the cells are at intersections of states and events.
Where, for a given state there is a valid event, the corresponding
cell contains a number or name identifying the new state to
transition
to (Fig. 2).

      The basic data structures that are used to represent an STT are
shown in Fig. 3, and are:
  1.  The Event-State Vector Index (ESVI).  This is an array of
       pointers indexed by state.  Each pointer points to an Event-
       State Vector (see below).
  2.  The Event-State Vectors (ESVs).  These are linked lists of ESV
       entries.
  3.  The Action Vector (AV).  This is an array of pointers indexed
by
       state.  Each pointer points to a C++ function which performs
the
       action appropriate to entering the indexed state.

      The ESVI is chosen to be represented by an array because there
are a finite number of states identified by a contiguous set of
integers.  Each array entry can, therefore, be directly indexed by
using its related state number.  The AV is chosen to be represented
by an array for the same reason.

Note: State is the major discriminator.

      The ESVs are chosen to be represented by linked lists because,
for each state, there is normally only a small subset of valid...