#
來源：http://www.tbdata.org/archives/1390#more-1390
Nginx的內存池實現得很精巧，代碼也很簡潔?？偟膩碚f，所有的內存池基本都一個宗旨：申請大塊內存，避免“細水長流”。
一、創建一個內存池
nginx內存池主要有下面兩個結構來維護，他們分別維護了內存池的頭部和數據部。此處數據部就是供用戶分配小塊內存的地方。
//該結構用來維護內存池的數據塊，供用戶分配之用。
typedef struct {
u_char *last; //當前內存分配結束位置，即下一段可分配內存的起始位置
u_char *end; //內存池結束位置
ngx_pool_t *next; //鏈接到下一個內存池
ngx_uint_t failed; //統計該內存池不能滿足分配請求的次數
} ngx_pool_data_t;
//該結構維護整個內存池的頭部信息。
struct ngx_pool_s {
ngx_pool_data_t d; //數據塊
size_t max; //數據塊的大小，即小塊內存的最大值
ngx_pool_t *current; //保存當前內存池
ngx_chain_t *chain; //可以掛一個chain結構
ngx_pool_large_t *large; //分配大塊內存用，即超過max的內存請求
ngx_pool_cleanup_t *cleanup; //掛載一些內存池釋放的時候，同時釋放的資源。
ngx_log_t *log;
};
有了上面的兩個結構，就可以創建一個內存池了，nginx用來創建一個內存池的接口是：ngx_pool_t *ngx_create_pool(size_t size, ngx_log_t *log)（位于src/core/ngx_palloc.c中）;調用這個函數就可以創建一個大小為size的內存池了。這里，我用內存池的結構圖來展 示，就不做具體的代碼分析了。
ngx_create_pool接口函數就是分配上圖這樣的一大塊內存，然后初始化好各個頭部字段（上圖中的彩色部分）。紅色表示的四個字段就是來自于上 述的第一個結構，維護數據部分，由圖可知：last是用戶從內存池分配新內存的開始位置，end是這塊內存池的結束位置，所有分配的內存都不能超過 end。藍色表示的max字段的值等于整個數據部分的長度，用戶請求的內存大于max時，就認為用戶請求的是一個大內存，此時需要在紫色表示的large 字段下面單獨分配；用戶請求的內存不大于max的話，就是小內存申請，直接在數據部分分配，此時將會移動last指針。
二、分配小塊內存(size <= max)
上面創建好了一個可用的內存池了，也提到了小塊內存的分配問題。nginx提供給用戶使用的內存分配接口有：
void *ngx_palloc(ngx_pool_t *pool, size_t size);
void *ngx_pnalloc(ngx_pool_t *pool, size_t size);
void *ngx_pcalloc(ngx_pool_t *pool, size_t size);
void *ngx_pmemalign(ngx_pool_t *pool, size_t size, size_t alignment);
ngx_palloc和ngx_pnalloc都是從內存池里分配size大小內存，至于分得的是小塊內存還是大塊內存，將取決于size的大小； 他們的不同之處在于，palloc取得的內存是對齊的，pnalloc則否。ngx_pcalloc是直接調用palloc分配好內存，然后進行一次0初 始化操作。ngx_pmemalign將在分配size大小的內存并按alignment對齊，然后掛到large字段下，當做大塊內存處理。下面用圖形 展示一下分配小塊內存的模型：
上圖這個內存池模型是由上3個小內存池構成的，由于第一個內存池上剩余的內存不夠分配了，于是就創建了第二個新的內存池，第三個內存池是由于前面兩個內存 池的剩余部分都不夠分配，所以創建了第三個內存池來滿足用戶的需求。由圖可見：所有的小內存池是由一個單向鏈表維護在一起的。這里還有兩個字段需要關 注，failed和current字段。failed表示的是當前這個內存池的剩余可用內存不能滿足用戶分配請求的次數，即是說：一個分配請求到來后，在 這個內存池上分配不到想要的內存，那么就failed就會增加1；這個分配請求將會遞交給下一個內存池去處理，如果下一個內存池也不能滿足，那么它的 failed也會加1，然后將請求繼續往下傳遞，直到滿足請求為止（如果沒有現成的內存池來滿足，會再創建一個新的內存池）。current字段會隨著 failed的增加而發生改變，如果current指向的內存池的failed達到了4的話，current就指向下一個內存池了。猜測：4這個值應該是 作者的經驗值，或者是一個統計值。
三、大塊內存的分配(size > max)
大塊內存的分配請求不會直接在內存池上分配內存來滿足，而是直接向操作系統申請這么一塊內存（就像直接使用malloc分配內存一樣），然后將這塊 內存掛到內存池頭部的large字段下。內存池的作用在于解決小塊內存池的頻繁申請問題，對于這種大塊內存，是可以忍受直接申請的。同樣，用圖形展示大塊 內存申請模型：
注意每塊大內存都對應有一個頭部結構（next&alloc），這個頭部結構是用來將所有大內存串成一個鏈表用的。這個頭部結構不是直接向操作系 統申請的，而是當做小塊內存（頭部結構沒幾個字節）直接在內存池里申請的。這樣的大塊內存在使用完后，可能需要第一時間釋放，節省內存空間，因此 nginx提供了接口函數：ngx_int_t ngx_pfree(ngx_pool_t *pool, void *p)；此函數專門用來釋放某個內存池上的某個大塊內存，p就是大內存的地址。ngx_pfree只會釋放大內存，不會釋放其對應的頭部結構，畢竟頭部結 構是當做小內存在內存池里申請的；遺留下來的頭部結構會作下一次申請大內存之用。
四、cleanup資源
可以看到所有掛載在內存池上的資源將形成一個循環鏈表，一路走來，發現鏈表這種看似簡單的數據結構卻被頻繁使用。由圖可知，每個需要清理的資源都對應有一 個頭部結構，這個結構中有一個關鍵的字段handler，handler是一個函數指針，在掛載一個資源到內存池上的時候，同時也會注冊一個清理資源的函 數到這個handler上。即是說，內存池在清理cleanup的時候，就是調用這個handler來清理對應的資源。比如：我們可以將一個開打的文件描 述符作為資源掛載到內存池上，同時提供一個關閉文件描述的函數注冊到handler上，那么內存池在釋放的時候，就會調用我們提供的關閉文件函數來處理文 件描述符資源了。
五、內存的釋放
nginx只提供給了用戶申請內存的接口，卻沒有釋放內存的接口，那么nginx是如何完成內存釋放的呢？總不能一直申請，用不釋放啊。針對這個問 題，nginx利用了web server應用的特殊場景來完成；一個web server總是不停的接受connection和request，所以nginx就將內存池分了不同的等級，有進程級的內存池、connection級 的內存池、request級的內存池。也就是說，創建好一個worker進程的時候，同時為這個worker進程創建一個內存池，待有新的連接到來后，就 在worker進程的內存池上為該連接創建起一個內存池；連接上到來一個request后，又在連接的內存池上為request創建起一個內存池。這樣， 在request被處理完后，就會釋放request的整個內存池，連接斷開后，就會釋放連接的內存池。因而，就保證了內存有分配也有釋放。
總結：通過內存的分配和釋放可以看出，nginx只是將小塊內存的申請聚集到一起申請，然后一起釋放。避免了頻繁申請小內存，降低內存碎片的產生等問題
參考：STL源碼分析
（一）vector容器
vector的數據安排以及操作方式，與array非常相似。兩者的唯一區別在于空間的運用的靈活性。array是靜態空間，一旦配置了就不能改變。vector是動態空間，隨著元素的加入，它的內部機制會自行擴充空間以容納新元素。因此，vector的運用對于內存的合理利用與運用的靈活性有很大的幫助，我們再也不必因為害怕空間不足而一開始要求一個大塊的array。
vector動態增加大小，并不是在原空間之后持續新空間（因為無法保證原空間之后尚有可供配置的空間），而是以原大小的兩倍另外配置一塊較大的空間，然后將原內容拷貝過來，然后才開始在原內容之后構造新元素，并釋放原空間。因此，對vector的任何操作，一旦引起空間重新配置，指向原vector的所有迭代器就都失效了。
（二）list容器
相對于vector的連續空間，list就顯得復雜許多，它的好處是每次插入或刪除一個元素，就配置或釋放一個元素空間。因此，list對于空間的運用有絕對的精準，一點也不浪費。而且，對于任何位置的元素插入或元素移除，list永遠是常數時間。STL中的list是一個雙向鏈表，而且是一個環狀雙向鏈表。
（三）deque容器
deque 是一種雙向開口的連續線性空間。所謂雙向開口，意思是可以在隊尾兩端分別做元素的插入和刪除操作。deque和vector的最大差異，一在于deque允許于常數時間內對起頭端進行元素的插入或移除操作，二在于deque沒有所謂容量觀念，因為它是動態地以分段連續空間組合而成，隨時可以增加一段新的空間并鏈接在一起。換句話說，像vector那樣"因舊空間不足而重新配置一塊更大空間，然后復制元素，再釋放舊空間"這樣的事情在 deque是不會發生的。
deque是由一段一段的定量連續空間構成。一旦有必要在deque的前端或尾端增加新空間，便配置一段定量連續空間，串接在整個deque的頭端或尾端。deque的最大任務，便是在這些分段的定量連續空間上，維護其整體連續的假象，并提供隨機存取的接口。避開了"重新配置，復制，釋放"的輪回，代價則是復雜的迭代器架構。因為有分段連續線性空間，就必須有中央控制，而為了維持整體連續的假象，數據結構的設計及迭代器前進后退等操作都頗為繁瑣。
deque采用一塊所謂的map作為主控。這里的map是一小塊連續空間，其中每個元素都是指針，指向另一段連續線性空間，稱為緩沖區。緩沖區才是deque的存儲空間主體。SGI STL允許我們指定緩沖區大小，默認值0表示將使用512 bytes緩沖區。
（四）stack
stack 是一種先進后出（First In Last Out , FILO）的數據結構。它只有一個出口，stack 允許新增元素，移除元素，取得最頂端元素。但除了最頂端外，沒有任何其它方法可以存取stack的其它元素，stack不允許遍歷行為。
以某種容器作為底部結構，將其接口改變，使之符合“先進后出”的特性，形成一個stack，是很容易做到的。deque是雙向開口的數據結構，若以deque為底部結構并封閉其頭端開口，便輕而易舉地形成了一個stack.因此，SGI STL 便以deque作為缺省情況下的stack底部結構，由于stack 系以底部容器完成其所有工作，而具有這種"修改某物接口，形成另一種風貌"之性質者，稱為adapter（配接器），因此，STL stack 往往不被歸類為container(容器)，而被歸類為 container adapter.
(五） queue
queue是一種先進先出(First In First Out,FIFO) 的數據結構。它有兩個出口，queue允許新增元素，移除元素，從最底端加入元素，取得最頂端元素。但除了最底端可以加入，最頂端可以取出外，沒有任何其它方法可以存取queue的其它元素。
以某種容器作為底部結構，將其接口改變，使之符合“先進先出”的特性，形成一個queue，是很容易做到的。deque是雙向開口的數據結構，若以 deque為底部結構并封閉其底部的出口和前端的入口，便輕而易舉地形成了一個queue.因此，SGI STL 便以deque作為缺省情況下的queue底部結構，由于queue 系以底部容器完成其所有工作，而具有這種"修改某物接口，形成另一種風貌"之性質者，稱為adapter（配接器），因此，STL queue往往不被歸類為container(容器)，而被歸類為 container adapter.
(六)heap
heap并不歸屬于STL容器組件，它是個幕后英雄，扮演priority queue的助手。priority queue允許用戶以任何次序將任何元素推入容器中，但取出時一定按從優先權最高的元素開始取。按照元素的排列方式，heap可分為max-heap和min-heap兩種，前者每個節點的鍵值(key)都大于或等于其子節點鍵值，后者的每個節點鍵值(key)都小于或等于其子節點鍵值。因此， max-heap的最大值在根節點，并總是位于底層array或vector的起頭處；min-heap的最小值在根節點，亦總是位于底層array或vector起頭處。STL 供應的是max-heap，用c++實現。
堆排序c語言實現
http://www.shnenglu.com/tankzhouqiang/archive/2011/03/21/142413.html
（七）priority_queue
priority_queue是一個擁有權值觀念的queue,它允許加入新元素，移除舊元素，審視元素值等功能。由于這是一個queue，所以只允許在底端加入元素，并從頂端取出元素，除此之外別無其它存取元素的途徑。priority_queue帶有權值觀念，其內的元素并非依照被推入的次序排列，而是自動依照元素的權值排列（通常權值以實值表示）。權值最高者，排在最前面。缺省情況下priority_queue系利用一個max-heap完成，后者是一個以vector表現的 complete binary tree.max-heap可以滿足priority_queue所需要的"依權值高低自動遞減排序"的特性。
priority_queue完全以底部容器作為根據，再加上heap處理規則，所以其實現非常簡單。缺省情況下是以vector為底部容器。queue以底部容器完成其所有工作。具有這種"修改某物接口，形成另一種風貌"之性質者，稱為adapter(配接器)，因此，STL priority_queue往往不被歸類為container(容器)，而被歸類為container adapter.
(八)set,multiset
set的特性是，所有元素都會根據元素的鍵值自動被排序。set的元素不像map那樣可以同時擁有實值(value)和鍵值(key), set 元素的鍵值就是實值，實值就是鍵值，set不允許兩個元素有相同的值。set是通過紅黑樹來實現的，由于紅黑樹（RB-tree）是一種平衡二叉搜索樹，自動排序的效果很不錯，所以標準的STL的set即以RB-Tree為底層機制。又由于set所開放的各種操作接口，RB-tree也都提供了，所以幾乎所有的set操作行為，都只有轉調用RB-tree的操作行為而已。
multiset的特性以及用法和set完全相同，唯一的差別在于它允許鍵值重復，因此它的插入操作采用的是底層機制RB-tree的insert_equal()而非insert_unique().
（九）map,multimap
map的特性是，所有元素都會根據元素的鍵值自動被排序。map的所有元素都是pair,同時擁有實值（value）和鍵值（key）. pair的第一元素被視為鍵值，第二元素被視為實值。map不允許兩個元素擁有相同的鍵值.由于RB-tree是一種平衡二叉搜索樹，自動排序的效果很不錯，所以標準的STL map即以RB-tree為底層機制。又由于map所開放的各種操作接口，RB-tree也都提供了，所以幾乎所有的map操作行為，都只是轉調RB-tree的操作行為。
multimap的特性以及用法與map完全相同，唯一的差別在于它允許鍵值重復，因此它的插入操作采用的是底層機制RB-tree的insert_equal()而非insert_unique。
（一）迪杰斯特拉算法（時間復雜度O(n2)）
迪杰斯特拉（Dijkstra）算法是求某個源點到其余各頂點的最短路徑，這是一個按路徑長度遞增的次序產生最短路徑的算法。
首先引進一個輔助向量D,它的每個分量D[i]表示當前所找到的從始點v到每個終點vi的最短路徑的長度。它的初態為：若從v到vi有弧，則D[i]為弧上的權值；否則置D[i]為無窮大。顯然，長度為D[j]=Min{D[i]|vi屬于V}的路徑就是從v出發的長度最短的一條最短路徑。因此，在一般情況下，下一條長度次短的最短路徑的長度必為D[j]=Min{D[i]|vi 屬于 V-S} 其中D[i]或者為?。╲,vi)上的權值，或者是D[k](vk屬于S)和?。╲k,vi）上的權值之和。算法步驟如下：
(1)假設用帶權的鄰接矩陣arcs來表示帶權有向圖，arcs[i][j]表示弧(vi,vj)上的權值。若(vi,vj)不存在，則置arcs[i][j]為無窮大。S為已找到從v出發的最短路徑的終點的集合，它的初始狀態為空集。那么，從v出發到圖上其余各頂點（終點）vi,可能達到的最短路徑長度的初值為：
D[i]=G.arcs[v][vi],vi屬于V
(2)選擇Vj，使得
D[j]=Min{D[i]|vi 屬于V-S}
vj 就是當前求得的一條從v出發的最短路徑的終點。令
S=SＵ?。辏?br />(3) 修改從v出發到集合V-S上任一頂點vk可達的最短路徑長度。如果D[j]+arcs[j][k]<D[k]則修改D[k]為 D[k]=D[j]+arcs[j][k]
(4) 重復操作(2),(3)共 n-1次。由此求得從v到圖上其余各頂點的最短路徑是依路徑長度遞增的序列。
（二）弗洛伊德(Floyd)算法（時間復雜度為O(n3)）
弗洛伊德（Floyd）算法是求圖中每一對頂點之間的最短路徑，時間復雜度為O(n3).
弗洛伊德算法仍從圖的帶權鄰接矩陣cost出發，其基本思想是 :
假設求從頂點vi到vj的最短路徑。如果從vi到vj有弧，則從vi到vj存在一條長度arcs[i][j]的路徑，該路徑不一定是最短路徑，尚需進行n次試探。首先考慮路徑(vi,v0,vj)是否存在（即判別?。╲i,v0）和(v0,vj)是否存在)。 如果存在，則比較(vi,vj)和(vi,v0,vj)是否存在(即判別弧(vi,v0)和(v0,vj)是否存在).如果存在，則比較(vi,vj)和(vi,v0,vj)的路徑長度取長度較短者為從vi到vj的中間頂點的序號不大于0的最短路徑。假如在路徑上再增加一個頂點v1,也就是說，如果(vi,...v1)和(v1...vj)分別為當前找到的中間頂點的序號不大于0的最短路徑，那么（vi,...,v1,...vj）就有可能是從vi到vj的中間頂點的序號不大于1的最短路徑。將它和已經得到的從vi到vj中間的頂點序號不大于0的最短路徑相比較，從中選出中間頂點的序號不大于1的最短路徑之后，再增加一個頂點v2,繼續進行試探。依次類推。在一般情況下，若(vi,...,vk)和(vk,...vj)分別是從vi到vk和從vk到vj的中間頂點的序號不大于k-1的最短路徑，則將(vi,...vk,...vj)和已經得到的從vi到vj且中間頂點序號不大于k-1的最短路徑相比較，其長度較短者便是從vi到vj的中間頂點的序號不大于k的最短路徑。這樣，在經過n次比較后，最后求得的必是從vi到vj的最短路徑。
現定義一個n階方陣序列
D(-1),D(0),D(1),...D(k),...D(n-1)
其中
D(-1)[i][j]=G.arcs[i][j].
D(k)[i][j]=Min{D(k-1)[i][j],D(k-1)[i][k]+D(k-1)[k][j]} 0<=k<=n-1
從上述計算公式可見，D(1)[i][j]是從vi到vj的中間頂點的序號不大于1的最短路徑的長度。D(k)[i][j]是從vi到vj的中間頂點的序號不大于k的最短路徑的長度。D(n-1)[i][j]就是從vi到vj的最短路徑的長度。
安全邊：在每一次迭代之前， A是某個最小生成樹的一個子集。在算法的每一步中，確定一條邊（u,v),使得將它加入集合A后，仍然不違反這個循環不等式，A U {(u,v)}仍然是某一個最小生成樹的子集。稱這樣的邊為A的安全邊。
識別安全邊的定理：設圖G=(V,E)是一個無向連通圖，并且在E上定義了一個具有實數值的加權函數w.設A是E的一個子集，它包含于G的某個最小生成樹中。設割(S,V-S)是G的任意一個不妨害A的割，且邊(u,v)是通過割(S,V-S)的一條輕邊，則邊(u,v)對集合A來說是安全的。
推論：設G=(V,E)是一個無向聯通圖，并且在E上定義了相應的實數值加權函數w.設A是E的子集，并包含于G的某一最小生成樹中。設C=(Vc,Ec)為森林GA=(V,A) 的一個連通分支。如果邊是連接C和Ga中其他某聯通分支的一條輕邊，則(u,v)對集合A來說是安全.
在Kruskal(
克魯斯卡爾)算法和Prim(普里姆)算法
在Kruskal算法中，集合A是一個森林，加入集合A中的安全邊總是圖中連接兩個不同聯通分支的最小權邊。在Prim算法中，集合A僅形成單棵樹，添加入集合A的安全邊總是連接樹與一個不在樹中的頂點的最小權邊。
Kruskal(
克魯斯卡爾)算法(O(ElgE))：
該算法找出森林中連接任意兩棵樹的所有邊中，具有最小權值的邊(u,v)作為安全邊，并把它添加到正在生長的森林中。設C1和C2表示邊(u,v)連接的兩棵樹，因為(u,v)必是連接C1和其他某棵樹的一條輕邊，所以由上面推論可知，(u,v)對C1來說是安全邊。Kruskal 算法同時也是一種貪心算法， 因為在算法的每一步中，添加到森林中的邊的權值都是盡可能小的。
下面是偽代碼:
MST-KRUSKAL(G,w)
A<--空集
for each vertex v 屬于 V[G]
do MAKE-SET(v)
sort the edges of E into nondecreasing order by weight w
for each edge(u,v)屬于E,taken in nondecreasing order by weight
do if FIND-SET(u)!=FIND-SET(v)
then A<--AU{(u,v)}
UNION(u,v)
return A
FIND-SET(u)返回包含u的集合中的一個代表元素。于是通過測試FIND-SET(u)是否等同于FIND-SET(v)，就可以確定頂點u和v是否屬于同一棵樹。通過過程UNION，可以實現樹與樹的合并。
Prim算法(O(ElgV))
Prim算法的特點是集合A中的邊總是形成單棵樹。樹從任意根頂點r開始形成，并逐漸生成，直至該樹覆蓋了V中的所有頂點。在每一步，一條連接了樹A與Ga=(V,A)中某孤立頂點的輕邊被加入樹A中。由推論可知，該規則僅加入對A安全的邊，因此當算法終止時，A中的邊形成了一棵最小生成樹。因此每次添加到樹中的邊都是使樹的權盡可能小的邊，因此，上述策略也是“貪心“的。
偽代碼如下：
MST-PRIM(G,w,r)
for each u 屬于V[G]
do key[u] <--空集
n[u]<--NIL
key[r]<--0
Q<--V[G]
while Q!=空集
do u<---EXTRACT-MIN(Q)
for each v屬于Adj[u]
do if v 屬于Q and w(u,v)<key[v]
then n[u]<---u
key[v]<--w(u,v)
參考：算法導論
剛又想起了很多事情，想起了二高的美好時光，懷念西大，牛逼的2533，一切仿佛都在眼前，我是個懷舊的人。最近壓力好大，等有時間了想回西安看看，見見老大，大頭還有魏嵩他們。等回家了也要去二高去看看，高中畢業后還沒去過。
看過STL空間配置器的源碼，總結一下：
(1)STL空間配置器：主要分三個文件實現，stl_construct.h 這里定義了全局函數construct()和destroy(),負責對象的構造和析構。stl_alloc.h文件中定義了一，二兩級配置器，彼此合作，配置器名為alloc. stl_uninitialized.h 這里定義了一些全局函數，用來填充(fill)或復制(copy)大塊內存數據，他們也都隸屬于STL標準規劃。
在stl_alloc.h中定義了兩級配置器，主要思想是申請大塊內存池，小塊內存直接從內存池中申請，當不夠用時再申請新的內存池，還有就是大塊內存直接申請。當申請空間大于128字節時調用第一級配置器，第一級配置器沒有用operator::new和operator::delete來申請空間，而是直接調用malloc/free和realloc，并且實現了類似c++中new-handler的機制。所謂c++ new handler機制是，你可以要求系統在內存配置需求無法被滿足時，調用一個指定的函數。換句話說，一旦::operator::new無法完成任務，在丟出std::bad_alloc異常狀態之前，會先調用由客端指定的處理例程，該處理例程通常稱為new-handler.new-handler解決內存做法有特定的模式。SGI第一級配置器的allocate()和realloc都是在調用malloc和realloc不成功后，改調用oom_malloc()和oom_realloc().后兩者都有內循環，不斷調用"內存不足處理例程",期望在某次調用之后，獲得足夠的內存而圓滿完成任務。但如果“內存不足處理例程“并未被客端設定，oom_malloc()和oom_realloc便調用_THROW_BAD_ALLOC, 丟出bad_alloc異常信息，或利用exit(1)硬生生中止程序。
在stl_alloc.h中定義的第二級配置器中，如果區塊夠大，超過128字節時，就移交第一級配置器處理，當區塊小于128字節時，則以內存池管理，此法又稱為次層配置，每次配置一大塊內存，并維護對應的自由鏈表(free-list).下次若再有相同大小的內存需求，就直接從free-list中拔出。如果客端釋還小額區塊，就由配置器回收到free-lists中，配置器除了負責配置，也負責回收。為了管理方便，SGI第二級配置器會主動將任何小額區塊的內存需求量上調至8的倍數。并維護16個free-lists,各自管理大小分別為8，16，24，32，40，48，56，64，72，80，88，96，104， 112，120，128 字節的小額區塊。當申請小于等于128字節時就會檢查對應的free list，如果free-list中有可用的區塊，就直接拿來，如果沒有，就準備為對應的free-list 重新填充空間。新的空間將取自內存池，缺省取得20個新節點，如果內存池不足（還足以一個以上的節點），就返回的相應的節點數.如果當內存池中連一個節點大小都不夠時，就申請新的內存池,大小為2*total_bytes+ROUND_UP(heap_size>>4), totoal_bytes 為申請的空間大小，ROUND_UP調整為8的倍數，heap_size為當前總申請內存池的大小。如果申請該內存池成功就把原來內存池中剩下的空間分配給適當的free-list.萬一山窮水盡，整個system heap空間都不夠了（以至無法為內存池注入源頭活水），malloc()行動失敗，就會四處尋找有無"尚有未用區塊，且區塊足夠大 "之free lists.找到了就挖一塊交出，找不到就調用第一級配置器。第一級配置器其實也是使用malloc來配置內存。但它有out-of-memory處理機制（類似new-handler機制），或許有機會釋放其他的內存拿來此處使用。如果可以就成功，否則發出bad_alloc異常。
參考：STL源碼分析
虛函數是在類中被聲明為virtual的成員函數，當編譯器看到通過指針或引用調用此類函數時，對其執行晚綁定，即通過指針（或引用）指向的類的類型信息來決定該函數是哪個類的。通常此類指針或引用都聲明為基類的，它可以指向基類或派生類的對象。
多態指同一個方法根據其所屬的不同對象可以有不同的行為（根據自己理解，不知這么說是否嚴謹）。
舉個例子說明虛函數、多態、早綁定和晚綁定：
李氏兩兄妹（哥哥和妹妹）參加姓氏運動會（不同姓氏組隊參加），哥哥男子項目比賽，妹妹參加女子項目比賽，開幕式有一個參賽隊伍代表發言儀式，兄妹倆都想
去露露臉，可只能一人去，最終他們決定到時抓鬮決定，而組委會也不反對，它才不關心是哥哥還是妹妹來發言，只要派一個姓李的來說兩句話就行。運動會如期舉
行，妹妹抓鬮獲得代表李家發言的機會，哥哥參加了男子項目比賽，妹妹參加了女子項目比賽。比賽結果就不是我們關心的了。
現在讓我們來做個類比（只討論與運動會相關的話題）：
（1）類的設計：
李氏兄妹屬于李氏家族，李氏是基類（這里還是抽象的純基類），李氏又派生出兩個子類（李氏男和李氏女），李氏男會所有男子項目的比賽（李氏男的成員函
數），李氏女會所有女子項目的比賽（李氏女的成員函數）。姓李的人都會發言（基類虛函數），李氏男和李氏女繼承自李氏當然也會發言，只是男女說話聲音不一
樣，內容也會又差異，給人感覺不同（李氏男和李氏女分別重新定義發言這個虛函數）。李氏兩兄妹就是李氏男和李氏女兩個類的實體。
（2）程序設計：
李氏兄妹填寫參賽報名表。
（3）編譯：
李氏兄妹的參賽報名表被上交給組委會（編譯器），哥哥和妹妹分別參加男子和女子的比賽，組委會一看就明白了（早綁定），只是發言人選不明確，組委會看到報
名表上寫的是“李家代表”（基類指針），組委會不能確定到底是誰，就做了個備注：如果是男的，就是哥哥李某某；如果是女的，就是妹妹李某某（晚綁定）。組
委會做好其它準備工作后，就等運動會開始了（編譯完畢）。
（4）程序運行：
運動會開始了（程序開始運行），開幕式上我們聽到了李家妹妹的發言，如果是哥哥運氣好抓鬮勝出，我們將聽到哥哥的發言（多態）。然后就是看到兄妹倆參加比賽了。。。
但愿這個比喻說清楚了虛函數、多態、早綁定和晚綁定的概念和它們之間的關系。再說一下，早綁定指編譯器在編譯期間即知道對象的具體類型并確定此對象調用成員函數的確切地址；而晚綁定是根據指針所指對象的類型信息得到類的虛函數表指針進而確定調用成員函數的確切地址。
2、揭密晚綁定的秘密
編譯器到底做了什么實現的虛函數的晚綁定呢？我們來探個究竟。
編譯器對每個包含虛函數的類創建一個表（稱為V TA B L E）。在V TA B L E中，編譯器放置特定類的虛函數地址。在每個帶有虛函數的類
中，編譯器秘密地置一指針，稱為v p o i n t e r（縮寫為V P T R），指向這個對象的V TA B L E。通過基類指針做虛函數調 用時（也就是做多態調用時），編譯器靜態地插入取得這個V P T R，并在V TA B L E表中查找函數地址的代碼，這樣就能調用正確的函數使晚捆綁發生。為每個類設置V TA B L E、初始化V P T R、為虛函數調用插入代碼，所有這些都是自動發生的，所以我們不必擔心這些。利用虛函數， 這個對象的合適的函數就能被調用，哪怕在編譯器還不知道這個對象的特定類型的情況下。（《C++編程思想》）
————這段話紅色加粗部分似乎有點問題，我個人的理解看后面的總結。
在任何類中不存在顯示的類型信息，可對象中必須存放類信息，否則類型不可能在運行時建立。那這個類信息是什么呢？我們來看下面幾個類：
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;
}
以上三個類中：
no_virtual沒有虛函數，sizeof(no_virtual)=4，類no_virtual的長度就是其成員變量整型a的長度；
one_virtual有一個虛函數，sizeof(one_virtual)=8；
two_virtual
有兩個虛函數，sizeof(two_virtual)=8； 有一個虛函數和兩個虛函數的類的長度沒有區別，其實它們的長度就是no_virtual的
長度加一個void指針的長度，它反映出，如果有一個或多個虛函數，編譯器在這個結構中插入一個指針（ V P T R）。在one_virtual 和
two_virtual之間沒有區別。這是因為V P T R指向一個存放地址的表，只需要一個指針，因為所有虛函數地址都包含在這個表中。
這個VPTR就可以看作類的類型信息。
那我們來看看編譯器是怎么建立VPTR指向的這個虛函數表的。先看下面兩個類：
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;
}
兩個類VPTR指向的虛函數表（VTABLE）分別如下：
base類
——————
VPTR——> |&base::vfun1 |
——————
|&base::vfun2 |
——————
derived類
———————
VPTR——> |&derived::vfun1 |
———————
|&base::vfun2 |
———————
|&derived::vfun3 |
———————
每當創建一個包含有虛函數的類或從包含有虛函數的類派生一個類時，編譯器就為這個類創建一個VTABLE，如上圖所示。在這個表中，編譯器放置了在這個類
中或在它的基類中所有已聲明為virtual的函數的地址。如果在這個派生類中沒有對在基類中聲明為virtual的函數進行重新定義，編譯器就使用基類
的這個虛函數地址。（在derived的VTABLE中，vfun2的入口就是這種情況。）然后編譯器在這個類中放置VPTR。當使用簡單繼承時，對于每
個對象只有一個VPTR。VPTR必須被初始化為指向相應的VTABLE，這在構造函數中發生。
一旦VPTR被初始化為指向相應的VTABLE，對象就"知道"它自己是什么類型。但只有當虛函數被調用時這種自我認知才有用。
個人總結如下：
1、從包含虛函數的類派生一個類時，編譯器就為該類創建一個VTABLE。其每一個表項是該類的虛函數地址。
2、在定義該派生類對象時，先調用其基類的構造函數，然后再初始化VPTR，最后再調用派生類的構造函數（
從二進制的視野來看，所謂基類子類是一個大結構體，其中this指針開頭的四個字節存放虛函數表頭指針。執行子類的構造函數的時候，首先調用基類構造函
數，this指針作為參數，在基類構造函數中填入基類的vptr，然后回到子類的構造函數，填入子類的vptr，覆蓋基類填入的vptr。如此以來完成
vptr的初始化。 ）
3、在實現動態綁定時，不能直接采用類對象，而一定要采用指針或者引用。因為采用類對象傳值方式，有臨時基類對象的產生，而采用指針，則是通過指針來訪問外部的派生類對象的VPTR來達到訪問派生類虛函數的結果。
VPTR
常常位于對象的開頭，編譯器能很容易地取到VPTR的值，從而確定VTABLE的位置。VPTR總指向VTABLE的開始地址，所有基類和它的子類的虛函
數地址（子類自己定義的虛函數除外）在VTABLE中存儲的位置總是相同的，如上面base類和derived類的VTABLE中vfun1和vfun2
的地址總是按相同的順序存儲。編譯器知道vfun1位于VPTR處，vfun2位于VPTR+1處，因此在用基類指針調用虛函數時，編譯器首先獲取指針指
向對象的類型信息（VPTR），然后就去調用虛函數。如一個base類指針pBase指向了一個derived對象，那pBase->vfun2
()被編譯器翻譯為 VPTR+1 的調用，因為虛函數vfun2的地址在VTABLE中位于索引為1的位置上。同理，pBase->vfun3
()被編譯器翻譯為 VPTR+2的調用。這就是所謂的晚綁定。
我們來看一下虛函數調用的匯編代碼，以加深理解。
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'
由編譯器的注釋可知，此時PTR _td$[esp+24]中存儲的就是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
調用test函數時完成了如下工作：取對象td的地址，將其壓棧，然后調用test。
pBase->vfun2();編譯生成的匯編代碼如下：
mov ecx, DWORD PTR _pBase$[esp-4]
mov eax, DWORD PTR [ecx]
jmp DWORD PTR [eax+4]
首先從棧中取出pBase指針指向的對象地址賦給ecx，然后取對象開頭的指針變量中的地址賦給eax，此時eax的值即為VPTR的值，也就是
VTABLE的地址。最后就是調用虛函數了，由于vfun2位于VTABLE的第二個位置，相當于 VPTR+1，每個函數指針是4個字節長，所以最后的
調用被編譯器翻譯為 jmp DWORD PTR [eax+4]。如果是調用pBase->vfun1()，這句就該被編譯為
jmp DWORD PTR [eax]。
現在應該對多態、虛函數、晚綁定有比較清楚的了解了吧。
轉貼：http://blog.csdn.net/shenmea00000/archive/2007/10/31/1859762.aspx
轉載：http://www.shnenglu.com/converse/archive/2007/08/29/31179.html
/********************************************************************
created: 2007/08/28
filename: avltree.c
author: Lichuang
purpose: AVL樹的實現代碼,
參考資料<<數據結構與算法分析-C語言描述>>, 作者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) // 插入到左子樹中
{
pNode->pLeft = Insert(nData, pNode->pLeft);
if (Height(pNode->pLeft) - Height(pNode->pRight) == 2) // AVL樹不平衡
{
if (nData < pNode->pLeft->nData)
{
// 插入到了左子樹左邊, 做單旋轉
pNode = SingleRotateWithLeft(pNode);
}
else
{
// 插入到了左子樹右邊, 做雙旋轉
pNode = DoubleRotateWithLeft(pNode);
}
}
}
else if (nData > pNode->nData) // 插入到右子樹中
{
pNode->pRight = Insert(nData, pNode->pRight);
if (Height(pNode->pRight) - Height(pNode->pLeft) == 2) // AVL樹不平衡
{
if (nData > pNode->pRight->nData)
{
// 插入到了右子樹右邊, 做單旋轉
pNode = SingleRotateWithRight(pNode);
}
else
{
// 插入到了右子樹左邊, 做雙旋轉
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;
// 結點的位置變了, 要更新結點的高度值
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;
// 結點的位置變了, 要更新結點的高度值
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);
}
// 后序遍歷樹以刪除樹
void DeleteTree(AVLTree** ppRoot)
{
if (NULL == ppRoot || NULL == *ppRoot)
return;
DeleteTree(&((*ppRoot)->pLeft));
DeleteTree(&((*ppRoot)->pRight));
free(*ppRoot);
*ppRoot = NULL;
}
// 中序遍歷打印樹的所有結點, 因為左結點 < 父結點 < 右結點, 因此打印出來數據的大小是遞增的
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);
}
聽著舒伯特和肖邦的小夜曲，兩種不同的風格，聽了都特別的舒服，感覺特別地寧靜，讓我浮躁的心能安靜下來，說不上好在哪里，可能比較符合我現在的心境吧，或許我生活中還缺少某種元素。
以STL的運用角度而言，空間配置器時最不需要介紹的東西，它總是隱藏在一切組件的背后，整個STL的操作對象（所有的數值）都存放在容器之內，而容器一定需要配置空間以置放資料。下面是一個簡單空間配置器代碼（來自 STL源碼剖析）：
//jjalloc.h
#ifndef _JJALLOC_
#define _JJALLOC_
#include<new>
#include<cstddef>
#include<cstdlib>
#include<climits>
#include<iostream>
using namespace std;
namespace JJ
{
template<class T>
inline T* _allocate(ptrdiff_t size,T*)
{
set_new_handler(0);
T *tmp=(T*)(::operator new((size_t)(size* sizeof(T))));
if(tmp==0){
cerr<<"out of memory"<<endl;
exit(1);
}
return tmp;
}
template<class T>
inline void _deallocate(T* buffer)
{
::operator delete(buffer);
}
template<class T1,class T2>
inline void _construct(T1 *p,const T2& value)
{
new(p)T1(value);//placement new operator
}
template<class T>
inline void _destroy(T* ptr)
{
ptr->~T();
}
template<class T>class allocator{
public:
typedef T value_type;
typedef T* pointer;
typedef const T* const_pointer;
typedef T& reference;
typedef const T& const_reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
template<class U>
struct rebind
{
typedef allocator<U>other;
};
pointer allocate(size_type n,const void * hint=0)
{
return _allocate((difference_type)n,(pointer)0);
}
void deallocate(pointer p,size_type n)
{
_deallocate(p);
}
void construct(pointer p,const T& value)
{
_construct(p,value);
}
void destroy(pointer p){_destroy(p);}
pointer address(reference x){return (pointer)&x;}
const_pointer const_address(const_reference x)
{
return (const_pointer)&x;
}
size_type max_size()const{
return size_type(UINT_MAX/sizeof(T));
}
};
}//end of namespace JJ
#endif
//jjalloc.cc,測試上面這個簡單的配置器
#include"jjalloc.h"
#include<vector>
#include<iostream>
using namespace std;
int main()
{
int ia[5]={0,1,2,3,4};
unsigned int i;
vector<int,JJ::allocator<int> >iv(ia,ia+5);
for(i=0;i<iv.size();i++)
cout<<iv[i]<<' ';
cout<<endl;
}