空间配置器：
作用：帮助容器配置空间存放信息
SGI空间配置器
标准空间配置器allocator：效率不好，只对::operator new和::operator delete做一层封装
特殊空间配置器alloc
：将new算式分为两阶段：用::operator配置内存，构造对象；
将delet算式分为两阶段：析构对象，用::operator delete释放内存
特殊空间配置器
内存配置：allocate()，判断区块大小，大于128字节调用一级配置器，小于检查自由链表中若有可用区块直接使用，否则为自由链表重新填充空间
内存释放：deallocate()，判断区块大小，大于128字节调用一级配置器，小于则找到对应自由链表，进行区块回收。
对象构造：construct()
对象析构：destroy()
双层配置器
一级配置器：使用malloc(),free()进行内存的分配与释放。类名:__malloc_alloc_template。
二级配置器：小于128字节时，采用内存池，维护自由链表，可从自由链表进行内存的分配与释放。内存需求量需上调为8的倍数。类名：__default_alloc_template。
内存池思路：
（1）内存池分配操作
1） 内存池剩余空间满足需求，正常分配，头指针加上需要分配的空间
2） 内存池不能完全满足，但能分配若干区块，头指针加上所能分配的区块空间
3） 内存池剩余空间连一个区块都不能满足，寻找分配链表，插入残余空间
（2）内存池补给操作
刚才分配了多少空间，现在再从堆中取出2倍内存+附加量。
1）堆空间不足，寻找分配链表中未使用区块。
2）若到处无内存，调用一级配置器获取内存。
内存基本处理函数:
uninitialized_copy()：对每个迭代器调用构造函数产生对象，并输出到指定位置上
unintialized_fill()
：对每个迭代器调用构造函数产生对象
unintialized_fill(n)
：对每个迭代器调用构造函数产生对象
construct() :
destroy() :
内存基本处理函数的思路:
判断迭代器的型别是否为POD(标量型别)，若是：采用STL的相应算法，否则：采取自己的方法按序构造元素。
#include <iostream>
#include <string>
#include <vector>
#include <iterator>
#include <algorithm>
using namespace std;
enum {_ALIGN=8};
enum {_MAX_BYTES=128};
enum {_NFREELISTS=_MAX_BYTES/_ALIGN};
template<bool threads,int inst>
class _default_malloc_template
{
private:
//将比特上调为8的倍数
static size_t ROUND_UP(size_t bytes)
{
return (((bytes)+_ALIGN-1) & ~(_ALIGN-1));//?
}
//free-lists的节点构造
union obj
{
union obj* free_list_link;
char client_data[1];
};
//根据区块大小来使用n号free-list
static size_t FREELIST_INDEX(size_t bytes)
{
return (((bytes)+_ALIGN-1)/(_ALIGN-1));//?
}
//返回大小为n的对象，并加入大小为n的区块到free list
//static void *refill(size_t n);
//配置nobjs个大小为size的区块
//static char* chunk_alloc(size_t size,int &nobjs);
private:
//16个free-lists
static obj* volatile free_list[_NFREELISTS];
static char* start_free;//内存池起始位置
static char* end_free;//内存池结束位置
static size_t heap_size;
public:
static void* allocate(size_t n)
{
obj* volatile * my_free_list;
obj* result;
//大于128调用一级配置器
if(n>(size_t)_MAX_BYTES)
{
return (malloc_alloc::allocate(n));
}
//寻找16个free_lists中的一个
my_free_list = free_list + FREELIST_INDEX(n);
result = *my_free_list;
if(result==0)
{
//没有找到可用free_list,重填free list
void *r = refill{ROUND_UP(n)};
return r;
}
//调整free_list
*my_free_list = result->free_list_link;
return(result);
}
//判区块大小，大于128带哦用第一级配置器，小于则找出对应free_list并回收
static void* deallocate(void* p,size_t n)
{
obj *q = (obj*) p;
obj * volatile *my_free_list;//?
//大于128调用第一级配置器
if(n>(size_t)_MAX_BYTES(p,n))
{
malloc::alloc::deallocate(p,n);
return n;
}
my_free_list = free_list + FREELIST_INDEX(n);
q->free_list_link = *my_free_list;
*my_free_list = q;
}
static void* reallocate(void* p,size_t old_sz,size_t new_sz);
//返回一个大小为n的对象，并且有时候会为适当的free_list增加节点，新的空间取自内存池，缺省取20个新节点
static void* refill(size_t n)
{
int nobjs = 20;
char* chunk = chunk_alloc(n,nobjs);
obj * volatile * my_free_list;//
obj * result;
obj * current_obj,*next_obj;
//如果只获得一个区块，这个区块分配给调用者,free list无新节点
if(1==nobjs)
{
return (chunk);
}
//否则准备调整free list，纳入新节点
my_free_list = free_list+FREELIST_INDEX(n);
//在chunk空间建立free list
result = (obj*)chunk;//这块返回给客户端
//以下导引free list执行新配置的空间(取自内存池)
*my_free_list = next_oj = (obj*)(chunk+n);
//以下将free list各节点串接,从1开始，第0个已经返回给客户端
for(i=1;;i++)
{
current_obj = next_obj;
next_obj = (obj*)((char*)next_obj+n);//?
if(nobjs -1 == i)//?
{
current_obj->free_list_link = 0;
break;
}
else
{
current_obj->free_list_link = next_obj;
}
}
return(result);
}
//从内存池取空间给free list使用,size已经为8的倍数
//char* chunk_alloc(size_t size,int& nobjs)
//{
// char* result;
//}
//char* _default_alloc_template<threads,inst>::heap_size = 0;
};
//静态成员的定义
template< bool threads,int inst >
char* _default_malloc_template<threads,inst>::start_free = 0;
template<bool threads,int inst>
char* _default_malloc_template<threads,inst>::end_free = 0;
template<bool threads,int inst>
size_t _default_malloc_template<threads,inst>::heap_size = 0;
//template<bool threads,int inst>
//_default_malloc_template<threads,inst>::obj * volatile
//_default_malloc_template<threads,inst>::free_list[16]; ?
//作用：将内存配置与对象构造分离，对范围内的每个对象进行复制。适用：实现容器。
//容器构造函数过程：1配置内存块，2使用ininitialized_copy()在内存块上构造元素
template<class InputIterator,class ForwardIterator>
ForwardIterator uninitialized_copy(InputIterator first,InputIterator last,ForwardIterator result)
{
return _uninitialized_copy(first,last,result,value_type(result));
}
template<class InputIterator,class ForwardIterator,class T>
inline ForwardIterator _unintialized_copy(InputIterator first,InputIterator last,ForwardIterator result,T*)
{
typedef typename _traits_type<T>::is_POD_type is_POD;
//利用is_POD()结果，让编译器做参数推导
return _uninitialized_copy_aux(first,last,result,is_POD());
}
//POD类型，析构函数无意义，则调用STL的copy
template<class InputIterator,class ForwardIterator,class _true_type>
inline ForwardIterator _uninitialized_copy_aux(InputIterator first,InputIterator last,ForwardIterator result,_true_type)
{
return copy(first,last,result);
}
//非POD类型，析构函数有意义，调用以下函数
//template<class InputIterator,class ForwardIterator>
//ForwardIterator _uninitialized_copy_aux(InputIterator first,InputIterator last,ForwardIterator result,_false_type)
//{
// ForwardIterator cur = result;
// //for(;first!=last;first++)//first与cur都必须++
// for(;first!=last;first++,cur++)
// {
// //按序构造元素
// construct(&*cur,f*first);//
// }
// return cur;
//}
//作用：将内存配置与对象构造分离。对范围内每个迭代器上复制x
template<class ForwardIterator,class T>
void unintialized_fill(ForwardIterator first,ForwardIterator last,const T& x);
//是POD型，析构函数无意义，则调用此函数
template<class ForwardIterator,class Size,class T,class _true_type>
inline ForwardIterator _uninitialized_fill_n_aux(ForwardIterator first,Size n,const T& x,_true_type)
{
return fill_n(first,n,x);//由高阶函数执行
}
//非POD型，析构函数有意义，调用此函数
template<class ForwardIterator,class Size,class T,class _false_type>
ForwardIterator _uninitialized_fill_n_aux_1(ForwardIterator first,Size n,const T& x,_false_type)
{
ForwardIterator cur = first;
for(;n>0;cur++,n--)
{
construct(&*cur,x);
}
return cur;
}
//判断迭代器的的value_type是否为POD(普通标量型别，无效构造函数)
template<class ForwardIterator,class Size,class T,class T1>
inline ForwardIterator _uninitialized_fill_n(ForwardIterator first,Size n,const T& x,T1*)
{
typedef typename _type_traits<T1>::is_POD_type is_POD;
return _unintialized_fill_n_aux(first,n,x,is_POD());
}
//作用:对[first,first+n]范围内每个迭代器上复制x
template<class ForwardIterator,class Size,class T>
ForwardIterator uninitialized_fill_n(ForwardIterator first,Size n,const T& x)
{
return _uninitialized_fill_n(first,n,x,value_type(first));
}
int main(int argc,char *argv[])
{
cout<<"具备次配置力的SGI空间配置器"<<endl;
getchar();
return 0;
}