内存管理——小型对象分配器实践输出

【注】此实践的基本思路来自《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(p);
		// 对齐校验
		assert((toRelease - pData) % blockSize == 0);
		*toRelease = firstAvailableBlock_;
		firstAvailableBlock_ = static_cast((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(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;
	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 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(){}
};