p-variadic-template.cpp

#ifndef MT_LIST_HPP
#define MT_LIST_HPP

#include <type_traits>
#include <utility>
#include <boost/iterator_adaptors.hpp>

namespace mt{
    template<class T>
    struct task_interface{
        typedef T type;
    };

    template<class T, int N>
    struct task{
        typedef T type;
        static const int value = N;
    };

    template<class T>
    struct linklist{
        linklist *next, *prev;
        T *obj;
        std::size_t id;
    };

    template<class Root>
    class list_iterator : public boost::iterator_adaptor<list_iterator<Root>, linklist<Root>*, Root, boost::bidirectional_traversal_tag>{
    private:
        typedef Root root;
        typedef linklist<root> task;

    public:
        typedef boost::iterator_adaptor<list_iterator, linklist<root>*, root, boost::bidirectional_traversal_tag> base_type;
        list_iterator() : base_type(), begin(nullptr), end(nullptr){}
        list_iterator(const list_iterator *begin_, const list_iterator *end_, task *p) : base_type(p), begin(begin_), end(end_){
            skip_positive();
        }

        template<class T>
        list_iterator(const list_iterator<T> *begin_, const list_iterator<T> *end_, linklist<T> *p)
            : base_type(reinterpret_cast<task*>(p)), begin(reinterpret_cast<const list_iterator*>(begin)), end(reinterpret_cast<const list_iterator*>(end_))
        {}

        void increment(){
            base_type::base_reference() = base_type::base()->next;
            skip_positive();
        }

        void decrement(){
            base_type::base_reference() = base_type::base()->prev;
            skip_negative();
        }

        typename root &dereference() const{
            return *static_cast<root*>(base_type::base_reference()->obj);
        }

        list_iterator operator =(const list_iterator &other){
            base_type::operator =(other);
            begin = other.begin, end = other.end;
            return *this;
        }

        operator bool(){
            return base_type::base_reference() && base_type::base_reference()->obj != nullptr ? true : false;
        }

        task *get_linklist() const{
            return base_type::base();
        }

        const list_iterator *list_begin() const{
            return begin;
        }

        const list_iterator *list_end() const{
            return end;
        }

    private:
        void skip_positive(){
            while(!*this && end->base_type::base_reference() != this->base_type::base_reference()){
                base_type::base_reference() = base_type::base()->next;
            }
        }

        void skip_negative(){
            while(!*this && begin->base_type::base_reference() != this->base_type::base_reference()){
                base_type::base_reference() = base_type::base()->prev;
            }
        }

        const list_iterator *begin, *end;
    };
    
    namespace aux{
        // at_impl
        template<int Count, int N, class T, class... Args>
        struct at_impl{
            typedef typename at_impl<Count + 1, N, Args...>::type type;
        };

        template<int Count, class T, class... Args>
        struct at_impl<Count, Count, T, Args...>{
            typedef T type;
        };

        // assign_impl
        template<int Count, int N, int M, class Rep, class List, class NewList>
        struct assign_impl;

        template<int Count, int N, int M, class Rep, class T, template<class...> class List, class... ListArgs, class... ListNewArgs>
        struct assign_impl<Count, N, M, Rep, List<T, ListArgs...>, List<ListNewArgs...>>{
            typedef typename assign_impl<Count + 1, N, M, Rep, List<ListArgs...>, List<ListNewArgs..., T>>::type type;
        };

        template<int N, int M, class Rep, class T, template<class...> class List, class... ListArgs, class... ListNewArgs>
        struct assign_impl<N, N, M, Rep, List<T, ListArgs...>, List<ListNewArgs...>>{
            typedef typename assign_impl<N + 1, N, M, Rep, List<ListArgs...>, List<ListNewArgs..., Rep>>::type type;
        };

        template<int Count, int N, class Rep, template<class...> class List, class... ListArgs, class... ListNewArgs>
        struct assign_impl<Count, N, Count, Rep, List<ListArgs...>, List<ListNewArgs...>>{
            typedef List<ListNewArgs...> type;
        };

        // insert_impl
        template<int Count, int N, int M, class Ins, class List, class NewList>
        struct insert_impl;

        template<int Count, int N, int M, class Ins, class T, template<class...> class List, class... ListArgs, class... ListNewArgs>
        struct insert_impl<Count, N, M, Ins, List<T, ListArgs...>, List<ListNewArgs...>>{
            typedef typename insert_impl<Count + 1, N, M, Ins, List<ListArgs...>, List<ListNewArgs..., T>>::type type;
        };

