SGI STL V3.2 源码剖析 - 空间配置器
1.1. 文件名
bits/stl_alloc.h
1.2. 背景知识
候捷在《STL源代码剖析》中说：“源码之前，了无秘密”，自然是大师的潇洒之语。但是，如果你不熟悉C++ template的基本语法，不明白Generic Programming的基本概念，那么即便STL的源码当前，对你来讲仍会有很多秘密。所以，先简要介绍一些必要的背景知识，扫清前进的障碍。
1.2.1. 两种风格的allocator
SGI STL中有两种风格的allocator，分别是STL standard style和SGI style，其区别说明如下：
1. STL standard allocator是STL标准定义的，必须实现以下接口和associated type（以下T表示该allocator负责管理的对象类型）：
? Associated type：
value_type 负责管理的对象类型（T）
pointer 指向T的指针
const_pointer 指向const T的指针
referance T的引用
const_referance T的const引用
size_type 分配的对象个数的类型，注意类型中还隐含着它可以表示的最大值，所以一般情况下size_type就是size_t，但某些情况下size_t可能无法胜任，比如某个allocator可以分配的对象个数非常多（从硬盘中分配空间），多至超过了size_t的最大值，此时size_type就不能是size_t，而应该是一个最大值更大的type。
defferance_type 指针相减结果的类型，一般情况下就是ptrdiff_t，但也有可能不是ptrdiff_t，道理同size_type。
rebind rebind是一个内置class，它定义了一个associated type other，other也是一个allocator的实例，但是负责管理的对象类型T不同。
? 接口：
default constructor
copy constructor
generic copy constructor
destructor
pointer address( referance& )
const_pointer address( const_referance& ) const
void* allocate( size_type __n, const void* hint )
分配空间，大小为__n*sizeof(T)，hint是一个保留参数，一般不使用，__n允许为零，如果__n为零则返回零。
void deallocate( pointer p, size_type n)
释放p指向的内存空间，n是T的个数。
size_type max_size()
可以分配的T的个数之最大值。
void constructor( pointer p, const Tp& )
在p所指向的空间上以Tp为蓝本构造T类型的对象。
void destroy( pointer p )
析构p所知向的T类型对象。
2. SGI style不需要实现上述associated type和接口，一般它只需要实现以下接口：
void * allocate(size_t n)
n表示分配的内存字节数，注意没有保留参数hint
void deallocate(void *p, size_t n)
n表示释放的内存字节数
void * reallocate(void *p, size_t old_sz, size_t new_sz)
old_sz和new_sz均表示字节数
1.2.2. 配接器 adaptor
配接器是一个类（通常称之为配接器类），它将某个类的接口改变为另一种接口。配接器类看起来像是一个新的类，之所以说看起来像，是因为配接器类必须依赖原来那个类的接口，不是一种真正意义上的独立的新类。
配接器是一种设计模式。
1.3. class __new_alloc
1.3.1. 风格
SGI Style allocator。
1.3.2. 接口
1.3.2.1. allocate
直接调用operator new分配空间。
1.3.2.2. deallocate
直接调用operator delete分配空间。
1.4. template class __malloc_alloc_template
1.4.1. 泛型参数
int __inst
__inst在代码中没有被使用过，存在的意义只是使得__malloc_alloc_template成为一个template，可以具现为不同的class。
1.4.2. 风格
SGI Style allocator。
1.4.3. 说明
1.4.3.1. 对operator new的全面模拟
由于allocator不使用operator new分配空间（它是用malloc分配空间），malloc跟operator new (注意是operator new 而不是new)的一个重要区别是new在发现空间不足时会不断地循环调用用户预先使用set_new_handel设置的new_handel函数，直至内存分配成功（或者其他情况跳出了循环），__malloc_alloc_template模拟实现了这种情况，它提供一个接口__set_malloc_handel，用来设置malloc_handel，当malloc失败时会循环调用malloc_handel直至下一次malloc分配成功（或者其他情况跳出了循环）。
为了保证allocate不会陷入死循环，malloc_handel的行为必须符合一下某种情况：
1. 释放空间，使得下一次malloc成功或更加趋向于成功；
2. 抛出异常；
3. 进程退出；
1.4.3.2. 函数指针、参数为函数指针的函数、返回值为函数指针的函数
1. void (* f)( int i )
f是一个指针(具体地说，它是一个函数指针)，它指向一个函数，该函数接收一个int参数，返回void；
2. void func( int (*p)( int i ) );
func是一个函数，它接收的参数是一个函数指针，该函数指针指向的函数接收一个int参数，返回一个int，func返回void；
3. void (* func( int i ) )( float f );
func是一个函数，它接收一个整型参数i，返回一个函数指针，该指针指向的函数接收一个float型参数，返回void；
4. void (* func( int (* f)( int i ) ) )( float f )
func是一个函数，它接收一个函数指针，返回值也是函数指针。
1.4.4. 接口
1.4.4.1. staitc void* allocate( size_t n )
调用malloc分配n个字节的内存空间，如果成功，则返回分配到的内存地址，如果失败则调用__S_oom_malloc，返回调用结果。
1.4.4.2. static void* deallocate( void* p, size_t /* n */ )
调用free释放p指向的内存空间。
1.4.4.3. static void* reallocate( void* p, size_t /* old_size */, size_t new_size )
调用realloc重新分配一块大小为new_size的内存空间，如果成功，则返回新地址，如果失败，则调用__S_oom_realloc，返回调用结果。
1.4.4.4. static void (* __set_malloc_handler( void (*__f)() ) )()
设置新的malloc_handel，返回旧的malloc_handel。malloc_handel是一个函数指针，接收void，返回void。
1.4.5. 实现
1.4.5.1. void* __S_oom_malloc( size_t n )
不断循环，先调用malloc_handel，后调用malloc，直至malloc成功或者其他条件退出。
1.4.6. 特化类 malloc_alloc
inst特化为0。
1.4.6.1. void* __S_oom_realloc( size_t n )
不断循环，先调用malloc_handel，后调用realloc，直至realloc成功或者其他条件退出。
1.4.7. 思考
为什么要使用template? used to permit multiple instantiations?
为什么要用malloc模拟operator new,而不直接使用operator new？也就是说既然有了__new_alloc，似乎没有必要再使用__malloc_alloc_template。
1.5. template class __default_alloc_template
1.5.1. 泛型参数
bool __thread 是否支持多线程；
int __inst 类似于__malloc_alloc_template的__inst；
1.5.2. 风格
SGI style allocator。
1.5.3. 接口
1.5.3.1. void* allocate( size_t n )
allocate采用所谓的双层分配策略，对小块内存和大块内存的分配和释放采用不同的策略，这样做的好处是：
1. 极大程度地提高了小块内存分配和释放的时间效率，小块内存分配和释放不再调用new和delete；
2. 由于减少了由于大量的小块内存分配和释放所造成的内存碎片以及操作系统管理内存的空间开销，所以提高了内存空间利用率。
下面详细说明allocate的分配策略：
如果分配的空间大小大于_MAX_BYTES（默认为128）或者设置了环境变量GLIBCPP_FORCE_NEW，那么直接使用__new_alloc::allocate来分配空间，__new_alloc::allocate直接使用new来分配内存的，这是内存分配的常规方法；
如果分配的空间大小小于等于_MAX_BYTES并且没有设置环境变量GLIBCPP_FORCE_NEW，那么先从FREELIST队列中取，如果在FREELIST没有取到，那么从memory pool中取20个节点挂到FREELIST中，并返回一个节点，也就是说同时在FREELIST中增加了19个节点；如果memory pool也空间不够（不够分配20个节点），那么尽可能多地分配节点，返回一个节点并将剩余节点挂到FREELIST中；如果连一个节点的空间都不够了，那么需要增长memory pool的空间然后再次申请。
增长memory pool的策略是首先将memory pool中的剩余空间作为一个节点（因为此时剩余空间大小一定小于128，不然不会一个节点空间都不够）挂到FREELIST中去（这样做是为了后面可以直接调用__new_alloc的allocate分配新的memory pool，而不需要调用reallocate，因为调用reallocate首先要释放原来的小空间，会产生内存碎片），然后调用__new_alloc的allocate企图为其分配40个节点外加一个调整因子（调整因子是当前已经分配了的所有小块内存，包括已经释放了的，的总大小整除16），如果_new_alloc::allocate也分配失败，那么尝试将FREELIST中的一个大节点回收到memory pool中，如果FREELIST中已经没有大节点了，那么再尝试调用一次__new_alloc::allocate（死马当成活马医）。
该方法是支持多线程的，前提是泛型参数__ thread必须设置为true，如果只是单线程访问，那么应该将__ thread设置为false，因为多线程版本总是比单线程版本慢。
注意一个实现技巧，多线程操作的时候也可以不用锁，如果不用锁，那么必须使用原子量，而且必须使用原子操作来操作这些原子量。
1.5.3.2. void deallocate( void* p, size_t n )
释放空间，是allocate的逆过程，大块内存直接调用__new_alloc::deallocate释放，小块内存回收到FREELIST中去，而不做实际的释放操作。
1.5.3.3. void reallocate( void* p, size_t old_size, size_t new_size )
如果原空间old_size和新空间new_size均大于_MAX_BYTES（128），那么直接调用全局的reallocate；
否则，如果old_size和new_size在FREELIST下标相同，也就是说old_size和new_size都小于等于_MAX_BYTES（128）而且两者整除_ALIGN(8)结果相等，那么直接返回，不用重新分配空间；
其他情况，都先调用自己的allocate分配空间，然后调用memcpy将旧空间的内容整体一次性拷贝到新空间，然后调用自己的deallocate释放旧的空间。
1.6. class alloc
如果定义了__USE_MALLOC，那么alloc即malloc_alloc，否则alloc为__default_alloc_template的多线程版本。
1.7. class single_client_alloc
如果定义了__USE_MALLOC，那么singel_client_alloc即malloc_alloc，否则singel_client_alloc为__default_alloc_template的单线程版本（或者称为thread-unsafe版本）。
1.8. template class __simple_alloc ( adaptor )
1.8.1. 泛型参数
typename _Tp 需要分配或者释放内存的对象类型
typename _Alloc 底层的allocator，必须是SGI Style的
1.8.2. 风格
它既不是standard style allocator也不是SGI style allocator，但趋向与将它看做是一种简化的STL standard allocator。
1.8.3. 说明
它是一个adaptor，将SGI style的allocator的接口转换为以下的接口。
1.8.4. 接口
1.8.4.1. static _T* allocate( size_t n )
为n个_T分配内存空间，返回_T*型的指针指向内存的开始位置。
底层是直接调用_Alloc的allocate方法分配空间的。
1.8.4.2. static _T* allocate()
分配1个_T的内存空间，返回_T*型的指针指向内存的开始位置。
底层是直接调用_Alloc的allocate方法分配空间的。
1.8.4.3. staitc void deallocate( _T* p, size_t n )
回收p指向的内存空间。
底层直接调用_Alloc的deallocate方法实现，注意_Alloc::deallocate必须接收两个参数，第二个参数size_t n传的是sizeof( _T )*n。
1.8.4.4. staitc void deallocate( _T* p )
回收p指向的内存空间。
底层直接调用_Alloc的deallocate方法实现，注意_Alloc::deallocate必须接收两个参数，第二个参数size_t n传的是sizeof( _T )。
1.9. template class __debug_alloc ( adaptor )
1.9.1. 泛型参数
typename _Alloc 底层的allocator，必须是SGI style的。
1.9.2. 风格
带debug功能的SGI style allocator。
1.9.3. 说明
它是一个adaptor，将一个SGI style allocator转化为带有debug功能的SGI style allocator。
__debug_alloc的allocate reallocate 会在新分配地址的头部额外多增加8个字节，用来存放新分配空间的大小，dealloate和reallocate会验证传入的释放空间大小是否等于待释放地址头部8个字节存放的空间大小，如果不相等，则abort。
1.9.4. 接口
1.9.4.1. static void* allocate( size_t n )
会额外在头部分配8个字节的空间，用来存储n。
1.9.4.2. static void deallocate( void* p, size_t n )
会比较n和p头部的8个字节是否相等，如果不相等，abort。
1.9.4.3. static void* reallocate( void* p, size_t old_size, size_t new_size )
会比较old_size和p头部的8个字节是否相等，如果不相等，abort。
1.10. template class allocator ( adaptor )
1.10.1. 泛型参数
_Tp 管理的对象类型。
1.10.2. 风格
STL standard allocator
1.10.3. 说明
它是一个adaptor，将一个SGI style allocator转化为STL standard allocator。
1.11. template class __allocator ( adaptor )
1.11.1. 泛型参数
typename _Tp 管理的对象类型
typename _Alloc 底层allocator，必须是SGI style的
1.11.2. 风格
STL standard allocator
1.11.3. 说明
它是一个adaptor，将SGI style的allocator来转换为STL standard allocator。
有一个_Tp为void的偏特化版本。
1.11.4. 偏特化
template< typename _Alloc> struct __allocate<void, _Alloc>
1.12. template class _Alloc_traits ( adaptor )
1.12.1. 泛型参数
typename _Tp
typename _Allocator
1.12.2. 说明
_Alloc_traits是一个adaptor，它有两个作用：
1. 它将一个既可能是STL standard style又可能是SGI style的_Allocator转化为STL standard allocator；
2. 它指明一个allocator是否是无状态的，如果是无状态的，那么它还会将它转化为SGI style allocator。该功能的好处是如果allocator是无状态的，那么就不需要在contain中保存这个allocator，可以节省空间。
1.12.3. Associated type
1.12.3.1. allocator_type
allocator_type定义为_Allocator::template rebind<_Tp>::other。
它是STL Standard Style的allocator。
1.12.3.2. _Alloc_type
只有当_S_instanceless为true时才声明这个associated type。
_Alloc_type必须有以下两个接口：
static _Tp* allocate(size_t n)
static void deallocate(_Tp*, size_t n)
其中n表示的是_Tp类型元素的个数。
1.12.4. 内部实现
1.12.4.1. static const bool _S_instanceless
设置为false。如果为true则表示allocator_type的两个实例没有任何区别（可以理解为allocator_type是无状态的），如果为false则表示有区别（可以理解为allocator_type是有状态的）。泛型版本应当设置为false，因为无状态是特殊情况。
1.12.5. 偏特化版本
1.12.5.1. template< typename _Tp, typename _Tp1 > _Alloc_traits< _Tp, allocator<_Tp1> >
它是针对allocator的偏特化版本，allocator_type为allocator<Tp1>，_S_instanceless为true，_Alloc_type为__simple_alloc<_Tp, __alloc>。
allocator是使用__alloc实现的一个STL standard allocator。
__alloc是__default_alloc_template的多线程版本特化类。
1.12.5.2. template< typename _Tp, int inst> _Alloc_traits< _Tp, __malloc_alloc_template< inst> >
它是针对__malloc_alloc_template的偏特化版本，allocator_type为__allocator<_Tp, __malloc_alloc_template<__inst> >，_S_instanceless为true，_Alloc_type为__simple_alloc<_Tp, __malloc_alloc_template<__inst> >。
1.12.5.3. template< typename _Tp, bool __thread, int __inst > _Alloc_traits< _Tp, __default_alloc_template< __thread, __inst > >
它是针对__default_alloc_template的偏特化版本，allocator_type为__allocator<_Tp, __default_alloc_template<__thread, __inst> >，_S_instanceless为true，_Alloc_type为__simple_alloc<_Tp, __default_alloc_template<__thread, __inst> >
1.12.5.4. template< typename _Tp, typename _Alloc > _Alloc_traits< _Tp, __debug_alloc< _Alloc> >
它是针对__debug_alloc的偏特化版本，allocator_type为__allocator<_Tp, __debug_alloc<_Alloc> >，_S_instanceless为true，_Alloc_type为__simple_alloc<_Tp, __debug_alloc<_Alloc> >
1.12.5.5. template<typename _Tp, typename _Tp1, int __inst> struct _Alloc_traits<_Tp, __allocator<_Tp1, __malloc_alloc_template<__inst> > >
它是针对__allocator<_Tp1, __malloc_alloc_template<__inst> >的偏特化版本，__allocator是一个adaptor，将__malloc_alloc_template的接口转换成STL standard allocator的接口。allocator_type为__allocator<_Tp, __malloc_alloc_template<__inst> >，_S_instanceless为true，_Alloc_type为__simple_alloc<_Tp, __malloc_alloc_template<__inst> >。
1.12.5.6. template<typename _Tp, typename _Tp1, bool __thr, int __inst> struct _Alloc_traits<_Tp, __allocator<_Tp1, __default_alloc_template<__thr, __inst> > >
它是针对__allocator<_Tp1, __default_alloc_template<__thr, __inst> > >的偏特化版本，__allocator是一个adaptor，将__malloc_alloc_template的接口转换成STL standard allocator的接口。allocator_type为_allocator<_Tp, __default_alloc_template<__thr,__inst> >，_S_instanceless为true，_Alloc_type为__simple_alloc<_Tp, __default_alloc_template<__thr,__inst> >
1.12.5.7. template<typename _Tp, typename _Tp1, typename _Alloc> struct _Alloc_traits<_Tp, __allocator<_Tp1, __debug_alloc<_Alloc> > >
它是针对__allocator<_Tp1, __debug_alloc<_Alloc> > >的偏特化版本，__allocator是一个adaptor，将__malloc_alloc_template的接口转换成STL standard allocator的接口。allocator_type为__allocator<_Tp, __debug_alloc<_Alloc> > allocator_type，_S_instanceless为true，_Alloc_type为__simple_alloc<_Tp, __debug_alloc<_Alloc> >
1.13. operator== 和 operator!=
1.13.1. allocator<T1> 与 allocator<T2>
相等。
1.13.2. __allocator<_Tp, _Alloc> 和 __allocator<_Tp, _Alloc>
如果它们赖以实现的底层的allocator相等，则相等，否则就不相等。
1.13.3. __malloc_alloc_template<inst> 和 __malloc_alloc_template<inst>
相等。
1.13.4. __default_alloc_template<__threads, __inst> 和 __default_alloc_template<__threads, __inst>
相等。
1.13.5. debug_alloc<_Alloc> 和 debug_alloc<_Alloc>
相等。
