第一種情況的前後合併時，需要刪除一個預留空間（看順序）並且刪除釋放節點，最後只留下一個節點，第二種情況首先向前合併，同時刪除B的釋放內存節點和A的預留空間，將AllocAddr移動到B的起始地址完成內存釋放.使用下面的代碼實現刪除釋放內存節點

__inline MemoryNode *PX_MemoryPool_GetFreeTable(unsigned int Index)
{
//index不可能大於等於節點數目，下斷言
assert(Index<G_MemoryPool.FreeTableCount);
//索引加1
Index++;
//向前偏移返回memoryNode的地址
return (MemoryNode *)((unsigned char *)G_MemoryPool.EndAddr-(sizeof(MemoryNode)*Index)+1);
}

void PX_MemoryPoolRemoveFreeNode(unsigned int Index)
{
unsigned int i;
MemoryNode *pFreeNode=PX_MemoryPool_GetFreeTable(Index);
//將之前的節點前移實現移除這個節點
for (i=Index;i<G_MemoryPool.FreeTableCount;i++)
{
(*pFreeNode)=*(pFreeNode-1);
pFreeNode--;
}
//釋放內存節點數減1
G_MemoryPool.FreeTableCount--;
}
最後，依照上述的幾種情況編寫內存釋放函數

void PX_Free( void *pAddress )
{
unsigned int i,sIndex;
MemoryNode *itNode;//迭代指針
MemoryNode FreeNode;//釋放內存節點
unsigned char *pcTempStart,*pcTempEnd;
unsigned char bExist;

bExist=0;
//依據地址得到內存信息節點
FreeNode=*(MemoryNode *)((unsigned char *)pAddress-sizeof(MemoryNode));
//重置內存節點的開始位置
FreeNode.StartAddr=(unsigned char *)FreeNode.StartAddr-sizeof(MemoryNode);

//假如這個節點是最後一個節點,也就是結束地址後一個就是AllocAddr
if ((char *)FreeNode.EndAddr+1==(char *)G_MemoryPool.AllocAddr)
{
//向前搜索是否有可以拼接的節點
for(i=0;i<G_MemoryPool.FreeTableCount;i++)
{
itNode=PX_MemoryPool_GetFreeTable(i);
if ((char *)itNode->EndAddr+1==(char *)FreeNode.StartAddr)
{
//如果有,將AllocAddr的地址移到那個節點的開始地址
G_MemoryPool.AllocAddr=itNode->StartAddr;
//恢復釋放節點的空間到FreeSize同時刪除預留空間的地址
G_MemoryPool.FreeSize+=((char*)FreeNode.EndAddr-(char *)FreeNode.StartAddr+sizeof(MemoryNode)+1);
//恢複合並的空間到FreeSize
G_MemoryPool.FreeSize+=(char*)itNode->EndAddr-(char *)itNode->StartAddr+1+sizeof(MemoryNode);
//移除這個節點
PX_MemoryPoolRemoveFreeNode(i);
//處理完成,返回
return;

}
}
//如果沒有需要拼接的節點,將AllocAddr直接連接到起始地址
G_MemoryPool.AllocAddr=(char *)FreeNode.StartAddr;
//恢復佔用的空間和預留空間
G_MemoryPool.FreeSize+=((char*)FreeNode.EndAddr-(char *)FreeNode.StartAddr+sizeof(MemoryNode)+1);
return;
}

//不是特殊情況

//記錄前一次連接索引的節點,若為0xfffffff表示沒有,如果有下一次連接節點且上一個節點存在,則刪除前一次的節點
sIndex=0xffffffff;

//查找是否有可連接的節點
for(i=0;i<G_MemoryPool.FreeTableCount;i++)
{
itNode=PX_MemoryPool_GetFreeTable(i);
pcTempStart=(unsigned char *)itNode->StartAddr;
pcTempEnd=(unsigned char *)itNode->EndAddr;
//查找是否有可以向後連接的節點
if (pcTempStart==(unsigned char *)FreeNode.EndAddr+1)
{
//如果有,按照之前所述連接節點
if(sIndex==0xffffffff)
{
sIndex=i;
//Refresh this node
itNode->StartAddr=FreeNode.StartAddr;
FreeNode=*itNode;
G_MemoryPool.FreeSize+=sizeof(MemoryNode); }
else
{
itNode->StartAddr=FreeNode.StartAddr;
G_MemoryPool.FreeSize+=sizeof(MemoryNode);
PX_MemoryPoolRemoveFreeNode(sIndex);
}
bExist=1;
}

//查找是否有可以向前連接的節點
if (pcTempEnd+1==(unsigned char *)FreeNode.StartAddr)
{
//如果有,按照之前所述連接節點
if(sIndex==0xffffffff)
{
sIndex=i;
//Refresh this node
itNode->EndAddr=FreeNode.EndAddr;
FreeNode=*itNode;
//移除上一個節點
G_MemoryPool.FreeSize+=sizeof(MemoryNode);
}
else
{
itNode->EndAddr=FreeNode.EndAddr;
G_MemoryPool.FreeSize+=sizeof(MemoryNode);
//移除上一個節點
PX_MemoryPoolRemoveFreeNode(sIndex);
}
bExist=1;
}
}
//如果沒有連接節點,分配釋放內存節點
if(bExist==0)
*PX_AllocFreeMemoryNode()=FreeNode;

//這個函數用於更新最大的釋放內存節點大小
PX_UpdateMaxFreqSize();

}

