2019/8/10 State Machine Design in C - CodeProject

14,260,254 members Sign in

Search for articles, questions, tips

articles Q&A forums stuff lounge ?

State Machine Design in C

David Lafreniere Rate this: 4.98 (19 votes)
2 Feb 2019 CPOL

A compact C finite state machine (FSM) implementation that's easy to use on embedded and PC-based systems.

Download C_StateMachine.zip - 55.3 KB

Introduction
In 2000, I wrote an article entitled "State Machine Design in C++" for C/C++ Users Journal (R.I.P.). Interestingly, that old article is still
available and (at the time of writing this article) the #1 hit on Google when searching for C++ state machine. The article was written
over 15 years ago, but I continue to use the basic idea on numerous projects. It's compact, easy to understand and, in most cases,
has just enough features to accomplish what I need.

Sometimes C is the right tool for the job. This article provides an alternate C language state machine implementation based on the
ideas presented within the article “State Machine Design in C++”. The design is suitable for any platform, embedded or PC, with any
C compiler. This state machine has the following features:

C language – state machine written in C

Compact – consumes a minimum amount of resources.
Objects – support multiple instantiations of a single state machine type.
Transition tables – transition tables precisely control state transition behavior.
Events – every event is a simple function with any argument types.
State action – every state action is a separate function with a single, unique event data argument if desired.
Guards/entry/exit actions – optionally a state machine can use guard conditions and separate entry/exit action functions
for each state.
Macros – optional multiline macro support simplifies usage by automating the code "machinery".
Error checking – compile time and runtime checks catch mistakes early.
Thread-safe – adding software locks to make the code thread-safe is easy.

The article is not a tutorial on the best design decomposition practices for software state machines. I'll be focusing on state machine
code and simple examples with just enough complexity to facilitate understanding the features and usage.

Background
A common design technique in the repertoire of most programmers is the venerable finite state machine (FSM). Designers use this
programming construct to break complex problems into manageable states and state transitions. There are innumerable ways to
implement a state machine.

https://www.codeproject.com/Articles/1275479/State-Machine-Design-in-C 1/17
2019/8/10 State Machine Design in C - CodeProject

A switch statement provides one of the easiest to implement and most common version of a state machine. Here, each case within
the switch statement becomes a state, implemented something like:

Hide   Copy Code

switch (currentState) {
case ST_IDLE:
// do something in the idle state
break;

case ST_STOP:
// do something in the stop state
break;

// etc...
}

This method is certainly appropriate for solving many different design problems. When employed on an event driven, multithreaded
project, however, state machines of this form can be quite limiting.

The first problem revolves around controlling what state transitions are valid and which ones are invalid. There is no way to enforce
the state transition rules. Any transition is allowed at any time, which is not particularly desirable. For most designs, only a few
transition patterns are valid. Ideally, the software design should enforce these predefined state sequences and prevent the
unwanted transitions. Another problem arises when trying to send data to a specific state. Since the entire state machine is located
within a single function, sending additional data to any given state proves difficult. And lastly these designs are rarely suitable for
use in a multithreaded system. The designer must ensure the state machine is called from a single thread of control.

Why use a state machine?

Implementing code using a state machine is an extremely handy design technique for solving complex engineering problems. State
machines break down the design into a series of steps, or what are called states in state-machine lingo. Each state performs some
narrowly defined task. Events, on the other hand, are the stimuli, which cause the state machine to move, or transition, between
states.

To take a simple example, which I will use throughout this article, let's say we are designing motor-control software. We want to
start and stop the motor, as well as change the motor's speed. Simple enough. The motor control events to be exposed to the client
software will be as follows:

1. Set Speed – sets the motor going at a specific speed.

2. Halt – stops the motor.

These events provide the ability to start the motor at whatever speed desired, which also implies changing the speed of an already
moving motor. Or we can stop the motor altogether. To the motor-control module, these two events, or functions, are considered
external events. To a client using our code, however, these are just plain functions.

These events are not state machine states. The steps required to handle these two events are different. In this case the states are:

1. Idle — the motor is not spinning but is at rest

Do nothing

2. Start — starts the motor from a dead stop

Turn on motor power

Set motor speed

3. Change Speed — adjust the speed of an already moving motor

Change motor speed

4. Stop — stop a moving motor

Turn off motor power

Go to the Idle state

As can be seen, breaking the motor control into discreet states, as opposed to having one monolithic function, we can more easily
manage the rules of how to operate the motor.

https://www.codeproject.com/Articles/1275479/State-Machine-Design-in-C 2/17
2019/8/10 State Machine Design in C - CodeProject

