小对象内存池——减少内存碎片

根据不同的块大小来划分不同的内存块链形成内存池组

每个链节点（也称为块）容纳一个对象，是内存分配的最小单位，其大小为sizeof(long)的2的正整数次幂

实现中限制了块大小最大值以及在一个链中块个数最大值

利用了free block来存储下一个free_block地址，节约了free block链的存储空间

memory_pool_base.h：

/* * memory_pool_base.h * * Created on: 2012-2-9 * Author: vivence*/#ifndef MEMORY_POOL_BASE_H_#define MEMORY_POOL_BASE_H_#include "util.h"#include <cassert>namespace ghost{struct MemoryPoolBase{struct Node{ Node* pNext;char mem[0]; };struct Head{void* pFirstFreeBlock; // pFirstFreeBlock指向的地址存储了pNextFreeBlock Node* pNode; };static const size_t MIN_BLOCK_SIZE = sizeof(long); template<typename Allocator>static Node* AllocNode(size_t blockSize, size_t blockCount) { assert(0 < blockSize && 0 < blockCount); Node* pNode = (Node*)Allocator::Alloc(sizeof(Node)+blockSize*blockCount); pNode->pNext = 0;// 初始化空闲块链，每个块的sizeof(long)字节存储了下一个空闲块的地址 for (size_t i = 0; i < blockCount-1; ++i) {long* ppNextFreeBlock = (long*)(pNode->mem + (i*blockSize)); *ppNextFreeBlock = (long)((char*)ppNextFreeBlock+blockSize); }// 最后一块的sizeof(long)字节存储0 *(long*)(pNode->mem + ((blockCount-1)*blockSize)) = 0;return pNode; } template<typename Allocator>static void FreeNode(Node& node) {if (0 != node.pNext) { FreeNode<Allocator>(*node.pNext); } Allocator::Free((void*)&node); } template<size_t BLOCK_SIZE>static void InitBlockSize(size_t* pBlockSize) { InitBlockSize<BLOCK_SIZE/2>(pBlockSize-1); *pBlockSize = BLOCK_SIZE; } template<size_t MAX_POOL_SIZE, size_t MAX_BLOCK_COUNT, size_t BLOCK_SIZE>static size_t CalcBlockCount() {// 大小与块数均做限制 if ((unsigned long long)(BLOCK_SIZE*MAX_BLOCK_COUNT) > (unsigned long long)MAX_POOL_SIZE) {return MAX_POOL_SIZE / BLOCK_SIZE; }return MAX_BLOCK_COUNT; } template<size_t MAX_POOL_SIZE, size_t MAX_BLOCK_COUNT, size_t BLOCK_SIZE>static void InitBlockCount(size_t* pBlockCount) {if (MIN_BLOCK_SIZE == BLOCK_SIZE) { *pBlockCount = CalcBlockCount<MAX_POOL_SIZE, MAX_BLOCK_COUNT, BLOCK_SIZE>();return; } InitBlockCount<MAX_POOL_SIZE, MAX_BLOCK_COUNT, BLOCK_SIZE/2>(pBlockCount-1); *pBlockCount = CalcBlockCount<MAX_POOL_SIZE, MAX_BLOCK_COUNT, BLOCK_SIZE>(); }};template<>void MemoryPoolBase::InitBlockSize<MemoryPoolBase::MIN_BLOCK_SIZE>(size_t* pBlockSize){ *pBlockSize = MemoryPoolBase::MIN_BLOCK_SIZE;}} // namespace ghost#endif /* MEMORY_POOL_BASE_H_ */

 

memory_pool.h：

