Nginx的內(nèi)存池實(shí)現(xiàn)（轉(zhuǎn)載）

//該結(jié)構(gòu)用來(lái)維護(hù)內(nèi)存池的數(shù)據(jù)塊，供用戶分配之用。
typedef struct {
    u_char               *last; 	//當(dāng)前內(nèi)存分配結(jié)束位置，即下一段可分配內(nèi)存的起始位置
    u_char               *end;  	//內(nèi)存池結(jié)束位置
    ngx_pool_t           *next; 	//鏈接到下一個(gè)內(nèi)存池
    ngx_uint_t            failed; 	//統(tǒng)計(jì)該內(nèi)存池不能滿足分配請(qǐng)求的次數(shù)
} ngx_pool_data_t;
//該結(jié)構(gòu)維護(hù)整個(gè)內(nèi)存池的頭部信息。
struct ngx_pool_s {
    ngx_pool_data_t       d; 		//數(shù)據(jù)塊
    size_t                max;		//數(shù)據(jù)塊的大小，即小塊內(nèi)存的最大值
    ngx_pool_t           *current;	//保存當(dāng)前內(nèi)存池
    ngx_chain_t          *chain;	//可以掛一個(gè)chain結(jié)構(gòu)
    ngx_pool_large_t     *large;	//分配大塊內(nèi)存用，即超過(guò)max的內(nèi)存請(qǐng)求
    ngx_pool_cleanup_t   *cleanup;	//掛載一些內(nèi)存池釋放的時(shí)候，同時(shí)釋放的資源。
    ngx_log_t            *log;
};

posted @ 2011-06-15 16:27 周強(qiáng) 閱讀(550) | 評(píng)論 (0) | 編輯 收藏

c++ STL 容器

posted @ 2011-06-02 11:28 周強(qiáng) 閱讀(5820) | 評(píng)論 (1) | 編輯 收藏

最短路徑

posted @ 2011-05-19 16:44 周強(qiáng) 閱讀(508) | 評(píng)論 (2) | 編輯 收藏

最小生成樹(shù)

posted @ 2011-05-19 11:09 周強(qiáng) 閱讀(685) | 評(píng)論 (2) | 編輯 收藏

懷舊

posted @ 2011-05-15 01:20 周強(qiáng) 閱讀(256) | 評(píng)論 (0) | 編輯 收藏

STL源碼分析空間配置器

posted @ 2011-05-12 10:19 周強(qiáng) 閱讀(2664) | 評(píng)論 (7) | 編輯 收藏