Every state machine has the concept of a "current state." This is the state the state machine currently occupies. At any given
moment in time, the state machine can be in only a single state. Every instance of a particular state machine instance can set the
initial state when defined. That initial state, however, does not execute during object creation. Only an event sent to the state
machine causes a state function to execute.

To graphically illustrate the states and events, we use a state diagram. Figure 1 below shows the state transitions for the motor
control module. A box denotes a state and a connecting arrow indicates the event transitions. Arrows with the event name listed are
external events, whereas unadorned lines are considered internal events. (I cover the differences between internal and external
events later in the article.)

Figure 1: Motor state diagram

As you can see, when an event comes in the state transition that occurs depends on state machine's current state. When a SetSpeed
event comes in, for instance, and the motor is in the Idle state, it transitions to the Start state. However, that same SetSpeed event
generated while the current state is Start transitions the motor to the ChangeSpeed state. You can also see that not all state
transitions are valid. For instance, the motor can't transition from ChangeSpeed to Idle without first going through the Stop state.

In short, using a state machine captures and enforces complex interactions, which might otherwise be difficult to convey and
implement.

Internal and external events

As I mentioned earlier, an event is the stimulus that causes a state machine to transition between states. For instance, a button press
could be an event. Events can be broken out into two categories: external and internal. The external event, at its most basic level, is
a function call into a state-machine module. These functions are public and are called from the outside or from code external to the
state-machine object. Any thread or task within a system can generate an external event. If the external event function call causes a
state transition to occur, the state will execute synchronously within the caller's thread of control. An internal event, on the other
hand, is self-generated by the state machine itself during state execution.

A typical scenario consists of an external event being generated, which, again, boils down to a function call into the module's public
interface. Based upon the event being generated and the state machine's current state, a lookup is performed to determine if a
transition is required. If so, the state machine transitions to the new state and the code for that state executes. At the end of the
state function, a check is performed to determine whether an internal event was generated. If so, another transition is performed
and the new state gets a chance to execute. This process continues until the state machine is no longer generating internal events,
at which time the original external event function call returns. The external event and all internal events, if any, execute within the
caller's thread of control.

Once the external event starts the state machine executing, it cannot be interrupted by another external event until the external
event and all internal events have completed execution if locks are used. This run to completion model provides a multithread-safe
environment for the state transitions. Semaphores or mutexes can be used in the state machine engine to block other threads that
https://www.codeproject.com/Articles/1275479/State-Machine-Design-in-C 3/17
2019/8/10 State Machine Design in C - CodeProject

might be trying to be simultaneously access the same state machine instance. See source code function
_SM_ExternalEvent() comments for where the locks go.

Event data
When an event is generated, it can optionally attach event data to be used by the state function during execution. Event data is a
single const or non-const pointer to any built-in or user-defined data type.

Once the state has completed execution, the event data is considered used up and must be deleted. Therefore, any event data sent
to a state machine must be dynamically created via SM_XAlloc().  The state machine engine automatically frees allocated event
data using SM_XFree().

State transitions
When an external event is generated, a lookup is performed to determine the state transition course of action. There are three
possible outcomes to an event: new state, event ignored, or cannot happen. A new state causes a transition to a new state where it
is allowed to execute. Transitions to the existing state are also possible, which means the current state is re-executed. For an ignored
event, no state executes. However, the event data, if any, is deleted. The last possibility, cannot happen, is reserved for situations
where the event is not valid given the current state of the state machine. If this occurs, the software faults.

In this implementation, internal events are not required to perform a validating transition lookup. The state transition is assumed to
be valid. You could check for both valid internal and external event transitions, but in practice, this just takes more storage space
and generates busywork for very little benefit. The real need for validating transitions lies in the asynchronous, external events
where a client can cause an event to occur at an inappropriate time. Once the state machine is executing, it cannot be interrupted. It
is under the control of the private implementation, thereby making transition checks unnecessary. This gives the designer the
freedom to change states, via internal events, without the burden of updating transition tables.

StateMachine module
The state machine source code is contained within the StateMachine.c and StateMachine.h files. The code below shows the partial
header. The StateMachine header contains various preprocessor multiline macros to ease implementation of a state machine.

Hide   Shrink   Copy Code

enum { EVENT_IGNORED = 0xFE, CANNOT_HAPPEN = 0xFF };

typedef void NoEventData;

// State machine constant data

typedef struct
{
const CHAR* name;
const BYTE maxStates;
const struct SM_StateStruct* stateMap;
const struct SM_StateStructEx* stateMapEx;
} SM_StateMachineConst;

// State machine instance data

typedef struct
{
const CHAR* name;
void* pInstance;
BYTE newState;
BYTE currentState;
BOOL eventGenerated;
void* pEventData;
} SM_StateMachine;

// Generic state function signatures

