c++內存優化：二級間接索引模式內存池

.H內容如下：

/********************************************************* 
在一些不確定內存總占用量的情形下，頻繁的使用new申請內存，再通過鏈表 
進行索引似乎是很常規的做法。自然，也很難做到隨機定位。 
下面的內存池類是用二層索引表來對內存進行大塊劃分，任何一個塊均只需索 
引3次即可定位。 
索引數量，每索引塊的分配單元數量，以及分配單元的字節長度均需為2的整數 
次冪(為了運算時的效率)
//by:www.datahf.net zhangyu(zhangyu.blog.51cto.com) 
*********************************************************/ 
class MemTable 
{ 
public: 
    MemTable(void); 
public: 
    ~MemTable(void); 
public: 
    void CREATE(MemTableIn *in_m);  
    void DEL(); 
    LPSTR NEW();//分配一個unit 
    LPSTR NEW_CONTINUEOUS(UINT n);//用於連續分配若干個unit 
    UINT NEW(UINT n); //用於可碎片方式分配若干個unit 
    LPSTR GET(UINT n);//用來獲得第n個分配的指針地址 
    int get_totle_unitnum(); 
public: 
    MemTableIn in; 
    LPSTR **pDouble_Indirect; 
    LPSTR lpBitmap; 
    LPSTR *pIndirect; 
 
    LPSTR m_lpFirstFree; 
    int nFree[3];//0表示二級索引的自由，1表示1級索引的自由，2表示塊自由索引號 
    INT32 m_EndBlkUseredUnits; 
    int m_Vblkbytes; 
    UINT m_UnitTotalNum; 
    UINT m_log2Rindexs,m_log2Runits,m_log2Rbitmap,m_log2Lindexs,m_log2Lunits,m_log2Lbitmap; 
    UINT m_log2UnitBytes; 
    UINT m_index2ID,m_index1ID,m_UnitID; 
}; 

.CPP內容如下： 

/** 
* ffs - Find the first set bit in an int 
* @x: 
* 
* Description...用來統計一個整型數據的最高為1的位，後面有多少位。 
*換個說法：從最高位開始找1，找到1後，看這個二進制數據1000....000是2的幾次方 
* 
* Returns: 
*/ 
int ffs(int x) 
{ 
    int r = 1; 
 
    if (!x) 
        return 0; 
    if (!(x & 0xffff)) { 
        x >>= 16; 
        r += 16; 
    } 
    if (!(x & 0xff)) { 
        x >>= 8; 
        r += 8; 
    } 
    if (!(x & 0xf)) { 
        x >>= 4; 
        r += 4; 
    } 
    if (!(x & 3)) { 
        x >>= 2; 
        r += 2; 
    } 
    if (!(x & 1)) { 
        x >>= 1; 
        r += 1; 
    } 
    return r; 
} 
LPSTR MemTree::GET(MemTreeHead *pHead,UINT n) 
{ 
    int t; 
    LPSTR lpt; 
    int i,ii; 
    //判斷是否直接存儲 
    if(n<m.rootDirectUnitNum) 
        return pHead->lpRootUnit + n*m.Vsizeof; 
    else 
        t=n-m.rootDirectUnitNum; 
 
    for(i=1;i<DEEP;i++) 
    { 
        if(t<TBT[i][0]) 
            break; 
        t-=TBT[i][0]; 
    } 
    //i便是深度，t是深度內的n 
    lpt=pHead->pROOT_INDEX[i-1]; 
    int D; 
    for(ii=1;ii<i;ii++) 
    { 
        D=t /TBT[i][ii]; 
        t=t % TBT[i][ii]; 
        lpt=*(LPSTR*)(lpt+sizeof(LPSTR)*D); 
    } 
    return (lpt +   t*m.Vsizeof); 
 
} 
 
MemTable::MemTable(void) 
{ 
} 
 