c++虛函數(shù)原理及實(shí)現(xiàn)（轉(zhuǎn)載）

 舉個(gè)例子說(shuō)明虛函數(shù)、多態(tài)、早綁定和晚綁定：
  李氏兩兄妹（哥哥和妹妹）參加姓氏運(yùn)動(dòng)會(huì)（不同姓氏組隊(duì)參加），哥哥男子項(xiàng)目比賽，妹妹參加女子項(xiàng)目比賽，開(kāi)幕式有一個(gè)參賽隊(duì)伍代表發(fā)言儀式，兄妹倆都想 去露露臉，可只能一人去，最終他們決定到時(shí)抓鬮決定，而組委會(huì)也不反對(duì)，它才不關(guān)心是哥哥還是妹妹來(lái)發(fā)言，只要派一個(gè)姓李的來(lái)說(shuō)兩句話就行。運(yùn)動(dòng)會(huì)如期舉 行，妹妹抓鬮獲得代表李家發(fā)言的機(jī)會(huì)，哥哥參加了男子項(xiàng)目比賽，妹妹參加了女子項(xiàng)目比賽。比賽結(jié)果就不是我們關(guān)心的了。
 現(xiàn)在讓我們來(lái)做個(gè)類比（只討論與運(yùn)動(dòng)會(huì)相關(guān)的話題）：
 （1）類的設(shè)計(jì)：
  李氏兄妹屬于李氏家族，李氏是基類（這里還是抽象的純基類），李氏又派生出兩個(gè)子類（李氏男和李氏女），李氏男會(huì)所有男子項(xiàng)目的比賽（李氏男的成員函 數(shù)），李氏女會(huì)所有女子項(xiàng)目的比賽（李氏女的成員函數(shù)）。姓李的人都會(huì)發(fā)言（基類虛函數(shù)），李氏男和李氏女繼承自李氏當(dāng)然也會(huì)發(fā)言，只是男女說(shuō)話聲音不一 樣，內(nèi)容也會(huì)又差異，給人感覺(jué)不同（李氏男和李氏女分別重新定義發(fā)言這個(gè)虛函數(shù)）。李氏兩兄妹就是李氏男和李氏女兩個(gè)類的實(shí)體。
 （2）程序設(shè)計(jì)：
 李氏兄妹填寫參賽報(bào)名表。
 （3）編譯：
  李氏兄妹的參賽報(bào)名表被上交給組委會(huì)（編譯器），哥哥和妹妹分別參加男子和女子的比賽，組委會(huì)一看就明白了（早綁定），只是發(fā)言人選不明確，組委會(huì)看到報(bào) 名表上寫的是“李家代表”（基類指針），組委會(huì)不能確定到底是誰(shuí)，就做了個(gè)備注：如果是男的，就是哥哥李某某；如果是女的，就是妹妹李某某（晚綁定）。組 委會(huì)做好其它準(zhǔn)備工作后，就等運(yùn)動(dòng)會(huì)開(kāi)始了（編譯完畢）。
 （4）程序運(yùn)行：
 運(yùn)動(dòng)會(huì)開(kāi)始了（程序開(kāi)始運(yùn)行），開(kāi)幕式上我們聽(tīng)到了李家妹妹的發(fā)言，如果是哥哥運(yùn)氣好抓鬮勝出，我們將聽(tīng)到哥哥的發(fā)言（多態(tài)）。然后就是看到兄妹倆參加比賽了。。。

 但愿這個(gè)比喻說(shuō)清楚了虛函數(shù)、多態(tài)、早綁定和晚綁定的概念和它們之間的關(guān)系。再說(shuō)一下，早綁定指編譯器在編譯期間即知道對(duì)象的具體類型并確定此對(duì)象調(diào)用成員函數(shù)的確切地址；而晚綁定是根據(jù)指針?biāo)笇?duì)象的類型信息得到類的虛函數(shù)表指針進(jìn)而確定調(diào)用成員函數(shù)的確切地址。
  

 2、揭密晚綁定的秘密

 編譯器到底做了什么實(shí)現(xiàn)的虛函數(shù)的晚綁定呢？我們來(lái)探個(gè)究竟。

  編譯器對(duì)每個(gè)包含虛函數(shù)的類創(chuàng)建一個(gè)表（稱為V TA B L E）。在V TA B L E中，編譯器放置特定類的虛函數(shù)地址。在每個(gè)帶有虛函數(shù)的類 中，編譯器秘密地置一指針，稱為v p o i n t e r（縮寫為V P T R），指向這個(gè)對(duì)象的V TA B L E。通過(guò)基類指針做虛函數(shù)調(diào) 用時(shí)（也就是做多態(tài)調(diào)用時(shí)），編譯器靜態(tài)地插入取得這個(gè)V P T R，并在V TA B L E表中查找函數(shù)地址的代碼，這樣就能調(diào)用正確的函數(shù)使晚捆綁發(fā)生。為每個(gè)類設(shè)置V TA B L E、初始化V P T R、為虛函數(shù)調(diào)用插入代碼，所有這些都是自動(dòng)發(fā)生的，所以我們不必?fù)?dān)心這些。利用虛函數(shù)， 這個(gè)對(duì)象的合適的函數(shù)就能被調(diào)用，哪怕在編譯器還不知道這個(gè)對(duì)象的特定類型的情況下。（《C++編程思想》）

