|
|
???使用STL已經有一段時間了，對里面的運作方式一直不了解。這幾天突發其想，找了一些關于STL源碼的書看了一下，覺得其內部實現非常精妙。作為進一步學習，我打算把STL中的主要組件自己動手實現一下。
???首先從空間配置器開始，從內部逐漸了解STL中各種容器的實現細節。
???根據STL的規范，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并沒有按C++ STD的說沒直接做一個Allocator出來,而是先做出兩個Allocator template及以內存池的形式來構?//造Allocator比STD::allocator效率更高且減少了內存碎片。下面是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????
//
一級空間配置器
????
{
????
public
:
????????
static
?
void
*
?allocate(size_t?n)
????????
{
????????????
void
*
?result?
=
?malloc(n);
????????????
if
?(result?
==
?NULL)
????????????
{
????????????????result?
=
?oom_malloc(n);????????
//
內存不足調用oom_malloc()進行處理
????????????}
????????????
return
?result;
????????}
????????
static
?
void
?deallocate(
void
*
?p,?size_t)????
//
第二個參數無所謂,只要一進來就把它干掉..
????????
{
????????????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);????????
//
內存不足時調用這個函數(因為里面有處理函數)
????????
static
?
void
*
?oom_realloc(
void
*
,?size_t);
//
同上
????????
static
?
void
?(
*
oom_malloc_handler)();????
//
內存不足時的處理函數
????}
;
????template
<
int
?inst
>
????
void
*
?malloc_alloc_template
<
inst
>
::oom_malloc(size_t?size)
????
{
????????
void
*
?result;
????????
????????
while
(
true
)????????????
//
反得調用處理函數,直到申請成功.如果沒有定義處理函數則拋出異常
????????
{
????????????
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;????????
//
到此完成一級空間配置器的定義
????
/**/
//////////////////////////////////////////////////////
????
//
下面是對一二級配置器的封裝,?其中Alloc即為空間配置器
????
//
默認用的是二級配置器,當>128K或內存不足時會交給一級
????
//
配置器處理
????
/**/
///////////////////////////////////////////////////
//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));????????
//
這里要用兩個參數是為了與后面的二級配置器配合(這個問題郁悶了我好久,呵呵,菜啊!)
????????????}
????????}
????????
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????
//
定義二級配置器
????
{
????
public
:
????????
static
?
void
*
?allocate(size_t?n)
????????
{
????????????
void
*
?result;
????????????
????????????
if
?(n?
>
?(size_t)MAX_BYTES)
????????????
{
????????????????result?
=
?malloc_alloc::allocate(n);????????
//
>128K交給一級配置器處理
????????????}
????????????
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,既可以作指針,又可以作為內存地址
????????
{
????????????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;????
//
內存池起始位置
????????
static
?
char
*
????chunk_end;????????
//
內存池結束位置
????????
static
?size_t????heap_size;????????
//
從開始至今在堆中申請的字節總數
????}
;
????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
}
;
????
//
核心部分,從內存池中申請空間
????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;????????????
//
內存池所剩水量
????????
if
?(?bytes_left?
>
?total_bytes)????????????????????????????
//
內存池中有足夠空間可以分配
????????
{
????????????result????????
=
????chunk_start;
????????????chunk_start?
+=
????total_bytes;
????????????
return
?result;
????????}
????????
else
?
if
(bytes_left?
>=
?size)????????????????????????
//
內存池中空間至少可以分配一個塊
????????
{
????????????nobjs????????????
=
????(
int
)bytes_left?
/
?size;
????????????total_bytes????????
=
????size?
*
?nobjs;
????????????result????????????
=
????chunk_start;
????????????chunk_start????
+=
????total_bytes;
????????????
return
?result;
????????}
????????
else
????????????????????????????????????????
//
內存池已山窮水盡一個塊都無法分配出來?T_T
????????
{
????????????size_t?bytes_to_get????
=
?total_bytes?
+
?round_up(heap_size?
>>
?
4
);????????
//
申請總數兩位加上擴展
????????????
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)????????
//
內存不足這下麻煩了,看看表中有沒有空間可以回收
????????????
{
????????????????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)????
//
找到適合的空間,進行回收
????????????????????
{????????????????????????
????????????????????????
*
my_free_list????
=
????p
->
free_list_link;
????????????????????????chunk_start????????
=
????(
char
*
)p;
????????????????????????chunk_end????????
+=
????i;
????????????????????????
return
?chunk_alloc(size,?nobjs);
????????????????????}
????????????????}
????????????????
????????????????
//
完全走投無路了,只好看看內存不足的處理函數能不能幫上忙
????????????????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);
????????}
????}
????
/**/
/*
?????*?返回一個大小為n的塊,?并且可能適當地為free_list增加節點
?????*
?????
*/
????template
<
bool
?threads,?
int
?inst
>
????
void
*
?default_alloc_template
<
threads,?inst
>
::refill(size_t?n)
????
{
????????size_t????????nobjs?
=
?
20
;????????????????
//
默認申請塊的個數
????????Obj
*
????????curr;
????????Obj
*
????????next;
????????
????????
char
*
????result?
=
?chunk_alloc(n,?nobjs);
????????
if
?(nobjs?
==
?
1
)????????
//
只申請到一塊空間則直接返回給調用者
????????
{
????????????
return
?result;
????????}
????????
else
????????????
//
申請到多于一個塊,將其它nobjs?-?1個塊加到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;
????
/**/
/*
?????*?對以定義好的兩個配置器模板進行封裝,以使其與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
?以下是測試文件，現在比較晚了。。沒有寫一個比較像樣的測試，以后有時候再寫寫。。。
//
?sgi_allocator.cpp?:?定義控制臺應用程序的入口點。
//
/**/
/*
?*????模擬SGI?STL中allocator的實現,以內存池的形式,構建一個比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
;
}
一個類似于SGI STL::allocator的空間配置器就這樣完成了：）個人感覺在建內存池的過程從其無所不用其極的空間申請方式中受益頗多～～～（呵呵，鏈表操作又復習了一遍。。）
?以下是在VS2005中可以正常編譯通過的源碼：
http://www.shnenglu.com/Files/szwolf/sgi_allocator.rar
|