typedef void (*SM_StateFunc)(SM_StateMachine* self, void* pEventData);
typedef BOOL (*SM_GuardFunc)(SM_StateMachine* self, void* pEventData);

https://www.codeproject.com/Articles/1275479/State-Machine-Design-in-C 4/17
2019/8/10 State Machine Design in C - CodeProject

typedef void (*SM_EntryFunc)(SM_StateMachine* self, void* pEventData);

typedef void (*SM_ExitFunc)(SM_StateMachine* self);

typedef struct SM_StateStruct

{
SM_StateFunc pStateFunc;
} SM_StateStruct;

typedef struct SM_StateStructEx

{
SM_StateFunc pStateFunc;
SM_GuardFunc pGuardFunc;
SM_EntryFunc pEntryFunc;
SM_ExitFunc pExitFunc;
} SM_StateStructEx;

// Public functions
#define SM_Event(_smName_, _eventFunc_, _eventData_) \
_eventFunc_(&_smName_##Obj, _eventData_)

// Protected functions
#define SM_InternalEvent(_newState_, _eventData_) \
_SM_InternalEvent(self, _newState_, _eventData_)
#define SM_GetInstance(_instance_) \
(_instance_*)(self->pInstance);

// Private functions
void _SM_ExternalEvent(SM_StateMachine* self, const SM_StateMachineConst* selfConst, BYTE
newState, void* pEventData);
void _SM_InternalEvent(SM_StateMachine* self, BYTE newState, void* pEventData);
void _SM_StateEngine(SM_StateMachine* self, const SM_StateMachineConst* selfConst);
void _SM_StateEngineEx(SM_StateMachine* self, const SM_StateMachineConst* selfConst);

#define SM_DECLARE(_smName_) \
extern SM_StateMachine _smName_##Obj;

#define SM_DEFINE(_smName_, _instance_) \

SM_StateMachine _smName_##Obj = { #_smName_, _instance_, \
0, 0, 0, 0 };

#define EVENT_DECLARE(_eventFunc_, _eventData_) \

void _eventFunc_(SM_StateMachine* self, _eventData_* pEventData);

#define EVENT_DEFINE(_eventFunc_, _eventData_) \

void _eventFunc_(SM_StateMachine* self, _eventData_* pEventData)

#define STATE_DECLARE(_stateFunc_, _eventData_) \

static void ST_##_stateFunc_(SM_StateMachine* self, _eventData_* pEventData);

#define STATE_DEFINE(_stateFunc_, _eventData_) \

static void ST_##_stateFunc_(SM_StateMachine* self, _eventData_* pEventData)

The SM_Event() macro is used to generate external events whereas SM_InternalEvent() generates an internal event
during state function execution. SM_GetInstance() obtains a pointer to the current state machine object.

SM_DECLARE and SM_DEFINE are used to create a state machine instance. EVENT_DECLARE and EVENT_DEFINE create
external event functions. And finally, STATE_DECLARE and STATE_DEFINE create state functions.

Motor example
Motor implements our hypothetical motor-control state machine, where clients can start the motor, at a specific speed, and stop
the motor. The Motor header interface is shown below:

Hide   Copy Code

https://www.codeproject.com/Articles/1275479/State-Machine-Design-in-C 5/17
2019/8/10 State Machine Design in C - CodeProject

#include "StateMachine.h"

// Motor object structure

typedef struct
{
INT currentSpeed;
} Motor;

// Event data structure

typedef struct
{
INT speed;
} MotorData;

// State machine event functions

EVENT_DECLARE(MTR_SetSpeed, MotorData)
EVENT_DECLARE(MTR_Halt, NoEventData)

The Motor source file uses macros to simplify usage by hiding the required state machine machinery.

Hide   Shrink   Copy Code

// State enumeration order must match the order of state
// method entries in the state map
enum States
{
ST_IDLE,
ST_STOP,
ST_START,
ST_CHANGE_SPEED,
ST_MAX_STATES
};

// State machine state functions

STATE_DECLARE(Idle, NoEventData)
STATE_DECLARE(Stop, NoEventData)
STATE_DECLARE(Start, MotorData)
STATE_DECLARE(ChangeSpeed, MotorData)

// State map to define state function order

BEGIN_STATE_MAP(Motor)
STATE_MAP_ENTRY(ST_Idle)
STATE_MAP_ENTRY(ST_Stop)
STATE_MAP_ENTRY(ST_Start)
STATE_MAP_ENTRY(ST_ChangeSpeed)
END_STATE_MAP(Motor)

// Set motor speed external event