        template<int N, int M, class Ins, class T, template<class...> class List, class... ListArgs, class... ListNewArgs>
        struct insert_impl<N, N, M, Ins, List<T, ListArgs...>, List<ListNewArgs...>>{
            typedef typename insert_impl<N + 1, N, M, Ins, List<ListArgs...>, List<ListNewArgs..., Ins, T>>::type type;
        };

        template<int Count, int N, class Ins, template<class...> class List, class... ListArgs, class... ListNewArgs>
        struct insert_impl<Count, N, Count, Ins, List<ListArgs...>, List<ListNewArgs...>>{
            typedef List<ListNewArgs...> type;
        };

        template<int Count, class Ins, template<class...> class List, class... ListArgs, class... ListNewArgs>
        struct insert_impl<Count, Count, Count, Ins, List<ListArgs...>, List<ListNewArgs...>>{
            typedef List<ListNewArgs..., Ins> type;
        };

        // erase_impl
        template<int Count, int N, int M, class List, class NewList>
        struct erase_impl;

        template<int Count, int N, int M, class T, template<class...> class List, class... ListArgs, class... ListNewArgs>
        struct erase_impl<Count, N, M, List<T, ListArgs...>, List<ListNewArgs...>>{
            typedef typename erase_impl<Count + 1, N, M, List<ListArgs...>, List<ListNewArgs..., T>>::type type;
        };

        template<int N, int M, class T, template<class...> class List, class... ListArgs, class... ListNewArgs>
        struct erase_impl<N, N, M, List<T, ListArgs...>, List<ListNewArgs...>>{
            typedef List<ListNewArgs..., ListArgs...> type;
        };

        // reverse_impl
        template<int Count, int M, class List, class NewList>
        struct reverse_impl;

        template<int Count, int M, class T, template<class...> class List, class... ListArgs, class... NewListArgs>
        struct reverse_impl<Count, M, List<T, ListArgs...>, List<NewListArgs...>>{
            typedef typename reverse_impl<Count + 1, M, List<ListArgs...>, List<T, NewListArgs...>>::type type;
        };

        template<int M, template<class...> class List, class... ListArgs, class... NewListArgs>
        struct reverse_impl<M, M, List<ListArgs...>, List<NewListArgs...>>{
            typedef List<NewListArgs...> type;
        };

        // list_interface_task_num_impl
        template<class... List>
        struct list_interface_task_num_impl;

        // stop
        template<>
        struct list_interface_task_num_impl<>{
            static const int value = 0;
        };

        // 'task_interface<base>' form
        template<class T, class... Args>
        struct list_interface_task_num_impl<task_interface<T>, Args...>{
            static const int value = 1 + list_interface_task_num_impl<Args...>::value;
        };

        // 'task<T, N>' form
        template<class T, int N, class... Args>
        struct list_interface_task_num_impl<task<T, N>, Args...>{
            static const int value = 1 + list_interface_task_num_impl<Args...>::value;
        };

        // nested form
        template<template<class...> class List, class... Args, class... NestedArgs, class Base>
        struct list_interface_task_num_impl<List<task_interface<Base>, NestedArgs...>, Args...>{
            static const int value = 1 + list_interface_task_num_impl<NestedArgs...>::value + list_interface_task_num_impl<Args...>::value;
        };

        // reserved_impl
        template<class... List>
        struct reserved_impl;

        template<>
        struct reserved_impl<>{
            template<class List>
            static void fn(List&){
                return;
            }
        };

        template<class T, class... Args>
        struct reserved_impl<task_interface<T>, Args...>{
            template<class List>
            static void fn(List &top_list){
                reserved_impl<Args...>::fn<List>(top_list);
            }
        };

        template<class T, int N, class... Args>
        struct reserved_impl<task<T, N>, Args...>{
            template<class List>
            static void fn(List &top_list){
                std::size_t id = mt::dynamic_type_id<typename List::signature, T>();
                top_list.reserve(id);
                auto &set(top_list.task_chunk[id]);
                auto *first = set.free.next, *last = set.free.prev;
                set.active_begin.next = first;
                first->prev = &set.active_begin;
                set.active_end.prev = last;
                last->next = &set.active_end;
                for(int i = 0; i < N; ++i){
                    set.ctor(set.task_pool[i].obj);
                }
                reserved_impl<Args...>::fn<List>(top_list);
            }
        };

        template<template<class...> class List, class... ListArgs, class... Args>
        struct reserved_impl<List<ListArgs...>, Args...>{
            template<class List>
            static void fn(List &top_list){
                reserved_impl<ListArgs...>::fn<List>(top_list);
                reserved_impl<Args...>::fn<List>(top_list);
            }
        };

