/*
 * Класс пула для быстрого выделения памяти под объекты заданного типа
 * 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;
}