EVENT_DEFINE(MTR_SetSpeed, MotorData)
{
// Given the SetSpeed event, transition to a new state based upon
// the current state of the state machine
BEGIN_TRANSITION_MAP // - Current State -
TRANSITION_MAP_ENTRY(ST_START) // ST_Idle
TRANSITION_MAP_ENTRY(CANNOT_HAPPEN) // ST_Stop
TRANSITION_MAP_ENTRY(ST_CHANGE_SPEED) // ST_Start
TRANSITION_MAP_ENTRY(ST_CHANGE_SPEED) // ST_ChangeSpeed
END_TRANSITION_MAP(Motor, pEventData)
}

// Halt motor external event

EVENT_DEFINE(MTR_Halt, NoEventData)
{
// Given the Halt event, transition to a new state based upon
// the current state of the state machine
BEGIN_TRANSITION_MAP // - Current State -
TRANSITION_MAP_ENTRY(EVENT_IGNORED) // ST_Idle
TRANSITION_MAP_ENTRY(CANNOT_HAPPEN) // ST_Stop
TRANSITION_MAP_ENTRY(ST_STOP) // ST_Start
https://www.codeproject.com/Articles/1275479/State-Machine-Design-in-C 6/17
2019/8/10 State Machine Design in C - CodeProject

TRANSITION_MAP_ENTRY(ST_STOP) // ST_ChangeSpeed
END_TRANSITION_MAP(Motor, pEventData)
}

External events
MTR_SetSpeed and MTR_Halt are considered external events into the Motor state machine. MTR_SetSpeed takes a
pointer to MotorData event data, containing the motor speed. This data structure will be freed using SM_XFree() upon
completion of the state processing, so it is imperative that it be created using SM_XAlloc() before the function call is made.

State enumerations
Each state function must have an enumeration associated with it. These enumerations are used to store the current state of the state
machine. In Motor, States provides these enumerations, which are used later for indexing into the transition map and state map
lookup tables.

State functions
State functions implement each state — one state function per state-machine state. STATE_DECLARE is used to declare the
state function interface and STATE_DEFINE defines the implementation.

Hide   Shrink   Copy Code

// State machine sits here when motor is not running
STATE_DEFINE(Idle, NoEventData)
{
printf("%s ST_Idle\n", self->name);
}

// Stop the motor

STATE_DEFINE(Stop, NoEventData)
{
// Get pointer to the instance data and update currentSpeed
Motor* pInstance = SM_GetInstance(Motor);
pInstance->currentSpeed = 0;

// Perform the stop motor processing here

printf("%s ST_Stop: %d\n", self->name, pInstance->currentSpeed);

// Transition to ST_Idle via an internal event

SM_InternalEvent(ST_IDLE, NULL);
}

// Start the motor going

STATE_DEFINE(Start, MotorData)
{
ASSERT_TRUE(pEventData);

// Get pointer to the instance data and update currentSpeed

Motor* pInstance = SM_GetInstance(Motor);
pInstance->currentSpeed = pEventData->speed;

// Set initial motor speed processing here

printf("%s ST_Start: %d\n", self->name, pInstance->currentSpeed);
}

// Changes the motor speed once the motor is moving

STATE_DEFINE(ChangeSpeed, MotorData)
{
ASSERT_TRUE(pEventData);

// Get pointer to the instance data and update currentSpeed

Motor* pInstance = SM_GetInstance(Motor);
pInstance->currentSpeed = pEventData->speed;

https://www.codeproject.com/Articles/1275479/State-Machine-Design-in-C 7/17
2019/8/10 State Machine Design in C - CodeProject

// Perform the change motor speed here

printf("%s ST_ChangeSpeed: %d\n", self->name, pInstance->currentSpeed);
}

STATE_DECLARE and STATE_DEFINE use two arguments. The first argument is the state function name. The second
argument is the event data type. If no event data is required, use NoEventData. Macros are also available for creating guard, exit
and entry actions which are explained later in the article.

The SM_GetInstance() macro obtains an instance to the state machine object. The argument to the macro is the state
machine name.

In this implementation, all state machine functions must adhere to these signatures, which are as follows:

Hide   Copy Code

// Generic state function signatures
typedef void (*SM_StateFunc)(SM_StateMachine* self, void* pEventData);
typedef BOOL (*SM_GuardFunc)(SM_StateMachine* self, void* pEventData);
typedef void (*SM_EntryFunc)(SM_StateMachine* self, void* pEventData);
typedef void (*SM_ExitFunc)(SM_StateMachine* self);

Each SM_StateFunc accepts a pointer to a SM_StateMachine object and event data. If NoEventData is used, the
pEventData argument will be NULL. Otherwise, the pEventData argument is of the type specified in STATE_DEFINE.

In Motor’s Start state function, the STATE_DEFINE(Start, MotorData) macro expands to:

Hide   Copy Code

void ST_Start(SM_StateMachine* self, MotorData* pEventData)

