SGI STL配置器詳解
SGI STL空間配置器是與衆不同的，其名稱是alloc而非allocator，而且不接受任何參數。如果你要在程式中采用SGI配置器，則不能采用标準寫法：
vector<int,std::allocator<int> > iv;//in VC or CB
vector<int,std::alloc> iv; //in GCC 必須這麼寫。
由于我們通常預設使用配置器，是以這個問題并不會對我們造成困擾。SGI也定義了一套符合部分标準，名為allocator的配置器，但SGI從未使用過它，因為他隻是對new以及delete進行了一層簡單的封裝，效率極低。SGI另有法寶供其自身使用，那就是特殊的空間配置器std::alloc，alloc具備兩層結構，分别為一級配置器和二級配置器，第一層配置器直接使用maloc()和free()函數，二級配置器則視情況采用不同的政策，當配置區塊超過128byte時，調用一級配置器，當配置區塊小于128時，為了降低額外負擔，采用複雜的memory pool整理方式。
SGI STL中可以選擇是否采用二級擴充卡，有如下宏條件定義：
'''
# ifdef __USE_MALLOC
typedef malloc_alloc alloc;//malloc_alloc為一級配置器
# else
...
template <bool threads, int inst>
class __default_alloc_template {...};//二級配置器
一級配置器的SGI STL源碼如下,其原理比較簡單，無需更多說明：
template <int __inst>
class __malloc_alloc_template {
private:
static void* _S_oom_malloc(size_t);
static void* _S_oom_realloc(void*, size_t);
#ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG
static void (* __malloc_alloc_oom_handler)();
#endif
public:
static void* allocate(size_t __n)
{
void* __result = malloc(__n);
if ( == __result) __result = _S_oom_malloc(__n);
return __result;
}
static void deallocate(void* __p, size_t /* __n */)
{
free(__p);
}
static void* reallocate(void* __p, size_t /* old_sz */, size_t __new_sz)
{
void* __result = realloc(__p, __new_sz);
if ( == __result) __result = _S_oom_realloc(__p, __new_sz);
return __result;
}
static void (* __set_malloc_handler(void (*__f)()))()
{
void (* __old)() = __malloc_alloc_oom_handler;
__malloc_alloc_oom_handler = __f;
return(__old);
}
};
// malloc_alloc out-of-memory handling
#ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG
template <int __inst>
void (* __malloc_alloc_template<__inst>::__malloc_alloc_oom_handler)() = ;
#endif
template <int __inst>
void*
__malloc_alloc_template<__inst>::_S_oom_malloc(size_t __n)
{
void (* __my_malloc_handler)();
void* __result;
for (;;) {
__my_malloc_handler = __malloc_alloc_oom_handler;
if ( == __my_malloc_handler) { __THROW_BAD_ALLOC; }
(*__my_malloc_handler)();
__result = malloc(__n);
if (__result) return(__result);
}
}
template <int __inst>
void* __malloc_alloc_template<__inst>::_S_oom_realloc(void* __p, size_t __n)
{
void (* __my_malloc_handler)();
void* __result;
for (;;) {
__my_malloc_handler = __malloc_alloc_oom_handler;
if ( == __my_malloc_handler) { __THROW_BAD_ALLOC; }
(*__my_malloc_handler)();
__result = realloc(__p, __n);
if (__result) return(__result);
}
}
第二級配置器__default_alloc_template剖析：
為了友善管理，SGI第二級配置器會主動将任何小額區塊的記憶體需求量調整至8的倍數，并且維護16個free-lists，各自管理大小為8到128這麼16個小額區塊。
union _Obj {
union _Obj* _M_free_list_link;
char _M_client_data[]; /* The client sees this. */
};
static _Obj* __STL_VOLATILE _S_free_list[_NFREELISTS];
為了維護一個連結清單，每個節點需要額外的指針指向下一個節點，這會造成一定的浪費，STL早已準備好解決途徑，那就是使用union來維護連結清單。當使用union第一字段時，union中的指針用來指向下一個節點，而當union使用第二字段時，union指針又可以指向實際用到的記憶體塊首位址。（其實個人了解覺得沒什麼意義，因為一般申請的記憶體塊都比較大。）
__default_alloc_template類部分聲明：
private:
// Really we should use static const int x = N
// instead of enum { x = N }, but few compilers accept the former.
#if ! (defined(__SUNPRO_CC) || defined(__GNUC__))
enum {_ALIGN = };
enum {_MAX_BYTES = };
enum {_NFREELISTS = }; // _MAX_BYTES/_ALIGN
# endif
static size_t
_S_round_up(size_t __bytes) /*__bytes不足8的倍數時，傳回8的倍數*/
{ return (((__bytes) + (size_t) _ALIGN-) & ~((size_t) _ALIGN - )); }
__PRIVATE:
union _Obj {
union _Obj* _M_free_list_link;
char _M_client_data[]; /* The client sees this. */
};
static size_t _S_freelist_index(size_t __bytes) {
return (((__bytes) + (size_t)_ALIGN-)/(size_t)_ALIGN - );
}// Returns an object of size __n, and optionally adds to size __n free list.
static void* _S_refill(size_t __n);
// Allocates a chunk for nobjs of size size. nobjs may be reduced
// if it is inconvenient to allocate the requested number.
static char* _S_chunk_alloc(size_t __size, int& __nobjs);
// Chunk allocation state.
static char* _S_start_free;
static char* _S_end_free;
static size_t _S_heap_size;
在配置設定記憶體時直接調用二級配置器，若大于128byte則使用一級配置器，二級配置器的基本接口函數如下：
public:
/* __n must be > 0 */
static void* allocate(size_t __n)
{
void* __ret = ;
//如果__n>128則調用一級配置器
if (__n > (size_t) _MAX_BYTES) {
__ret = malloc_alloc::allocate(__n);
}
else {
_Obj* __STL_VOLATILE* __my_free_list
= _S_free_list + _S_freelist_index(__n);//取得__n所在連結清單首節點
_Obj* __RESTRICT __result = *__my_free_list;
if (__result == )
__ret = _S_refill(_S_round_up(__n));//如果連結清單首節點為空，表示該__n大小記憶體區沒有可用碎片。
else {
*__my_free_list = __result -> _M_free_list_link;
__ret = __result;//如果存在則取出，并且删除首節點。
}
}
return __ret;
};
/* __p may not be 0 */
static void deallocate(void* __p, size_t __n)
{
if (__n > (size_t) _MAX_BYTES)
malloc_alloc::deallocate(__p, __n);
else {
_Obj* __STL_VOLATILE* __my_free_list
= _S_free_list + _S_freelist_index(__n);
_Obj* __q = (_Obj*)__p;
__q -> _M_free_list_link = *__my_free_list;//将需要釋放的小記憶體插入對應連結清單首節點。
*__my_free_list = __q;
}
}
static void* reallocate(void* __p, size_t __old_sz, size_t __new_sz);//将p指針重新指向一塊記憶體塊。
} ;
下面單獨分析每個函數的源碼：
調用二級配置器時，當對應連結清單為空時，需要_S_refill()函數向記憶體池(memory pool)重新申請，記憶體池的首位址為static char* _S_start_free，末尾位址為
static char* _S_end_free來維護。
/*if (__result == 0)
__ret = _S_refill(_S_round_up(__n));//如果連結清單首節點為空，表示該__n大小記憶體區沒有可用碎片。*/
template <bool __threads, int __inst>
void*
__default_alloc_template<__threads, __inst>::_S_refill(size_t __n)
{
int __nobjs = ;//預設申請20塊區域
char* __chunk = _S_chunk_alloc(__n, __nobjs);//真正向記憶體池申請的函數，__nobjs傳遞參數為引用，__nobjs的傳回值表示已申請到的個數。
_Obj* __STL_VOLATILE* __my_free_list;
_Obj* __result;
_Obj* __current_obj;
_Obj* __next_obj;
int __i;
if ( == __nobjs) return(__chunk);//當隻申請到1塊時，直接傳回
__my_free_list = _S_free_list + _S_freelist_index(__n);
/* Build free list in chunk */
__result = (_Obj*)__chunk;
*__my_free_list = __next_obj = (_Obj*)(__chunk + __n);
for (__i = ; ; __i++) {
__current_obj = __next_obj;
__next_obj = (_Obj*)((char*)__next_obj + __n);
if (__nobjs - == __i) {
__current_obj -> _M_free_list_link = ;
break;
} else {
__current_obj -> _M_free_list_link = __next_obj;
}
}
return(__result);
_S_chunk_alloc()函數向記憶體池申請資源：
/* We allocate memory in large chunks in order to avoid fragmenting */
/* the malloc heap too much. */
/* We assume that size is properly aligned. */
/* We hold the allocation lock. */
template <bool __threads, int __inst>
char*
__default_alloc_template<__threads, __inst>::_S_chunk_alloc(size_t __size,
int& __nobjs)
{
char* __result;
size_t __total_bytes = __size * __nobjs;
size_t __bytes_left = _S_end_free - _S_start_free;
if (__bytes_left >= __total_bytes) {
__result = _S_start_free;
_S_start_free += __total_bytes;
return(__result);
} else if (__bytes_left >= __size) {
__nobjs = (int)(__bytes_left/__size);
__total_bytes = __size * __nobjs;
__result = _S_start_free;
_S_start_free += __total_bytes;
return(__result);
} else {
size_t __bytes_to_get =
* __total_bytes + _S_round_up(_S_heap_size >> );
// Try to make use of the left-over piece.
if (__bytes_left > ) {
//如果剩餘空間小于__size,則将剩餘空間插入對應連結清單。
_Obj* __STL_VOLATILE* __my_free_list =
_S_free_list + _S_freelist_index(__bytes_left);
((_Obj*)_S_start_free) -> _M_free_list_link = *__my_free_list;
*__my_free_list = (_Obj*)_S_start_free;
}
_S_start_free = (char*)malloc(__bytes_to_get);
if ( == _S_start_free) {
size_t __i;
_Obj* __STL_VOLATILE* __my_free_list;
_Obj* __p;
/*當malloc申請記憶體失敗時，我們将手伸向還沒有被使用的連結清單區塊，當然不會選擇那些比__size還要小的區塊，這樣遞歸下去會導緻效率變得很低。*/
for (__i = __size;
__i <= (size_t) _MAX_BYTES;
__i += (size_t) _ALIGN) {
__my_free_list = _S_free_list + _S_freelist_index(__i);
__p = *__my_free_list;
if ( != __p) {
*__my_free_list = __p -> _M_free_list_link;
_S_start_free = (char*)__p;
_S_end_free = _S_start_free + __i;
return(_S_chunk_alloc(__size, __nobjs));
// Any leftover piece will eventually make it to the
// right free list.
}
}
_S_end_free = ; // In case of exception.
_S_start_free = (char*)malloc_alloc::allocate(__bytes_to_get);
// This should either throw an
// exception or remedy the situation. Thus we assume it
// succeeded.
}
_S_heap_size += __bytes_to_get;
_S_end_free = _S_start_free + __bytes_to_get;
return(_S_chunk_alloc(__size, __nobjs));//此時記憶體池空間已經足夠，遞歸調用_S_chunk_alloc來調整__nobjs的值以及記憶體塊布局。
}
}
為了使配置器擁有标準接口，STL選擇将其做進一步的封裝：
template<class _Tp, class _Alloc>
class simple_alloc {
public:
static _Tp* allocate(size_t __n)
{ return == __n ? : (_Tp*) _Alloc::allocate(__n * sizeof (_Tp)); }
static _Tp* allocate(void)
{ return (_Tp*) _Alloc::allocate(sizeof (_Tp)); }
static void deallocate(_Tp* __p, size_t __n)
{ if ( != __n) _Alloc::deallocate(__p, __n * sizeof (_Tp)); }
static void deallocate(_Tp* __p)
{ _Alloc::deallocate(__p, sizeof (_Tp)); }
};
于是在vector類中可以看到是這樣使用的：
typedef simple_alloc<value_type,Alloc> data_allocator;
配置器的大體實作就是這麼多了，當然還有防止多線程的加鎖方案沒有加進去。
![STL--vector容器STL—vector容器[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)