CMapPtrToPtr 的內(nèi)存管理問題
CMapPtrToPtr 類保存的是若干個(gè)映射項(xiàng)的集合。每個(gè)映射項(xiàng)保存了一對(duì)映射關(guān)系,一個(gè)稱為 鍵 ( key ),相當(dāng)于數(shù)學(xué)中的 x ,另一個(gè)稱為 值 ( value ),相當(dāng)于 y 。為了將這些映射關(guān)系連在一起,還要在每個(gè)映射項(xiàng)中記錄下下一個(gè)映射項(xiàng)的地址,所以可以用下面的 CAssoc 結(jié)構(gòu)表示一對(duì)映射關(guān)系。
// AFXCOLL.H
class CMapPtrToPtr : public CObject
{
protected:
// Association
struct CAssoc
{
CAssoc * pNext ;
void* key ;
void* value ;
};
protected:
int m_nCount ; // 記錄了程序一共使用了多少個(gè) CAssoc 結(jié)構(gòu),即關(guān)聯(lián)的個(gè)數(shù)
CAssoc * m_pFreeList ;
struct CPlex* m_pBlocks ;
int m_nBlockSize ;
CAssoc * NewAssoc ();
void FreeAssoc ( CAssoc *);
};
此結(jié)構(gòu)表示給定一個(gè) key ,僅有一個(gè) value 與它相對(duì)應(yīng)。如果有多組這樣一一對(duì)應(yīng)的數(shù)據(jù),就要在內(nèi)存中分配多個(gè)具有 CAssoc 結(jié)構(gòu)大小的空間來保存各成員的值。其中 pNext 成員將這些內(nèi)存塊 連在一起 。
按照這種鏈表的結(jié)構(gòu),假設(shè)用戶要用 CMapPtrToPtr 類保存成千上萬條中文和英文的對(duì)應(yīng)數(shù)據(jù),就要在內(nèi)存中 new 上萬個(gè) CAssoc 結(jié)構(gòu),調(diào)用這上萬個(gè) new 函數(shù)的開銷是多大?為了能夠正確的銷毀, new 函數(shù)又要向每個(gè) CAssoc 結(jié)構(gòu)中添加額外的信息( delete 靠這些記錄信息才能正確的釋放內(nèi)存),這又會(huì)浪費(fèi)多少內(nèi)存?
如此多大小相同的內(nèi)存塊不斷地被分配、釋放產(chǎn)生的結(jié)果是什么呢? 內(nèi)存碎片 。
如果兩個(gè) CAssoc 占用的是不連續(xù)的內(nèi)存空間,而且中間間隔的空間又恰好不足以容納另一個(gè) CAssoc 結(jié)構(gòu),就會(huì)有內(nèi)存碎片產(chǎn)生。通常解決這個(gè)問題的比較好的方法是 預(yù)先 為 CAssoc 結(jié)構(gòu)申請(qǐng)一塊比較大的內(nèi)存,當(dāng)要為 CAssoc 結(jié)構(gòu)分配空間的時(shí)候,并不真的申請(qǐng)新的空間,而是讓它使用上面 預(yù)留 的空間, 直到 這塊空間被使用完 再 申請(qǐng)新的空間。此即 內(nèi)存的池化管理( Memory Pool )。
寫一個(gè)分配內(nèi)存的全局函數(shù),每一次調(diào)用此函數(shù)都可以獲得一個(gè)指定大小的 內(nèi)存塊 來容納 多個(gè) CAssoc 結(jié)構(gòu)。另外,還 必須要有一種機(jī)制將此函數(shù)申請(qǐng)的內(nèi)存塊記錄下來 ,以便當(dāng) CMapPtrToPtr 類的對(duì)象銷毀的時(shí)候 釋放所有 內(nèi)存空間。在每個(gè)內(nèi)存塊 頭部 安排指向下一個(gè)內(nèi)存塊首地址的 pNext 指針就可以將所有內(nèi)存塊鏈接在一起了,這樣做的結(jié)果是每一個(gè)內(nèi)存塊都由 pNext 指針和真正的用戶數(shù)據(jù)組成,如下圖所示。只需要記錄下 pHead 指針就有辦法釋放所有內(nèi)存空間了。
內(nèi)存的組織形式(內(nèi)存鏈)
在每一塊內(nèi)存的頭部增加的數(shù)據(jù)可以用 CPlex 結(jié)構(gòu)來表示 。當(dāng)然,此結(jié)構(gòu)只有一個(gè) pNext 成員,但是為了方便,把分配內(nèi)存的全局函數(shù)以靜態(tài)函數(shù)的形式封裝到 CPlex 結(jié)構(gòu)中,把釋放內(nèi)存鏈的函數(shù)也封裝到其中。
CPlex 結(jié)構(gòu)
CPlex 結(jié)構(gòu)是真正進(jìn)行 CRT 動(dòng)態(tài)內(nèi)存分配操作的執(zhí)行者,它僅包含一個(gè)指針,指向另一個(gè) CPlex 對(duì)象以創(chuàng)建一個(gè) CPlex 鏈表,所以它的大小只為 4 字節(jié)。當(dāng)進(jìn)行內(nèi)存分配時(shí),就需要 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 是最終分配內(nèi)存的全局函數(shù),這個(gè)函數(shù)會(huì)將所分配的內(nèi)存添加到以 pHead 為首地址的內(nèi)存鏈中。參數(shù) pHead 是用戶提供的保存鏈中第一個(gè)內(nèi)存塊的首地址的指針。以后釋放此鏈的內(nèi)存時(shí),直接使用“ pHead->FreeDataChain() ”語句即可。下面是這些函數(shù)的具體實(shí)現(xiàn),應(yīng)放在 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 ;
}
}
這種管理內(nèi)存的方式很簡(jiǎn)單,也很實(shí)用。使用的時(shí)候除了調(diào)用 CPlex::Create 函數(shù)為小的結(jié)構(gòu)申請(qǐng)大的內(nèi)存空間以外,還要定義一個(gè) CPlex 類型的指針用于記錄整個(gè)鏈的首地址。下面的示例程序先用 CPlex::Create 函數(shù)申請(qǐng)了一大塊內(nèi)存,在使用完畢以后又通過 CPlex 指針將之釋放,代碼如下。
// CPlex 使用 例程
#include "afxplex_.h" // 包含定義 CPlex 結(jié)構(gòu)的文件
struct CMyData
{
int nSomeData;
int nSomeMoreData;
};
int main()
{
CPlex* pBlocks = NULL ; // 用于保存鏈中第一個(gè)內(nèi)存塊的首地址,必須被初始化為 NULL
CPlex:: Create (pBlocks, 10, sizeof(CMyData));
CMyData* pData = (CMyData*)pBlocks-> data ();
// 現(xiàn)在 pData 是 CPlex::Create 函數(shù)申請(qǐng)的 10 個(gè) CMyData 結(jié)構(gòu)的首地址
//... // 使用 pData 指向的內(nèi)存
// 使用完畢,繼續(xù)申請(qǐng)
CPlex:: Create (pBlocks, 10, sizeof(CMyData));
pData = (CMyData*)pBlocks-> data ();
// 最后釋放鏈中的所有內(nèi)存塊
pBlocks-> FreeDataChain ();
return 0;
}
CPlex::Create 函數(shù)是 CPlex 的靜態(tài)成員,使用起來就相當(dāng)于全局函數(shù),所以上面的代碼直接調(diào)用 CPlex::Create 函數(shù)來為 CMyData 結(jié)構(gòu)申請(qǐng)一塊大的空間,空間的首地址返回給 pBlocks 變量。
最后的一條語句會(huì)釋放掉前面 CPlex::Create 申請(qǐng)的全部空間。
CMapPtrToPtr 的內(nèi)存管理方案
由于 CAssoc 結(jié)構(gòu)只會(huì)被 CMapPtrToPtr 類使用,所以把它的定義放在了類中。 NewAssoc 函數(shù)負(fù)責(zé)在預(yù)留的空間中給 CAssoc 結(jié)構(gòu)分配空間,如果預(yù)留的空間已經(jīng)使用完了,它會(huì)調(diào)用 CPlex::Create 函數(shù)申請(qǐng) m_nBlockSize*sizeof(CAssoc) 大小的內(nèi)存塊,代碼如下。
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 結(jié)構(gòu)連成了一個(gè)空閑鏈,成員 m_pFreeList 是這個(gè)鏈的頭指針。
這是 CAssoc 結(jié)構(gòu)中 pNext 成員的一個(gè)重要應(yīng)用。為 CAssoc 結(jié)構(gòu)分配新的內(nèi)存( NewAssoc )或釋放 CAssoc 結(jié)構(gòu)占用的內(nèi)存( FreeAssoc )都是圍繞 m_pFreeList 指向的空閑鏈進(jìn)行的。類的構(gòu)造函數(shù)會(huì)初始化 m_pFreeList 的值為 NULL ,所以在第一次調(diào)用 NewAssoc 函數(shù)的時(shí)候程序會(huì)申請(qǐng)新的內(nèi)存塊,此內(nèi)存塊的頭部是一個(gè) CPlex 結(jié)構(gòu),緊接著是可以容納 m_nBlockSize 個(gè) CAssoc 結(jié)構(gòu)的空間, m_pBlocks 成員保存的是內(nèi)存塊鏈的頭指針,以后還要通過該成員調(diào)用 FreeDataChain 函數(shù)釋放所有的內(nèi)存塊。申請(qǐng)新的內(nèi)存塊以后就要向空閑鏈中添加元素了。真正從空閑鏈中移去元素的過程是很簡(jiǎn)單的,同 FreeAssoc 函數(shù)向空閑鏈中添加元素的過程非常相似,都是要改變頭指針 m_pFreeList 。
CMap* 系列和 C*List 系列均采用基于 CPlex 結(jié)構(gòu)的內(nèi)存池化管理。
CFixedAlloc 類簡(jiǎn)介
基于 CPlex 結(jié)構(gòu)的 CFixedAlloc 類( FIXALLOC.H/ FIXALLOC.CPP )保存的是若干節(jié)點(diǎn) CNode 的集合。 這里 CNode 只有一個(gè)成員 CNode* pNext , pNext 指向下一個(gè)節(jié)點(diǎn),以便鏈化管理。實(shí)際應(yīng)用中, CNode 會(huì)有實(shí)際的數(shù)據(jù)成員,因此其構(gòu)造函數(shù)中 ASSERT (nAllocSize >= sizeof(CNode));
CFixedAlloc 是一個(gè)非常簡(jiǎn)單的類,它由臨界區(qū) m_protect 提供線程安全。 m_nAllocSize 中包含了類的對(duì)象大小, m_nBlockSize 指定了每個(gè)固定內(nèi)存塊能包含的對(duì)象數(shù),這兩個(gè)成員都在構(gòu)造函數(shù)中設(shè)置。
在類聲明中添加 DECLARE_FIXED_ALLOC() 宏,在含有類定義的 CPP 文件中添加 IMPLEMENT_FIXED_ALLOC() 宏,這樣該類將調(diào)用 CFixedAlloc 類(重載 了 operator new 和 operator delete )對(duì)內(nèi)存進(jìn)行優(yōu)化管理。
參考:
《 Windows 程序設(shè)計(jì)》王艷平
《 用未公開的 MFC 類加強(qiáng)動(dòng)態(tài)內(nèi)存分配 》
《 池內(nèi)春秋 -Memory Pool 的 設(shè)計(jì)哲學(xué)和無痛運(yùn)用 》
《 C++ Memory Pool 》
《 一種自適應(yīng)變長(zhǎng)塊內(nèi)存池 》
《 基于 C 語言的內(nèi)存池的設(shè)計(jì)與實(shí)現(xiàn) 》
《 young library 的輕量級(jí)內(nèi)存池設(shè)計(jì)與實(shí)現(xiàn) 》
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號(hào)聯(lián)系: 360901061
您的支持是博主寫作最大的動(dòng)力,如果您喜歡我的文章,感覺我的文章對(duì)您有幫助,請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點(diǎn)擊下面給點(diǎn)支持吧,站長(zhǎng)非常感激您!手機(jī)微信長(zhǎng)按不能支付解決辦法:請(qǐng)將微信支付二維碼保存到相冊(cè),切換到微信,然后點(diǎn)擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
