szwolf

???使用STL已經(jīng)有一段時(shí)間了，對(duì)里面的運(yùn)作方式一直不了解。這幾天突發(fā)其想，找了一些關(guān)于STL源碼的書(shū)看了一下，覺(jué)得其內(nèi)部實(shí)現(xiàn)非常精妙。作為進(jìn)一步學(xué)習(xí)，我打算把STL中的主要組件自己動(dòng)手實(shí)現(xiàn)一下。
???首先從空間配置器開(kāi)始，從內(nèi)部逐漸了解STL中各種容器的實(shí)現(xiàn)細(xì)節(jié)。
???根據(jù)STL的規(guī)范，allocator必須有以下接口：
???

typedef????size_t????????size_type;
typedef????T????????value_type;
typedef????T * ????????pointer;
typedef????ptrdiff_t????difference_type;
typedef???? const ?T * ????const_pointer;
typedef????T & ????????reference;
typedef???? const ?T & ????const_reference;

rebind
allocator( const ?allocator < U >& ?)
~ allocator()?
pointer?address(reference?x)
const_pointer?address(const_pointer?x)
T * ?allocate(size_type?n,? void * ?p? = ? 0 )
void ?deallocate(pointer?p,?size_type?n)
size_type?max_size()
void ?construct(pointer?p,?const_reference?val)
void ?destroy(pointer?p)

?SGI STL并沒(méi)有按C++ STD的說(shuō)沒(méi)直接做一個(gè)Allocator出來(lái),而是先做出兩個(gè)Allocator template及以內(nèi)存池的形式來(lái)構(gòu)?//造Allocator比STD::allocator效率更高且減少了內(nèi)存碎片。下面是sgi_allocator.h的代碼:

#ifndef?SGI_ALLOCATOR
#define ?SGI_ALLOCATOR
#include? < iostream >
#include? < cstddef > ???????? // for?size_t
using ? namespace ?std;

