【注】此实践的基本思路来自《Modern C++ Design》
四层结构
实现Chunk
struct Chunk
{
Chunk() : pData(nullptr), firstAvailableBlock_(0), blocksAvailable_(0)
{
}
Chunk(size_t blockSize, unsigned char blocks)
{
pData = new unsigned char[blockSize * blocks];
firstAvailableBlock_ = 0;
blocksAvailable_ = blocks;
unsigned char* p = pData_;
// 给每个block编号
for (unsigned char i = 0; i != blocks; p = p + blockSize)
{
*p = ++i;
}
}
~Chunk()
{
if (pData)
{
delete[] pData;
pData = nullptr;
}
firstAvailable_ = 0;
blocksAvailable_ = 0;
}
Chunk(Chunk&& chunk)
{
pData = chunk.pData;
chunk.pData = nullptr;
firstAvailable_ = chunk.firstAvailable_;
blocksAvailable_ = chunk.blocksAvailable_;
}
Chunk(Chunk& chunk)
{
pData = chunk.pData;
chunk.pData = nullptr;
firstAvailable_ = chunk.firstAvailable_;
chunk.firstAvailable_ = 0;
blocksAvailable_ = chunk.blocksAvailable_;
chunk.blocksAvailable_ = 0;
}
Chunk& operator=(Chunk& chunk)
{
if (this != &chunk)
{
pData = chunk.pData;
chunk.pData = nullptr;
firstAvailable_ = chunk.firstAvailable_;
chunk.firstAvailable_ = 0;
blocksAvailable_ = chunk.blocksAvailable_;
chunk.blocksAvailable_ = 0;
}
return *this;
}
Chunk& operator=(Chunk&& chunk)
{
pData = chunk.pData;
chunk.pData = nullptr;
firstAvailable_ = chunk.firstAvailable_;
chunk.firstAvailable_ = 0;
blocksAvailable_ = chunk.blocksAvailable_;
chunk.blocksAvailable_ = 0;
return *this;
}
void* allocate(size_t blocksize)
{
if (not blocksAvailable_) return nullptr;
auto* pResult = pData + firstAvailableBlock_*blockSize;
firstAvailableBlock_ = *pResult; // 获得下一块内存的索引
--blocksAvailable_;
return pResult;
}
void deallocate(void* p, size_t blockSize)
{
assert(p >= pData);
auto* toRelease = static_cast<unsigned char*>(p);
// 对齐校验
assert((toRelease - pData) % blockSize == 0);
*toRelease = firstAvailableBlock_;
firstAvailableBlock_ = static_cast<unsigned char>((toRelease - pData) / blockSize);
// 截断检查
assert(firstAvailableBlock_ == (toRelease - pData) / blockSize);
++blockAvailable_;
}
bool empty() const
{
return blocksAvailable_ == 0;
}
bool available() const
{
return not empty();
}
bool full() const
{
return firstAvailableBlock_ == 0 and blocksAvailable_ != 0;
}
bool used() const
{
return firstAvailableBlock_ != 0;
}
bool contains(void* p, size_t blockSize, unsigned char numBlocks) const
{
auto cp = static_cast<unsigned char*>(p);
return pData <= p && p < pData + blockSize*numBlocks;
}
private:
unsigned char* pData_;
unsigned char firstAvailableBlock_;
unsigned char blocksAvailable_;
};
初始化
执行完第一次分配
实现FixedAllocator
struct FixedAllocator
{
FixedAllocator(size_t blockSize, unsigned char numBlocks) : blockSize_(blockSize), numBlocks_(numBlocks), chunks_({Chunk(blockSize_, numBlocks)}) allocChunk_(nullptr),deallocChunk_(nullptr)
{
}
~FixedAllocator()
{
blockSize_ = 0;
numBlocks_ = 0;
chunks_.clear();
allocChunk_ = nullptr;
deallocChunk_ = nullptr;
}
void* allocate()
{
if (allocChunk_ == nullptr or allocChunk->empty())
{
auto it = std::find_if(chunks_.begin(), chunks_.end(), [](const Chunk& chunk){
return chunk.available();
});
if (it != chunks_.end())
{
allocChunk_ = &(*it);
}
else
{
chunks_.emplace_back(Chunk(blockSize_, numBlocks_));
allocChunk_ = &(chunks_.back());
deallocChunk_ = &(chunks_.front());
}
}
assert(allocChunk_ != nullptr);
assert(allocChunk_->available());
return allocChunk_.allocate(blockSize_);
}
void deallocate(void* p)
{
if (deallocChunk_)
{
if (deallocChunk_->contains(p, blockSize_, numBlocks_))
{
deallocChunk_->deallocate(p, blockSize_);
}
else
{
auto it = Chunks::iterator(deallocChunk_);
while (++it != chunks_.end())
{
if (it->contains(p))
{
it->deallocate(p, blockSize_);
deallocChunk_ = &(*it);
return ;
}
}
it = Chunks::iterator(deallocChunk_);
assert(it != chunks_.begin());
while(--it != chunks_.rend())
{
if (it->contains(p, blockSize_, numBlocks_))
{
it->deallocate(p, blockSize_);
deallocChunk_ = &(*it);
return ;
}
}
}
}
else
{
auto it = std::find_if(chunks_.begin(), chunks_.end(), [this](const Chunk& chunk) {
return chunk.used() and chunk.contains(p, blockSize_, numBlocks_);
});
if (it != chunks_.end())
{
deallocChunk_ = &(*it);
deallocChunk_->deallocate(p, blockSize_);
}
else
{
assert(false);
}
}
}
size_t getBlockSize() const
{
return blockSize_;
}
private:
size_t blockSize_;
unsigned char numBlocks_;
using Chunks = std::vector<Chunk>;
Chunks chunks_;
Chunk* allocChunk_;
Chunk* deallocChunk_;
};
实现SmallObjAllocator
struct SmallObjAllocator
{
SmallObjAllocator(size_t chunkSize, size_t maxObjSize)
: chunkSize_(chunkSize), maxObjSize_(maxObjSize)
, pool_(), pLastAlloc_(nullptr), pLastDealloc_(nullptr)
{
}
void* allocate(size_t numBytes)
{
if (numBytes > maxObjSize_)
return ::operator new(numBytes);
else
{
if (pLastAlloc_ and pLastAlloc_->getBlockSize() == numBytes)
{
return pLastAlloc_->allocate();
}
// 此处可以二分查找优化
auto it = std::find_if(pool_.begin(), pool_.end(), [numBytes](const FixedAllocator& alloc){
return alloc.getBlockSize() == numBytes;
});
if (it != pool_.end())
{
return it->allocate();
}
esle
{
pool_.emplace_back(FixedAllocator(numBytes, chunkSize_ ));
pLastAlloc_ = &(pool_.back());
return pLastAlloc_->allocate();
}
}
}
void deallocate(void* p, size_t size)
{
if (size > maxObjSize_)
{
::operator delete(p);
}
else
{
if (pLastDealloc_ and pLastDealloc_->getBlockSize() == size)
{
pLastDealloc_->deallocate(p);
}
else
{
auto it = std::find_if(pool_.begin(), pool_.end(), [size](const FixedAllocator& alloc){
return alloc.getBlockSize() == size;
});
assert(it != pool_.end());
it->deallocate(p);
}
}
}
private:
size_t chunkSize_;
size_t maxObjSize_;
std::vector<FixedAllocator> pool_;
FixedAllocator* pLastAlloc_;
FixedAllocator* pLastDealloc_;
};
实现SmallObject
SmallObjAllocator& getSmallObjAlloc()
{
static SmallObjAllocator alloc(5, 1024);
return alloc;
}
struct SmallObject
{
static void* operator new(size_t size)
{
return getSmallObjAlloc().allocate(size);
}
static void operator delete(void* p, size_t size)
{
getSmallObjAlloc().deallocate(p, size);
}
virtual ~Smal1Object(){}
};
