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 的輕量級內存池設計與實現 》
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
