Boost.MPL and type list generation

Question

Background

This is for a memory manager in a game engine. I have a freelist implemented, and would like to have a compile-time list if these. (A MPL or Fusion vector, for example). The freelist's correspond to allocation sizes, and when allocating/deallocating objects of size less than a constant, they will go to the corresponding freelist.

In the end, this means small objects globally have amortized constant time allocation and constant time deallocation. (Yay.)

Problem

The problem is generating the types I need, so I may eventually use Fusion to instantiate those types. The types in use are (shortened, etc.):

template <size_t N>
struct data_block
{
    size_t mSize; // = N
    char mData[N];
};

template <typename T, size_t ElementsPerPage,
    template <typename> class Allocator = std::allocator >
class freelist { /* ... */ };

template <typename T>
class callocator; // allocator that uses malloc/free

The freelist's will manage data_block's of power-of-2 sizes, starting from a minimum going to a maximum. So what I want is:

static const size_t MinimumSmallSize = 4; // anything smaller gets rounded up
static const size_t MaximumSmallSize = 512; // anything bigger goes to the large allocator
static const size_t ElementsPerPage = 4096;

// mpl magic

To generate this:

typedef boost::mpl::vector<
    freelist<data_block<4>, ElementsPerPage, callocator>,
    freelist<data_block<8>, ElementsPerPage, callocator>
    // ...
    freelist<data_block<256>, ElementsPerPage, callocator>
    freelist<data_block<512>, ElementsPerPage, callocator>
    > free_list_collection;

Obviously, I could do this by hand but I'd rather avoid that for a more general and tweakable interface. Using the Fusion vector in code should be simpler than hard-coded members, too.

Question

I'm not sure the best way to go about this; I've never used MPL extensively before. Any ideas? I had a few poor ideas such as making a range, then remove_if it's not power of 2, etc., but surely that's not best. Maybe something recursive instead, that doubles each time, pushing into my result vector? I'm not sure how to go about that.

Answer 1

This is the best solution I came up with, and it's fairly simple. It requires a log and pow meta-template, which I've included for those who want to play or try it:

#include <boost/mpl/for_each.hpp>
#include <boost/mpl/range_c.hpp>
#include <boost/mpl/transform.hpp>
#include <boost/mpl/vector.hpp>
#include <iostream>

namespace bmpl = boost::mpl;

//// helpers
template <size_t N, size_t Base>
struct log
{
    static const size_t value = 1 + log<N / Base, Base>::value;
};

template <size_t Base>
struct log<1, Base>
{
    static const size_t value = 0;
};

template <size_t Base>
struct log<0, Base>
{
    static const size_t value = 0;
};

template <size_t N, size_t Power>
struct pow
{
    static const size_t value = N * pow<N, Power - 1>::value;
};

template <size_t N>
struct pow<N, 0>
{
    static const size_t value = 1;
};

//// types and constants
template <size_t N>
struct data_block
{
    size_t mSize; // = N
    char mData[N];
};

template <typename T, size_t ElementsPerPage,
    template <typename> class Allocator = std::allocator >
class freelist { /* ... */ };

template <typename T>
class callocator; // allocator that uses malloc/free

static const size_t MinimumSmallSize = 4;
static const size_t MaximumSmallSize = 512;
static const size_t ElementsPerPage = 4096;

//// type generation
// turn a power into a freelist
template <typename T>
struct make_freelist
{
    static const size_t DataSize = pow<2, T::value>::value;
    typedef data_block<DataSize> data_type;

    typedef freelist<data_type, ElementsPerPage, callocator> type;
};

// list of powers
typedef bmpl::range_c<size_t, log<MinimumSmallSize, 2>::value,
                        log<MaximumSmallSize, 2>::value + 1> size_range_powers;

// transform that list into freelists, into a vector
typedef bmpl::transform<size_range_powers, make_freelist<bmpl::_1>,
                            bmpl::back_inserter<bmpl::vector<> > >::type size_range;

//// testing
struct print_type
{
    template <typename T>
    void operator()(const T&) const
    {
        std::cout << typeid(T).name() << "\n";
    }
};

int main(void)
{
    bmpl::for_each<size_range>(print_type());
    std::cout << std::endl;
}

The core of it is just a struct and two typedef's. The log trick reduced the size of the range greatly, and pow of course just undoes the log. Works exactly how I'd like, and I don't see any way to make it simpler.

That said, I've decided to go with Boost.Pool, so I won't be needing my solution (because their pool sizes are dynamic, not compile-time.) But this was good fun.