/*
 * Класс пула для быстрого выделения памяти под объекты заданного типа
 * TYPE сразу блоками по BLOCK элементов
 */

template<typename TYPE, size_t BLOCK> class CC_Pool {

    public:

    class Block;

    class Wrapper {
        public:
        TYPE object;
        Wrapper *next; // следующий репер в очереди свободные реперов в блоке
        Block *block; // блок, которому принадлежит репер
    };

    class Block {
        public:
        Wrapper wrappers[BLOCK];
        Wrapper *first;
        Block *next;
        void init();
        int wrapCount;
    };

    static __thread Block* first; // Указатель на первый блок, к котором есть свободные репперы

    static TYPE *create();
    static void remove(TYPE*);

    static __thread int blockCount;

    CC_Pool();

};

template<typename TYPE, size_t BLOCK> __thread typename CC_Pool<TYPE, BLOCK>::Block * CC_Pool<TYPE, BLOCK>::first = nullptr;
template<typename TYPE, size_t BLOCK> __thread int CC_Pool<TYPE, BLOCK>::blockCount = 0;

template<typename TYPE, size_t BLOCK> CC_Pool<TYPE, BLOCK>::CC_Pool()
{
    blockCount = 0;
}

template<typename TYPE, size_t BLOCK> inline TYPE* CC_Pool<TYPE, BLOCK>::create()
{
    if (first == nullptr) {
        // нет свободных блоков, надо зарезервировать новый блок
        first = (Block*) :: operator new (sizeof(Block));
        first->init();
        blockCount++;
    }

    // в первом свободном блоке зарезервировать первый свободный элемент
    Wrapper *wrapper = first->first;
    first->first = first->first->next;
    first->wrapCount--;

    // если блок при этом перестал быть свободным - убрать его из очереди
    if (first->first == nullptr) {
        first = first->next;
    }

    // вернуть объект, заключенный в рэппере
    return (TYPE*) &wrapper->object;
}

template<typename TYPE, size_t BLOCK> inline void CC_Pool<TYPE, BLOCK>::remove(TYPE *object)
{
    // определить реппер по объеку
    Wrapper *wrapper = (Wrapper*) object;

    // Этот реппер относится к блоку
    Block *block = wrapper->block;

    if (block->first == nullptr) {
        // если блок полный, то поставить его в очередь как пустой,
        // поскольку в нем сейчас освободится один репер
        block->next = first;
        first = block;
    }

    // поставить этот репер первым в очереди свободных реперов блока
    wrapper->next = block->first;
    block->first = wrapper;

    // если этот и следующий блоки совсем пустые, то удалить следующий
    block->wrapCount++;
    if (block->wrapCount == BLOCK && block->next != nullptr && block->next->wrapCount == BLOCK) {
        Block *next = block->next;
        block->next = block->next->next;
        delete next;
        blockCount--;
    }
}

template<typename TYPE, size_t BLOCK> void CC_Pool<TYPE, BLOCK>::Block::init()
{
    next = nullptr;
    // все рэпперы в блоке надо поставить в очередь свободных
    first = &wrappers[0];
    for (int i = 0; i < BLOCK-1; i++) {
        wrappers[i].next = &wrappers[i+1];
        wrappers[i].block = this;
    }
    wrappers[BLOCK-1].next = nullptr;
    wrappers[BLOCK-1].block = this;
    wrapCount = BLOCK;
}