c--内存池设计-学位论文.doc

C++内存池设计

在项目中进程要对变量和对象分配空间，由于频繁的使用new和delete很消耗程序的运行时间，而且容易产生各种内存泄露，内存释放错误等问题。为此，需要设计一个通用的内存池来完成相关的分配和释放的工作。

建立内存池：
首先向系统申请一块内存，这块内存的大小由使用者根据需要设置初始内存大小。

定义一个如下面代码所示的双向链表，将从系统分配的内存分为若干块。使用双向链表方便指针向前和向后遍历查找。

链表中*Data指向了系统分配的内存，pUser使用二级指针保存了内存申请者的地址，方便以后系统内存块更改，改变申请者的指向。后面会详细介绍。将双向链表指向指向内存如下所示：

假设内存池初始块数为4块，每块的大小为100个字节，则向系统申请400个字节的内存块，每块的大小为100字节。之后使用双向链表DATA指针指向内存块，每个指针能分配的大小如图所示从大到小递减。
对象内存分配：
对内存的链表指针分配好后，用户可以使用内存池进行内存分配，对于用户的内存分配有两种情况，一种是在现有的内存池中能找到合适的内存块，另一种情况是现有内的内存池没有足够的内存块来分配，需要重新向系统申请内存来满足用户的需求。下面分别就这两种内存分配情况进行说明：

情况1内存池有足够的内存块进行分配

假设用户申请了240个字节的内存空间，内存池现在有四个内存块空闲，每个内存块的大小为100字节，那么内存池将会给用户取整分配三个内存块。如上图所示，并将指向400内存块的指针的DATE返回给用户使用。

情况2内存池没有足够的内存块进行分配
接着上图，假设用户现在要接着分别300字节的内存空间，现有内存池的大小已经不能满足，因此需要扩大现有的内存池使用大小。考虑到由于分配给用户的内存空间必须要是连续的内存块，因此这个连续的内存块越大，能分配给用户的内存就多。因此使用C语言的realloc函数来满足要求。
函数简介
原型：extern void *realloc(void *mem_address, unsigned int newsize);
语法：指针名=（数据类型*）realloc（要改变内存大小的指针名，新的大小）。//新的大小一定要大于原来的大小，不然的话会导致数据丢失！
头文件：#include 有些编译器需要#include ，在TC2.0中可以使用alloc.h头文件
功能：先判断当前的指针是否有足够的连续空间，如果有，扩大mem_address指向的地址，并且将mem_address返回，如果空间不够，先按照newsize指定的大小分配空间，将原有数据从头到尾拷贝到新分配的内存区域，而后释放原来mem_address所指内存区域（注意：原来指针是自动释放，不需要使用free），同时返回新分配的内存区域的首地址。即重新分配存储器块的地址。
返回值：如果重新分配成功则返回指向被分配内存的指针，否则返回空指针NULL。

由realloc函数定义可知，新分配的内存空间可能是在原有的内存基础上扩充，还有可能是在另外的一个地方新开辟一块内存。无论哪种情况多要对新加的内存进行指针指向分配。并且对于第二种情况，会出现的问题是原有的指针全都失效。因为原有指向的内存已经不存在了，因此指向它的指针将失效，原有分配的对象也将失效。为了解决这个问题，在新分配内存后需要重定向原有的指针，并且使用二级指针改变已经分配了对象的地址的指向，使它指向新内存。

重定向原有内存的指针的指向，和已经分配了内存的对象的指向。

对象释放内存：

假如先前的申请了250个字节分配了三个内存块的用户释放了内存，这时链表指针向后查找直到找到第一个被使用的内存块，或链表结尾。之后在先前查找直到找到前面第一个被使用的内存块或者是头指针，之后更新这个区间段内存块的大小。

释放内存池：

首先释放向系统申请的内存块，之后在清空所有的双向链表。

释放向系统申请的内存

释放双向链表。