        struct reserved_tag{};

        // 動的タスクアレイ確保子
        template<class T, int N>
        void *dynamic_aligned_storage_array_reserver(){
            return new typename std::aligned_storage<sizeof(T), std::alignment_of<T>::value>::type[N];
        }

        // 動的タスクアレイ解放子
        template<class T>
        void dynamic_aligned_storage_array_releaser(void *&ptr){
            delete[] static_cast<typename std::aligned_storage<sizeof(T), std::alignment_of<T>::value>::type*>(ptr);
            ptr = nullptr;
        }

        // 動的削除子
        template<class T>
        void dynamic_deleter(void *ptr){
            delete static_cast<T*>(ptr);
        }

        // 動的配列削除子
        template<class T>
        void dynamic_array_deleter(void *ptr){
            delete[] static_cast<T*>(ptr);
        }

        // 動的デストラクタコール
        template<class T>
        void dynamic_dtor(void *ptr){
            static_cast<T*>(ptr)->~T();
        }

        // 動的生成子
        template<class T>
        void dynamic_placement_ctor(void *ptr){
            new(static_cast<T*>(ptr)) T;
        }

        // listからlinklistを構築する
        template<class TopList, class... List>
        struct make_tasklist;

        template<class TopList>
        struct make_tasklist<TopList>{
            static std::pair<typename TopList::task*, typename TopList::task*> fn(bool, TopList*){
                return std::make_pair(nullptr, nullptr);
            }
        };

        template<class TopList, class T, class... Args>
        struct make_tasklist<TopList, task_interface<T>, Args...>{
            static std::pair<typename TopList::task*, typename TopList::task*> fn(bool is_top, TopList *list_ptr){
                typename TopList::task_set &task_set(list_ptr->task_chunk[mt::dynamic_type_id<typename TopList::signature, T>()]);
                auto p = make_tasklist<TopList, Args...>::fn(is_top, list_ptr);
                task_set.active_begin.next = p.first;
                task_set.active_end.prev = p.second;
                if(p.first){
                    p.first->prev = &task_set.active_begin;
                    p.second->next = &task_set.active_end;
                }
                task_set.pool = new typename TopList::interface_type::type*;
                *task_set.pool = new T;
                task_set.active_begin.obj = *task_set.pool;
                task_set.active_end.obj = *task_set.pool;
                task_set.task_pool = nullptr;
                task_set.pool_deleter = dynamic_deleter<T>;
                return std::make_pair(&task_set.active_begin, &task_set.active_end);
            }
        };

        template<class TopList, class T, int N, class... Args>
        struct make_tasklist<TopList, task<T, N>, Args...>{
            static std::pair<typename TopList::task*, typename TopList::task*> fn(bool is_top, TopList *list_ptr){
                const std::size_t id = mt::dynamic_type_id<typename TopList::signature, T>();
                typename TopList::task_set &set(list_ptr->task_chunk[id]);
                set.active_begin.next = &set.active_end;
                set.active_begin.obj = nullptr;
                set.active_end.prev = &set.active_begin;
                set.active_end.obj = nullptr;
                set.aligned_array_pool = nullptr;
                set.num = N;
                set.pool = new typename TopList::interface_type::type*[N];
                set.task_pool = new typename TopList::task[N];
                set.obj_size = sizeof(T);
                set.aligned_storage_array_reserver = dynamic_aligned_storage_array_reserver<T, N>;
                set.aligned_storage_array_releaser = dynamic_aligned_storage_array_releaser<T>;
                set.pool_deleter = dynamic_array_deleter<T>;
                set.ctor = dynamic_placement_ctor<T>;
                set.dtor = dynamic_dtor<T>;
                auto p = make_tasklist<TopList, Args...>::fn(is_top, list_ptr);
                set.active_end.next = p.first;
                if(p.first){
                    p.first->prev = &set.active_end;
                }
                return std::make_pair(&set.active_begin, p.second ? p.second : &set.active_end);
            }
        };

        template<class TopList, template<class...> class List, class... NestedArgs, class... Args>
        struct make_tasklist<TopList, List<NestedArgs...>, Args...>{
            static std::pair<typename TopList::task*, typename TopList::task*> fn(bool is_top, TopList *list_ptr){
                auto p = make_tasklist<TopList, NestedArgs...>::fn(false, list_ptr);
                auto q = make_tasklist<TopList, Args...>::fn(is_top, list_ptr);
                p.second->next = q.first;
                if(q.first){
                    q.first->prev = p.second;
                }
                return std::make_pair(p.first, q.second ? q.second : p.second);
            }
        };