MemTable::~MemTable(void) 
{ 
    //釋放所有空間 
    for(int i=0;i<in.nIndexNum;i++) 
    { 
        LPSTR *pp=pDouble_Indirect[i]; 
        if(pp==NULL) 
            break; 
        for(int ii=0;ii<in.nIndexNum;ii++) 
        { 
            LPSTR p=pp[ii]; 
            if(p==NULL) 
                break; 
            else 
                delete [] p; 
        } 
        delete [] pp; 
    } 
    delete [] pDouble_Indirect; 
} 
void MemTable::CREATE(MemTableIn *in_m) 
{ 
    //1、初始化一些參考塊 
    memset(&in,0,sizeof(in)); 
    in=*in_m; 
    m_UnitTotalNum=0; 
    nFree[0]=nFree[1]=nFree[2]=0; 
 
    m_Vblkbytes= in.nUnitBytes *in.nUnitPerIndex; 
    m_log2Runits=ffs(in.nUnitPerIndex)-1; 
    m_log2Rindexs=ffs(in.nIndexNum)-1; 
    m_log2UnitBytes=ffs(in.nUnitBytes)-1; 
 
    m_log2Lindexs=sizeof(UINT)*8-m_log2Rindexs; 
    m_log2Lunits=sizeof(UINT)*8-m_log2Runits; 
     
 
 
    //2、初始化二級索引表 
    pDouble_Indirect=new LPSTR* [in.nIndexNum]; 
    memset(pDouble_Indirect,0,in.nIndexNum*sizeof(LPSTR)); 
    nFree[0]=in.nIndexNum; 
} 
LPSTR MemTable::NEW() 
{ 
    LPSTR lpReturn; 
    if(nFree[2]==0)//直接塊用光了 
    { 
        if(nFree[1]==0) 
        { 
            if(nFree[0]==0) 
                return NULL;//寫日志：達到最大分配數量 
 
            pIndirect=pDouble_Indirect[in.nIndexNum - nFree[0]]=new LPSTR [in.nIndexNum]; 
            memset(pIndirect,0,in.nIndexNum*sizeof(LPSTR)); 
            nFree[1]=in.nIndexNum-1; 
 
            lpReturn=pIndirect[0]=new char[m_Vblkbytes]; 
            memset(lpReturn,0,m_Vblkbytes); 
            nFree[2]=in.nUnitPerIndex-1; 
            m_lpFirstFree = lpReturn + in.nUnitBytes;    
            nFree[0]--; 
             
        } 
        else 
        { 
            lpReturn=pIndirect[in.nIndexNum - nFree[1]]=new char[m_Vblkbytes]; 
            memset(lpReturn,0,m_Vblkbytes); 
            nFree[1]--; 
            nFree[2]=in.nUnitPerIndex-1; 
            m_lpFirstFree = lpReturn + in.nUnitBytes; 
        } 
    } 
    else 
    { 
        lpReturn=m_lpFirstFree; 
        nFree[2]--; 
        m_lpFirstFree += in.nUnitBytes; 
    } 
    m_UnitTotalNum++; 
    return lpReturn; 
 
}//by:www.datahf.net zhangyu(zhangyu.blog.51cto.com) 
UINT MemTable::NEW(UINT n) 
{ 
    UINT nReturn=m_UnitTotalNum; 
    for(int i=0;i<n;i++) 
        NEW(); 
    return nReturn; 
 
} 
LPSTR MemTable::NEW_CONTINUEOUS(UINT n) 
{ 
    LPSTR lpReturn; 
    if(n>in.nUnitPerIndex) 
        return NULL; 
 
    if(nFree[2]>=n) 
    { 
        nFree[2]-=n; 
        lpReturn=m_lpFirstFree; 
        m_UnitTotalNum+=n; 
        m_lpFirstFree += (n*in.nUnitBytes); 
    } 
    else 
    { 
        m_UnitTotalNum+=nFree[2];//剩余空間保留、忽略 
        nFree[2]=0; 
        lpReturn=NEW(); 
        nFree[2] -= (n-1); 
        m_lpFirstFree += ((n-1)*in.nUnitBytes); 
        m_UnitTotalNum += (n-1); 
    } 
    return lpReturn; 
} 
LPSTR MemTable::GET(UINT n) 
{ //by:www.datahf.net zhangyu(zhangyu.blog.51cto.com) 
    if(n>=m_UnitTotalNum) 
        return NULL;//寫日志：超過范圍 
    m_UnitID=n<< m_log2Lunits >>m_log2Lunits; 
    m_index1ID=n >> m_log2Runits; 
    m_index2ID=m_index1ID >> m_log2Rindexs; 
    m_index1ID=m_index1ID <<m_log2Lindexs >>m_log2Lindexs; 
 
    return (pDouble_Indirect[m_index2ID][m_index1ID] + (m_UnitID<<m_log2UnitBytes)); 
 
} 
void MemTable::DEL() 
{ 
 
 
} 

本文出自 “張宇(數據恢復)” 博客，請務必保留此出處http://zhangyu.blog.51cto.com/197148/680592