State Machines with Function Pointers

A state machine has a finite set of states, a set of events, and transition rules. When an event arrives, the machine moves from its current state to a new one and optionally performs an action. This chapter builds state machines in C with function-pointer dispatch tables, then rebuilds them in Rust with enums and pattern matching.

Why State Machines Matter

Drivers, protocol parsers, network stacks, and user-interface logic are all state machines. A TCP connection goes through LISTEN, SYN_SENT, ESTABLISHED, FIN_WAIT, and more. A UART driver handles IDLE, RECEIVING, ERROR. If you write systems code, you write state machines.

Dispatch Tables: Array of Function Pointers

The simplest state machine is an array of function pointers indexed by state. Each function handles the current state and returns the next state.

/* dispatch_table.c -- state machine via function pointer array */
#include <stdio.h>

typedef enum {
    STATE_IDLE,
    STATE_RUNNING,
    STATE_STOPPED,
    STATE_COUNT   /* number of states */
} state_t;

typedef enum {
    EVENT_START,
    EVENT_STOP,
    EVENT_RESET,
    EVENT_COUNT
} event_t;

typedef state_t (*handler_fn)(void);

state_t on_idle_start(void)
{
    printf("  IDLE -> start -> RUNNING\n");
    return STATE_RUNNING;
}

state_t on_idle_stop(void)
{
    printf("  IDLE -> stop -> (stay IDLE)\n");
    return STATE_IDLE;
}

state_t on_idle_reset(void)
{
    printf("  IDLE -> reset -> (stay IDLE)\n");
    return STATE_IDLE;
}

state_t on_running_start(void)
{
    printf("  RUNNING -> start -> (stay RUNNING)\n");
    return STATE_RUNNING;
}

state_t on_running_stop(void)
{
    printf("  RUNNING -> stop -> STOPPED\n");
    return STATE_STOPPED;
}

state_t on_running_reset(void)
{
    printf("  RUNNING -> reset -> IDLE\n");
    return STATE_IDLE;
}

state_t on_stopped_start(void)
{
    printf("  STOPPED -> start -> RUNNING\n");
    return STATE_RUNNING;
}

state_t on_stopped_stop(void)
{
    printf("  STOPPED -> stop -> (stay STOPPED)\n");
    return STATE_STOPPED;
}

state_t on_stopped_reset(void)
{
    printf("  STOPPED -> reset -> IDLE\n");
    return STATE_IDLE;
}

/* 2D dispatch table: [state][event] -> handler */
static handler_fn dispatch[STATE_COUNT][EVENT_COUNT] = {
    [STATE_IDLE]    = { on_idle_start,    on_idle_stop,    on_idle_reset    },
    [STATE_RUNNING] = { on_running_start, on_running_stop, on_running_reset },
    [STATE_STOPPED] = { on_stopped_start, on_stopped_stop, on_stopped_reset },
};

static const char *state_names[] = { "IDLE", "RUNNING", "STOPPED" };

int main(void)
{
    state_t current = STATE_IDLE;

    event_t events[] = {
        EVENT_START, EVENT_STOP, EVENT_RESET, EVENT_START, EVENT_STOP
    };

    for (int i = 0; i < 5; i++) {
        printf("State: %s\n", state_names[current]);
        current = dispatch[current][events[i]]();
    }
    printf("Final state: %s\n", state_names[current]);

    return 0;
}

  Dispatch table layout:

              EVENT_START       EVENT_STOP        EVENT_RESET
            +----------------+----------------+----------------+
  IDLE      | on_idle_start  | on_idle_stop   | on_idle_reset  |
            +----------------+----------------+----------------+
  RUNNING   | on_run_start   | on_run_stop    | on_run_reset   |
            +----------------+----------------+----------------+
  STOPPED   | on_stop_start  | on_stop_stop   | on_stop_reset  |
            +----------------+----------------+----------------+

  Lookup: dispatch[current_state][event]() -> next_state

Try It: Add a STATE_ERROR and an EVENT_ERROR that transitions from any state to STATE_ERROR. Only EVENT_RESET can leave STATE_ERROR.

Protocol Parser State Machine

A real use case: parsing a simple key=value protocol. Messages look like KEY=VALUE\n. The parser walks through states as it reads each character.

/* parser_sm.c -- protocol parser state machine */
#include <stdio.h>
#include <string.h>

typedef enum {
    PS_KEY,       /* reading the key */
    PS_VALUE,     /* reading the value */
    PS_DONE,      /* line complete */
    PS_ERROR      /* malformed input */
} parse_state_t;

struct parser {
    parse_state_t state;
    char key[64];
    char value[256];
    int  key_len;
    int  val_len;
};

void parser_init(struct parser *p)
{
    p->state   = PS_KEY;
    p->key_len = 0;
    p->val_len = 0;
    p->key[0]  = '\0';
    p->value[0] = '\0';
}