/* * memory_pool.h * * Created on: 2012-2-9 * Author: vivence*/#ifndef MEMORY_POOL_H_#define MEMORY_POOL_H_#include "memory_pool_base.h"namespace ghost{// MBS必须是sizeof(long)的2的正整数次幂倍template<typename A, size_t MPS, size_t MBS, size_t MBC>class MemoryPool : public MemoryPoolBase{public: typedef A Allocator;static const size_t MAX_POOL_SIZE = MPS; // 最大池大小 static const size_t MAX_BLOCK_SIZE = MBS; // 最大块大小 static const size_t MAX_BLOCK_COUNT = MBC; // 最大块个数/每池/每节点private:// 每种不同的块大小拥有一个池 Head heads_[Get2PowerOf<MAX_BLOCK_SIZE/MIN_BLOCK_SIZE>::RESULT+1];// 通过索引找到块大小 static size_t s_blockSizes_[Get2PowerOf<MAX_BLOCK_SIZE/MIN_BLOCK_SIZE>::RESULT+1];// 通过索引找到块个数/每池/每节点，不同块大小的池每个节点能够一次性分配的块个数 static size_t s_blockCounts_[Get2PowerOf<MAX_BLOCK_SIZE/MIN_BLOCK_SIZE>::RESULT+1];public: MemoryPool() : heads_({{0, 0}}) {// 初始化 Init_(); } ~MemoryPool() {// 释放 Uninit_(); } MemoryPool(const MemoryPool&) = delete; MemoryPool& operator =(const MemoryPool&) = delete;private:void Init_() {// 初始化静态数据 static bool unused = InitStatics_(); unused; }void Uninit_() {// 释放池内存 for (size_t i = 0; i < Get2PowerOf<MAX_BLOCK_SIZE/MIN_BLOCK_SIZE>::RESULT+1; ++i) { UninitHead_(heads_[i]); } }public:// 分配内存接口 void* Alloc(size_t size) {if (0 == size || size > MAX_BLOCK_SIZE) {// 使用原生分配 return Allocator::Alloc(size); }// 找到块大小能容纳下size且最接近size的池 size_t index = GetHeadIndex_(size); assert(~0u != index); // size正确不可能获取不到index Head& head = heads_[index];return GetFreeBlock_(head, index); }// 释放内存接口 void Free(void* pMem) {if (0 == pMem) {return; }// 检测是否属于池分配，如果不是则用原生释放 for (size_t i = 0; i < Get2PowerOf<MAX_BLOCK_SIZE/MIN_BLOCK_SIZE>::RESULT+1; ++i) {if (CheckPointerFromPool_(heads_[i], s_blockSizes_[i], s_blockCounts_[i], pMem)) {// 放回池 PutFreeBlock_(heads_[i], pMem);return; } } Allocator::Free(pMem); }private:static bool InitStatics_() {// 最大块大小不能为0 static_assert(0 < MAX_BLOCK_SIZE,"MAX_BLOCK_SIZE must be bigger than 0");// 最多块个数不能为0 static_assert(0 < MAX_BLOCK_COUNT,"MAX_BLOCK_COUNT must be bigger than 0");// 最大块大小不能超过池大小 static_assert( MAX_POOL_SIZE >= MAX_BLOCK_SIZE,"MAX_POOL_SIZE must be not smaller than MAX_BLOCK_SIZE");// 最大块大小必须是最小块大小的整数倍 static_assert(0 == MAX_BLOCK_SIZE%MIN_BLOCK_SIZE,"MAX_BLOCK_SIZE must be MIN_BLOCK_SIZE*x (x is a positive integer)");// 最大块大小为sizeof(long)的2的整数幂倍 static_assert( Is2PowerOfX<MAX_BLOCK_SIZE/MIN_BLOCK_SIZE>::RESULT,"MAX_BLOCK_SIZE must be MIN_BLOCK_SIZE*2^x (x is a positive integer)");// 存储每个块大小，便于通过索引获取，无需每次都计算 InitBlockSize<MAX_BLOCK_SIZE>(&s_blockSizes_[Get2PowerOf<MAX_BLOCK_SIZE/MIN_BLOCK_SIZE>::RESULT]);// 存储每个块个数，便于通过索引获取，无需每次都计算 InitBlockCount<MAX_POOL_SIZE, MAX_BLOCK_COUNT, MAX_BLOCK_SIZE>(&s_blockCounts_[Get2PowerOf<MAX_BLOCK_SIZE/MIN_BLOCK_SIZE>::RESULT]);return true; }static size_t GetHeadIndex_(size_t size) { size_t biggerBlockSize = MIN_BLOCK_SIZE;for (size_t i = 0; i <= Get2PowerOf<MAX_BLOCK_SIZE/MIN_BLOCK_SIZE>::RESULT; ++i) {if (size > biggerBlockSize) { biggerBlockSize *= 2; }else {return i; } }return ~0u; }static void InitHead_(Head& head, size_t blockSize, size_t blockCount) {if (0 == head.pNode) {// 初始分配池内存 head.pNode = AllocNode<Allocator>(blockSize, blockCount); head.pFirstFreeBlock = head.pNode->mem; MacksureNextFreeBlock_(head, blockSize, blockCount); } }static void UninitHead_(Head& head) {if (0 != head.pNode) {// 释放池内存 FreeNode<Allocator>(*head.pNode); head.pNode = 0; head.pFirstFreeBlock = 0; } }static void* GetFreeBlock_(Head& head, size_t index) {if (0 == head.pNode) { InitHead_(head, s_blockSizes_[index], s_blockCounts_[index]); } MacksureNextFreeBlock_(head, s_blockSizes_[index], s_blockCounts_[index]);void* pFreeBlock = head.pFirstFreeBlock; head.pFirstFreeBlock = (void*)(*(long*)head.pFirstFreeBlock);return pFreeBlock; }static void PutFreeBlock_(Head& head, void* pMem) { *(long*)pMem = (long)head.pFirstFreeBlock; head.pFirstFreeBlock = pMem; }static void MacksureNextFreeBlock_(Head& head, size_t blockSize, size_t blockCount) { assert(0 != head.pFirstFreeBlock); // 至少存在一个空闲块 long* ppNextFreeBlock = (long*)head.pFirstFreeBlock;if (0 == *ppNextFreeBlock) {// 申请下一个节点 Node* pTailNode = head.pNode;while (0 != pTailNode->pNext) { pTailNode = pTailNode->pNext; } pTailNode->pNext = AllocNode<Allocator>(blockSize, blockCount); *ppNextFreeBlock = (long)(pTailNode->pNext->mem); } }static bool CheckPointerFromPool_(Head& head, size_t blockSize, size_t blockCount, void* pMem) { assert(0 != pMem);if (0 == head.pNode) {return false; } Node* pNode = head.pNode;while (pNode) {if ((char*)pMem == pNode->mem || ((char*)pMem > pNode->mem && (char*)pMem < (pNode->mem + blockSize*blockCount) && 0 == ((char*)pMem - pNode->mem)%blockSize)) {// pMem在Node所申请的内存区间且位于正确的块地址偏移上 return true; } pNode = pNode->pNext; }return false; }};template<typename A, size_t MPS, size_t MBS, size_t MBC>size_t MemoryPool<A, MPS, MBS, MBC>::s_blockSizes_[Get2PowerOf<MemoryPool<A, MPS, MBS, MBC>::MAX_BLOCK_SIZE/MemoryPool<A, MPS, MBS, MBC>::MIN_BLOCK_SIZE>::RESULT+1] = {0};template<typename A, size_t MPS, size_t MBS, size_t MBC>size_t MemoryPool<A, MPS, MBS, MBC>::s_blockCounts_[Get2PowerOf<MemoryPool<A, MPS, MBS, MBC>::MAX_BLOCK_SIZE/MemoryPool<A, MPS, MBS, MBC>::MIN_BLOCK_SIZE>::RESULT+1] = {0};} // namespace ghost#endif /* MEMORY_POOL_H_ */

 

