Dispatch Table Example

Contents

Introduction

This page shows how a dispatch table can be implemented in C or C++. A dispatch table is a way of associating a function with a string or numeric value in a general way. The concepts illustrated include data structure initialization, typedefs for functions, and calling functions through pointers.

The code is taken from a real application, which is described very briefly here so you can get an idea of what the code is trying to accomplish.

The application does a random number sampling experiment in order to test some hypotheses about what strategies people use to estimate time intervals. The experimenters who use the program type in the name of the strategy they want to test, and at one point the program has to call a different function depending on the name of the strategy the experimenter typed in.

The sample.h Header File

The name of the header file for this program is sample.h. There are two sampling strategies, and the header file begins by setting up symbolic names for numerical constants that can be used to identify these strategies, plus another constant that should "never" be used: 
#define UNDEFINED_STRATEGY	0
#define RANDOM_R_STRATEGY	1
#define RANDOM_NR_STRATEGY	2
As the '#' at the beginning of each line indicates, these lines are handled by the preprocessor. Wherever one of the names listed here appears in a source code file, the preprocessor will substitute the text that appears on the remainder of the line. That is, wherever the program uses the symbol RANDOM_R_STRATEGY, the compiler will see the character 1 because of preprocessor text substitution.

In C++ it would have been better to use integer constants rather than these preprocessor definitions because then the compiler would be able to check that the symbols are being used properly as integers. But I didn't. In fact, these symbolic constants were never actually used for anything in this program, but I have left them in this Web page just to give some idea of how they might be used.

The program needs to put pointers to functions into a data structure. The functions all take two arguments of types int and bool and return an int, so here is the definition of a new data type for such functions, and the definition of a structured data type that includes a pointer to such a function: 
typedef		int chooseDist_t(int, bool);

struct strategy {
  char		*name;
  int		type;
  chooseDist_t	*chooseDist;
  };
Now the header file can provide the equivalent of function prototypes for some functions of type chooseDist_t: 
extern chooseDist_t	noStrategy, selRandom_r, selRandom_nr;
There will be a list of strategy structs, and as we shall see, there will be numStrategies elements in this array: 
extern const strategy	strategyList[];
extern const int	numStrategies;

The sample.cc Source File

This source code file #includes the header file we just defined. In addition, this file is the one that actually initializes the global data declared in the header file: 
#include "sample.h"

const strategy	strategyList[] = {

//               - name ----    - type ----------       - chooseDist -
		{"undefined",	UNDEFINED_STRATEGY,	noStrategy	},
		{"random_wr",	RANDOM_R_STRATEGY,	selRandom_r	},
		{"random_wor",	RANDOM_NR_STRATEGY,	selRandom_nr	},

                };

const int	numStrategies = sizeof(strategyList) / sizeof(strategy);
The comment line is to help you remember the names of the three fields of the data structures being initialized.
There are several things to notice about these two statements. First, the number of elements in strategyList[] is determined by the number of initializers coded. This version of the program initializes just three elements, and the compiler will give us this value in the constant numStrategies using the sizeof operator (which is part of the C and C++ languages, not a function).

It so happens that the three preprocessor constants have the same numerical values as the subscripts of their array elements, but this is not a requirement in order for this code to work properly. The three initialization lines could appear in any order, and the type codes would be properly assoicated with the corresponding names and function pointers..

The point of all this is that the array can be redefined easily when the experimenters decide they want to add new strategies to the program.

Determining Which Strategy to Use

Here is the code that reads and interpets a strategy name from a text file: 
int		i;
bool		found = false;
char		strategy[80];
ifstream	configFile("config.dat", ios::in);

  //  Be sure config.dat opened all right.
  if (!configFile) {

    cerr << "Unable to open \"config.dat\"" << endl;
    exit(EXIT_FAILURE);

    }

  //  Read strategy name and locate it in strategyList
  configFile >> strategy;

  for (i = 0; i < numStrategies; i++) {

    if (!strcasecmp(strategy, strategyList[i].name)) {

      found = true;
      strategyType = strategyList[i].type;
      break;

      }

    }

    if (!found) {

      cerr << "\"" << strategy << "\" is not a valid strategy name"
           << endl;
      exit(EXIT_FAILURE);

      }
Read the man page for strcasecmp() to see how that function works.

When the above piece of code finishes executing, a global integer named strategyType will have a value of 0, 1, or 2, corresponding to the names UNDEFINED_STRATEGY, RANDOM_R_STRATEGY, or RANDOM_NR_STRATEGY.

Using the Dispatch Table

Here is some code from the part of the program that actually does the timing experiment:

      //  Select first reference distribution
      refDist = strategyList[strategyType].chooseDist(target, true);

      //  Get a matching sample
      while (!match(refDist, target, grand(0))) {

        refDist = strategyList[strategyType].chooseDist(target, false);

	}
This is the code that demonstrates calling a function using a pointer. Remember, chooseDist is the name of a member of the strategy data structure that holds a pointer to a function of type chooseDist_t.

Exercise: Figure out how to improve the program so that we could guarantee that strategyType has the proper subscript value without counting on the programmer to set the predefined constants UNDEFINED_STRATEGY, RANDOM_R_STRATEGY, and RANDOM_NR_STRATEGY to the values 0, 1, and 2 respectively.

The rules.cc Source File

Just for completeness, here is the function definition for one of the functions of type chooseDist_t: 
#include "sample.h"

int
selRandom_r(int target, bool first) {

  return rand() % numDists;

  }
Dr. Christopher Vickery
Queens College fo CUNY