一个超简单的内存池.doc

一个简单的内存池Memory-PoolSUNNY.MAN内存池(Memory Pool)是一种内存分配方式。 通常我们习惯直接使用new、malloc等API申请分配内存，这样做的缺点在于：由于所申请内存块的大小不定，当频繁使用时会造成大量的内存碎片并进而降低性能。内存池则是在真正使用内存之前，先申请分配一定数量的、大小相等的内存块留作备用。当有新的内存需求时，就从内存池中分出一部分内存块，若内存块不够再继续申请新的内存。这样做的一个显著优点是尽量避免了内存碎片，使得内存分配效率得到提升。有不少地方内存分配不允许失败. 作为在这些情况下确保分配的方式开发者创建了一个已知为内存池(或者是 mempool )的抽象. 这种内存的分配方式优点是内存分配肯定成功，缺点在于占用大量内存。一般来说做为缓存我强烈建议使用循环队列。当然不得不用的情况下可以使用所谓的“内存池”。一块固定的内存,被分成很多小块应用在不同的地方。当不再使用时把这小块归还给内存池，再使用的时候，内存池根据一定的算法，重新划分一块符合要求的内存给需要的线程。一般来说内存池的结构如下图所示：结构中主要包含block、list 和pool这三个结构体，block结构包含指向实际内存空间的指针，前向和后向指针让block能够组成双向链表；list结构中free指针指向空闲内存块组成的链表，used指针指向程序使用中的内存块组成的链表，size值为内存块的大小，list之间组成单向链表；pool结构记录list链表的头和尾。本例中仅有一个list链表所以pool结构没有使用.所以结构如下图所示：其中每一个block为分配的内存块，在本例中每一个内存块对应内存大小+12个字节。4个字节为开始的位置，4个字节为结束的位置，4个字节为指针的位置。为什么要记录指针的值呢，因为释放的时候，我们要找到这个空间并把它归还给内存池。内存池的内存申请：根据所申请内存的大小，遍历Freelist链表，查看是否存在相匹配size,在这里这个”匹配”是需要根据算法来遍历计算的。我这个例子中，仅是找一个大小最为相近的来分配。如果所有Freelist链表中都没有符合这个SIZE的块，则分配失败。分配成功后移动刚才块的头指针到新位置，并把新分配的块信息块加入到Allocate链表中。 内存池的内存释放:把已经不再使用的内存释放还给内存池。释放时首先从分配链表里，把那个信息块删除。然后再未分配链表中，把这信息块加入。如果头或是尾或是头尾有和链表中已经存在的块重合的，则合并。如果都没有，则把它插按开始的顺序进行插入。简单代码如下：1.定义信息块描述结构typedef struct Nodeinfo int nStart;/开始位置 int nEnd;/结束位置 BYTE *pBuf;/所在的内存地址值_tagNodeinfo;2.成员变量BYTE *m_pMem;/整个内存池的指针 CListm_listAllocate;/已经分配的块链表 CListm_listFree;/空闲的块链表 long m_nCount;/整个内存池的大小3.接口函数CMYNew(int nMB=50*1024*1024);/默认大小为50MCMYNew(void);BYTE *MyAllocate(int nCount);/用来分配内存void MyFree(BYTE *pbuf);/通过指针来释入内存void Display();/显示分配链表和空闲链表的存储情况4.构造函数的实现m_nCount=nMB;m_pMem=new BYTE(nMB);m_nLastError=NOERROR;if(!m_pMem)m_nLastError=NOMEMORY;else Nodeinfo *newNode=new Nodeinfo; newNode-nStart=0; newNode-nEnd=nMB-1;/整体是一个块，空闲链表中的指针值没有意义 m_listFree.AddTail(newNode);/加入空闲链表5.析构函数的实现if(m_pMem)delete m_pMem;/删除内存m_pMem=NULL;/释放未用内存链表中的信息块POSITION pos=m_listFree.GetHeadPosition();while(pos)Nodeinfo *pNode=m_listFree.GetAt(pos); if(pNode)delete pNode;m_listFree.GetNext(pos);m_listFree.RemoveAll();/ 释放已分配内存块的地址pos=m_listAllocate.GetHeadPosition();while(pos)Nodeinfo *pNode=m_listAllocate.GetAt(pos);if(pNode)delete pNode;m_listAllocate.GetNext(pos);m_listAllocate.RemoveAll();5.内存池的内存分配BYTE *CMYNew:MyAllocate(int nCount) BYTE *pbuf=NULL; Nodeinfo *nodeinfo=NULL; POSITION pos=m_listFree.GetHeadPosition(); POSITION posEqual=0; BOOL bEqual=FALSE; while(pos) Nodeinfo *pNode=m_listFree.GetAt(pos); if(pNode) if(pNode-nEnd-pNode-nStart)nCount) if(nodeinfo) if(nodeinfo-nEnd-nodeinfo-nStartpNode-nEnd-pNode-nStart) nodeinfo=pNode;/空间更小者 /if nodeinfo else/第一个匹配项 nodeinfo=pNode; else if(pNode-nEnd-pNode-nStart)=nCount)/最匹配 nodeinfo=pNode; bEqual=TRUE; posEqual=pos; break; /=nCoun /如果有空间pNode m_listFree.GetNext(pos); /while pos if(nodeinfo)/可以分配 pbuf=&m_pMemnodeinfo-nStart;if(bEqual) nodeinfo-pBuf=pbuf; m_listAllocate.AddTail(nodeinfo);/加到已分配中 m_listFree.RemoveAt(posEqual);/从空闲中移除else Nodeinfo *pnewAll=new Nodeinfo; pnewAll-nStart= nodeinfo-nStart; pnewAll-nEnd=pnewAll-nStart+nCount-1;/结尾 m_listAllocate.AddTail(pnewAll);/加到已分配中 nodeinfo-nStart+=nCount;/改没分配 pnewAll-pBuf=pbuf;/是否全部分完 / Display(); return pbuf;6.内存池的释放void CMYNew:MyFree(BYTE *pbuf) Nodeinfo *pNodeInfoResult=NULL; POSITION pos=m_listAllocate.GetHeadPosition(); while(pos) Nodeinfo *pNodeInfo=m_listAllocate.GetAt(pos); if(pNodeInfo) if(pNodeInfo-pBuf=pbuf)/如果是这块 pNodeInfoResult=pNodeInfo; m_listAllocate.RemoveAt(pos);/移除 break; /if podeinfo m_listAllocate.GetNext(pos); /while / BOOL bTreatFree=FALSE; if(pNodeInfoResult)/如果已经可以删除 pos=m_listFree.GetHeadPosition(); while(pos) Nodeinfo *pNodeInfo=m_listFree.GetAt(pos); if(pNodeInfo) if(pNodeInfo-nEnd+1=pNodeInfoResult-nStart)/如果恰好是一空闲的尾部则合并 pNodeInfo-nEnd=pNodeInfoResult-nEnd;/合并 m_listFree.GetNext(pos);/看后面的 if(pos) Nodeinfo *pNodeInfo1= m_listFree.GetAt(pos); if(pNodeInfo1) if(pNodeInfo1-nStart=pNodeInfo-nEnd+1) pNodeInfo-nEnd=pNodeInfo1-nEnd;/再次扩大空闲区m_listFree.RemoveAt(pos);/移除这个点delete pNodeInfo1; /也恰好是别一个点的开始 /后面的Pos delete pNodeInfoResult;/删除 pNodeInfoResult=NULL; / bTreatFree=TRUE; break; /恰好是空闲尾 if(pNodeInfo-nStart=pNodeInfoResult-nEnd+1)/如果恰好是一空闲的头部则合并 pNodeInfo-nStart=pNodeInfoResult-nStart;/合并 m_listFree.GetPrev(pos);/看前面的 if(pos) Nodeinfo *pNodeInfo1= m_listFree.GetAt(pos); if(pNodeInfo1) if(pNodeInfo1-nEnd+1=pNodeInfo-nStart) pNodeInfo-nStart=pNodeInfo1-nStart;/再次扩大空闲区 m_listFree.RemoveAt(pos);/移除这个点 delete pNodeInfo1; /也恰好是别一个点的开始 /后面的Pos delete pNodeInfoResult;/删除 pNodeInfoResult=NULL; / bTreatFree=TRUE; break; /恰好是空闲尾 /pNodeInfo m_listFree.GetNext(pos); /while if(pNodeInfoResult)/只是一块闲存 BOOL bIinsert=FALSE; pos=m_listFree.GetHeadPosition();while(pos)Nodeinfo *pNodeInfo=m_listFree.GetAt(pos);if(pNodeInfo)if(pNodeInfo-nStartpNodeInfoResult-nStart)/如果是这块 m_listFree.InsertBefore(pos,pNodeInfoResult);bIinsert=TRUE;break;/if podeinfom_listFree.GetNext(pos);/while if(bIinsert=FALSE)m_listFree.AddTail(pNodeInfoResult); /if可以删除 / Display();7.显示函数void CMYNew:Display()POSITION pos=m_listFree.GetHeadPosition();while(pos)Nodeinfo *pNode=m_listFree.GetAt(pos);if(pNode) TRACE(LFree%d-%dn,pNode-nStart,pNode-nEnd);m_li