可変長template引数でネスト機能付きタスクリストを作る

動機

タスクシステムでゲームを作るうえで、ポリモーフィズムを実現するために指定したクラスの順序ごとにオーバーライドされた関数が実行されてほしい。
例えばあらかじめ定められた基底tasklist::taskにあるupdateメンバ関数をオーバーライドするクラスa0, a1, a2, ...があったとして、それらを統括するtaskmainにテンプレートパラメーターでtaskmain<sst::line<a0, a1, a2>>などの様に引数を与えると、以降その型のアクティブなインスタンスの呼び出しで「a0のインスタンス全て→a1のインスタンス全て→a2のインスタンス全て→...」という実行挙動がなされてほしい。
次はa0からa5の実装の例です。ただし、create_taskとdelete_taskについてはまだ説明することがあるので実装を保留しています。

#include <iostream>
#include <string>

template<class T>
T *create_task();
template<class T>
tasklist::storage *delete_task(tasklist::arstorage);

struct a0 : public tasklist::task{
    void update(tasklist::arstorage t) override{
        std::cout << "struct a0" << std::endl;
        // 自身のタスクを削除する
        delete_task<a0>(t);
    }
};

struct a1 : public tasklist::task{
    int i;
    a1() : i(0){}

    void update(tasklist::arstorage) override{
        // メッセージを表示してtask a0を生成する
        std::cout << "struct a1 " << i << std::endl;
        ++i;
        create_task<a0>();
    }
};

struct a2 : public tasklist::task{
    void update(tasklist::arstorage t) override{
        // メッセージを表示するだけ
        std::cout << "struct a2" << std::endl;
    }
};

struct a3 : public tasklist::task{
    int i;
    a3() : i(0){}

    void update(tasklist::arstorage) override{
        // メッセージを表示してtask a1を生成する
        std::cout << "struct a3 " << i << std::endl;
        ++i;
        create_task<a1>();
    }
};

struct a4 : public tasklist::task{
    int i;
    a4() : i(0){}

    void update(tasklist::arstorage) override{
        // メッセージを表示してtask a3を生成する
        std::cout << "struct a4 " << i << std::endl;
        ++i;
        create_task<a3>();
    }
};

struct a5 : public tasklist::task{
    int i;
    a5() : i(0){}

    void update(tasklist::arstorage) override{
        // メッセージを表示してtask a4を生成する
        std::cout << "struct a5 " << i << std::endl;
        ++i;
        create_task<a4>();
    }
};

型を保持したいので、まず可変長template引数で以下のホルダーを実装します。

namespace sst{
    namespace aux{
        template<int N, class... TS>
        struct get_type_helper;

        template<int N, class T, class... TS>
        struct get_type_helper<N, T, TS...>{
            using type = typename get_type_helper<N - 1, TS...>::type;
        };

        template<class T, class... TS>
        struct get_type_helper<0, T, TS...>{
            using type = T;
        };
    }

    template<class T, int N>
    struct task{
        static const int num = N; // Tの存在できるインスタンス数
        using type = T;
    };

    template<class... TS>
    struct line{
        static const int num = sizeof...(TS);
        template<int N>
        struct typeholder{
            using type = typename aux::get_type_helper<N, TS...>::type;
        };
    };
}

sst::lineで複数の型を保持し、typeholderメンバで任意の位置の型を取得できるようになりました。
後述する理由によりやや手間ではありますが、以下の記法が可能になりました。

tasklist::taskmain<
    sst::line<task<a0, 10>, task<a1, 10>, task<a2, 10>>
> taskmain;

しかしタスクを表現したクラスa0, a1, a2をただ直線上に並べるだけで、ヒエラルキーを構築して型をまとめてカテゴライズできないとなるとやや不便です。以下のようなwrapperをsst内部に書き足します。

template<class T, class L>
struct nest{
    using type = T;
    using line = L;
};

sst::nestはタグとして機能する型typeと、ネスト対象となる型lineを保持します。
実際に使ってみると以下の様になります。

tasklist::taskmain<
    sst::line<
        sst::task<a0, 10>,
        sst::task<a1, 10>,
        sst::nest<
            sst::task<a2, 0>,
            sst::line<
                sst::task<a3, 10>,
                sst::task<a4, 10>,
                sst::task<a5, 10>
            >
        >
    >
> taskmain;

一番上の実行ヒエラルキーにa0, a1があり、次のヒエラルキーa2にa3, a4, a5が存在する、という複雑な表現ができるようになりました。
後でこれらに関して、a0, a1やa3, a4, a5のインスタンスのイテレーターを定数時間で得たり、a2で括られた型のインスタンス群のイテレーターを包括して取得する方法を実装していきましょう。

メモリ管理

