Untitled

struct MemoryBlock {
	uint32_t position = 0;
	uint32_t size = 0;
};

template <typename T>
class UniversalPool {
public:
	UniversalPool(uint32_t memSize, bool ownsMemory)
		: memSize(memSize), ownsMemory(ownsMemory) {
		if (ownsMemory) this->memStart = new T[memSize];

		emptyBlocks = new MemoryBlock[blockCapacity];
		insertEmptyBlock(0, 0, memSize);
	}

	~UniversalPool() {
		if (ownsMemory) delete[] memStart;
		delete[] emptyBlocks;
	}

	void reset() {
		blockCount = 1;
		emptyBlocks[0].position = 0;
		emptyBlocks[0].size = memSize;
	}

	void deallocate(uint32_t position, uint32_t size) {
		int blockIndex = findRightBlockIndex(position, size);

		if (blockIndex < blockCount) {
			MemoryBlock rightBlock = emptyBlocks[blockIndex];

			if (rightBlock.position == position + size) {
				size += rightBlock.size;

				removeEmptyBlock(blockIndex);
			}
		}

		if (blockIndex > 0) {
			MemoryBlock leftBlock = emptyBlocks[blockIndex - 1];

			if (leftBlock.position + leftBlock.size == position) {
				position = leftBlock.position;
				size += leftBlock.size;

				removeEmptyBlock(--blockIndex);
			}
		}

		insertEmptyBlock(blockIndex, position, size);
	}

	uint32_t allocate(uint32_t size) {
		int bestFitIndex = -1;
		MemoryBlock bestFitBlock;
		for (int blockIndex = 0; blockIndex < blockCount; blockIndex++) {
			MemoryBlock memBlock = emptyBlocks[blockIndex];

			if (memBlock.size >= size && (memBlock.size < bestFitBlock.size || bestFitIndex == -1)) {
				bestFitIndex = blockIndex;
				bestFitBlock = memBlock;

				if (memBlock.size == size) break;
			}
		}

		if (bestFitIndex == -1) return -1;

		uint32_t leftoverBlock = bestFitBlock.size - size;
		if (leftoverBlock == 0) {
			removeEmptyBlock(bestFitIndex);
		} else {
			emptyBlocks[bestFitIndex].position += size;
			emptyBlocks[bestFitIndex].size = leftoverBlock;
		}

		return bestFitBlock.position;
	}

	T* getPositionAddress(uint32_t position) {
		return memStart + position;
	}

	T* getStartAddress() {
		return memStart;
	}
protected:
	T* memStart = 0;
	uint32_t memSize = 0;
	bool ownsMemory;

	MemoryBlock* emptyBlocks = nullptr;
	int blockCount = 0, blockCapacity = 10000;

	int findRightBlockIndex(uint32_t position, uint32_t size) {
		int l = 0, r = blockCount;
		while (l < r) {
			int m = (l + r) / 2;
			if (emptyBlocks[m].position >= position + size) {
				r = m;
			} else {
				l = m + 1;
			}
		}

		return r;
	}

	void insertEmptyBlock(int index, uint32_t position, uint32_t size) {
		if (blockCount == blockCapacity) increaseBlockCapacity();
		memmove(emptyBlocks + index + 1, emptyBlocks + index, (blockCount - index) * sizeof(MemoryBlock));

		emptyBlocks[index].position = position;
		emptyBlocks[index].size = size;

		blockCount++;
	}

	void removeEmptyBlock(int index) {
		memmove(emptyBlocks + index, emptyBlocks + index + 1, (blockCount - index - 1) * sizeof(MemoryBlock));

		blockCount--;
	}

	void increaseBlockCapacity() {
		MemoryBlock* newEmptyBlocks = new MemoryBlock[blockCapacity * 2];
		memcpy(newEmptyBlocks, emptyBlocks, blockCount * sizeof(MemoryBlock));

		delete[] emptyBlocks;
		emptyBlocks = newEmptyBlocks;
		blockCapacity *= 2;
	}
};