Notice that every state function has self and pEventData arguments. self is a pointer to the state machine object and
pEventData is the event data. Also note that the macro prepends “ST_” to the state name to create the function
ST_Start().
Similarly, the Stop state function STATE_DEFINE(Stop, NoEventData) is expands to:
Hide   Copy Code
void ST_Stop(SM_StateMachine* self, void* pEventData)

Stop doesn't accept event data so the pEventData argument is void*. 

Three characters are added to each state/guard/entry/exit function automatically within the macros. For instance, if declaring a
function using STATE_DEFINE(Idle, NoEventData) the actual state function name is called ST_Idle().

1. ST_ - state function prepend characters

2. GD_ - guard function prepend characters
3. EN_ - entry function prepend characters
4. EX_ - exit function prepend characters

SM_GuardFunc and SM_Entry function typedef’s also accept event data. SM_ExitFunc is unique in that no event
data is allowed.

State map
The state-machine engine knows which state function to call by using the state map. The state map maps the currentState
variable to a specific state function. For instance, if currentState is 2, then the third state-map function pointer entry will be
called (counting from zero). The state map table is created using these three macros:

Hide   Copy Code

BEGIN_STATE_MAP
STATE_MAP_ENTRY
END_STATE_MAP

https://www.codeproject.com/Articles/1275479/State-Machine-Design-in-C 8/17
2019/8/10 State Machine Design in C - CodeProject

BEGIN_STATE_MAP starts the state map sequence. Each STATE_MAP_ENTRY has a state function name argument.
END_STATE_MAP terminates the map. The state map for Motor is shown below.
Hide   Copy Code
BEGIN_STATE_MAP(Motor)
STATE_MAP_ENTRY(ST_Idle)
STATE_MAP_ENTRY(ST_Stop)
STATE_MAP_ENTRY(ST_Start)
STATE_MAP_ENTRY(ST_ChangeSpeed)
END_STATE_MAP

Alternatively, guard/entry/exit features require utilizing the _EX (extended) version of the macros.

Hide   Copy Code

BEGIN_STATE_MAP_EX
STATE_MAP_ENTRY_EX or STATE_MAP_ENTRY_ALL_EX
END_STATE_MAP_EX

The STATE_MAP_ENTRY_ALL_EX macro has four arguments for the state action, guard condition, entry action and exit action
in that order. The state action is mandatory but the other actions are optional. If a state doesn't have an action, then use 0 for the
argument. If a state doesn't have any guard/entry/exit options, the STATE_MAP_ENTRY_EX macro defaults all unused options
to 0. The macro snippet below is for an advanced example presented later in the article.

Hide   Copy Code

// State map to define state function order
BEGIN_STATE_MAP_EX(CentrifugeTest)
STATE_MAP_ENTRY_ALL_EX(ST_Idle, 0, EN_Idle, 0)
STATE_MAP_ENTRY_EX(ST_Completed)
STATE_MAP_ENTRY_EX(ST_Failed)
STATE_MAP_ENTRY_ALL_EX(ST_StartTest, GD_StartTest, 0, 0)
STATE_MAP_ENTRY_EX(ST_Acceleration)
STATE_MAP_ENTRY_ALL_EX(ST_WaitForAcceleration, 0, 0, EX_WaitForAcceleration)
STATE_MAP_ENTRY_EX(ST_Deceleration)
STATE_MAP_ENTRY_ALL_EX(ST_WaitForDeceleration, 0, 0, EX_WaitForDeceleration)
END_STATE_MAP_EX(CentrifugeTest)

Don’t forget to add the prepended characters (ST_, GD_, EN_ or EX_) for each function.

State machine objects

In C++, objects are integral to the language. Using C, you have to work a bit harder to accomplish similar behavior. This C language
state machine supports multiple state machine objects (or instances) instead of having a single, static state machine
implementation.

The SM_StateMachine data structure stores state machine instance data; one object per state machine instance.
The SM_StateMachineConst data structure stores constant data; one constant object per state machine type.

The state machine is defined using SM_DEFINE macro. The first argument is the state machine name. The second argument is a
pointer to a user defined state machine structure, or NULL if no user object.

Hide   Copy Code

#define SM_DEFINE(_smName_, _instance_) \
SM_StateMachine _smName_##Obj = { #_smName_, _instance_, \
0, 0, 0, 0 };

In this example, the state machine name is Motor and two objects and two state machines are created.

Hide   Copy Code

// Define motor objects
static Motor motorObj1;
static Motor motorObj2;

// Define two public Motor state machine instances

https://www.codeproject.com/Articles/1275479/State-Machine-Design-in-C 9/17
2019/8/10 State Machine Design in C - CodeProject