————這段話紅色加粗部分似乎有點(diǎn)問(wèn)題，我個(gè)人的理解看后面的總結(jié)。

 在任何類中不存在顯示的類型信息，可對(duì)象中必須存放類信息，否則類型不可能在運(yùn)行時(shí)建立。那這個(gè)類信息是什么呢？我們來(lái)看下面幾個(gè)類：

 class no_virtual
 {
 public:
     void fun1() const{}
     int  fun2() const { return a; }
 private:
     int a;
 }

 class one_virtual
 {
 public:
     virtual void fun1() const{}
     int  fun2() const { return a; }
 private:
     int a;
 }

 class two_virtual
 {
 public:
     virtual void fun1() const{}
     virtual int  fun2() const { return a; }
 private:
     int a;
 }

 以上三個(gè)類中：
 no_virtual沒(méi)有虛函數(shù)，sizeof(no_virtual)=4，類no_virtual的長(zhǎng)度就是其成員變量整型a的長(zhǎng)度；
 one_virtual有一個(gè)虛函數(shù)，sizeof(one_virtual)=8；
 two_virtual 有兩個(gè)虛函數(shù)，sizeof(two_virtual)=8； 有一個(gè)虛函數(shù)和兩個(gè)虛函數(shù)的類的長(zhǎng)度沒(méi)有區(qū)別，其實(shí)它們的長(zhǎng)度就是no_virtual的 長(zhǎng)度加一個(gè)void指針的長(zhǎng)度，它反映出，如果有一個(gè)或多個(gè)虛函數(shù)，編譯器在這個(gè)結(jié)構(gòu)中插入一個(gè)指針（ V P T R）。在one_virtual 和 two_virtual之間沒(méi)有區(qū)別。這是因?yàn)閂 P T R指向一個(gè)存放地址的表，只需要一個(gè)指針，因?yàn)樗刑摵瘮?shù)地址都包含在這個(gè)表中。

 這個(gè)VPTR就可以看作類的類型信息。

 那我們來(lái)看看編譯器是怎么建立VPTR指向的這個(gè)虛函數(shù)表的。先看下面兩個(gè)類：
 class base
 {
 public:
     void bfun(){}
     virtual void vfun1(){}
     virtual int vfun2(){}
 private:
     int a;
 }

 class derived : public base
 {
 public:
     void dfun(){}
     virtual void vfun1(){}
     virtual int vfun3(){}
 private:
     int b;
 }

 兩個(gè)類VPTR指向的虛函數(shù)表（VTABLE）分別如下：
 base類
                       ——————
 VPTR——> |&base::vfun1 |
                       ——————
                  |&base::vfun2 |
                   ——————
       
 derived類
                       ———————
 VPTR——> |&derived::vfun1 |
                       ———————
                   |&base::vfun2    |
                   ———————
                   |&derived::vfun3 |
                    ———————
     
  每當(dāng)創(chuàng)建一個(gè)包含有虛函數(shù)的類或從包含有虛函數(shù)的類派生一個(gè)類時(shí)，編譯器就為這個(gè)類創(chuàng)建一個(gè)VTABLE，如上圖所示。在這個(gè)表中，編譯器放置了在這個(gè)類 中或在它的基類中所有已聲明為virtual的函數(shù)的地址。如果在這個(gè)派生類中沒(méi)有對(duì)在基類中聲明為virtual的函數(shù)進(jìn)行重新定義，編譯器就使用基類 的這個(gè)虛函數(shù)地址。（在derived的VTABLE中，vfun2的入口就是這種情況。）然后編譯器在這個(gè)類中放置VPTR。當(dāng)使用簡(jiǎn)單繼承時(shí)，對(duì)于每 個(gè)對(duì)象只有一個(gè)VPTR。VPTR必須被初始化為指向相應(yīng)的VTABLE，這在構(gòu)造函數(shù)中發(fā)生。
 一旦VPTR被初始化為指向相應(yīng)的VTABLE，對(duì)象就"知道"它自己是什么類型。但只有當(dāng)虛函數(shù)被調(diào)用時(shí)這種自我認(rèn)知才有用。