util.h：

/* * util.h * * Created on: 2012-2-9 * Author: vivence*/#ifndef UTIL_H_#define UTIL_H_#include <stdlib.h>namespace ghost{template<size_t NUMBER>struct Is2PowerOfX{static const bool RESULT = ((0 < NUMBER) && (0 == (NUMBER & (NUMBER-1))));};template<size_t NUMBER>struct Get2PowerOf{static const size_t RESULT = Get2PowerOf<NUMBER/2>::RESULT+1;};template<>struct Get2PowerOf<1>{static const size_t RESULT = 0;};template<>struct Get2PowerOf<0>{static const size_t RESULT = 0;};struct RawAllocator{static void* Alloc(size_t size){return malloc(size);}static void Free(void* pMem){free(pMem);}};} // namespace ghost#endif /* UTIL_H_ */

 

test.cpp：

/* * test.cpp * * Created on: 2012-2-8 * Author: vivence*/#include "memory_pool.h"#include <iostream>#include <iomanip>#include <vector>#include <algorithm>#include <functional>int main(){using namespace ghost;// 每个不同块大小的池大小不超过10M，最大块大小不超过sizeof(long)*2*2*2，一个池一次最多分配20块 typedef MemoryPool<RawAllocator, 1024*1024*10, sizeof(long)*2*2*2, 20> TestMemoryPool; TestMemoryPool test; std::vector<void*> vec;for (size_t i = 1; i < sizeof(long)*2*2*2*2; ++i) {for (size_t j = 0; j < 100; ++j) { vec.push_back(test.Alloc(i)); } } std::for_each(vec.begin(), vec.end(), std::bind(std::mem_fn(&TestMemoryPool::Free), &test, std::placeholders::_1));return 0;}

 

转载于:https://www.cnblogs.com/EvilGhost/archive/2012/03/09/memory_pool.html