后续改进：
1， 需要对多线程的支持，目前的内存池还只能在单线程的环境下运行。
2， 如果之前得到内存的对象，在新内存分配前有指针复制操作，原有对象可以通过保存的指针地址进行重定向，但是之前分别的对象不能保证。引进对于分配的对象尽量不要使用指针复制。如果一定需要这么做，那就在每次使用前，在重定向一下。重新进行一次复制操作（保险起见，不知道我的表述是否清楚明白）。

源代码：

头文件链表节点的定义
#include
#include
#include
#include
using namespace std;
namespace MemePool
{
typedef unsigned char EigthByte;
//内存池的默认大小和分配节点的默认大小
static const size_t DEFAULTMEMEPOOLSIZE = 1000;
static const size_t DEFAULTMEMENODESIZE = 100;
//内存初始分配内容 二进制位1111 1111
static const int NEW_ALLOCATED_MEMORY_CONTENT = 0xFF;
//内存分配节点（双向链表）
typedef struct TMemeNode
{
//指向前一节点
TMemeNode *first
//指向后一节点
TMemeNode *next;
//节点大小
size_t idataSize;
//节点是否被使用
bool isUsed;
//分配的节点的后一节点
TMemeNode *pEndNode;
//记录内存池分配的首地址
bool isMemeBegin;
//保存分配的内存地址
EigthByte *Data ;
//使用者对象的地址
void **pUser;
} TMemeLinkNode;

};

内存池实现：

namespace MemePool
{
//内存池的实现 作者邮箱a584851044@
class CMemePool
{
public:
//线程池构造函数
CMemePool(const size_t &sInitialMemoryPoolSize = DEFAULTMEMEPOOLSIZE,
const size_t &sMemoryChunkSize = DEFAULTMEMENODESIZE);
~CMemePool();
//分配内存
void *GetMemeroy(void **p,const size_t &sSize);

//释放分配内存
void FreeAllocMemeroy(void *p,const size_t &sSize);
//释放内存池所有内存
void FreeAllMemeroy();
//展示内存池的使用情况
void ShowTheMemePoolStatue();
//获取错误信息
void GetErrorInfo();
private:
//禁止复制与构造，要传递就用引用吧
CMemePool(CMemePool *tCMemePool);
CMemePool& operator =(CMemePool &tCMemePool);
void AllocPoolMemeroy();
void CalLinkNodeNum();
void CalMemeSize();
void LinkMemeryToNode(EigthByte *PAlloc);
void UpdateLinkNodeSize(TMemeNode *PNode);
void CalNeetLinkNumber(const size_t &sSize);
void* FindMemeNode(const size_t &sSize);
TMemeNode * SearchAllocNode(void *p);
void CleanAllMemeDate();
void CleatAllLinkNode();
void ResetLinkToMemery();
//双向链表的头节点
TMemeLinkNode *m_Head;
//双向链表的当前节点
TMemeLinkNode *m_Current;
//双向链表的最后节点
TMemeLinkNode *m_LastNode;
EigthByte *m_PAlloc;
//保存第一次运行头地址
bool m_isFirst;
//内存块分配数目
size_t m_Number;
//内存块总的数目
size_t m_AllNumber;
//每一个内存块的大小
size_t m_MemLinkSize;
//内存池分配的大小
size_t m_MemePollSize;
//内存块总分配大小
size_t m_AllAloctsize;
//内存池使用的大小
size_t m_MemePoolUseSize;
//内存池空闲的大小
size_t m_MemePoolFreeSize;
//分配了多少个对象
size_t m_iUseObject;
//保存错误信息
string m_sError;
//保存请求分配内存用户信息
void **m_User;
};

};