個(gè)人總結(jié)如下：
1、從包含虛函數(shù)的類派生一個(gè)類時(shí)，編譯器就為該類創(chuàng)建一個(gè)VTABLE。其每一個(gè)表項(xiàng)是該類的虛函數(shù)地址。
2、在定義該派生類對(duì)象時(shí)，先調(diào)用其基類的構(gòu)造函數(shù)，然后再初始化VPTR，最后再調(diào)用派生類的構(gòu)造函數(shù)（ 從二進(jìn)制的視野來(lái)看，所謂基類子類是一個(gè)大結(jié)構(gòu)體，其中this指針開(kāi)頭的四個(gè)字節(jié)存放虛函數(shù)表頭指針。執(zhí)行子類的構(gòu)造函數(shù)的時(shí)候，首先調(diào)用基類構(gòu)造函 數(shù)，this指針作為參數(shù)，在基類構(gòu)造函數(shù)中填入基類的vptr，然后回到子類的構(gòu)造函數(shù)，填入子類的vptr，覆蓋基類填入的vptr。如此以來(lái)完成 vptr的初始化。 ）
3、在實(shí)現(xiàn)動(dòng)態(tài)綁定時(shí)，不能直接采用類對(duì)象，而一定要采用指針或者引用。因?yàn)椴捎妙悓?duì)象傳值方式，有臨時(shí)基類對(duì)象的產(chǎn)生，而采用指針，則是通過(guò)指針來(lái)訪問(wèn)外部的派生類對(duì)象的VPTR來(lái)達(dá)到訪問(wèn)派生類虛函數(shù)的結(jié)果。

 VPTR 常常位于對(duì)象的開(kāi)頭，編譯器能很容易地取到VPTR的值，從而確定VTABLE的位置。VPTR總指向VTABLE的開(kāi)始地址，所有基類和它的子類的虛函 數(shù)地址（子類自己定義的虛函數(shù)除外）在VTABLE中存儲(chǔ)的位置總是相同的，如上面base類和derived類的VTABLE中vfun1和vfun2 的地址總是按相同的順序存儲(chǔ)。編譯器知道vfun1位于VPTR處，vfun2位于VPTR+1處，因此在用基類指針調(diào)用虛函數(shù)時(shí)，編譯器首先獲取指針指 向?qū)ο蟮念愋托畔ⅲ╒PTR），然后就去調(diào)用虛函數(shù)。如一個(gè)base類指針pBase指向了一個(gè)derived對(duì)象，那pBase->vfun2 ()被編譯器翻譯為 VPTR+1 的調(diào)用，因?yàn)樘摵瘮?shù)vfun2的地址在VTABLE中位于索引為1的位置上。同理，pBase->vfun3 ()被編譯器翻譯為 VPTR+2的調(diào)用。這就是所謂的晚綁定。

 我們來(lái)看一下虛函數(shù)調(diào)用的匯編代碼，以加深理解。

 void test(base* pBase)
 {
  pBase->vfun2();
 }

 int main(int argc, char* argv[])
 {
  derived td;
  

 
  test(&td);
  
  return 0;
 }

 derived td;編譯生成的匯編代碼如下：
  mov DWORD PTR _td$[esp+24], OFFSET FLAT:??_7derived@@6B@ ; derived::`vftable'
  由編譯器的注釋可知，此時(shí)PTR _td$[esp+24]中存儲(chǔ)的就是derived類的VTABLE地址。
  
 test(&td);編譯生成的匯編代碼如下：
  lea eax, DWORD PTR _td$[esp+24]    
  mov DWORD PTR __$EHRec$[esp+32], 0
  push eax
  call ?test@@YAXPAVbase@@@Z   ; test 
  調(diào)用test函數(shù)時(shí)完成了如下工作：取對(duì)象td的地址，將其壓棧，然后調(diào)用test。

 pBase->vfun2();編譯生成的匯編代碼如下：
   mov ecx, DWORD PTR _pBase$[esp-4]
  mov eax, DWORD PTR [ecx]
  jmp DWORD PTR [eax+4]
   首先從棧中取出pBase指針指向的對(duì)象地址賦給ecx，然后取對(duì)象開(kāi)頭的指針變量中的地址賦給eax，此時(shí)eax的值即為VPTR的值，也就是 VTABLE的地址。最后就是調(diào)用虛函數(shù)了，由于vfun2位于VTABLE的第二個(gè)位置，相當(dāng)于 VPTR+1，每個(gè)函數(shù)指針是4個(gè)字節(jié)長(zhǎng)，所以最后的 調(diào)用被編譯器翻譯為 jmp DWORD PTR [eax+4]。如果是調(diào)用pBase->vfun1()，這句就該被編譯為 jmp DWORD PTR [eax]。
  

 現(xiàn)在應(yīng)該對(duì)多態(tài)、虛函數(shù)、晚綁定有比較清楚的了解了吧。
 

posted @ 2011-05-11 14:13 周強(qiáng) 閱讀(344) | 評(píng)論 (0) | 編輯 收藏

AVL樹(shù)（轉(zhuǎn)載）

轉(zhuǎn)載：http://www.shnenglu.com/converse/archive/2007/08/29/31179.html

/********************************************************************
created:    2007/08/28
filename:     avltree.c
author:        Lichuang

purpose:    AVL樹(shù)的實(shí)現(xiàn)代碼, 
            參考資料<<數(shù)據(jù)結(jié)構(gòu)與算法分析-C語(yǔ)言描述>>, 作者Allen Weiss
*********************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct AVLTree
{
    int nData;
    struct AVLTree* pLeft;
    struct AVLTree* pRight;
    int nHeight;
}AVLTree;

int Max(int a, int b);
int Height(AVLTree* pNode);
AVLTree* Insert(int nData, AVLTree* pNode);
AVLTree* SingleRotateWithLeft(AVLTree* pNode);
AVLTree* SingleRotateWithRight(AVLTree* pNode);
AVLTree* DoubleRotateWithLeft(AVLTree* pNode);
AVLTree* DoubleRotateWithRight(AVLTree* pNode);
void DeleteTree(AVLTree** ppRoot);
void PrintTree(AVLTree* pRoot);

int main()
{
    int i;
    AVLTree* pRoot = NULL;

    srand((unsigned int)::time(NULL));
    
    for (i = 0; i < 100000000; ++i)
    {
        pRoot = Insert(::rand(), pRoot);
    }

    //PrintTree(pRoot);

    DeleteTree(&pRoot);

    return 0;
}

int Max(int a, int b)
{
    return (a > b ? a : b);
}

int Height(AVLTree* pNode)
{
    if (NULL == pNode)
        return -1;

    return pNode->nHeight;
}

AVLTree* Insert(int nData, AVLTree* pNode)
{
    if (NULL == pNode)
    {
        pNode = (AVLTree*)malloc(sizeof(AVLTree));
        pNode->nData = nData;
        pNode->nHeight = 0;
        pNode->pLeft = pNode->pRight = NULL;
    }
    else if (nData < pNode->nData)          // 插入到左子樹(shù)中
    {
        pNode->pLeft = Insert(nData, pNode->pLeft);
        if (Height(pNode->pLeft) - Height(pNode->pRight) == 2)    // AVL樹(shù)不平衡
        {
            if (nData < pNode->pLeft->nData)
            {
                // 插入到了左子樹(shù)左邊, 做單旋轉(zhuǎn)
                pNode = SingleRotateWithLeft(pNode);
            }
            else 
            {
                // 插入到了左子樹(shù)右邊, 做雙旋轉(zhuǎn)
                pNode = DoubleRotateWithLeft(pNode);
            }
        }
    }
    else if (nData > pNode->nData)          // 插入到右子樹(shù)中
    {
        pNode->pRight = Insert(nData, pNode->pRight);
        if (Height(pNode->pRight) - Height(pNode->pLeft) == 2)    // AVL樹(shù)不平衡
        {
            if (nData > pNode->pRight->nData)
            {
                // 插入到了右子樹(shù)右邊, 做單旋轉(zhuǎn)
                pNode = SingleRotateWithRight(pNode);
            }
            else 
            {
                // 插入到了右子樹(shù)左邊, 做雙旋轉(zhuǎn)
                pNode = DoubleRotateWithRight(pNode);
            }
        }
    }

    pNode->nHeight = Max(Height(pNode->pLeft), Height(pNode->pRight)) + 1;

    return pNode;
}

/********************************************************************
      pNode                                pNode->pLeft 
      /                                             \
pNode->pLeft                      ==>              pNode
           \                                       /
          pNode->pLeft->pRight                   pNode->pLeft->pRight
*********************************************************************/
AVLTree* SingleRotateWithLeft(AVLTree* pNode)
{
    AVLTree* pNode1;

    pNode1 = pNode->pLeft;
    pNode->pLeft = pNode1->pRight;
    pNode1->pRight = pNode;

    // 結(jié)點(diǎn)的位置變了, 要更新結(jié)點(diǎn)的高度值
    pNode->nHeight = Max(Height(pNode->pLeft), Height(pNode->pRight)) + 1;
    pNode1->nHeight = Max(Height(pNode1->pLeft), pNode->nHeight) + 1;

    return pNode1;
}

/********************************************************************
pNode                                   pNode->pRight
     \                                  /
     pNode->pRight           ==>    pNode 
     /                                   \
pNode->pRight->pLeft                     pNode->pRight->pLeft
*********************************************************************/
AVLTree* SingleRotateWithRight(AVLTree* pNode)
{
    AVLTree* pNode1;

    pNode1 = pNode->pRight;
    pNode->pRight = pNode1->pLeft;
    pNode1->pLeft = pNode;

    // 結(jié)點(diǎn)的位置變了, 要更新結(jié)點(diǎn)的高度值
    pNode->nHeight = Max(Height(pNode->pLeft), Height(pNode->pRight)) + 1;
    pNode1->nHeight = Max(Height(pNode1->pRight), pNode->nHeight) + 1;

    return pNode1;
}

AVLTree* DoubleRotateWithLeft(AVLTree* pNode)
{
    pNode->pLeft = SingleRotateWithRight(pNode->pLeft);

    return SingleRotateWithLeft(pNode);
}

AVLTree* DoubleRotateWithRight(AVLTree* pNode)
{
    pNode->pRight = SingleRotateWithLeft(pNode->pRight);

    return SingleRotateWithRight(pNode);
}

// 后序遍歷樹(shù)以刪除樹(shù)
void DeleteTree(AVLTree** ppRoot)
{
    if (NULL == ppRoot || NULL == *ppRoot)
        return;

    DeleteTree(&((*ppRoot)->pLeft));
    DeleteTree(&((*ppRoot)->pRight));
    free(*ppRoot);
    *ppRoot = NULL;
}

// 中序遍歷打印樹(shù)的所有結(jié)點(diǎn), 因?yàn)樽蠼Y(jié)點(diǎn) < 父結(jié)點(diǎn) < 右結(jié)點(diǎn), 因此打印出來(lái)數(shù)據(jù)的大小是遞增的
void PrintTree(AVLTree* pRoot)
{
    if (NULL == pRoot)
        return;

    static int n = 0;

    PrintTree(pRoot->pLeft);
    printf("[%d]nData = %d\n", ++n, pRoot->nData);
    PrintTree(pRoot->pRight);
}

posted @ 2011-05-11 10:25 周強(qiáng) 閱讀(281) | 評(píng)論 (0) | 編輯 收藏

小夜曲

posted @ 2011-05-11 01:13 周強(qiáng) 閱讀(218) | 評(píng)論 (0) | 編輯 收藏

一個(gè)簡(jiǎn)單的空間配置器

posted @ 2011-05-04 00:55 周強(qiáng) 閱讀(493) | 評(píng)論 (0) | 編輯 收藏