[原创文章欢迎转载,但请保留作者信息]
Justin 于 2009-10-28
看的版本是
侯捷的繁体版
,有些术语乃至字都有些难懂。进度和理解程度竟然也没比英文的好多少@#¥%
侯捷把allocator译为配置器。配置器的接口大多不被STL用户看到,它的重要性在于几乎所有的其他STL对象都会请到它来配置(内存)资源。
STL自己的配置器有两套。第一套allocate是简单的对C++的operator new和delete的封装,STL自己没有用,也不推荐别人用(那你写来做啥捏?);第二套alloc是基于malloc、realloc和free实现的。alloc自身又有两级:
-
二级配置器实际上是个内存仓库管理员。当有资源申请需求时,alloc会先判断所需空间的大小。如果等于或小于128bytes,就使用二级配置器。这个内存仓库管理员有16个储藏室,分别存放着分配好的8bytes、16bytes、24bytes直至128bytes的内存块。二级配置器的设计基本就是STL allocator的精华了,本文最后会继续记录有什么需要注意的地方。
-
当需求空间大于128bytes时,我们就需要一级配置器申请。它没有什么现成的资源可以直接分配,而是用malloc/realloc向系统讨的。对于申请失败的处理,STL仿照C++的处理机制,提供了接口由客户指定函数作为new handler,以处理内存不足的情况。如果用户没有指定相应的函数,则直接抛出异常。
OK,重新回到二级配置器的可圈可点之处:
-
union的使用。“内存仓库管理员”的16个“储藏室”实际上是16个单向的linked-list,list中的每个节点就是一块内存。一块挂在list上的内存是没有被人用的,所以书上说它叫free list。说实话,如果是我来做这样的list的话,节点的设计一定是小学生水平,用一个struct,里面两个指针:一个指向空闲的内存,一个指向下一个节点。STL给我上了一课:使用union。(好吧,我还是要抄一下代码):
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
union obj
{
union obj* free_list_link;
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
char client_data[1]; /**//* The client sees this. */
};
我认为这里巧妙的利用了free list的这一个特点:当一块内存还挂在list上时,没有人在意这块内存里是什么;当真的有人要读写这块内存的时候(也就是已经分配给用户使用的时候),这块内存已经和list没有任何瓜葛了。
因此,同一块内存就可以在不同的时间扮演不同的角色:挂在list的时候就储存下一块内存的地址,脱离list后就随便你存放什么了。union几乎就是为这一功能量身定做的!减少了原来小学生设计的50%空间消耗!哇呀呀,太巧妙啦~~(请原谅我的浅薄,不知为不知,是知也……)
-
当申请空间的大小不是8bytes的整数倍时,用一个函数ROUND_UP向上取整为8bytes的整数倍数。这个函数是用位操作一次实现的。(好吧,我会去看Hacker’s Delight的……)
-
当没有某一个“储藏室”内内存用完了,而且这个时候又有用户申请时(哪壶不开提哪壶啊)的处理方法比较曲折,以下是我的解读(当然还是要免责一下:极小可能是完全正确的@#¥%)
碰到开门后发现“储藏室”没有存货的时候,二级配置器的第一个反应就是向内存池(memory pool)求助(外援?):
-
如果内存池有足够的货,就直接把需要的内存拨到相应的list上(发货到储藏室)。大功告成。
-
如果内存池还有空余内存,但是不能完全满足需要,那就本着互助互惠的原则,能给多少就给多少并且告诉你我只能给你XX个了,剩下的你自己去想办法吧。仁至义尽。
-
如果内存池的库存连一个单元的需求都满足不了了,面对的事情就比较罗嗦了:
-
先看看内存池还有没有剩下的资源,如果有,虽然不能满足当前的申请需要(比如说是56bytes),但可以放到更小一些的“储藏室”里嘛(比如说24bytes)。既然来了,能拿走的就拿走,总比空手回去好……
-
通过malloc向系统要资源(爸,我要你的钱)。因为是malloc,所以是在堆上(heap)找空闲的内存。既然是申请,自然就有以下两种结果:
-
malloc成功,总算抓住一根救命稻草。后面的工作就简单了,把堆上的内存扔到内存池,然后通过函数嵌套重新回到内存池里申请资源。
-
malloc失败(儿啊,家里也不宽裕了……)。外援是援不了了,这次真的是只能靠自己了。重新检查free list(储藏室)里的可用资源,不过这回是看看更大尺寸的free list里有没有可以用的(比如申请的是56bytes,这次回头看看有没有64bytes、72bytes等可以利用的内存块),如果有,就拿出一块,放回到内存池里。接下来就是通过函数嵌套重新回到内存池里去找资源了。说白了这种做法就是拆东墙补西墙@#¥%
如果自己家里也没存货了(所有大的储藏室都没有空余的内存块可以返回到内存池里),还真是屋漏偏逢连夜雨啊……没有其他办法了,只好求助本家兄弟——一级配置器,反正如果它也搞不定,就抛出异常,谁爱管就管去吧,老子管不了也不想管了@#¥%
-
__true_type与__false_type的使用。这个我会再专门写一篇学习笔记。【链接临时占位】
其实真正的STL配置器应该要更加复杂,因为侯捷在写这本书的时候为了省事就把多线程(书中称为多绪)的部分给跳过了。