SM_DEFINE(Motor1SM, &motorObj1)
SM_DEFINE(Motor2SM, &motorObj2)

Each motor object handles state execution independent of the other. The Motor structure is used to store state machine instance-
specific data. Within a state function, use SM_GetInstance() to obtain a pointer to the Motor object at runtime.

Hide   Copy Code

// Get pointer to the instance data and update currentSpeed
Motor* pInstance = SM_GetInstance(Motor);
pInstance->currentSpeed = pEventData->speed;

Transition map
The last detail to attend to are the state transition rules. How does the state machine know what transitions should occur? The
answer is the transition map. A transition map is lookup table that maps the currentState variable to a state enum constant.
Every external event function has a transition map table created with three macros:

Hide   Copy Code

BEGIN_TRANSITION_MAP
TRANSITION_MAP_ENTRY
END_TRANSITION_MAP

The MTR_Halt event function in Motor defines the transition map as:

Hide   Copy Code

// Halt motor external event
EVENT_DEFINE(MTR_Halt, NoEventData)
{
// Given the Halt event, transition to a new state based upon
// the current state of the state machine
BEGIN_TRANSITION_MAP // - Current State -
TRANSITION_MAP_ENTRY(EVENT_IGNORED) // ST_Idle
TRANSITION_MAP_ENTRY(CANNOT_HAPPEN) // ST_Stop
TRANSITION_MAP_ENTRY(ST_STOP) // ST_Start
TRANSITION_MAP_ENTRY(ST_STOP) // ST_ChangeSpeed
END_TRANSITION_MAP(Motor, pEventData)
}

BEGIN_TRANSITION_MAP starts the map. Each TRANSITION_MAP_ENTRY that follows indicates what the state machine
should do based upon the current state. The number of entries in each transition map table must match the number of state
functions exactly. In our example, we have four state functions, so we need four transition map entries. The location of each entry
matches the order of state functions defined within the state map. Thus, the first entry within the MTR_Halt function indicates an
EVENT_IGNORED as shown below.

Hide   Copy Code

TRANSITION_MAP_ENTRY (EVENT_IGNORED) // ST_Idle

This is interpreted as "If a Halt event occurs while the current state is state Idle, just ignore the event."

Similarly, the third entry in the map is:

Hide   Copy Code

TRANSITION_MAP_ENTRY (ST_STOP) // ST_Start

This indicates "If a Halt event occurs while current is state Start, then transition to state Stop."

END_TRANSITION_MAP terminates the map. The first argument to this macro is the state machine name. The second
argument is the event data.

The C_ASSERT() macro is used within END_TRANSITION_MAP. If there is a mismatch between the number of state machine
states and the number of transition map entries, a compile time error is generated.

https://www.codeproject.com/Articles/1275479/State-Machine-Design-in-C 10/17
2019/8/10 State Machine Design in C - CodeProject

New state machine steps

Creating a new state machine requires a few basic high-level steps:

1. Create a States enumeration with one entry per state function.

2. Define state functions.
3. Define event functions.
4. Create one state map lookup table using the STATE_MAP macros.
5. Create one transition map lookup table for each external event function using the TRANSITION_MAP macros.

State engine
The state engine executes the state functions based upon events generated. The transition map is an array of SM_StateStruct
instances indexed by the currentState variable. When the _SM_StateEngine() function executes, it looks up the
correct state function within the SM_StateStruct array. After the state function has a chance to execute, it frees the event
data, if any, before checking to see if any internal events were generated via SM_InternalEvent().

Hide   Shrink   Copy Code

// The state engine executes the state machine states
void _SM_StateEngine(SM_StateMachine* self, SM_StateMachineConst* selfConst)
{
void* pDataTemp = NULL;

ASSERT_TRUE(self);
ASSERT_TRUE(selfConst);

// While events are being generated keep executing states

while (self->eventGenerated)
{
// Error check that the new state is valid before proceeding
ASSERT_TRUE(self->newState < selfConst->maxStates);

// Get the pointers from the state map

SM_StateFunc state = selfConst->stateMap[self->newState].pStateFunc;

// Copy of event data pointer

pDataTemp = self->pEventData;

// Event data used up, reset the pointer

self->pEventData = NULL;

// Event used up, reset the flag

self->eventGenerated = FALSE;

// Switch to the new current state

self->currentState = self->newState;

// Execute the state action passing in event data

ASSERT_TRUE(state != NULL);
state(self, pDataTemp);

// If event data was used, then delete it

if (pDataTemp)
{
SM_XFree(pDataTemp);
pDataTemp = NULL;
}
}
}

The state engine logic for guard, entry, state, and exit actions is expressed by the following sequence. The
_SM_StateEngine() engine implements only #1 and #5 below. The extended _SM_StateEngineEx() engine uses the
entire logic sequence.

