?
[原創(chuàng)文章歡迎轉(zhuǎn)載，但請(qǐng)保留作者信息]
Justin 于 2009-10-28
看的版本是
侯捷的繁體版
，有些術(shù)語(yǔ)乃至字都有些難懂。進(jìn)度和理解程度竟然也沒比英文的好多少@#￥%
侯捷把a(bǔ)llocator譯為配置器。配置器的接口大多不被STL用戶看到，它的重要性在于幾乎所有的其他STL對(duì)象都會(huì)請(qǐng)到它來配置(內(nèi)存)資源。
STL自己的配置器有兩套。第一套allocate是簡(jiǎn)單的對(duì)C++的operator new和delete的封裝，STL自己沒有用，也不推薦別人用(那你寫來做啥捏？)；第二套alloc是基于malloc、realloc和free實(shí)現(xiàn)的。alloc自身又有兩級(jí)：
-
二級(jí)配置器實(shí)際上是個(gè)內(nèi)存?zhèn)}庫(kù)管理員。當(dāng)有資源申請(qǐng)需求時(shí)，alloc會(huì)先判斷所需空間的大小。如果等于或小于128bytes，就使用二級(jí)配置器。這個(gè)內(nèi)存?zhèn)}庫(kù)管理員有16個(gè)儲(chǔ)藏室，分別存放著分配好的8bytes、16bytes、24bytes直至128bytes的內(nèi)存塊。二級(jí)配置器的設(shè)計(jì)基本就是STL allocator的精華了，本文最后會(huì)繼續(xù)記錄有什么需要注意的地方。
-
當(dāng)需求空間大于128bytes時(shí)，我們就需要一級(jí)配置器申請(qǐng)。它沒有什么現(xiàn)成的資源可以直接分配，而是用malloc/realloc向系統(tǒng)討的。對(duì)于申請(qǐng)失敗的處理，STL仿照C++的處理機(jī)制，提供了接口由客戶指定函數(shù)作為new handler，以處理內(nèi)存不足的情況。如果用戶沒有指定相應(yīng)的函數(shù)，則直接拋出異常。
OK，重新回到二級(jí)配置器的可圈可點(diǎn)之處：
-
union的使用。“內(nèi)存?zhèn)}庫(kù)管理員”的16個(gè)“儲(chǔ)藏室”實(shí)際上是16個(gè)單向的linked-list，list中的每個(gè)節(jié)點(diǎn)就是一塊內(nèi)存。一塊掛在list上的內(nèi)存是沒有被人用的，所以書上說它叫free list。說實(shí)話，如果是我來做這樣的list的話，節(jié)點(diǎn)的設(shè)計(jì)一定是小學(xué)生水平，用一個(gè)struct，里面兩個(gè)指針：一個(gè)指向空閑的內(nèi)存，一個(gè)指向下一個(gè)節(jié)點(diǎn)。STL給我上了一課：使用union。(好吧，我還是要抄一下代碼)：
union?obj?
{
??????union?obj*?free_list_link;
??????char?client_data[1];?/**//*?The?client?sees?this.?*/
};
我認(rèn)為這里巧妙的利用了free list的這一個(gè)特點(diǎn)：當(dāng)一塊內(nèi)存還掛在list上時(shí)，沒有人在意這塊內(nèi)存里是什么；當(dāng)真的有人要讀寫這塊內(nèi)存的時(shí)候(也就是已經(jīng)分配給用戶使用的時(shí)候)，這塊內(nèi)存已經(jīng)和list沒有任何瓜葛了。
因此，同一塊內(nèi)存就可以在不同的時(shí)間扮演不同的角色：掛在list的時(shí)候就儲(chǔ)存下一塊內(nèi)存的地址，脫離list后就隨便你存放什么了。union幾乎就是為這一功能量身定做的！減少了原來小學(xué)生設(shè)計(jì)的50%空間消耗！哇呀呀，太巧妙啦～～（請(qǐng)?jiān)徫业臏\薄，不知為不知，是知也……）
-
當(dāng)申請(qǐng)空間的大小不是8bytes的整數(shù)倍時(shí)，用一個(gè)函數(shù)ROUND_UP向上取整為8bytes的整數(shù)倍數(shù)。這個(gè)函數(shù)是用位操作一次實(shí)現(xiàn)的。(好吧，我會(huì)去看Hacker’s Delight的……)
-
當(dāng)沒有某一個(gè)“儲(chǔ)藏室”內(nèi)內(nèi)存用完了，而且這個(gè)時(shí)候又有用戶申請(qǐng)時(shí)(哪壺不開提哪壺啊)的處理方法比較曲折，以下是我的解讀(當(dāng)然還是要免責(zé)一下：極小可能是完全正確的@#￥%)
?? 碰到開門后發(fā)現(xiàn)“儲(chǔ)藏室”沒有存貨的時(shí)候，二級(jí)配置器的第一個(gè)反應(yīng)就是向內(nèi)存池(memory pool)求助(外援？)：
-
如果內(nèi)存池有足夠的貨，就直接把需要的內(nèi)存撥到相應(yīng)的list上(發(fā)貨到儲(chǔ)藏室)。大功告成。
-
如果內(nèi)存池還有空余內(nèi)存，但是不能完全滿足需要，那就本著互助互惠的原則，能給多少就給多少并且告訴你我只能給你XX個(gè)了，剩下的你自己去想辦法吧。仁至義盡。
-
如果內(nèi)存池的庫(kù)存連一個(gè)單元的需求都滿足不了了，面對(duì)的事情就比較羅嗦了：
-
先看看內(nèi)存池還有沒有剩下的資源，如果有，雖然不能滿足當(dāng)前的申請(qǐng)需要(比如說是56bytes)，但可以放到更小一些的“儲(chǔ)藏室”里嘛(比如說24bytes)。既然來了，能拿走的就拿走，總比空手回去好……
-
通過malloc向系統(tǒng)要資源(爸，我要你的錢)。因?yàn)槭莔alloc，所以是在堆上(heap)找空閑的內(nèi)存。既然是申請(qǐng)，自然就有以下兩種結(jié)果：
-
malloc成功，總算抓住一根救命稻草。后面的工作就簡(jiǎn)單了，把堆上的內(nèi)存扔到內(nèi)存池，然后通過函數(shù)嵌套重新回到內(nèi)存池里申請(qǐng)資源。
-
malloc失敗(兒啊，家里也不寬裕了……)。外援是援不了了，這次真的是只能靠自己了。重新檢查free list(儲(chǔ)藏室)里的可用資源，不過這回是看看更大尺寸的free list里有沒有可以用的(比如申請(qǐng)的是56bytes，這次回頭看看有沒有64bytes、72bytes等可以利用的內(nèi)存塊)，如果有，就拿出一塊，放回到內(nèi)存池里。接下來就是通過函數(shù)嵌套重新回到內(nèi)存池里去找資源了。說白了這種做法就是拆東墻補(bǔ)西墻@#￥%
如果自己家里也沒存貨了(所有大的儲(chǔ)藏室都沒有空余的內(nèi)存塊可以返回到內(nèi)存池里)，還真是屋漏偏逢連夜雨啊……沒有其他辦法了，只好求助本家兄弟——一級(jí)配置器，反正如果它也搞不定，就拋出異常，誰愛管就管去吧，老子管不了也不想管了@#￥%
-
__true_type與__false_type的使用。這個(gè)我會(huì)再專門寫一篇學(xué)習(xí)筆記。【鏈接臨時(shí)占位】
其實(shí)真正的STL配置器應(yīng)該要更加復(fù)雜，因?yàn)楹罱菰趯戇@本書的時(shí)候?yàn)榱耸∈戮桶讯嗑€程(書中稱為多緒)的部分給跳過了。