分配內存

從空閑空間中分配內存

在上一個章節的」 分割一塊可用的內存」,」不能失敗的內存釋放」中,給出了這個空閑空間分配內存的方法與分配代碼,在這裡就不再複述了,它的流程非常簡單

1. 分割出一塊合適的空間大小
2. 初始化內存節點
3. 預留空間
4. 返回起始地址

短短几步,就能夠完成空閑空間的內存分配,當內存空間不夠時,返回0

從已釋放內存中分配內存

回收內存再分配,是一個內存池能否能夠持續良好持續運行的一個必要功能,同時,這也常常成為碎片產生的原因.但是內存池是否能夠完全避免產生碎片呢,當然這並不是不可能的,但是付出的代價往往不值得我們這樣去做.所以,內存碎片,儘可能的減少卻不能夠完全避免.

那麼應該如何減少碎片呢,其實這和環境與用法有很大的不同,一個老練的碼農往往喜歡把內存分配到2的整數冪,這也對減少碎片有很大的幫助,比如你分配了一個64位元組大小的內存釋放之後又分配一個32位元組和4個8位元組的內存,剛好就填充了之前的空間,越小的內存分配越容易填充之前的碎片,當然,假如你申請的內存和釋放的內存一直保持一致的大小,這個碎片也就能夠最大程度的消除了.

過多的碎片不僅佔用了不必要的內存空間,也拖慢了再分配和釋放,因此,內存分配並不僅僅只是演算法上的,很多時候也是使用和習慣上的.

那麼如果需要從已分配內存當中新分配內存應該怎麼辦呢,我們先來討論一下不產生碎片的情況,最直觀的是,你釋放了一個內存的大小,剛好就是你想再分配內存的大小,這是無縫的,自然不會產生碎片.但是我們不能就僅僅止步於此,我們再來看看內存的結構,

是的,在PainterEngine內存池結構中,分配一個size大小的內存,需要size+2*sizeof(MemoryNode)大小的內存空間,分配內存分配的大小,是我們主觀上的大小,我們為其多分配一些內存空間,並不會出什麼大不了的問題,比如你申請 16位元組大小,而我分配了32位元組給你,多餘的位元組並不會對其它功能造成影響,頂多我不知道不用就是了,而且這樣比我們分割這個已經釋放的內存空間更有好處,畢竟,為新劃分的空間需要預留額外的sizeof(MemoryNode)大小的空間而且也會照成碎片,那麼,我們可以這樣規定

假如已經釋放的內存大小大於等於size並且小於sizeof(MemoryNode)+size,我們就將這個已經釋放的內存全部分配給需求的內存.

當然,我們不可能期待每個已經釋放內存都像上面一樣,很多時候,我們釋放了大小為128位元組的空間,下一次卻只需要32位元組的內存空間,把這個128位元組的釋放空間都分配給這個只需要32位元組的內存節點,顯然是太過的浪費了,這個時候,我們必須要對內存進行分割

分割並不複雜,只需要把原先的釋放內存首地址作為分配內存的首地址,填充MemoryNode節點,然後將結束地址+1替換到原來的釋放內存節點的首地址就可以了,同時別忘了預留一個內存節點的空間.

MemoryNode *PX_AllocFromFreq(unsigned int Size)
{
unsigned int i,fSize;
MemoryNode *itNode,*allocNode;

//大小加上頭部內存節點需要空間
Size+=sizeof(MemoryNode);
//比對最大已釋放內存大小,若小於,分配肯定是失敗的
if (G_MemoryPool.MaxMemoryfragSize>=Size)
{
//開始搜索滿足條件的節點
for(i=0;i<G_MemoryPool.FreeTableCount;i++)
{

itNode=PX_MemoryPool_GetFreeTable(i);
//計算節點大小
fSize=(char *)itNode->EndAddr-(char *)itNode->StartAddr+1;
//滿足內存節點完全分配的情況
if (Size<=fSize&&(Size+sizeof(MemoryNode)>fSize))
{
//初始化新的內存節點
allocNode=(MemoryNode *)itNode->StartAddr;
allocNode->StartAddr=(char *)itNode->StartAddr+sizeof(MemoryNode);
allocNode->EndAddr=itNode->EndAddr;
//因為是完全分配,直接刪除原來的節點,因為空間已經預留過了,所以不需要預留空間
PX_MemoryPoolRemoveFreeNode(i);
//重新跟新最大釋放內存節點大小
PX_UpdateMaxFreqSize();
return allocNode;
}
else
{
//不滿足完全分配的情況,開始進行內存分割
if(Size<fSize)
{
//確認FreeSize足夠分配一個內存節點
if (G_MemoryPool.FreeSize<sizeof(MemoryNode))
{
return 0;
}
//初始化內存節點
allocNode=(MemoryNode *)itNode->StartAddr;
allocNode->StartAddr=(char*)itNode->StartAddr+sizeof(MemoryNode);
allocNode->EndAddr=(char *)itNode->StartAddr+Size-1;
//重新計算釋放內存節點的起始位置,完成分割
itNode->StartAddr=(char *)allocNode->EndAddr+1;
//預留空間
G_MemoryPool.FreeSize-=sizeof(MemoryNode);
//再次重新計算最大釋放內存節點大小
PX_UpdateMaxFreqSize();
return allocNode;
}
}
}
return 0;
}
else
{
return 0;
}
}

推薦閱讀：