https://www.codeproject.com/Articles/1275479/State-Machine-Design-in-C 11/17
2019/8/10 State Machine Design in C - CodeProject

1. Evaluate the state transition table. If EVENT_IGNORED, the event is ignored and the transition is not performed. If
CANNOT_HAPPEN, the software faults. Otherwise, continue with next step.
2. If a guard condition is defined execute the guard condition function. If the guard condition returns FALSE, the state
transition is ignored and the state function is not called. If the guard returns TRUE, or if no guard condition exists, the state
function will be executed.
3. If transitioning to a new state and an exit action is defined for the current state, call the current state exit action function.
4. If transitioning to a new state and an entry action is defined for the new state, call the new state entry action function.
5. Call the state action function for the new state. The new state is now the current state.

Generating events
At this point, we have a working state machine. Let's see how to generate events to it. An external event is generated by dynamically
creating the event data structure using SM_XAlloc(), assigning the structure member variables, and calling the external event
function using the SM_Event() macro. The following code fragment shows how a synchronous call is made.

Hide   Copy Code

MotorData* data;

// Create event data

data = SM_XAlloc(sizeof(MotorData));
data->speed = 100;

// Call MTR_SetSpeed event function to start motor

SM_Event(Motor1SM, MTR_SetSpeed, data);

The SM_Event() first argument is the state machine name. The second argument is the event function to invoke. The third
argument is the event data, or NULL if no data.

To generate an internal event from within a state function, call SM_InternalEvent(). If the destination doesn't accept event
data, then the last argument is NULL. Otherwise, create the event data using SM_XAlloc().

Hide   Copy Code

SM_InternalEvent(ST_IDLE, NULL);

In the example above, once the state function completes execution the state machine will transition to the ST_Idle state. If, on
the other hand, event data needs to be sent to the destination state, then the data structure needs to be created on the heap and
passed in as an argument.

Hide   Copy Code

MotorData* data;
data = SM_XAlloc(sizeof(MotorData));
data->speed = 100;
SM_InternalEvent(ST_CHANGE_SPEED, data);

No heap usage
All state machine event data must be dynamically created. However, on some systems using the heap is undesirable. The included
x_allocator module is a fixed block memory allocator that eliminates heap usage. Define USE_SM_ALLOCATOR within
StateMachine.c to use the fixed block allocator. See the References section below for x_allocator information.

CentrifugeTest example
The CentrifugeTest example shows how an extended state machine is created using guard, entry and exit actions. The state
diagram is shown below.

https://www.codeproject.com/Articles/1275479/State-Machine-Design-in-C 12/17
2019/8/10 State Machine Design in C - CodeProject

Figure 2: CentrifugeTest state diagram

A CentrifgeTest object and state machine is created. The only difference here is that the state machine is a singleton,
meaning the object is private and only one instance of CentrifugeTest can be created. This is unlike the Motor state
machine where multiple instances are allowed.

Hide   Copy Code

// CentrifugeTest object structure
typedef struct
{
INT speed;
BOOL pollActive;
} CentrifugeTest;

// Define private instance of motor state machine

CentrifugeTest centrifugeTestObj;
SM_DEFINE(CentrifugeTestSM, &centrifugeTestObj)

https://www.codeproject.com/Articles/1275479/State-Machine-Design-in-C 13/17
2019/8/10 State Machine Design in C - CodeProject

The extended state machine uses ENTRY_DECLARE, GUARD_DECLARE and EXIT_DECLARE macros.

Hide   Shrink   Copy Code

// State enumeration order must match the order of state
// method entries in the state map
enum States
{
ST_IDLE,
ST_COMPLETED,
ST_FAILED,
ST_START_TEST,
ST_ACCELERATION,
ST_WAIT_FOR_ACCELERATION,
ST_DECELERATION,
ST_WAIT_FOR_DECELERATION,
ST_MAX_STATES
};

// State machine state functions

STATE_DECLARE(Idle, NoEventData)
ENTRY_DECLARE(Idle, NoEventData)
STATE_DECLARE(Completed, NoEventData)
STATE_DECLARE(Failed, NoEventData)
STATE_DECLARE(StartTest, NoEventData)
GUARD_DECLARE(StartTest, NoEventData)
STATE_DECLARE(Acceleration, NoEventData)
STATE_DECLARE(WaitForAcceleration, NoEventData)
EXIT_DECLARE(WaitForAcceleration)
STATE_DECLARE(Deceleration, NoEventData)
STATE_DECLARE(WaitForDeceleration, NoEventData)
EXIT_DECLARE(WaitForDeceleration)

// State map to define state function order

BEGIN_STATE_MAP_EX(CentrifugeTest)
STATE_MAP_ENTRY_ALL_EX(ST_Idle, 0, EN_Idle, 0)
STATE_MAP_ENTRY_EX(ST_Completed)
STATE_MAP_ENTRY_EX(ST_Failed)
STATE_MAP_ENTRY_ALL_EX(ST_StartTest, GD_StartTest, 0, 0)
STATE_MAP_ENTRY_EX(ST_Acceleration)
STATE_MAP_ENTRY_ALL_EX(ST_WaitForAcceleration, 0, 0, EX_WaitForAcceleration)
STATE_MAP_ENTRY_EX(ST_Deceleration)
STATE_MAP_ENTRY_ALL_EX(ST_WaitForDeceleration, 0, 0, EX_WaitForDeceleration)
END_STATE_MAP_EX(CentrifugeTest)

Notice the _EX extended state map macros so the guard/entry/exit features are supported. Each guard/entry/exit DECLARE
macro must be matched with the DEFINE. For instance, a guard condition for the StartTest state function is declared as:

Hide   Copy Code

GUARD_DECLARE(StartTest, NoEventData)

The guard condition function returns TRUE if the state function is to be executed or FALSE otherwise.

Hide   Copy Code

// Guard condition to determine whether StartTest state is executed.
GUARD_DEFINE(StartTest, NoEventData)
{
printf("%s GD_StartTest\n", self->name);
if (centrifugeTestObj.speed == 0)
return TRUE; // Centrifuge stopped. OK to start test.
else
return FALSE; // Centrifuge spinning. Can't start test.
}

Multithread safety
https://www.codeproject.com/Articles/1275479/State-Machine-Design-in-C 14/17
2019/8/10 State Machine Design in C - CodeProject

To prevent preemption by another thread when the state machine is in the process of execution, the StateMachine module
can use locks within the _SM_ExternalEvent() function. Before the external event is allowed to execute, a semaphore can be
locked. When the external event and all internal events have been processed, the software lock is released, allowing another
external event to enter the state machine instance.

Comments indicate where the lock and unlock should be placed if the application is multithreaded and mutiple threads are able to
access a single state machine instance. Note that each StateMachine object should have its own instance of a software lock.
This prevents a single instance from locking and preventing all other StateMachine objects from executing. Software locks are
only required if a StateMachine instance is called by multiple threads of control. If not, then locks are not required.

Conclusion
Implementing a state machine using this method as opposed to the old switch statement style may seem like extra effort. However,
the payoff is in a more robust design that is capable of being employed uniformly over an entire multithreaded system. Having each
state in its own function provides easier reading than a single huge switch statement, and allows unique event data to be sent to
each state. In addition, validating state transitions prevents client misuse by eliminating the side effects caused by unwanted state
transitions.

This C language version is a close translation of the C++ implementation I’ve used for many years on different projects. Consider
the C++ implementation within the References section if using C++.

References
State Machine Design in C++ - by David Lafreniere
A Fixed Block Allocator in C - by David Lafreniere

History
2nd February, 2019

Initial release

License
This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

https://www.codeproject.com/Articles/1275479/State-Machine-Design-in-C 15/17
2019/8/10 State Machine Design in C - CodeProject

David Lafreniere
United States

I've been a professional software engineer for over 20 years. When not writing code, I enjoy spending time with the family,
camping and riding motorcycles around Southern California.

Comments and Discussions

 

You must Sign In to use this message board.

Search Comments

First Prev Next

I got compiler warnings

Marcel Wagner 7-Aug-19 13:00

Excellent work!
Mike Hankey 18-Mar-19 5:07

Re: Excellent work!

David Lafreniere 20-Mar-19 16:31

My vote of 5
Espen Harlinn 9-Mar-19 8:43

Re: My vote of 5
David Lafreniere 12-Mar-19 0:58

Still relevant
pwasser 5-Mar-19 23:58

Re: Still relevant

David Lafreniere 7-Mar-19 17:18

Thanks for your work

FredBienvenu 18-Feb-19 21:42

Re: Thanks for your work

David Lafreniere 20-Feb-19 13:06

Excellent!
Southmountain 13-Feb-19 15:30

Re: Excellent!
https://www.codeproject.com/Articles/1275479/State-Machine-Design-in-C 16/17
2019/8/10 State Machine Design in C - CodeProject

David Lafreniere 14-Feb-19 1:27

Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Permalink Layout: fixed | fluid Article Copyright 2019 by David Lafreniere

Advertise Everything else Copyright © CodeProject, 1999-2019
Privacy
Cookies Web05 2.8.190808.1
Terms of Use

https://www.codeproject.com/Articles/1275479/State-Machine-Design-in-C 17/17