        // リストの再帰デストラクタ
        template<class TopList, class... List>
        struct tasklist_dtor;

        template<class TopList>
        struct tasklist_dtor<TopList>{
            static void fn(TopList*){
                return;
            }
        };

        template<class TopList, class T, class... Args>
        struct tasklist_dtor<TopList, task_interface<T>, Args...>{
            static void fn(TopList *list_ptr){
                typename TopList::task_set &task_set(list_ptr->task_chunk[dynamic_type_id<typename TopList::signature, T>()]);
                delete *task_set.pool;
                delete task_set.pool;
                tasklist_dtor<TopList, Args...>::fn(list_ptr);
            }
        };

        template<class TopList, class T, int N, class... Args>
        struct tasklist_dtor<TopList, task<T, N>, Args...>{
            static void fn(TopList *list_ptr){
                typename TopList::task_set &task_set(list_ptr->task_chunk[dynamic_type_id<typename TopList::signature, T>()]);
                delete[] static_cast<
                    typename std::aligned_storage<
                        sizeof(T),
                        std::alignment_of<T>::value
                    >::type*
                >(task_set.aligned_array_pool);
                delete task_set.pool;
                delete[] task_set.task_pool;
                tasklist_dtor<TopList, Args...>::fn(list_ptr);
            }
        };

        template<class TopList, template<class...> class List, class... NestedArgs, class... Args>
        struct tasklist_dtor<TopList, List<NestedArgs...>, Args...>{
            static void fn(TopList *list_ptr){
                tasklist_dtor<TopList, NestedArgs...>::fn(list_ptr);
                tasklist_dtor<TopList, Args...>::fn(list_ptr);
            }
        };

        // 動的に型のIDを付与/取得する
        // 核
        template<class Signature>
        std::size_t incremental_type_id(){
            static std::size_t i = 0;
            return i++;
        }
    }

    namespace{
        aux::reserved_tag reserved;
    }

    // 動的に型のIDを付与/取得する
    template<class Signature, class T>
    std::size_t dynamic_type_id(){
        static std::size_t id = aux::incremental_type_id<Signature>();
        return id;
    }

    template<class Signature>
    class list_generator{
    public:
        // シグネチャ
        typedef Signature signature;

        template<class... Args>
        class list{
        public:
            // list内部にもシグネチャを侵入させておく
            typedef Signature signature;

            // N番目の要素の型を得る
            template<int N>
            struct at{
                typedef typename aux::at_impl<0, N, Args...>::type type;
            };

            // N番目にTを割り当てる
            template<int N, class T>
            struct assign{
                typedef typename aux::assign_impl<0, N, sizeof...(Args), T, list, list<>>::type type;
            };

            // N番目にTを挿入する
            template<int N, class T>
            struct insert{
                typedef typename aux::insert_impl<0, N, sizeof...(Args), T, list, list<>>::type type;
            };

            // N番目の要素を削除する
            template<int N>
            struct erase{
                typedef typename aux::erase_impl<0, N, sizeof...(Args), list, list<>>::type type;
            };

            // リストのサイズを得る
            struct size{
                static const int value = sizeof...(Args);
            };

            // 先頭の要素
            struct front{ typedef typename at<0>::type type; };

            // 最後尾の要素
            struct back{ typedef typename at<size::value - 1>::type type; };

            // 先頭に要素を追加
            template<class T>
            struct push_front{
                typedef list<T, Args...> type;
            };

            // 最後尾に要素を追加
            template<class T>
            struct push_back{
                typedef list<Args..., T> type;
            };

            // 順序を反転する
            struct reverse{
                typedef typename aux::reverse_impl<0, sizeof...(Args), list, list<>>::type type;
            };

            // nested list counter
            struct interface_task_num{
                static const int value = aux::list_interface_task_num_impl<Args...>::value;
            };

            // interface type
            struct interface_type{
                typedef typename front::type::type type;
            };

            // task
            typedef linklist<typename interface_type::type> task;

            // iterator
            typedef list_iterator<typename interface_type::type> iterator;

            // iterator begin
            iterator begin(){
                return iterator(&begin_, &end_, begin_.iterator::base_type::base()->next);
            }

            // iterator end
            iterator end(){
                return end_;
            }

            // iterator template begin (template argument)
            template<class T> iterator t_begin(){
                return t_begin(dynamic_type_id<signature, T>());
            }

