Click here to Skip to main content
65,938 articles
CodeProject is changing. Read more.
Articles / Languages / C

Finite State Menu

4.04/5 (12 votes)
8 Jul 2014CPOL5 min read 30.4K   769  
An finite state menu implemented using multiple linked-lists and function pointers in C for use with embedded programming.

Introduction

This article is focused on creating a simple menu using a quadruple linked-list that can be used on an embedded system. This can be seen as an alternative to using multiple switch case statements which can get very messy. This system was designed to work on a PIC 18f4550, with and 16x2 LCD display, a keypad consisting of 16 keys and compiled using the CCS C Compiler. For testing purposes, I first designed the menu part in normal C, this article will demonstrate how it works.

Background

The user input to the embedded system is usually just a few keys and is less flexible compared to a computers keyboard and mouse inputs. To simulate this, we will only be using the keys: 'a', 'w', ’s’ and 'd'. Where 'a' means go left, 'w' means go up, 'd' to go right and 's' to go down and also to select that menu item in the menu.

In a previous project, I needed a menu that must be operated by 4 buttons, it implemented the following functionality:

  • Display temperature and time
  • Set both min and max values for a safe temperature region
  • Set a specific time for a light to switch on and off
  • Set the time for an actuator to switch on, and specify the amount of times it should do the work before switching off again

Taking the example of specifying a time for the light to switch on meant that the following structure had to be set up using switch case statements: Main Menu -> Light Control -> Time On -> [Do function].

Already you have 3 nested switch case statements, where each must evaluate which of the 4 keys is pressed and act accordingly. This made code maintenance a difficult task and it became 'messy' (cluttered) fast. I continued with this approach because the deadline was too close to experiment and find another way.

We will now look at ‘the another way’ to implement this menu structure using linked lists and function pointers in C.

Using the Code

Keeping this modular a separate file called "menu.h" was created to store the levels/nodes of the menu and the functions to traverse the structure. (In the article, level and node is used interchangeably)

Each menu item will be represented as a level structure. Each structure has a pointer to a level structure, above, below, previous and next to it. If you don't want that path to be travelled, provide a 0; else provide a valid level pointer. The DoWork function pointer stores the pointer of a void function that will do the work if invoked.

C++
struct level {
   char name[16];
   struct level *next;
   struct level *prev;
   struct level *down;
   struct level *up;
   void (*DoWork)(void);
};

The menu levels are created as follows:

C++
struct level normalM, fanM, fanSpeed, fanRpm, tempM, *currentM;

Where currentM is a pointer of a level structure and will be the only one used to traverse the structure. Next is a function to build a menu level.

C++
void BuildMenu(struct level *currentNode, char name[16], void (*DoWork)(void) , struct level *prevNode, struct level *nextNode,struct level *upNode,struct level *downNode)
{
    strcpy(currentNode->name, name);
    currentNode->prev = prevNode;
    currentNode->next = nextNode;
    currentNode->up = upNode;
    currentNode->down = downNode;
    currentNode->DoWork = DoWork;
}

The first argument passes in the node that you are building by reference. Then you pass in the name of that node. The third argument needs a void function that it will do whenever the user selects this menu item. Arguments 4 to 7 specify which levels is on each side of the current level, they must all be passed in by reference to get the address of them.

NOTE: A 0 must be specified if the current node does not have that option, for example:

C++
BuildMenu(&normalM,"Normal", 0, 0,&fanM, 0, 0);

Here we build the normalM level, by giving it a name of "Normal", specifying that it doesn’t have a function to do when invoked, that it doesn’t have a previous node, that the next node is fanM and that it doesn't have any nodes up or down. The whole menu is then setup:

C++
BuildMenu(&normalM,"Normal", 0, 0,&fanM, 0, 0);

BuildMenu(&fanM,"Fan Control", 0, &normalM,&tempM, 0, &fanSpeed);

      BuildMenu(&fanSpeed,"Fan Speed", DoWork_FanSpeed, 0, &fanRpm, &fanM, 0);

      BuildMenu(&fanRpm,"Fan RPM", DoWork_FanRpm, &fanSpeed, 0, &fanM , 0);

BuildMenu(&tempM,"Temperature", DoWork_Temp, &fanM,0, 0, 0);

A visualization of what the above menu looks like:

Image 1

The dark black circles represent 0, where no path is defined. I like to think of them in the sense of a ROM, where the black circles are the burned links.

Then the functions to traverse the menu gets a little interesting:

C++
void Next(struct level **currentNode) //Correct
{
  if( (*currentNode) ->next != 0)
  (*currentNode) = (*currentNode)->next;
}

The argument of the function takes a pointer, to a pointer of a level structure. This is needed because we want to make the current level to be the next level if it is not 0. So we cannot pass it by value, it has to be by reference. The pass by value function will look something like this, but is INCORRECT as the variable currentNode then only has function scope and will not persist the pointer to the structures values.

C++
void Next(struct level *currentNode) //Incorrect
{
  if(currentNode->next != 0)
    currentNode = currentNode->next;
}