namespace ?SGI
{
????template < int ?inst >
???? class ?malloc_alloc_template???? // 一級(jí)空間配置器
???? {
???? public :
???????? static ? void * ?allocate(size_t?n)
???????? {
???????????? void * ?result? = ?malloc(n);
???????????? if ?(result? == ?NULL)
???????????? {
????????????????result? = ?oom_malloc(n);???????? // 內(nèi)存不足調(diào)用oom_malloc()進(jìn)行處理
????????????}

???????????? return ?result;
????????}

???????? static ? void ?deallocate( void * ?p,?size_t)???? // 第二個(gè)參數(shù)無(wú)所謂,只要一進(jìn)來(lái)就把它干掉..
???????? {
????????????free(p);
????????}

???????? static ? void * ?reallocate( void * ?p,?size_t /**/ /* old?size */ ,?size_t?new_size)
???????? {
???????????? void * ?result? = ?realloc(p,?new_size);
???????????? if (result? == ?NULL)
???????????? {
????????????????result? = ?oom_realloc(p,?new_size);
????????????}

???????????? return ?result;
????????}

???????? static ? void ?( * set_malloc_handler( void ?( * f)()))()
???????? {
???????????? void ?( * old)()? = ?oom_malloc_handler;
????????????oom_malloc_handler? = ?f;

???????????? return ?old;
????????}
???? private :
???????? static ? void * ?oom_malloc(size_t);???????? // 內(nèi)存不足時(shí)調(diào)用這個(gè)函數(shù)(因?yàn)槔锩嬗刑幚砗瘮?shù))
???????? static ? void * ?oom_realloc( void * ,?size_t); // 同上
???????? static ? void ?( * oom_malloc_handler)();???? // 內(nèi)存不足時(shí)的處理函數(shù)
????} ;
????template < int ?inst >
???? void * ?malloc_alloc_template < inst > ::oom_malloc(size_t?size)
???? {
???????? void * ?result;
????????
???????? while ( true )???????????? // 反得調(diào)用處理函數(shù),直到申請(qǐng)成功.如果沒(méi)有定義處理函數(shù)則拋出異常
???????? {
???????????? if ?(oom_malloc_handler? == ?NULL)
???????????? {
???????????????? throw ?bad_alloc();
????????????}
????????????( * oom_malloc_handler)();
???????????? if ?(?(result? = ?malloc(size))? != ?NULL)
???????????? {
???????????????? return ?result;
????????????}
????????}
????}

????template < int ?inst >
???? void * ?malloc_alloc_template < inst > ::oom_realloc( void * ?p,?size_t?new_size)
???? {
???????? void * ?result;

???????? while ( true )
???????? {
???????????? if ?(oom_malloc_handler? == ?NULl)
???????????? {
???????????????? throw ?bad_alloc();
????????????}
????????????( * oom_alloc_handler)();
???????????? if ?(?(result? = ?realloc(p,?new_size))? != ?NULL)
???????????? {
???????????????? return ?result;
????????????}
????????}
????}

????template < int ?inst >
???? void ?( * malloc_alloc_template < inst > ::oom_malloc_handler)()? = ?NULL;

????typedef?malloc_alloc_template < 0 > ?malloc_alloc;???????? // 到此完成一級(jí)空間配置器的定義

???? /**/ //////////////////////////////////////////////////////
???? // 下面是對(duì)一二級(jí)配置器的封裝,?其中Alloc即為空間配置器
???? // 默認(rèn)用的是二級(jí)配置器,當(dāng)>128K或內(nèi)存不足時(shí)會(huì)交給一級(jí)
???? // 配置器處理
???? /**/ /////////////////////////////////////////////////// //j?
????template < typename?T,?typename?Alloc > ????????????
???? class ?simple_alloc
???? {
???? public :
???????? static ?T * ?allocate(size_t?n)
???????? {
???????????? return ?n? == ? 0 ? ? ? 0 ?:?(T * )Alloc::allocate(n? * ? sizeof (T));
????????}

???????? static ?T * ?allocate()
???????? {
???????????? return ?(T * )Alloc::allocate( sizeof (T));
????????}

???????? static ? void ?deallocate(T * ?p,?size_t?n)
???????? {
???????????? if ?(n? != ? 0 )
???????????? {
????????????????Alloc::deallocate(p,?n? * ? sizeof (T));???????? // 這里要用兩個(gè)參數(shù)是為了與后面的二級(jí)配置器配合(這個(gè)問(wèn)題郁悶了我好久,呵呵,菜啊!)
????????????}
????????}

???????? static ? void ?deallocate(T * ?p)
???????? {
????????????Alloc::deallocate(p,? sizeof (T));
????????}
????} ;

???? enum {ALIGN? = ? 8 ,?MAX_BYTES? = ? 128 ,?NFREELISTS? = ? 16 } ;???? // ?其中NFREELISTS?=?MAX_BYTES?/?ALIGN
????
????template < bool ?threads,? int ?inst >
???? class ?default_alloc_template???? // 定義二級(jí)配置器
???? {
???? public :
???????? static ? void * ?allocate(size_t?n)
???????? {
???????????? void * ?result;
????????????
???????????? if ?(n? > ?(size_t)MAX_BYTES)
???????????? {
????????????????result? = ?malloc_alloc::allocate(n);???????? // >128K交給一級(jí)配置器處理
????????????}
???????????? else
???????????? {
????????????????Obj * ? volatile * ?my_free_list???? = ?free_list? + ?free_list_index(n);
???????????????? if ?(?(result? = ? * my_free_list)? == ?NULL)
???????????????? {
????????????????????result???? = ????refill(round_up(n));
????????????????}
???????????????? else
???????????????? {
????????????????????Obj * ?tmp???????? = ? * my_free_list;
???????????????????? * my_free_list???? = ?tmp -> free_list_link;
????????????????????result???????????? = ?tmp;
????????????????}
????????????}

???????????? return ?result;
????????}

???????? static ? void ?deallocate( void * ?p,?size_t?n)
???????? {
???????????? if ?(n? > ?(size_t)MAX_BYTES)
???????????? {
????????????????malloc_alloc::deallocate(p,?n);
????????????}
???????????? else
???????????? {
????????????????Obj * ? volatile * ?my_free_list? = ?free_list? + ?free_list_index(n);
????????????????Obj * ?q? = ?(Obj * )?p;
????????????????q -> free_list_link???? = ? * my_free_list;
???????????????? * my_free_list???????? = ?q;
????????????}
????????}

???????? static ? void * ?reallocate( void * ?p,?size_t?old_size,?size_t?new_ize);

???? private :
???????? static ?size_t?round_up(size_t?bytes)
???????? {
???????????? return ?((bytes? + ?(size_t)ALIGN? - ? 1 )? & ? ~ ((size_t)ALIGN? - ? 1 ));
????????}
????????
????????union?Obj???????????? // Trick,既可以作指針,又可以作為內(nèi)存地址
???????? {
????????????union?Obj * ?free_list_link;
???????????? char ?client_data[ 1 ];
????????} ;

???????? static ?Obj * ? volatile ?free_list[NFREELISTS];

???????? static ?size_t?free_list_index(size_t?size)
???????? {
???????????? return ?((size? + ?(size_t)ALIGN? - ? 1 )? / ?(size_t)ALIGN? - 1 );
????????}
????????
???????? static ? void * ?refill(size_t?n);
???????? static ? char * ?chunk_alloc(size_t?size,?size_t & ?objs);
????????
???????? static ? char * ????chunk_start;???? // 內(nèi)存池起始位置
???????? static ? char * ????chunk_end;???????? // 內(nèi)存池結(jié)束位置
???????? static ?size_t????heap_size;???????? // 從開(kāi)始至今在堆中申請(qǐng)的字節(jié)總數(shù)

????} ;

????template < bool ?threads,? int ?inst >
???? char * ?default_alloc_template < threads,?inst > ::chunk_start? = ?NULL;

????template < bool ?threads,? int ?inst >
???? char * ?default_alloc_template < threads,?inst > ::chunk_end? = ?NULL;

????template < bool ?threads,? int ?inst >
????size_t?default_alloc_template < threads,?inst > ::heap_size? = ? 0 ;
????
????template < bool ?threads,? int ?inst >
????typename?default_alloc_template < threads,?inst > ::Obj * ? volatile ?default_alloc_template < threads,?inst > ::free_list[NFREELISTS]? = ? { 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 } ;


???? // 核心部分,從內(nèi)存池中申請(qǐng)空間
????template < bool ?threads,? int ?inst >
???? char * ?default_alloc_template < threads,?inst > ::chunk_alloc(size_t?size,?size_t & ?nobjs)
???? {
???????? char * ????result???????? = ?NULL;
????????size_t????total_bytes???? = ?size? * ?nobjs;????????????????????????
????????size_t????bytes_left???? = ?chunk_end? - ?chunk_start;???????????? // 內(nèi)存池所剩水量

???????? if ?(?bytes_left? > ?total_bytes)???????????????????????????? // 內(nèi)存池中有足夠空間可以分配
???????? {
????????????result???????? = ????chunk_start;
????????????chunk_start? += ????total_bytes;

???????????? return ?result;
????????}
???????? else ? if (bytes_left? >= ?size)???????????????????????? // 內(nèi)存池中空間至少可以分配一個(gè)塊
???????? {
????????????nobjs???????????? = ????( int )bytes_left? / ?size;
????????????total_bytes???????? = ????size? * ?nobjs;
????????????result???????????? = ????chunk_start;
????????????chunk_start???? += ????total_bytes;

???????????? return ?result;
????????}
???????? else ???????????????????????????????????????? // 內(nèi)存池已山窮水盡一個(gè)塊都無(wú)法分配出來(lái)?T_T
???????? {
????????????size_t?bytes_to_get???? = ?total_bytes? + ?round_up(heap_size? >> ? 4 );???????? // 申請(qǐng)總數(shù)兩位加上擴(kuò)展

???????????? if ?(bytes_left? > ? 0 )
???????????? {
????????????????Obj * ? volatile * ?my_free_list???????????? = ?free_list? + ?free_list_index(bytes_left);
????????????????((Obj * )chunk_start) -> free_list_link???? = ? * my_free_list;
???????????????? * my_free_list???????????????????????? = ?(Obj * )chunk_start;
????????????}
????????????chunk_start???? = ????( char * )malloc(bytes_to_get);
???????????? if ?(chunk_start? == ?NULL)???????? // 內(nèi)存不足這下麻煩了,看看表中有沒(méi)有空間可以回收
???????????? {
????????????????Obj * ? volatile * ?my_free_list;
????????????????Obj * ?p;

???????????????? for (size_t?i? = ?size;?i? <= ?MAX_BYTES;?i? += ?ALIGN)
???????????????? {
????????????????????my_free_list???? = ????free_list? + ?free_list_index(i);
????????????????????p???????????????? = ???? * my_free_list;

???????????????????? if ?(p? != ?NULL)???? // 找到適合的空間,進(jìn)行回收
???????????????????? {????????????????????????
???????????????????????? * my_free_list???? = ????p -> free_list_link;
????????????????????????chunk_start???????? = ????( char * )p;
????????????????????????chunk_end???????? += ????i;

???????????????????????? return ?chunk_alloc(size,?nobjs);

????????????????????}
????????????????}
????????????????
???????????????? // 完全走投無(wú)路了,只好看看內(nèi)存不足的處理函數(shù)能不能幫上忙
????????????????chunk_end???? = ????NULL;
????????????????chunk_start???? = ????( char * )malloc_alloc::allocate(bytes_to_get);
????????????}
????????????chunk_end???? += ????bytes_to_get;
????????????heap_size???? += ????bytes_to_get;

???????????? return ?chunk_alloc(size,?nobjs);
????????}
????}

???? /**/ /*
?????*?返回一個(gè)大小為n的塊,?并且可能適當(dāng)?shù)貫閒ree_list增加節(jié)點(diǎn)
?????*
????? */
????template < bool ?threads,? int ?inst >
???? void * ?default_alloc_template < threads,?inst > ::refill(size_t?n)
???? {
????????size_t????????nobjs? = ? 20 ;???????????????? // 默認(rèn)申請(qǐng)塊的個(gè)數(shù)
????????Obj * ????????curr;
????????Obj * ????????next;
????????

???????? char * ????result? = ?chunk_alloc(n,?nobjs);
???????? if ?(nobjs? == ? 1 )???????? // 只申請(qǐng)到一塊空間則直接返回給調(diào)用者
???????? {
???????????? return ?result;
????????}
???????? else ???????????? // 申請(qǐng)到多于一個(gè)塊,將其它nobjs?-?1個(gè)塊加到free_list中?:?)
???????? {
????????????Obj * ? volatile * ?my_free_list???? = ?free_list? + ?free_list_index(n);;
???????????? * my_free_list? = ?next? = ?(Obj * )(result? + ?n);
???????????? for ( int ?i? = ? 1 ;?;? ++ i)
???????????? {????????????????
????????????????curr???? = ????next;
????????????????next???? = ?(Obj * )(?( char * )next? + ?n);

???????????????? if ?(i? == ?nobjs? - ? 1 )
???????????????? {
????????????????????curr -> free_list_link???? = ????NULL;
???????????????????? break ;
????????????????}
???????????????? else
???????????????? {
????????????????????curr -> free_list_link???? = ????next;
????????????????}
????????????}
???????????? return ?result;
????????}
????}

????template < bool ?threads,? int ?inst >
???? static ? void * ?default_alloc_template < threads,?inst > ::reallocate( void * ?p,?size_t?old_size,?size_t?new_size)
???? {
???????? if ?(old_size? > ?MAX_BYTES? && ?new_size? > ?MAX_BYTES)
???????? {
???????????? return ?realloc(p,?new_size);
????????}

???????? if ?(round_up(old_size)? == ?round_up(new_size))
???????? {
???????????? return ?p;
????????}

???????? void * ?result? = ?malloc(new_size);
???????? int ?copy_size? = ?new_size? > ?old_size? ? ?old_size?:?new_size;
????????memcpy(result,?p,?copy_size);

???????? return ?result;
????}
????
????typedef?default_alloc_template < false ,? 0 > ?alloc;

???? /**/ /*
?????*?對(duì)以定義好的兩個(gè)配置器模板進(jìn)行封裝,以使其與STL相容
????? */
????template < typename?T >
???? class ?allocator
???? {
???? public :
????????typedef????????size_t????????size_type;
????????typedef????????T????????????value_type;
????????typedef????????T * ????????????pointer;
????????typedef????????ptrdiff_t????difference_type;
????????typedef???????? const ?T * ????const_pointer;
????????typedef????????T & ????????????reference;
????????typedef???????? const ?T & ????const_reference;

????????template < typename?U > ?
???????? struct ?rebind
???????? {
????????????typedef?allocator < U > ?other;
????????} ;

????????allocator()? throw ()
???????? {
????????}

????????template < typename?U >
????????allocator( const ?allocator < U >& ?)? throw ()
???????? {
????????}
????????
???????? ~ allocator()? throw ()
???????? {
????????}

????????pointer?address(reference?x)? const
???????? {
???????????? return ? & ?x;
????????}

????????const_pointer?address(const_pointer?x)? const
???????? {
???????????? return ? & x;
????????}

????????T * ?allocate(size_type?n,? void * ?p? = ? 0 )
???????? {
???????????? return ?n? != ? 0 ? ? ?static_cast < T *> (alloc::allocate(n? * ? sizeof (T)))?:? 0 ;
????????}

???????? void ?deallocate(pointer?p,?size_type?n)
???????? {
????????????alloc::deallocate(p,?n * sizeof (T));
????????}

????????size_type?max_size()? const ? throw ()
???????? {
???????????? return ?(size_t) - 1 / sizeof (T);
????????}

???????? void ?construct(pointer?p,?const_reference?val)
???????? {
???????????? new (p)T(val);
????????}

???????? void ?destroy(pointer?p)
???????? {
????????????p ->~ T();
????????} ????????
????} ;

}

