Untitled
unknown
c_cpp
a year ago
3.3 kB
16
Indexable
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; } };
Editor is loading...
Leave a Comment