Dynamic dispatching to template functions

As in the first post I wrote, less than a month ago, this time I am going to visit another stackoverflow question. The user has a template parametrized by a template argument and wants to write a non-templated function that takes an integer argument and will
dispatch the call to the appropriate template.

Basically the problem to solve is:

template <int N>
struct A {
   static void f();
};
void dispatch( int i ) {
    A<i>::f();              // !!!
}

This will not compile, the argument i is a runtime value, it might come from user input, a file, the network... but the templates are proccessed way before by the compiler.

A first approach to the problem would be manually creating a lookup table:

typedef void (*fptr)();
fptr lookup[] = { &A<0>::f, &A<1>::f, /* ... */ };

And it will work: at compile time all of the instantiations of the template are created and functions pointers stored in the array, now dispatch only needs to use that lookup table and call lookup[i]();. But it is a little cumbersome to write if the possible values is more than a couple.

The problem

Automate the creation of the lookup table so that the user does not need to enter all of the possible values manually.

Approach

Because we are talking about template instantiation, automatic instantiation of the templates and build up of the lookup table must be done at compile time, only lookups will be performed at runtime.

Compile time programming implies working with the template sublanguage, which was not designed to be a programming language. Not being born as a true language, it is a bit awkward to work with, and the set of language primitives that can be used is small: there are no loops, or conditions.

Metaprogramming might be a bit cumbersome, but it is not that hard. It basically boils down to creating a class template that solves the general step of the algorithm and recursively instantiates itself with a smaller subset of the problem, then creating an specialization that represents the stop condition. It is not that different from a regular recursive function if it were not for the fact that the conditions are not checked inside the function, but by the compiler doing pattern matching of the arguments.

Setup of the problem

First we need to create the lookup table. I don't like having to type complex types often, and arrays of function pointers are not a simple type, so I will just start with a typedef, a constant to represent the size and the lookup array itself:

typedef void (*fptr)();
const int limit = 10;
fptr lookup[ limit ];

Now we just need to fill it with values.

General step: fill the Nth element

In the general step we fill an array of N elements by filling in the Nth element and recursively calling the same function to solve the smaller problem of filling N-1 elements.

template <int N>
struct init_lookup {
    static void init( fptr *lookup ) {
        lookup[ N ] = &A<N>::f;
        init_lookup<N-1>::init( lookup );
    }
};

Not that hard, we just need to call init_lookup<N>::init( lookup ); and that will initialize all elements from the Nth to the zeroth... oh, well, not really. We did not add a stop condition, so let's do it.

The stop condition

The stop condition is an specialization that will be matched by the compiler. In our case, when the problem to solve has a single element (0). In that case we want to fill the element in, but we do not want to continue instantiating the template.

template <>
struct init_lookup<0> {
    static void init( ftpr *lookup ) {
        lookup[ 0 ] = &A<N>::f;
        // No recursive call
    }
};

Syntactic sugar

With the solution as implemented the user can just call the appropriate init_lookup<limit>::init function from main and it will be set. But I find it nicer if the lookup table was automatically created without me having to retype the sizes, even if I do have a constant for it. That can be easily achieved by providing a helper function:

template <int N>
void lookup_initialization( fptr (&lookup)[N] ) {
    init_lookup<N-1>::init( lookup );
}

If we change that function signature to return an integer, we can use it to initialize a static variable and we will not need to call it from main.

The final solution

In the final solution I have changed the templates a bit so that the array is passed by reference. I tend to prefer passing arrays by reference as the compiler gets the extra size information. We could then add an static assert to verify that we do not try to write beyond the end of the array. I have also offset the position argument by one so that the specialization is just a stop condition and does not contain any logic.

typedef void (*fptr)();
namespace {
    // L: size of the array
    // N: element to initialize (offset by 1)
    template <int L, int N>
    struct init_lookup {
        static_assert( N <= L );
        static void init( fptr (&lookup)[L] ) {
            lookup[ N-1 ] = &A<N-1>::f;
            init_lookup<L,N-1>::init( lookup );
        }
    };
    template <int L>
    struct init_lookup<L,0> {
        static_assert( L >= 0 );
        static void init( fptr (&lookup)[L] ) {
        }
    };
    template <int N>
    int lookup_initialization( fptr (&lookup)[N] ) {
        init_lookup<N,N>::init( lookup );
        return 0;
    }
}
const int limit = 10;
fptr lookup[ limit ];
static const int xxx_ignored = lookup_initialization(lookup);