//-------------------------------
//recalloc分配新内存后，之前指向旧内存的指针就失效了
//需要重新定位，之前分配对象的指向也要重新定位
namespace MemePool
{

/*****************************************
内存池构造函数
by 风清扬song 13-07-28
*****************************************/
CMemePool::CMemePool(const size_t &sInitialMemoryPoolSize,const size_t &sMemoryChunkSize)
{
//初始化内存池的大小
m_MemePollSize = sInitialMemoryPoolSize;
//初始化每个内存块的大小
m_MemLinkSize = sMemoryChunkSize;
//初始化一些参数
m_MemePoolFreeSize = 0;
m_MemePoolUseSize = 0;
m_Current = NULL;
m_LastNode = NULL;
m_Number = 0;
m_AllAloctsize = 0;

m_AllNumber = 0;
m_iUseObject = 0;
m_Head = new TMemeLinkNode;
m_Head->next = NULL;
m_Head->first = NULL;
m_Head->Data = NULL;
m_isFirst = true;
//分配线程池函数
AllocPoolMemeroy();

}

/*****************************************
内存池析构函数
by 风清扬song 13-07-28
****************/
CMemePool::~CMemePool()
{
FreeAllMemeroy();
}

/*****************************************
内存池分配内存函数
by 风清扬song 13-07-28
*****************************************/
void CMemePool::AllocPoolMemeroy()
{
//计算需要的链表节点数目
CalLinkNodeNum();
//计算真正要分配的内存大小
CalMemeSize();
m_AllNumber = m_AllNumber + m_Number;
m_AllAloctsize += m_MemePollSize;
m_MemePoolFreeSize += m_MemePollSize;
//追加分配内存，原有内存的内容不会受到影响
m_PAlloc = (EigthByte *)realloc(m_PAlloc,(m_AllAloctsize)*sizeof(EigthByte));

//内存分配失败
if(NULL == m_PAlloc)
{
m_sError = "Alloc Memeroy Pool Failture";
return;
}
//不是第一次分配内存
if(false == m_isFirst)
{ //新分配内存后原有指针全失效，需要重定向
ResetLinkToMemery();
}
//分配的内存内容初始化
// memset(((void *) PAlloc), NEW_ALLOCATED_MEMORY_CONTENT, m_MemePollSize) ;
//将分配的线程池内存与链表节点关联
LinkMemeryToNode(&m_PAlloc[m_AllAloctsize - m_MemePollSize]);
}

/*****************************************
将原内存的指针进行重定向（Alloc后原有内存可能被释放了）
by 风清扬song 13-07-28
*****************************************/
void CMemePool::ResetLinkToMemery()
{
TMemeLinkNode *pTemp = m_Head->next;
int iIndex = 0;
while(NULL != pTemp)
{
//重定向指针链表的指向
pTemp->Data = &m_PAlloc[iIndex * m_MemLinkSize];
if(NULL != pTemp->pUser)
{
//重定向用户指针的指向
*pTemp->pUser = pTemp->Data;
}
iIndex++;
pTemp = pTemp->next;
}
}

/*****************************************
计算需要的内存链表节点数目
by 风清扬song 13-07-28
*****************************************/
void CMemePool::CalLinkNodeNum()
{
float fTempValue = m_MemePollSize / m_MemLinkSize;
//向上取整需要的节点数目
m_Number = ceil(fTempValue);
}

/*****************************************
计算内存池真正分配的内存的大小
by 风清扬song 13-07-28
****/
void CMemePool::CalMemeSize()
{
m_MemePollSize = (size_t)(m_Number * m_MemLinkSize);
}

/*****************************************
将分配的内存和链表节点相关联
by 风清扬song 13-07-28
*****************************************/
void CMemePool::LinkMemeryToNode(EigthByte *PAlloc)
{
TMemeLinkNode *PNode;
//遍历每一个节点分配空间
for(size_t iIndex = 0; iIndex < m_Number ; iIndex ++)
{
PNode = new TMemeLinkNode();
if(NULL == m_LastNode)
{
PNode->next = m_Head->next;
m_Head->next = PNode;
PNode->first = m_Head;
m_LastNode = PNode;
}
else
{
PNode->next = m_LastNode->next;
m_LastNode->next = PNode;
PNode->first = m_LastNode;
m_LastNode = PNode;
}

m_LastNode->isUsed = false;
m_LastNode->idataSize = m_MemePollSize - iIndex * m_MemLinkSize;
m_LastNode->Data = &PAlloc[iIndex * m_MemLinkSize];
m_LastNode->isMemeBegin = false;
m_LastNode->pUser = NULL;
//记录内存块的首地址，释放时使用
if(true == m_isFirst && 0 == iIndex)
{
m_LastNode->isMemeBegin = true;
m_isFirst = false;
}
}
UpdateLinkNodeSize(m_LastNode);
}

/****
更新当前节点的前后大小值
by 风清扬song 13-07-28
*****************************************/
void CMemePool::UpdateLinkNodeSize(TMemeNode *PNode)
{
TMemeNode *PTemp;
PTemp = PNode->next;
int iDateSize = 0;
//当前节点的后一个节点没分配，得到它的DataSize值
if(NULL != PTemp && false == PTemp->isUsed)
{
iDateSize = PTemp->idataSize;
}
//由最后一个节点在向前遍历，更新所有的节点大小值
int iIndex = 1;
while(PNode != m_Head && false == PNode->isUsed)
{
PNode->idataSize = iIndex * m_MemLinkSize + iDateSize;
iIndex++;
PNode = PNode->first;
}

m_Current = PNode->next;
}

/*****************************************
分配内存空间
by 风清扬song 13-07-28
*****************************************/
void *CMemePool::GetMemeroy(void **p,const size_t &sSize)
{
m_MemePoolFreeSize -= sSize;
m_MemePoolUseSize += sSize;
//保存请求内存分配的用户信息
m_User = p;
//增加分配对象数目

m_iUseObject++;
//有合适的内存块
void *pFind = FindMemeNode(sSize);
if(NULL != pFind)
{
return pFind;
}

TMemeNode *PTemp;
PTemp = m_Current;
m_Current = m_Current->next;
//遍历内存块找到合适的内存
while(PTemp != m_Current)
{
//走到结尾，从头来
if(NULL == m_Current)
{
m_Current = mHead->next;
}

//跳过已经分配的节点
if(true == m_Current->isUsed)
{
m_Current = m_Current->pEndNode;
// m_Current = m_Current->first;
}

pFind = FindMemeNode(sSize);
if(NULL != pFind)
{
return pFind;
}

if(PTemp == m_Current)
{
break;
}

m_Current = m_Current->next;

}

//在当前的所有节点链表中没有合适的，新分配吧
m_MemePollSize = sSize;
AllocPoolMemeroy();
return FindMemeNode(sSize);
}

/*****************************************
计算所需的内存块数目
by 风清扬song 13-07-28
*****************************************/
void CMemePool::CalNeetLinkNumber(const size_t &sSize)
{
float fTempValue = sSize / m_MemLinkSize;
//向上取整需要的节点数目
m_Number = ceil(fTempValue);
if(0 == m_Number)
{
m_Number = 1;
}
}

/*****************************************
找到合适的内存分配节点了
by 风清扬song 13-07-28
*****************************************/
void* CMemePool::FindMemeNode(const size_t &sSize)
{
if(m_Current->idataSize >= sSize && false == m_Current->isUsed)
{
CalNeetLinkNumber(sSize);
size_t iIndex = 0;
TMemeLinkNode *pTemp = m_Current;
while(iIndex < m_Number)
{
m_Current->isUsed = true;
m_Current = m_Current->next;
iIndex++;
}
//保存分配内存的用户信息
pTemp->pUser = m_User;
//记录分配了几块内存，避免后续遍历
pTemp->pEndNode = m_Current->next;
return pTemp->Data;
}
else
{
return NULL;
}
}

/*****************************************
收回分配的内存块
by 风清扬song 13-07-28
*******************/
void CMemePool::FreeAllocMemeroy(void *p,const size_t &sSize)
{
//减少分配数目
m_iUseObject--;
m_MemePoolUseSize -= sSize;
m_MemePoolFreeSize += sSize;
TMemeNode *pFind = SearchAllocNode(p);
if(NULL == pFind)
{
m_sError = "can not find the alloc point,you may use wrong";
}
//恢复内存为初始化
//memset(((void *) pFind->Data), NEW_ALLOCATED_MEMORY_CONTENT, sSize) ;
//计算向后移动多少内存块
CalNeetLinkNumber(sSize);
size_t iIndex = 0;
while(iIndex != m_Number)
{
pFind->isUsed = false;
pFind = pFind->next;
iIndex++;
}
//内存归还后，更新前后节点的大小
UpdateLinkNodeSize(pFind->first);

}

/*****************************************
查找之前分配内存的节点
by 风清扬song 13-07-28
*****************************************/
TMemeNode * CMemePool::SearchAllocNode(void *p)
{
TMemeNode *PTemp = m_Head->next;
while(NULL != PTemp)
{
if(PTemp->Data == (EigthByte *) p)
{
//释放内存的用户清空之前保存的用户信息
PTemp->pUser = NULL;
return PTemp;
}
PTemp = PTemp->next;
}

return NULL;
}

/*****************************************
清空线程池
by 风清扬song 13-07-28
*****************************************/
void CMemePool:FreeAllMemeroy()
{
//所有内存对象都释放了
if(0 != m_iUseObject)
{
m_sError = "warning there is some object not release";
}
CleanAllMemeDate();
CleatAllLinkNode();
}

/*****************************************
清空向系统申请的内存
by 风清扬song 13-07-28
****************************************/
void CMemePool::CleanAllMemeDate()
{
TMemeLinkNode *pTemp = m_Head->next;
while(NULL != pTemp)
{
//内存被连城了一块，从首地址就可以全部删除
if(pTemp->isMemeBegin&&NULL != pTemp->Data)
{
delete []pTemp->Data;
return;
}
pTemp = pTemp->next;
}

}

/**************************
清空双向链表
by 风清扬song 13-07-28
*****************************************/
void CMemePool::CleatAllLinkNode()
{
TMemeLinkNode *pTemp = m_Head->next;
while(NULL != pTemp)
{
TMemeLinkNode *qTemp = pTemp;
pTemp = pTemp->next;
delete qTemp;
}
if(NULL != m_Head)
{
delete m_Head;
}

}

/*****************************************
显示内存池运行状态
by 风清扬song 13-07-28
*****************************************/
void CMemePool::ShowTheMemePoolStatue()
{
cout<<"\n\n\t\t\t内存池使用状况输出\t\t\t\n\n";
cout<<"\t\t总内存池大小:"<octsize<<"使用大小:"<next;
int iIndex = 1;
while(NULL != pTemp)
{
cout<<"\n内存池号:"<idataSize<<"\t\t是否被使用:"<isUsed<next;
}
}

};

