32235855-2

a.cpp

#include <cassert>
#include <tuple>
#include <iostream>
#include "types.h"

using std::size_t;

// Basic typelist object
template<typename... TL>
struct TypeList{
        static const int size = sizeof...(TL);
};

// Metafunction Concat: Concatenate two typelists
template<typename L, typename R>
struct Concat;

template<typename... TL, typename... TR>
struct Concat <TypeList<TL...>, TypeList<TR...>> {
        typedef TypeList<TL..., TR...> type;
};

template<typename L, typename R>
using Concat_t = typename Concat<L,R>::type;

// Metafunction First: Get first type from a typelist
template<typename T>
struct First;

template<typename T, typename... TL>
struct First <TypeList<T, TL...>> {
        typedef T type;
};

template<typename T>
using First_t = typename First<T>::type;

// Metafunction Split: Split a typelist at a particular index
template<int i, typename TL>
struct Split;

template<int k, typename... TL>
struct Split<k, TypeList<TL...>> {
private:
        typedef Split<k/2, TypeList<TL...>> FirstSplit;
        typedef Split<k-k/2, typename FirstSplit::R> SecondSplit;
public:
        typedef Concat_t<typename FirstSplit::L, typename SecondSplit::L> L;
        typedef typename SecondSplit::R R;
};

template<typename T, typename... TL>
struct Split<0, TypeList<T, TL...>> {
        typedef TypeList<> L;
        typedef TypeList<T, TL...> R;
};

template<typename T, typename... TL>
struct Split<1, TypeList<T, TL...>> {
        typedef TypeList<T> L;
        typedef TypeList<TL...> R;
};

template<int k>
struct Split<k, TypeList<>> {
        typedef TypeList<> L;
        typedef TypeList<> R;
};


// Metafunction Subdivide: Split a typelist into two roughly equal typelists
template<typename TL>
struct Subdivide : Split<TL::size / 2, TL> {};

// Metafunction MakeTree: Make a tree from a typelist
template<typename T>
struct MakeTree;

/*
template<>
struct MakeTree<TypeList<>> {
    typedef TypeList<> L;
    typedef TypeList<> R;
    static const int size = 0;
};*/

template<typename T>
struct MakeTree<TypeList<T>> {
        typedef TypeList<> L;
        typedef TypeList<T> R;
        static const int size = R::size;
};

template<typename T1, typename T2, typename... TL>
struct MakeTree<TypeList<T1, T2, TL...>> {
private:
        typedef TypeList<T1, T2, TL...> MyList;
        typedef Subdivide<MyList> MySubdivide;
public:
        typedef MakeTree<typename MySubdivide::L> L;
        typedef MakeTree<typename MySubdivide::R> R;
        static const int size = L::size + R::size;
};

// Typehandler: What our lists will be made of
template<typename T>
struct type_handler_helper {
    typedef int result_type;
    typedef T input_type;
    typedef result_type (*func_ptr_type)(const input_type &);
};

template<typename T, typename type_handler_helper<T>::func_ptr_type me>
struct type_handler {
        typedef type_handler_helper<T> base;
        typedef typename base::func_ptr_type func_ptr_type;
        typedef typename base::result_type result_type;
        typedef typename base::input_type input_type;

        static constexpr func_ptr_type my_func = me;
        static result_type apply(const input_type & t) {
                return me(t);
        }
};

// Binary search implementation
template <typename T, bool b = (T::L::size != 0)>
struct apply_helper;

template <typename T>
struct apply_helper<T, false> {
    template<typename V>
    static int apply(const V & v, size_t index) {
     //   assert(index == 0);
        return First_t<typename T::R>::apply(v);
    }
};

template <typename T>
struct apply_helper<T, true> {
        template<typename V>
        static int apply(const V & v, size_t index) {
                if( index >= T::L::size ) {
                        return apply_helper<typename T::R>::apply(v, index - T::L::size);
                } else {
                        return apply_helper<typename T::L>::apply(v, index);
                }
        }
};

// Original functions

inline int fun2(int x) {
    return x;
}
inline int fun2(double x) {
    return 0;   
}
inline int fun2(float x) {
    return -1;   
}

template<int N>
inline int g0(const test_tuple & t) { return test_visitor()(std::get<N>(t)); }

// Registry

typedef TypeList<
   type_handler<test_tuple, &g0<0> >,
   type_handler<test_tuple, &g0<1> >,
   type_handler<test_tuple, &g0<2> >,
   type_handler<test_tuple, &g0<3> >,
   type_handler<test_tuple, &g0<4> >,
   type_handler<test_tuple, &g0<5> >,
   type_handler<test_tuple, &g0<6> >,
   type_handler<test_tuple, &g0<7> >,
   type_handler<test_tuple, &g0<8> >,
   type_handler<test_tuple, &g0<9> >
> registry;

typedef MakeTree<registry> jump_table;

int apply(const test_tuple & t, size_t index) {
        return apply_helper<jump_table>::apply(t, index);
}

int main(int argc, char** argv) {
        long long x=0;
        test_tuple t;
        size_t ntry = 100000000;
        for(size_t i = 0; i < ntry; ++i) {
                for(size_t j = 0; j < 10; ++j) {
                        x += apply(t, j);
                }
                if(i % (ntry/10) == 0) {
                        std::cout << "." << std::endl;;
                }
        }
        std::cout << x << " must be " << 55*ntry << std::endl;
        return 0;
}                    

types.h

#ifndef _TYPES_H
#define _TYPES_H

#include <tuple>

template<int N>
struct e {};

struct test_visitor {
        typedef int return_type;

        int operator()(const e<1>& ) const { return 1; }
        int operator()(const e<2>& ) const { return 2; }
        int operator()(const e<3>& ) const { return 3; }
        int operator()(const e<4>& ) const { return 4; }
        int operator()(const e<5>& ) const { return 5; }
        int operator()(const e<6>& ) const { return 6; }
        int operator()(const e<7>& ) const { return 7; }
        int operator()(const e<8>& ) const { return 8; }
        int operator()(const e<9>& ) const { return 9; }
        int operator()(const e<10>& ) const { return 10; }
};

using test_tuple = std::tuple<e<1>,e<2>,e<3>,e<4>,e<5>,e<6>,e<7>,e<8>,e<9>,e<10>>;

#endif // _TYPES_H