Boost.MPL和类型列表生成 [英] Boost.MPL and type list generation

问题描述

这是在游戏引擎的内存管理器。我有一个空闲列表实现，希望有，如果这些编译时间列表。 （A MPL或融合载体，例如）。分配空闲列表的对应分配大小，当/重新分配尺寸小于恒定的对象，他们会去相应的空闲列表。

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.)

问题是我生成所需要的类型，所以我可能最终使用融合来实例化这些类型。在使用中类型（缩短等）：

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

的空闲列表的将管理 DATA_BLOCK 的功率为2的尺寸，从最低开始去一个最大值。所以，我要的是：

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

要产生这样的：

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;

很显然，我可以用手工做，但我宁愿避免了更普遍的和可修改的界面。使用code融合的载体应该比硬$ C $裁谈会成员国更简单了。

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.

我不知道去了解这一点的最好方式;我从来没有广泛使用过MPL。有任何想法吗？我有几个想法差如做一个范围，那么的remove_if 这不是2的幂等，但肯定这不是最好的。也许一些递归代替，每一次双打，推到我的结果向量？我不知道如何去说。

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.

推荐答案

这是我想出了最好的解决方案，它是相当简单的。它需要一个日志和 POW 元模板，我已经包括那些谁想玩或者试试吧

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;
}

它的核心仅仅是一个结构和两个的typedef 的。在日志诱骗减少范围的规模很大， POW 当然只是解开登录。作品究竟怎么想的，我看不出有什么办法让它更简单。

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.

这是说，我已经决定去与Boost.Pool，所以我不会需要我的解决方案（因为它们的池的大小是动态的，而不是编译时）。但是，这是好开心。

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.

这篇关于Boost.MPL和类型列表生成的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！