测试代码：

int main(int argc, char* argv[])
{
CMemePool *g_ptrMemPool = new CMemePool() ;
char *ptrCharArray = (char *) g_ptrMemPool->GetMemeroy((void**)&ptrCharArray,700) ;

g_ptrMemPool->ShowTheMemePoolStatue();
char * ptrCharArrayB = (char *) g_ptrMemPool->GetMemeroy((void**)&ptrCharArrayB,80) ;
g_ptrMemPool->ShowTheMemePoolStatue();

char * ptrCharArrayC = (char *) g_ptrMemPool->GetMemeroy((void**)&ptrCharArrayC,400) ;

g_ptrMemPool->ShowTheMemePoolStatue();
g_ptrMemPool->FreeAllocMemeroy(ptrCharArray, 700) ;
g_ptrMemPool->ShowTheMemePoolStatue();
gptrMemPool->FreeAllocMemeroy(ptrCharArrayC, 400) ;

g_ptrMemPool->FreeAllocMemeroy(ptrCharArrayB, 80) ;

ptrCharArray = (char *) g_ptrMemPool->GetMemeroy((void**)&ptrCharArray,1300) ;
g_ptrMemPool->ShowTheMemePoolStatue();

for(int i=0; i< 1200; i++)
{
ptrCharArray[i] = 'a';
}

g_ptrMemPool->ShowTheMemePoolStatue();
char c = ptrCharArray[800];

g_ptrMemPool->FreeAllocMemeroy(ptrCharArray, 1300) ;
g_ptrMemPool->ShowTheMemePoolStatue();
delete g_ptrMemPool ;

std::cout << "MemoryPool Program finished..." << std::endl ;
system("PA