Archive for March, 2014

Replacing nested switches with multi-dimensional arrays of pointers to functions

Monday, March 17th, 2014 Nigel Jones

It’s been way too long since I’ve written a blog post. To those kind souls that have written to inquire if I’m still alive and kicking – thank you.  The bottom line is that there simply aren’t enough hours in the day. Anyway in an effort to get back in the groove so to speak, I thought I’d answer an email from Francois Alibert who wrote to ask how to replace a nested switch statement with a multi-dimensional array of pointers to functions. Here’s a program that illustrates his conundrum:

#include <stdint.h>
#include <stdio.h>

typedef enum 
{State1, State2, State3, Last_State}
MainState_t;

typedef enum 
    {SubState1, SubState2, SubState3, SubState4, SubState5, SubState6, Last_SubState}
SubState_t;

void demo(MainState_t State,  SubState_t SubState);

/*     Functions called from nested switch statement. 
    First digit is main state, second digit is substate */

void fn11(void);
void fn16(void);

void fn24(void);

void fn32(void);
void fn33(void);
void fn35(void);

void main(void)
{
    MainState_t main_state;
    SubState_t sub_state;
    
    for (main_state = State1; main_state < Last_State; main_state++)
    {
        for(sub_state = SubState1; sub_state < Last_SubState; sub_state++)
        {
            demo(main_state, sub_state);
        }
    }
}

void demo(MainState_t State,  SubState_t SubState)
{
    switch (State)
    {
        case State1:
            switch (SubState)
            {
                case SubState1:
                fn11();
                break;
                
                case SubState6:
                fn16();
                break;
            
                default:
                break;
            }
        break;

        case State2:
            switch (SubState)
            {
                case SubState4:
                fn24();
                break;
    
                default:
                break;
            }
        break;
    
        case State3:
        {
            switch (SubState)
            {
                case SubState2:
                fn32();
                break;
                
                case SubState3:
                fn33();
                break;                
                
                case SubState5:
                fn35();
                break;
    
                default:
                break;
            }
        }
        break;
        
        default:
        break;
    }
}

void fn11(void)
{
    puts("State 1, substate 1");
}

void fn16(void)
{
    puts("State 1, substate 6");
}

void fn24(void)
{
    puts("State 2, substate 4");
}

void fn32(void)
{
    puts("State 3, substate 2");
}

void fn33(void)
{
    puts("State 3, substate 3");
}

void fn35(void)
{
    puts("State 3, substate 5");
}

The key points are that we have nested switch statements and the substate is sparse. That is the number of substates for main state 1 is different to that of the substates for main state 2 and so on. If you’ve ever been in the situation of having to write a nested state machine like this, you’ll rapidly find that the code becomes very unwieldy. In particular functions many of hundreds of lines long with break statements all over the place are the norm. The result can be a maintenance nightmare. Of course if you end up going to three levels, then the problem compounds. Anyway, before looking at a pointer to function implementation, here’s the output from the above code:

State 1, substate 1
State 1, substate 6
State 2, substate 4
State 3, substate 2
State 3, substate 3
State 3, substate 5

In addition, using IAR’s AVR compiler, the code size with full size optimization is 574 bytes and the execution time is  2159 cycles, with the bulk of the execution time taken up by the puts() call.

Let’s now turn this into a pointer to function implementation. The function demo becomes this:

void demo(MainState_t State,  SubState_t SubState)
{
    static void (* const pf[Last_State][Last_SubState])(void) = 
    {
        {fn11, fnDummy, fnDummy, fnDummy, fnDummy, fn16},
        {fnDummy, fnDummy, fnDummy, fn24, fnDummy, fnDummy},
        {fnDummy, fn32, fn33, fnDummy, fn35, fnDummy}
    };
    
    if ((State < Last_State) && (SubState < Last_SubState))
    {
        (*pf[State][SubState])();
    }
}

Note that the empty portions of the array are populated with a call to fnDummy(), which as its name suggests is a dummy function that does nothing. You can of course put a NULL pointer in the array, and then extract the pointer, check to see if its non-NULL and call the function, However in my experience its always faster to just call a dummy function.

So how does this stack up to the nested switch statements? Well as written, the code size has increased to 628 bytes and cycles to 2846. This is a significant increase in overhead. However the code is a lot more compact, and in my opinion dramatically more maintainable. Furthermore, if you can guarantee by design that the parameters passed to demo() are within the array bounds (as is the case with this example), then you can arguably dispense with the bounds checking code. In which case the code size becomes 618 bytes and the execution time 2684 cycles. It’s your call as to whether the tradeoff is worth it.