The Previous and Up function is also defined like the correct Next function. Down, however takes into account the DoWork function pointer. It first checks to see if there is work to do and if there is, then it does it, if there isn’t then it checks to see if there is a node below and if there is then the current node moves one down.

That’s it, the following shows how to implement the functions and structure of the menu.h header.

C++
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "menu.h"

//void functions for menu level actions

void DoWork_FanSpeed(void);
void DoWork_FanRpm();
void DoWork_Temp();

//declare all levels/nodes of menu

struct level normalM,fanM,fanSpeed,fanRpm,tempM, *currentM;

int main()
{
    //Build the menu in a hierarchical structure
    BuildMenu(&normalM,"Normal", 0, 0,&fanM, 0, 0);
    BuildMenu(&fanM,"Fan Control", 0, &normalM,&tempM, 0, &fanSpeed);
        BuildMenu(&fanSpeed,"Fan Speed", DoWork_FanSpeed, 0, &fanRpm, &fanM, 0);
        BuildMenu(&fanRpm,"Fan RPM", DoWork_FanRpm, &fanSpeed, 0, &fanM , 0);
    BuildMenu(&tempM,"Temperature", DoWork_Temp, &fanM,0, 0, 0);

    //Assign the current menu item the first item in the menu
    currentM = &normalM;
    printf("%s\n",currentM->name);

  char cKey;

  do
    {
        scanf("%c",&cKey);
        switch(cKey)
        {
            case 'd':
                system("cls"); //Clear screen
                Next(&currentM);  //Check if there is a next node and then go there
                printf("%s\n",currentM->name);
            break;

            case 'a':
                system("cls");
                Prev(&currentM);
                printf("%s\n",currentM->name);
            break;

            case 's':
                system("cls");
                Down(&currentM);
                printf("%s\n",currentM->name);
            break;

             case 'w':
                 system("cls");
                 Up(&currentM);
                 printf("%s\n",currentM->name);
            break;
        }
    }while(cKey != '~');

    return 0;
}

void DoWork_FanSpeed()
{
    printf("Adjusting Fan speed\n");
}

void DoWork_FanRpm()
{
    printf("Changing Fan Rpm\n");
}

void DoWork_Temp()
{
    printf("Temperature display\n");
}

This in practice, works very well with the C standard, but many Embedded compilers try to replicate the C language as best they can, so I soon found out that the CSS C compiler does not support function pointers, bummer.

So the alternative solution was to create an enum that describes the functions that needs to be done for each menu item and change the level structure to hold that enum value. Then when the action Down is preformed, it checks to see what value is in that level’s enum and then executes the appropriate function using a switch case. Also you cannot pass in a constant string to a function it must be stored first. Strcpy does this internally so it should be called outside our function individually for each level.

So for the CCS C, the actual implementation was:

C++
typedef enum task {None,Normal,Fanspeed,FanRpm,Temp}; // None = 0

struct level {
   char name[16];
   struct level *next;
   struct level *prev;
   struct level *down;
   struct level *up;
   task DoTask; //Changed function pointer to hold enum value
} normalM,fanM,fanSpeedM,fanRpmM,tempM, *currentM;

//Removed char name[16] and the function pointer
void BuildMenu(struct level *currentNode, task DoTask, struct level *prevNode, struct level *nextNode,struct level *upNode,struct level *downNode)
{   
    currentNode->prev = prevNode;
    currentNode->next = nextNode;
    currentNode->up = upNode;
    currentNode->down = downNode;
    currentNode->DoTask = DoTask;
}

void ExecuteTask(task taskToDo)
{
    switch(taskToDo)
    {
        case Fanspeed:
             DoWork_FanSpeed();
            break;

        case FanRpm:
            DoWork_FanRpm();
            break;

        case Temp:
            DoWork_Temp();
            break;
    }

    delay_ms(1000);
}

void Down(struct level **currentNode)
{
    if((*currentNode)->DoTask != None)
        ExecuteTask((*currentNode)->DoTask);
    else if((*currentNode)->down != 0)
        (*currentNode) = (*currentNode)->down;
}

  BuildMenu(&normalM, None, 0,&fanM, 0, 0);
     strcpy(normalM.name, "Normal");  
     
  BuildMenu(&fanM, None, &normalM,&tempM, 0, &fanSpeedM);
     strcpy(fanM.name, "Fan Control");

        BuildMenu(&fanSpeedM, Fanspeed , 0, &fanRpmM, &fanM, 0);
           strcpy(fanSpeedM.name, "Fan Speed");

        BuildMenu(&fanRpmM, FanRpm, &fanSpeedM, 0, &fanM , 0);
           strcpy(fanRpmM.name, "Fan RPM");

    BuildMenu(&tempM, Temp, &fanM,0, 0, 0);
       strcpy(tempM.name, "Temperature");

The rest is still as it was in the normal C implementation.

Points of Interest

This is my first article, so please be gentle..

License

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