parse_state_t feed_key(struct parser *p, char c)
{
    if (c == '=') {
        p->key[p->key_len] = '\0';
        return PS_VALUE;
    }
    if (c == '\n' || c == '\r')
        return PS_ERROR;   /* newline before '=' */
    if (p->key_len < 63) {
        p->key[p->key_len++] = c;
    }
    return PS_KEY;
}

parse_state_t feed_value(struct parser *p, char c)
{
    if (c == '\n') {
        p->value[p->val_len] = '\0';
        return PS_DONE;
    }
    if (p->val_len < 255) {
        p->value[p->val_len++] = c;
    }
    return PS_VALUE;
}

parse_state_t feed_done(struct parser *p, char c)
{
    (void)c;
    (void)p;
    return PS_DONE;   /* ignore further input */
}

parse_state_t feed_error(struct parser *p, char c)
{
    (void)c;
    (void)p;
    return PS_ERROR;
}

typedef parse_state_t (*feed_fn)(struct parser *, char);

static feed_fn state_handlers[] = {
    [PS_KEY]   = feed_key,
    [PS_VALUE] = feed_value,
    [PS_DONE]  = feed_done,
    [PS_ERROR] = feed_error,
};

void parser_feed(struct parser *p, char c)
{
    p->state = state_handlers[p->state](p, c);
}

int main(void)
{
    const char *input = "host=192.168.1.1\n";

    struct parser p;
    parser_init(&p);

    for (int i = 0; input[i] != '\0'; i++)
        parser_feed(&p, input[i]);

    if (p.state == PS_DONE)
        printf("Parsed: key='%s', value='%s'\n", p.key, p.value);
    else
        printf("Parse error\n");

    return 0;
}

  State transitions for "host=192.168.1.1\n":

  'h' -> PS_KEY
  'o' -> PS_KEY
  's' -> PS_KEY
  't' -> PS_KEY
  '=' -> PS_VALUE  (key complete: "host")
  '1' -> PS_VALUE
  '9' -> PS_VALUE
  '2' -> PS_VALUE
  ...
  '1' -> PS_VALUE
  '\n' -> PS_DONE  (value complete: "192.168.1.1")

Driver Prep: Many driver protocols (I2C, SPI, USB) use state machines for packet parsing. The function-pointer-per-state pattern keeps the code modular: each state handler is a small, testable function.

Event-Driven Design

In event-driven systems, a main loop reads events and dispatches them to the current state handler. This decouples event sources from state logic.

/* event_driven.c -- event loop with state machine */
#include <stdio.h>
#include <string.h>

typedef enum { ST_OFF, ST_ON, ST_COUNT } state_t;
typedef enum { EV_PRESS, EV_TIMER, EV_COUNT } event_t;

typedef struct {
    state_t  state;
    int      press_count;
} context_t;

typedef state_t (*handler_fn)(context_t *ctx);

state_t off_press(context_t *ctx)
{
    ctx->press_count++;
    printf("  [OFF] Button pressed (#%d) -> ON\n", ctx->press_count);
    return ST_ON;
}

state_t off_timer(context_t *ctx)
{
    (void)ctx;
    printf("  [OFF] Timer tick -> (stay OFF)\n");
    return ST_OFF;
}

state_t on_press(context_t *ctx)
{
    ctx->press_count++;
    printf("  [ON] Button pressed (#%d) -> OFF\n", ctx->press_count);
    return ST_OFF;
}

state_t on_timer(context_t *ctx)
{
    (void)ctx;
    printf("  [ON] Timer tick -> (stay ON)\n");
    return ST_ON;
}

static handler_fn dispatch[ST_COUNT][EV_COUNT] = {
    [ST_OFF] = { off_press, off_timer },
    [ST_ON]  = { on_press,  on_timer  },
};

void process_event(context_t *ctx, event_t ev)
{
    ctx->state = dispatch[ctx->state][ev](ctx);
}

int main(void)
{
    context_t ctx = { .state = ST_OFF, .press_count = 0 };

    /* Simulate an event stream */
    event_t events[] = { EV_TIMER, EV_PRESS, EV_TIMER, EV_PRESS, EV_PRESS };

    for (int i = 0; i < 5; i++)
        process_event(&ctx, events[i]);

    printf("Final press count: %d\n", ctx.press_count);
    return 0;
}

Try It: Add a ST_BLINK state entered by pressing the button while ON. A timer tick in BLINK goes back to ON. A press in BLINK goes to OFF.

Rust: enum + match

Rust's enums with data (algebraic data types) and exhaustive pattern matching are a natural fit for state machines. The compiler verifies you handle every state.

// state_machine.rs -- state machine with enum + match
#[derive(Debug, Clone, Copy, PartialEq)]
enum State {
    Idle,
    Running,
    Stopped,
}

#[derive(Debug, Clone, Copy)]
enum Event {
    Start,
    Stop,
    Reset,
}

fn transition(state: State, event: Event) -> State {
    match (state, event) {
        (State::Idle,    Event::Start) => {
            println!("  IDLE -> Start -> RUNNING");
            State::Running
        }
        (State::Running, Event::Stop) => {
            println!("  RUNNING -> Stop -> STOPPED");
            State::Stopped
        }
        (State::Running, Event::Reset) => {
            println!("  RUNNING -> Reset -> IDLE");
            State::Idle
        }
        (State::Stopped, Event::Start) => {
            println!("  STOPPED -> Start -> RUNNING");
            State::Running
        }
        (State::Stopped, Event::Reset) => {
            println!("  STOPPED -> Reset -> IDLE");
            State::Idle
        }
        (s, e) => {
            println!("  {:?} -> {:?} -> (no change)", s, e);
            s
        }
    }
}

fn main() {
    let mut state = State::Idle;

    let events = [
        Event::Start, Event::Stop, Event::Reset,
        Event::Start, Event::Stop,
    ];

    for &event in &events {
        println!("State: {:?}", state);
        state = transition(state, event);
    }
    println!("Final state: {:?}", state);
}

Rust Note: If you add a new variant to the State enum and forget to handle it in the match, the compiler refuses to build. In C, adding a new state to the enum but forgetting to add a row to the dispatch table compiles fine and crashes at runtime with a NULL function pointer call.

Protocol Parser in Rust

The same key=value parser, but using Rust enums.

// parser_sm.rs -- protocol parser with enum states
#[derive(Debug)]
enum ParseState {
    Key,
    Value,
    Done,
    Error(String),
}

struct Parser {
    state: ParseState,
    key: String,
    value: String,
}

impl Parser {
    fn new() -> Self {
        Parser {
            state: ParseState::Key,
            key: String::new(),
            value: String::new(),
        }
    }

    fn feed(&mut self, c: char) {
        self.state = match &self.state {
            ParseState::Key => {
                if c == '=' {
                    ParseState::Value
                } else if c == '\n' || c == '\r' {
                    ParseState::Error("newline before '='".into())
                } else {
                    self.key.push(c);
                    ParseState::Key
                }
            }
            ParseState::Value => {
                if c == '\n' {
                    ParseState::Done
                } else {
                    self.value.push(c);
                    ParseState::Value
                }
            }
            ParseState::Done => ParseState::Done,
            ParseState::Error(msg) => ParseState::Error(msg.clone()),
        };
    }

    fn result(&self) -> Option<(&str, &str)> {
        match &self.state {
            ParseState::Done => Some((&self.key, &self.value)),
            _ => None,
        }
    }
}

fn main() {
    let input = "host=192.168.1.1\n";

    let mut parser = Parser::new();
    for c in input.chars() {
        parser.feed(c);
    }

    match parser.result() {
        Some((k, v)) => println!("Parsed: key='{}', value='{}'", k, v),
        None => println!("Parse error: {:?}", parser.state),
    }
}

Notice that the Rust Error variant carries a message. Rust enums can hold data per variant -- C enums cannot.

Try It: Extend the Rust parser to handle multiple key=value pairs separated by newlines. After each Done state, reset to Key and collect results into a Vec<(String, String)>.

Why This Matters for Drivers

Device drivers are inherently state machines. A block device goes through initialization, ready, busy, and error states. A network driver manages link negotiation states. An interrupt handler transitions a UART between idle, receiving, and transmitting.

The C function-pointer dispatch table maps directly to how the kernel structures driver state machines. The Rust enum + match approach is how the kernel's Rust abstractions will express the same logic with compile-time exhaustiveness checking.

  Typical driver state machine:

          init_hw()        ready_for_io()
  PROBE ----------> INIT --------------> READY
                      |                    |  ^
                      | error              |  | io_complete()
                      v                    v  |
                    ERROR <--- error --- BUSY
                      |
                      | reset()
                      v
                    PROBE (retry)

Driver Prep: When you write a driver, draw the state diagram first. Enumerate every state and every event. Then implement it as a dispatch table (C) or enum + match (Rust). Missing transitions become obvious on paper before they become bugs in production.

Knowledge Check

1. What advantage does a 2D dispatch table [state][event] have over a large switch statement with nested switches?
2. In the Rust parser, why do we use std::mem::replace to take ownership of the current state before matching on it?
3. How does Rust's exhaustive match checking prevent a class of bugs that C dispatch tables are vulnerable to?

Common Pitfalls

• Uninitialized dispatch table entries -- in C, a missing entry is a NULL pointer. Calling it is undefined behavior. Always initialize every cell or add a bounds check.
• Forgetting to handle "no transition" -- some state/event combinations should be no-ops. Make this explicit, not accidental.
• State explosion -- too many states and events make the table unwieldy. Decompose into hierarchical state machines if the table exceeds about 5x5.
• Side effects in transition logic -- keep handlers pure when possible. Separate "compute next state" from "perform action" for testability.
• Rust: forgetting std::mem::replace -- if you match on &self.state you cannot move data out of variants. The take-and-replace idiom is standard for owned state machines.