The State Pattern Approach
The Array of Structs FSM approach seemed to solve almost every problem quite elegantly, so why bother exploring another method? The main challenge arises when multiple event sources need to be handled by the FSM, thus requiring additional conditional logic.
With the current 2D FSM table (states × button event), adding an additional event source would require transforming it into a 3D array, to account for all combinations of states and event sources.
Suppose we want to expand the menu system by adding an expandable submenu that requires vertical navigation functionality. In the current design, a "button select" event automatically switches the FSM into horizontal navigation mode, which works fine for the options navigation and options editing but does not fit the new submenu scenario. Simply adding a new state would not solve the issue, because there is an overlap in the type of events - The newly added submenu and the main menu respond to the same button events but require different behavior.
This overlap means the FSM must either add an extra layer of conditional logic or add an extra dimension to differentiate event sources, both of which reduce the elegance and clarity of the original approach. The latter would also lead to an exponential growth of the FSM table, resulting in many redundant entries and an over bloated array with reduced maintainability.
This limitation motivates exploring the classic State Pattern, which allows for more flexible and scalable event handling. Furthermore, mixing the Array of Structs method with the State Pattern will preserve the constant lookup time while providing clean and modular design at the expense of some additional coding overhead.
State Pattern Architecture
The State Pattern is a behavioral design pattern that allows an object to change its behavior dynamically based on its internal state. Instead of using complex conditional statements, the pattern delegates behavior to state objects where each encapsulates state specific logic.
The overall coordination is performed by the Context, which maintains a reference to the current state and delegates operations to it.
All the State objects implement a common State interface (a struct in case of C implementation), which defines the set of operations that can be performed, regardless of the current state. This also ensures that the Context can interact with states in a uniform way without knowing anything of each state internals.
Returning to our menu implementation, a new menu item, that follows different navigation logic, is added. The tree diagram bellow illustrates the new menu structure:
We will introduce a new software event source generated by the menu, which will trigger an event whenever the navigation logic needs to switch from its standard implementation. As a result, the State Pattern will handle two distinct event sources:
- Hardware events – generated by physical button presses.
- Software events – generated internally by the menu logic to signal a change in the navigation logic.
By using the State Pattern implementation, we avoid forcing the FSM table into a 3D array (states × hardware events × software events). Instead, each state object can react independently to both event sources while keeping the logic modular and easily maintainable.
The Context object holds a reference to the current state and dispatches both hardware and software events to it. The state object decides when to transition to another state and performs the transitioning by exploiting a pointer to a pointer to the current state (State **), which is passed as an argument by the Context. This allows the state itself to change the active state without requiring access to a Context method, thus remaining completly decoupled from the Context’s internals.
The following UML diagram illustrates the FSM’s structure:
Code implementation
I've decided to go all in and build a fully fledged State Pattern implementation. While I'll only share selected code snippets here for discussion, the complete implementation will be available on my GitHub repository.
State Common Interface
#include <stdio.h>
#ifndef STATE_H
#define STATE_H
#include <events.h>
//--- State Interface ---
typedef struct State {
void (*OnSoftwareEvent)(const struct State **CurrentState, menu_event_t event);
void (*OnHardwareEvent)(const struct State **CurrentState, button_t event);
} state_t;
typedef struct {
void (*handler)(void);
const state_t *nextState;
} state_tbl_entry_t;
Concrete State for Standard Navigation
#include <stdint.h>
#include <stddef.h>
#include "events.h"
#include "state.h"
#include "states.h"
#include "menu.h"
static void OnSoftwareEvent(const state_t **CurrentState, menu_event_t event){
static const state_tbl_entry_t tbl[MENU_EVENT_COUNT] = {
[MENU_EVENT_SPECIAL_NAV] = {NULL, &State_Special_Nav},
[MENU_EVENT_STANDARD_NAV] = {NULL, &State_Standard_Nav}
};
*CurrentState=tbl[event].nextState;
if (tbl[event].handler) tbl[event].handler();
}
static void OnHardwareEvent(const state_t **CurrentState, button_t event){
static const state_tbl_entry_t tbl[BTN_COUNT] = {
{MENU_MoveUp, &State_Standard_Nav}, //BTN_UP
{MENU_MoveDown, &State_Standard_Nav}, //BTN_DOWN
{MENU_Select, &State_Option_Nav}, //BTN_SELECT
{MENU_Esc, &State_Standard_Nav} //BTN_ESC
};
*CurrentState=tbl[event].nextState;
if (tbl[event].handler) tbl[event].handler();
}
const state_t State_Standard_Nav = {
.OnSoftwareEvent=&OnSoftwareEvent,
.OnHardwareEvent=&OnHardwareEvent
};
Notice that the state still employs a table-based approach for transitioning thus it preserves the constant lookup time.
Context Object
#include <stdint.h>
#include "states.h"
#include "fsm.h"
typedef struct{
const state_t *currentState;
} context_t;
//initialize Context to point to a State
static context_t Context= {
.currentState=&State_Standard_Nav
};
void FSM_OnSoftwareEvent(menu_event_t event){
Context.currentState->OnSoftwareEvent(&Context.currentState,event);
};
void FSM_OnHardwareEvent(button_t event){
Context.currentState->OnHardwareEvent(&Context.currentState,event);
};
Main
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <conio.h>
#include "events.h"
#include "menu.h"
#include "fsm.h"
//--- NON Blocking Button Handler ---//
void GetButton(void) {
if (_kbhit()) {
char ch = _getch();
ch = toupper(ch);
switch (ch) {
case 'Q': RaiseButtonEvent(BTN_UP);return;
case 'W': RaiseButtonEvent(BTN_DOWN);return;
case 'E': RaiseButtonEvent(BTN_SELECT);return;
case 'R': RaiseButtonEvent(BTN_ESC);return;
default: return;
}
}
}
int main(void) {
MENU_Initialize();
while (1) {
GetButton();
button_t btn_event = GetButtonEvent();
if (btn_event!=BTN_NONE){
ClearButtonEvent();
FSM_OnHardwareEvent(btn_event);
}
menu_event_t menu_event= GetMenuEvent();
if (menu_event!=MENU_EVENT_NONE){
ClearMenuEvent();
FSM_OnSoftwareEvent(menu_event);
}
}
return (EXIT_SUCCESS);
}
Notice that the main() function acts solely as an event monitor and dispatcher. It continuously checks for button presses and software events generated by the menu logic and forwards them to the FSM for processing.
The code has been structured in a way to be easily adaptable for deployment on an embedded system. Obviously the GetButton() will be replaced by an interrupt-driven or polling-based routine that reads the GPIO pins corresponding to physical buttons.
The project was developed in NetBeans using GCC - C99. I've written almost identical code using Microchip's XC8 compiler, so porting it to a microcontroller should be straightforward.
This is a demo of the menu navigation:
