CMapPtrToPtr 的内存管理问题
CMapPtrToPtr 类保存的是若干个映射项的集合。每个映射项保存了一对映射关系，一个称为 键 （ key ），相当于数学中的 x ，另一个称为 值 （ value ），相当于 y 。为了将这些映射关系连在一起，还要在每个映射项中记录下下一个映射项的地址，所以可以用下面的 CAssoc 结构表示一对映射关系。
// AFXCOLL.H
class CMapPtrToPtr : public CObject
{
protected:
// Association
struct CAssoc
{
CAssoc * pNext ;
void* key ;
void* value ;
};
protected:
int m_nCount ; // 记录了程序一共使用了多少个 CAssoc 结构，即关联的个数
CAssoc * m_pFreeList ;
struct CPlex* m_pBlocks ;
int m_nBlockSize ;
CAssoc * NewAssoc ();
void FreeAssoc ( CAssoc *);
};
此结构表示给定一个 key ，仅有一个 value 与它相对应。如果有多组这样一一对应的数据，就要在内存中分配多个具有 CAssoc 结构大小的空间来保存各成员的值。其中 pNext 成员将这些内存块 连在一起 。
按照这种链表的结构，假设用户要用 CMapPtrToPtr 类保存成千上万条中文和英文的对应数据，就要在内存中 new 上万个 CAssoc 结构，调用这上万个 new 函数的开销是多大？为了能够正确的销毁， new 函数又要向每个 CAssoc 结构中添加额外的信息（ delete 靠这些记录信息才能正确的释放内存），这又会浪费多少内存？
如此多大小相同的内存块不断地被分配、释放产生的结果是什么呢？ 内存碎片 。
如果两个 CAssoc 占用的是不连续的内存空间，而且中间间隔的空间又恰好不足以容纳另一个 CAssoc 结构，就会有内存碎片产生。通常解决这个问题的比较好的方法是 预先 为 CAssoc 结构申请一块比较大的内存，当要为 CAssoc 结构分配空间的时候，并不真的申请新的空间，而是让它使用上面 预留 的空间， 直到 这块空间被使用完 再 申请新的空间。此即 内存的池化管理（ Memory Pool ）。
写一个分配内存的全局函数，每一次调用此函数都可以获得一个指定大小的 内存块 来容纳 多个 CAssoc 结构。另外，还 必须要有一种机制将此函数申请的内存块记录下来 ，以便当 CMapPtrToPtr 类的对象销毁的时候 释放所有 内存空间。在每个内存块 头部 安排指向下一个内存块首地址的 pNext 指针就可以将所有内存块链接在一起了，这样做的结果是每一个内存块都由 pNext 指针和真正的用户数据组成，如下图所示。只需要记录下 pHead 指针就有办法释放所有内存空间了。
内存的组织形式（内存链）
在每一块内存的头部增加的数据可以用 CPlex 结构来表示 。当然，此结构只有一个 pNext 成员，但是为了方便，把分配内存的全局函数以静态函数的形式封装到 CPlex 结构中，把释放内存链的函数也封装到其中。
CPlex 结构
CPlex 结构是真正进行 CRT 动态内存分配操作的执行者，它仅包含一个指针，指向另一个 CPlex 对象以创建一个 CPlex 链表，所以它的大小只为 4 字节。当进行内存分配时，就需要 sizeof(CPlex) + nMax * cbElement 。
// AFXPLEX_.H
struct CPlex // warning variable length structure
{
CPlex* pNext ; // chaining pointer
#if ( _AFX_PACKING >= 8)
DWORD dwReserved [1]; // align on 8 byte boundary
#endif
// BYTE data[maxNum*elementSize];
void* data () { return this+1; } // pay attention to this+1,skip all members of CPlex,the offset is sizeof(CPlex))
static CPlex* PASCAL Create (CPlex*& head, UINT nMax , UINT cbElement);
// like 'calloc' but no zero fill
// may throw memory exceptions
void FreeDataChain (); // free this one and links
};
CPlex:: Create 是最终分配内存的全局函数，这个函数会将所分配的内存添加到以 pHead 为首地址的内存链中。参数 pHead 是用户提供的保存链中第一个内存块的首地址的指针。以后释放此链的内存时，直接使用“ pHead->FreeDataChain() ”语句即可。下面是这些函数的具体实现，应放在 PLEX.CPP 文件中。
// PLEX.CPP
CPlex* PASCAL CPlex:: Create (CPlex*& pHead , UINT nMax , UINT cbElement)
{
ASSERT ( nMax > 0 && cbElement > 0);
CPlex* p = (CPlex*) new BYTE [sizeof(CPlex) + nMax * cbElement];
// may throw exception
p -> pNext = pHead ;
pHead = p ; // change head (adds in reverse order for simplicity)
return p ;
}
void CPlex:: FreeDataChain () // free this one and links
{
CPlex* p = this;
while ( p != NULL )
{
BYTE * bytes = ( BYTE *) p ; // every object is a block of bytes
CPlex* pNext = p -> pNext ;
delete[] bytes;
p = pNext ;
}
}
这种管理内存的方式很简单，也很实用。使用的时候除了调用 CPlex::Create 函数为小的结构申请大的内存空间以外，还要定义一个 CPlex 类型的指针用于记录整个链的首地址。下面的示例程序先用 CPlex::Create 函数申请了一大块内存，在使用完毕以后又通过 CPlex 指针将之释放，代码如下。
// CPlex 使用 例程
#include "afxplex_.h" // 包含定义 CPlex 结构的文件
struct CMyData
{
int nSomeData;
int nSomeMoreData;
};
int main()
{
CPlex* pBlocks = NULL ; // 用于保存链中第一个内存块的首地址，必须被初始化为 NULL
CPlex:: Create (pBlocks, 10, sizeof(CMyData));
CMyData* pData = (CMyData*)pBlocks-> data ();
// 现在 pData 是 CPlex::Create 函数申请的 10 个 CMyData 结构的首地址
//... // 使用 pData 指向的内存
// 使用完毕，继续申请
CPlex:: Create (pBlocks, 10, sizeof(CMyData));
pData = (CMyData*)pBlocks-> data ();
// 最后释放链中的所有内存块
pBlocks-> FreeDataChain ();
return 0;
}
CPlex::Create 函数是 CPlex 的静态成员，使用起来就相当于全局函数，所以上面的代码直接调用 CPlex::Create 函数来为 CMyData 结构申请一块大的空间，空间的首地址返回给 pBlocks 变量。
最后的一条语句会释放掉前面 CPlex::Create 申请的全部空间。
CMapPtrToPtr 的内存管理方案
由于 CAssoc 结构只会被 CMapPtrToPtr 类使用，所以把它的定义放在了类中。 NewAssoc 函数负责在预留的空间中给 CAssoc 结构分配空间，如果预留的空间已经使用完了，它会调用 CPlex::Create 函数申请 m_nBlockSize*sizeof(CAssoc) 大小的内存块，代码如下。
CMapPtrToPtr ::CAssoc* CMapPtrToPtr :: NewAssoc ()
{
if ( m_pFreeList == NULL )
{
// add another block
CPlex* newBlock = CPlex:: Create ( m_pBlocks , m_nBlockSize , sizeof( CMapPtrToPtr ::CAssoc));
// chain them into free list
CMapPtrToPtr ::CAssoc* pAssoc = ( CMapPtrToPtr ::CAssoc*) newBlock -> data ();
// free in reverse order to make it easier to debug
pAssoc += m_nBlockSize - 1;
for ( int i = m_nBlockSize -1; i >= 0; i --, pAssoc --)
{
pAssoc -> pNext = m_pFreeList ;
m_pFreeList = pAssoc ;
}
}
ASSERT ( m_pFreeList != NULL ); // we must have something
CMapPtrToPtr ::CAssoc* pAssoc = m_pFreeList ;
m_pFreeList = m_pFreeList -> pNext ;
m_nCount ++;
ASSERT ( m_nCount > 0); // make sure we don't overflow
pAssoc -> key = 0;
pAssoc -> value = 0;
return pAssoc ;
}
void CMapPtrToPtr :: FreeAssoc ( CMapPtrToPtr ::CAssoc* pAssoc )
{
// just recycle to free list,not really free
pAssoc -> pNext = m_pFreeList ;
m_pFreeList = pAssoc ;
m_nCount --;
ASSERT ( m_nCount >= 0); // make sure we don't underflow
// if no more elements, cleanup completely
if ( m_nCount == 0)
RemoveAll ();
}
CMapPtrToPtr 中 没有被使用的 CAssoc 结构连成了一个空闲链，成员 m_pFreeList 是这个链的头指针。
这是 CAssoc 结构中 pNext 成员的一个重要应用。为 CAssoc 结构分配新的内存（ NewAssoc ）或释放 CAssoc 结构占用的内存（ FreeAssoc ）都是围绕 m_pFreeList 指向的空闲链进行的。类的构造函数会初始化 m_pFreeList 的值为 NULL ，所以在第一次调用 NewAssoc 函数的时候程序会申请新的内存块，此内存块的头部是一个 CPlex 结构，紧接着是可以容纳 m_nBlockSize 个 CAssoc 结构的空间， m_pBlocks 成员保存的是内存块链的头指针，以后还要通过该成员调用 FreeDataChain 函数释放所有的内存块。申请新的内存块以后就要向空闲链中添加元素了。真正从空闲链中移去元素的过程是很简单的，同 FreeAssoc 函数向空闲链中添加元素的过程非常相似，都是要改变头指针 m_pFreeList 。
CMap* 系列和 C*List 系列均采用基于 CPlex 结构的内存池化管理。
CFixedAlloc 类简介
基于 CPlex 结构的 CFixedAlloc 类（ FIXALLOC.H/ FIXALLOC.CPP ）保存的是若干节点 CNode 的集合。 这里 CNode 只有一个成员 CNode* pNext ， pNext 指向下一个节点，以便链化管理。实际应用中， CNode 会有实际的数据成员，因此其构造函数中 ASSERT (nAllocSize >= sizeof(CNode));
CFixedAlloc 是一个非常简单的类，它由临界区 m_protect 提供线程安全。 m_nAllocSize 中包含了类的对象大小， m_nBlockSize 指定了每个固定内存块能包含的对象数，这两个成员都在构造函数中设置。
在类声明中添加 DECLARE_FIXED_ALLOC() 宏，在含有类定义的 CPP 文件中添加 IMPLEMENT_FIXED_ALLOC() 宏，这样该类将调用 CFixedAlloc 类（重载 了 operator new 和 operator delete ）对内存进行优化管理。
参考：
《 Windows 程序设计》王艳平
《 池內春秋 -Memory Pool 的 設計哲學和無痛運用 》
《 Apache 内存池内幕 》
《 碎片式内存池的可行性分析 》
《 C++ Memory Pool 》
《 一种自适应变长块内存池 》
《 基于 C 语言的内存池的设计与实现 》
《 young library 的轻量级内存池设计与实现 》