タスクリストはリンクリストでメモリ管理を行います。そのクラスをstorageとすると、以下の実装になります。

template<class = void>
struct xstorage{
    using fn_type = void (*)(xstorage<>*&);

    xstorage<> *next, *prev;
    void *wa;
    fn_type fn;
    enum class sp{
        storage,
        begin,
        end
    };
    sp spflag; 
};

using storage = xstorage<>;
using arstorage = storage*&;

双方向リンクリストなのでnextとprevが用意されています。
void *waはワーキングエリアで、ここにa0, a1, a2, ...のインスタンスの実体がアロケートされます。
fn_type及びfnは、継承関係にある型構造のインターフェイスのメンバ関数の実行をType Erasureで一般化して仲介する関数ポインタです。
spflagは、現在のストレージが通常のストレージであるか、それともイテレータのために用意されたbegin/endダミーストレージであるかを区別するフラグです。
ストレージの操作は通常ポインタを介して行われますが、ストレージ内部のインスタンスで関数実行中に自分自身を削除するケースがあるはずなのでその時のためにポインタの参照であるarstorage型を記述しておきます。

全てのタスクの基底クラス

class task{
    template<class L>
    friend class taskmain;

private:
    inline static void fn(tasklist::arstorage t){
        static_cast<task*>(t->wa)->update(t);
    }

public:
    inline virtual void update(tasklist::arstorage){}
};

後述するクラスtaskmain内でのみfn関数を認識可能な状態にしたいのでfriend宣言しておきます。その実態はワーキングエリアを自身の型にキャストして継承先のupdateメンバ関数を呼び出す事です。

タスクを統括するクラス

次はタスクを統括するクラスです。想定する機能としては、タスク巡回のために

• 指定した型のタスクのイテレーターを定数時間で持ってくる。
• タスクのメモリ領域を事前に保持しておく。

その他、型操作としてネストされている型を判定したり取り除いたりします。

template<class L>
class taskmain{
private:
    int *tasknum;
    storage
        xbegin_,
        xend_,
        *sysarray,
        **taskarray;
    void **workingarea;
    using allocator = void *(*)();
    using deallocator = void (*)(void*&);
    allocator *alloc_;
    deallocator *dealloc_;
    // ....
};

tasknum は型ごとに現在のタスク数を保持する配列です。
xbegin_, xend_ はトップレベルのイテレーターとして機能するダミーのストレージです。
sysarray は型ごとのイテレーターを保持するダミーストレージ配列です。
taskarray は型ごとにタスクのストレージを保持します。型->タスクとなっているので二重の配列です。
alloc_, dealloc_ は workingarea をアロケートするためのアロケーターで、型に依存しないようにtemplate関数の実体を函数ポインタで保持するようになっています。

template<class T, int N>
inline static void *alloc(){
    return new T[N];
}

template<class T>
inline static void dealloc(void *&ptr){
    delete[] static_cast<T*>(ptr);
    ptr = nullptr;
}

型操作は次の通りです。

// ネスト型を取り除く
template<class T>
struct nested_test;

template<class T, int i>
struct nested_test<sst::task<T, i>>{
    using type = T;
    using line = void;
};

template<class T, class K>
struct nested_test<sst::nest<T, K>>{
    using type = T;
    using line = K;
};

//タスク型を取り除く
template<class T>
struct distasktype{
    using type = T;
};

template<class T, int i>
struct distasktype<sst::task<T, i>>{
    using type = T;
};

//ネスト型を取り除く
template<class T>
struct disnesttype{
    using type = T;
};

template<class T, class U>
struct disnesttype<sst::nest<T, U>>{
    using type = T;
};

実際に使ってみる

今までの実装を踏まえて例です。

int main(){
    // タスクのメモリ領域を確保する
    taskmain.reserve<a0>();
    taskmain.reserve<a1>();
    taskmain.reserve<a2>();
    taskmain.reserve<a3>();
    taskmain.reserve<a4>();
    taskmain.reserve<a5>();

    // タスク a5 を生成する
    taskmain.create_task<a5>();

    // タスクを回す
    for(int i = 0; i < 6; ++i){
        std::cout << i << "--------" << std::endl;
        taskmain();
    }

    // a2で束ねられたタスクをカウントする
    int n = 0;
    for(
        tasklist::storage *t = taskmain.begin<a2>();
        t != taskmain.end<a2>();
        t = t->next
    ){
        if(t->spflag == tasklist::storage::sp::storage){
            ++n;
        }
    }

    std::cout
        << "a2で束ねられたタスクの数は"
        << n
        << "個です"
        << std::endl;

    return 0;
}

終わりに

大体の形はこんなものになります。
ネストを考慮した型の操作など、入り組んだコードはありますが説明が長くなるので割愛します。
ソースコードの全容をgistに掲載しておきました