            // iterator template begin (dynamic type id argument)
            iterator t_begin(std::size_t id){
                task_set &set(task_chunk[id]);
                return iterator(&begin_, &end_, set.active_begin.next);
            }

            // iterator template end (template argument)
            template<class T> iterator t_end(){
                return t_end(dynamic_type_id<signature, T>());
            }

            // iterator template end (dynamic type id argument)
            iterator t_end(std::size_t id){
                task_set &set(task_chunk[id]);
                return iterator(&begin_, &end_, &set.active_end);
            }

            // create task
            template<class T> iterator create_task(){
                return create_task(dynamic_type_id<signature, T>());
            }

            iterator create_task(std::size_t id){
                task_set &set(task_chunk[id]);
                if(set.free.next == &set.free){
                    return end();
                }else{
                    task *t = set.free.next;
                    set.free.next = t->next;
                    t->next = set.active_begin.next;
                    t->next->prev = t;
                    t->prev = &set.active_begin;
                    set.active_begin.next = t;
                    set.ctor(t->obj);
                    return iterator(&begin_, &end_, t);
                }
            }

            // delete task
            iterator delete_task(iterator iter){
                return iterator(&begin_, &end_, delete_task(iter.base_type::base()));
            }

            task *delete_task(task *t){
                task *n = t->prev;
                std::size_t id = t->id;
                task_set &set(task_chunk[id]);
                set.dtor(t->obj);
                t->next->prev = t->prev;
                t->prev->next = t->next;
                t->next = set.free.next;
                set.free.next = t;
                return n;
            }

            // reserve
            template<class T>
            void reserve(){
                reserve(dynamic_type_id<signature, T>());
            }

            void reserve(std::size_t id){
                task_set &set(task_chunk[id]);
                void *aligned_array = set.aligned_storage_array_reserver();
                set.aligned_array_pool = aligned_array;
                for(int i = 0; i < set.num; ++i){
                    set.pool[i] = reinterpret_cast<typename interface_type::type*>(static_cast<char*>(aligned_array) + i * set.obj_size);
                    set.task_pool[i].obj = set.pool[i];
                    set.task_pool[i].id = id;
                }
                for(int i = 0; i < set.num - 1; ++i){
                    set.task_pool[i].next = &set.task_pool[i + 1];
                    set.task_pool[i + 1].prev = &set.task_pool[i];
                }
                set.free.next = set.task_pool;
                set.free.prev = &set.task_pool[set.num - 1];
                set.task_pool[set.num - 1].next = &set.free;
            }

            // release
            template<class T>
            void release(){
                release(dynamic_type_id<signature, T>());
            }

            void release(std::size_t id){
                task_set &set(task_chunk[id]);
                set.active_begin.next = &set.active_end;
                set.active_end.prev = &set.active_begin;
                set.aligned_storage_array_releaser(set.aligned_array_pool);
            }

            // constructor
            list(){
                make_tasklist();
            }

            list(aux::reserved_tag){
                make_tasklist();
                aux::reserved_impl<list>::fn<list>(*this);
            }

            // destructor
            virtual ~list(){
                tasklist_dtor();
            }

        private:
            // taskの一連のセット
            struct task_set{
                int num, obj_size;
                task active_begin, active_end, free;
                task *task_pool;
                typename interface_type::type **pool;
                void *aligned_array_pool;
                void *(*aligned_storage_array_reserver)();
                void (*aligned_storage_array_releaser)(void*&);
                void (*ctor)(void*);
                void (*dtor)(void*);
                void (*pool_deleter)(void*);
            };

            // タスクのチャンク
            task_set task_chunk[interface_task_num::value];

            // 開始点と終了点
            iterator begin_, end_;

            // tasklistを生成するauxにあるclassにfriend宣言しておく
            template<class TopList, class... List>
            friend struct aux::make_tasklist;

            // 線形リストを構築する
            void make_tasklist(){
                std::pair<task*, task*> p = aux::make_tasklist<list, list>::fn(true, this);
                begin_ = iterator(&begin_, &end_, p.first), end_ = iterator(&begin_, &end_, p.second);
                begin_.base()->obj = nullptr, end_.base()->obj = nullptr;
            }

            // tasklistのデストラクタを呼び出すauxにあるclassにfriend宣言しておく
            template<class TopList, class... List>
            friend struct aux::tasklist_dtor;

            // 構築した線形リストを破棄する
            void tasklist_dtor(){
                aux::tasklist_dtor<list, list>::fn(this);
            }

            template<class... List>
            friend struct aux::reserved_impl;
        };
    };
}

#endif // MT_LIST_HPP