#endif

?以下是測(cè)試文件，現(xiàn)在比較晚了。。沒(méi)有寫(xiě)一個(gè)比較像樣的測(cè)試，以后有時(shí)候再寫(xiě)寫(xiě)。。。

// ?sgi_allocator.cpp?:?定義控制臺(tái)應(yīng)用程序的入口點(diǎn)。
//
/**/ /*
?*????模擬SGI?STL中allocator的實(shí)現(xiàn),以內(nèi)存池的形式,構(gòu)建一個(gè)比STD::allocator
?*????更高效的空間配置器
?*????作者:?Szwolf
?*????2006.8.3:23.31'暑假@SZU
?*
? */
#include? " stdafx.h "
#include? " sgi_allocator.h "
#include? < iostream >
#include? < vector >
#include? < algorithm >

using ? namespace ?std;

class ?test
{
public :
????friend?ostream & ? operator ? << ?(ostream & ?os,? const ?test & ?x)
???? {
???????? return ?os? << ? " test?success?:?) " ? << ?endl;
????}
} ;

int ?_tmain( int ?argc,?_TCHAR * ?argv[])
{
???? int ?a[]? = ? { 1 , 2 , 3 , 4 } ;
????test?b[ 10 ];
????vector < int ,?SGI::allocator < int > ? > ?vec(a,?a? + ? 4 );
????vector < test,?SGI::allocator < test > ? > vec2(b,?b + 10 );
????copy(vec.begin(),?vec.end(),?ostream_iterator < int > (cout,? " ? " ));
????cout? << ?endl;
????copy(vec2.begin(),?vec2.end(),?ostream_iterator < test > (cout));
????cout? << ?endl;

???? return ? 0 ;
}

一個(gè)類(lèi)似于SGI STL::allocator的空間配置器就這樣完成了：）個(gè)人感覺(jué)在建內(nèi)存池的過(guò)程從其無(wú)所不用其極的空間申請(qǐng)方式中受益頗多～～～（呵呵，鏈表操作又復(fù)習(xí)了一遍。。）
?以下是在VS2005中可以正常編譯通過(guò)的源碼：
http://www.shnenglu.com/Files/szwolf/sgi_allocator.rar