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;
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程序设计》王艳平
《基于C语言的内存池的设计与实现》
