[大数据]第二章 空间适配器（allocator）

1.空间配置器的标准接口

根据STL的规范，以下是allocator的必要接口：

allocator: :value_type 
allocator: :pointer 
allocator::const_pointer
allocator::reference
allocator::const_reference 
allocator::size_type 
allocator::difference_type 
allocator: :rebind

//一个嵌套的(nested) class template,class rebind<U>拥有唯一成员other, 那是一个typedef, 代表allocator<U>

allocator: : allocator () 
default constructor
 
allocator::allocator(const allocator&) 
copy constructor 

template <class U>allocator: :allocator(const allocator<U>&)
泛化的copy constructor allocaLor:: ~allocator () 
default constructor 

pointer allocator::address(reference x) const 
返回某个对象的地址。算式a.address(x)等同于&x

const_pointer allocator::address(const_reference x) const 
返回某个const对象的地址。算式a.address(x)等同与&x

pointer allocator::allocate(size_type n, cosnt void*= 0) 
配置空间，足以存储n个 T 对象．第二参数是个提示。实现上可能会利用它来增进区域性(locality) , 或完全忽略之

void allocator: :deallocate(pointer p, size_type n) 
归还先前配置的空间

size_type allocator::max_size().const 
返回可成功配置的最大量

void allocator: :construct(pointer p, const T& x) 
等同于new(const void*) p) T(x) 

void allocator: :destroy(pointer p) 
等同于p->~T()

1.1 简单的空间配置器，JJ::allocator

#include<new>
#include<cstddef>
#include<cstdlib>
#include<climits>
#include<iostream>
#include<vector>
using namespace std;

namespace JJ
{
	template <class T>
	inline T* _allocate(ptrdiff_t size, T*)

	{
		set_new_handler(0);
		T* tmp = (T*)(::new_handler new((size_t)(size * sizeof(T))));
		if (tmp == 0)
		{
			cerr << "out of memory" << endl;
			exit(1);
		}
		return tmp;

	}
	template <class T>
	inline void _deallocate(T* buffer) {
		::operator delete(buffer);
	}

	template <class T1,class T2>
	inline void _deallocate(T* buffer) {
		::operator delete(buffer);
	}

	template <class T1,class T2>
	inline void _construct(T1* p, const T2& value) {
		new(p) T1(value);
	}

	template <class>
	inline allocator(T* ptr) {
		ptr->~T();
	}

	template <class T>
	class allocator {
		public：
			typedef T
			typedef T*
			typedef const T*
			typedef T&
			typedef const T&
			typedef size_t
			typedef ptrdiff_t

			typedef <class U>
			struct rebind {
			typedef allocator<U> other;
		};

		pointer allocator(size_type n, const coid* hint = 0) {
			return _allocate((difference_type)n, (pointer)0);
		}

		void deallocate(pointer p, size_type n)
		{
			_deallocate(p);
		}

		void construct(pointer p, const T& value) {
			_construct(p, value);
		}

		void destroy(pointer p)
		{
			_destroy(p);
		}

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

		const_pointer const_address(const_reference x) {
			return (const_pointer)&x;
		}

		size_type max_size()const {
			return size_type(UINT_MAX / sizeof(T));
		}
	};
}

//JJ::allocator应用于程序之中，只能有限度搭配PJ STL和RW STL
int main()
{
	int ia[5] = { 0,1,2,3,4 };
	unsigned int i;

	vector<int, JJ::allocator<int> >iv(ia, ia + 5);
	for (i = 0; i < iv.size(); i++)
		cout << iv[i] << ' ' << endl;

}

2.具备次配置力（sub-allocation)的SGI空间配置器

SGI STL的配詈器与众不同， 也与标准规范不同， 其名称是alloc而非allocator, 而且不接受任何参数。换句话说，如果你要在程序中明白采用SGI配置器，则不能采用标准写法：

vector<int,std::allocator<int> >iv;//in VC or CB

必须这样写：

vector<int.std::alloc> iv;//in GCC

SGI STL allocator未能符合标准规格，不会带来困扰，因为通常我们使用缺省的空间配置器，很少需要自行指定配置器名称，而SGISTL的 每一个容器都已经指定其缺省的空间配置器为alloc。 例如下面的vector声明：

template <class T, class Alloc=alloc> //缺省使用alloc为配置器 class vector { ... }; 

2.1 SGI标准的空间配宣器， std ::allocator

SGI也定义有一个符合部分标准、 名为allocator的配置器，不建议使用。 主要原因是效率低， 只把C++的::operator new和::operator delete做一层薄薄的包装而已。下面是SGI的std::allocator全貌：

G++ 2.91.57, cygnus\cygwin-b20\include\g++\defalloc.h完整列表
//我们不赞成包含此文件。这是原始的HP default allocator。提供它只是为了
 //回溯兼容
//
// DO NOT USE THIS FILE 不要使用这个文件，除非你手上的容器是以旧式做法
//完成一—那就需要一个拥有HP-style i玑erface的空间配置器。SGI STL使用
//不同的allocator接口。SGI-styleallocators不带有任何与对象型别相关
//的参数； 它们只响应void* 指针（侯捷注： 如果是标准接口， 就会响应一个
// "指向对象型别 的指针，T*)。 此文件并不包含于其它任何SGI STL头文件
#include <new.h> 
#include <stddef.h> 
#include <s七dlib.h>
#include <limi七s.h>
#include <ios七ream.h>
#include <algobase.h> 
template <class T> 
inline T* allocate(ptrdiff_t size, T*) {
set_new—handler(O); 
T* tmp = (T*) (: :opera七or new ((size_t) (size * sizeof (T)))) ;
 if (tmp == 0) { 
 cerr << "out of memory" << endl; exit (1); 
 }
 return tmp;
 }
 template <class T>
 inline void deallocate(T* buffer){
 ::operator delete(buffer);
 }
 template <class T> class allocator { public: 
typedef T value_type; 
typedef T* pointer; 
typedef const T* const _pointer; typedef T& reference; 
typedef const T&const _reference;
typedef size_t size_type; 
typedef ptrdiff_t difference_type; 
pointer allocate(size—type n) { 
return : :allocate((difference_type) n, (pointer) 0);
}
void deallocate(pointer p) { : :deallocate(p); } 
pointer address(reference x) { return (pointer)&x; } const_pointer const_address(const_reference x) { 
return (const_pointer)&x;
}
size_type init_page_size() {
return max(size_type(l), size_type(4096/sizeof(T)));
}
size _typ e max_s1.ze() const {
return max(size_type(l), size_type(UINT_MAX/sizeof(T)));
}
};
//特化版本(specialization)。注意，为什么最前面不需加上templa:te<>?
//见1. 9 .1节的状态测试。注意，只适用于GCC
class allocator<void> { 
public: 
typedef void* pointer;
};

2.2 SGI特殊的空间配宣器， std ::alloc

上面的allocator只是基层内存配置/释放行为（也就是::operator new和::operator delete)的 层薄薄的包装， 并没有考虑到任何效率上的强化，SGI有其他方法供其本身使用。

一般C++内存配置操作和释放方式：

class Foo{...};
Foo* pf = new Foo;//配置内存，然后构造对象
delete pf;//将对象析构，然后释放内存

new含两阶段操作:

1. 调用:: operator new配置内存；
2. 调用Foo::Foo ()构造对象内容。

delete含两阶段操作：

1. 调用Foo: :-Foo() 将对象析构；
2. 调用: :operator delete释放内存。

STL allocator将这两阶段操作区分开来。内存配置操 作由alloc:allocate() 负责，内存释放操作由alloc: :deallocate() 负责； 对象构造操作由: : construct () 负责，对象析构操作由: : destroy () 负责。STL标准指出 配置器定义于 之中，SGI 内 含以下两个文件：

#include <stl_alloc.h> //负责内存空间的配置与释放
#include <stl_construct.h>//负责对象内容的构造与析构

内存空间的配置/释放与对象内容的构造/析构由有这两个文件定义，<stl_construct.h>定义有两个基本函数：构造用的construct()和析构用的destroy ()。在复杂的内存动态配置与释放之前，让我们先看清楚这两个函数如何完成对象的构造和析构。：

2.3 构造和析构基本工具： construct()和destroy()

#include <new.h>
template <class Tl, class T2> 
inline void const ruet(Tl* p, const T2& value) {
new (p) Tl (value); // placement new; 调用Tl:: Tl (value);
}
//以下是destroy()第一版本， 接受一个指针 template <class T> 
inline void destroy(T* pointer) { 
pointer->~T () ;I//调用dtor ~T ()
}
//以下是destroy ()第二版本， 接受两个迭代器。 此函数设法找出元素的数值型别， 
//进而利用_type_traits<>求取最适当措施
template <class ForwardIterator>
inline void destroy(ForwardIterator first,ForwardIterator last) { 
__destroy(first, last, value_type(first));

//判断元素的数值型别(value type)是否有
trivial destructor template <class Forwarditerator, class T> 
inline void __destroy(ForwardIterator first, Forwarditerator last, T*)
{
typedef typename _type_traits<T>: :has_trivial_destructor trivial_destructor; _destroy_aux(first, last, trivial_destructor());
}
//如果元素的数值型别(value type l有non-trivial destructor…
template <class ForwardIterator>
inline void 
_destroy_aux(Forwarditerator first, ForwardIterator last, _false_type) {
for (; first < last; ++first)
destroy(&*first);
}
//如果元素的数值观别(value type)有trivial destructor…
template <class ForwardIterator> 
inline void destroy—aux(Forwarditerator, Forwarditerator, _true_type) {} 
//以下是destroy ()第二版本针对迭代器为char* 和wchar_t*的特化版
inlinf" void destroy(char*, char*) {} 
inline void destroy(wchar_t*, wchar_t *) {} 

• 作为构造 、 析构的函数被设计为全局函数，STL还规定配置器必须拥有名为construct ()和destroy ()的两个成员 函数, 然而真正在SGI STL中大显身手的那个名为std: :alloc的配置器并未遵守这一 规则。
  • construct ()接受一个指针p和一个初值value, 该函数的用途就是将初值设定到指针所指的空间上

destroy ()有两个版本：

1. 第一版本接受一个指针，准备将该指针所指之物析构掉。 这很简单，直接调用该对象的析构函数即可
2. 第二版本接受frist和last 两个迭代器,准备将[first, last )范围内的所有对象析构掉。不确定析构范围，可能很大，而每个对象的析构函数都无关痛痒，那一次次调用是种伤害。因此，首页利用value_type()获得迭代器所指对象类型，在利用_type_traits判断该类型析构函数是否无关痛痒。若是（_true_type），就结束；若为（_false_type），循环查看整个范围，循环一个对象调用destroy()。

2.4 空间的配宣与释放， std::alloc

了解内存配置后的对象构造行为和内存释放前的对象析构行为，现在 看看内存的配置和释放。
对象构造前的空间配置和对象析构后的空间释放， 由<S七 l_alloc.h>负责， SGI对此的设计哲学如下：

1. 向systemheap要求空间。
2. 考虑多线程(multi-threads)状态。
3. 考虑内存不足时的应变措施。
4. 考虑过多 “小型区块可能造成的内存碎片(fragment)问题。

C++的内存配置基本操作:: operator new(), 内存释放基本操作是:: operator delete()。 这两个全局函数相当于C的malloc ()和free()函 数 是的， 正是如此，SGI正是以malloc ()和free()完成内存的配置与释放。

考虑到小型区块所可能造成的内存破碎问题，SGI设计了双层级配置器：

1. 第一级配置器直接使用malloc()和free()。
2. 第二级配置器则视情况采用不同的策略： 配置区块超过128 bytes，用第一级配置器；当小于128 bytes，用复杂的memory pool整理方式，不再求助于第一级配置器。
3. 整个设计究竟只开放第一级配置器， 或是同时开放第二级配置器， 取决于_USE_MALLOC6 是否被定义（ 我们可以轻易测试出来，SGI STL并未定义_USE_MALLOC)。

# ifdef _USE_MALLOC 
．．．
typedef _malloc_alloc_template<O> malloc—alloc;
typedef malloc_alloc alloc;//令alloc为第一级配置器
 # else 
 ...
//令alloc为第二级配置器
typedef _default_alloc_template<_NODE_ALLOCATOR_THREADS, 0> alloc;
 #endif /* ! _USE_MALLOC */ 

1. 其中_malloc_alloc_template就是第 一 级配置器，
2. default_alloc template就是第二级配置器。
3. alloc并 不接受任何template型别参数。

无论alloc被定义为第一级或第二级配置器， SGI还为它再包装一个接口如下， 使配置器的接口能够符合STL规格：

template<class T, class Alloc> 
class simple_alloc ( 
public: 
static T *allocate(size_t n)
{return 0 == n?0 : (T*)Alloc::allocate{n*sizeof(T));
static T *allocate(void)
{return (T*) Alloc::allocate(n * sizeof(T));
static void deallocate(T *p,size_t n)
{if(0 !=n) Alloc::deallocate(p,n*sizeof(T));
staitc void deallocate(T *p)
{Alloc::deallocate(p,sizeof (T));}

其内部四个成员函数其实都是单纯的转调用，调用传递给配置器（可能是第一级也可能是第二级）的成员函数。 这个接口使配置器的配置单位从bytes转为个别元素 的大小(sizeof (T))。 SGISTL容器全都使用这个simple_alloc接口、 例如：

template<class T, class Alloc = alloc> //缺省使用alloc为配置器
class vector { 
protected: 
//专属之空间配置器，每次配置个元素大小
typedef simple_alloc<value_type,Alloc>data_allocator;
void deallocate(){
if(...)
data_allocator::deallocate(start,end_of_storage - start);
}
...
};

一、 二级配置器的关系， 接口包装， 及实际运用方式:

2.5 第一级配宣器__m alloc_alloc_tem plate剖析

#if 0
# include<new>
# define __THROW_BAD_ALLOC throw bad_alloc
#elif !defined(__THROW_BAD_ALLOC)
# include <iostream.h>
# define __THROW_BAD_ALLOC cerr<<"out memory"<<endl;
exit(1)
#endif
//malloc-based allocator通常比default alloc 慢
//一般而言是thread-safe,并且对于空间的运用比较高效(efficient）
//以下是第一级配置器
//注意，无"template型别参数”。至于“非型别参数"inst，则完全没派上用场 
template <int inst> 
class _malloc_alloc—template { 
private:
//以下都是函数指针，所代表的函数将用来处理内存不足的情况
// oom: ou七ofmemory. 
static void *oom_malloc(size_t); 
static void *oom_realloc(void * size_t);
static void (* __malloc_alloc_oom_handler)();

public:
static void* allocate(size_t n) 
{
void *result = malloc(n);//第一级配置器直接使用malloc()
//以下无法满足需求时，改用oom_malloc() 
if (0 == result) result= oom_malloc(n); 
return result; 
}
static void deallocate (void *p, size_t /*n*/) 
{
free(p);//第一级适配器直接使用free()
}
static void* reallocate (void *p, size_t /*old_sz */, size_t new_sz)
{
void* result= realloc(p, new—sz);//第一级配置器直接使用realloc() 
//下无法满足需求时，改用oom_realloc() 
if (0 == result) result=oom_realloc(p, new_sz); 
return result; 
}
//以下仿真C++的set_new_handler{)。换句话说，你可以通过它
//指定你自己的out-of-memoryhandler 
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
 //初始值为0，有待客端设定
 template <int,inst>
 void (* malloc_alloc_template<inst>::_malloc_alloc_oom_handler) ()=O;
template <int inst> 
void* _malloc_alloc_template<inst>: :oom_malloc(size_t n) 
{ 
void (* my_malloc_handler) (); 
void *result; 
for (;;) { //不断尝试释放、配置、再释放、再配置...
 my_malloc—handler= _malloc_alloc_oom_handler; 
 if (0 == my—malloc—handler) { _THROW—BAD—ALLOC; } 
 (*my _malloc_handler) () ; //调用处理例程，企图释放内存
  result = malloc (n); //再次尝试配置内存
if (result) return(result); 
  }
}
template <int inst> 
void*__malloc_alloc_template<inst>::oom_realloc(void *p,size_t n)
{
void (* my—rnalloc_handler)(); 
void *result; 
for (;;) { //不断尝试释放、配置、再释放、再配置…
my_malloc_handler = _malloc_alloc_oom_handler;
if(0 == my_malloc_handler) {__THROW_BAD_ALLOC; } 
(*my_malloc_handler)();//调用处理例程，企图释放内存
 result = realloc (p, n); //再次尝试配置内存
if (result) return(result);
}
 }
 //注意，以下直接将参数inst指定为0
typedef _malloc_alloc_template<O>malloc_alloc;

1. 第一级配置器以malloc() , free () , realloc ()等C函数执行实际的内存 配置、释放、重配置操作，并实现出类似C++new-handler的机制。不能直接运用C++new-handler机制，因为它并非使用::operator new来配置内存。

2. C++new handler机制指可以要求系统在内存配置需求无法被满足时，调用一个你所指定的函数。换句话说，一旦:;operator new无法完成任务， 在丢出std::bad_alloc异常状态之前，会先调用由客端指定的处理例程。该处理例程通常即被称为new-handler。new-handler解决内存不足的做法有特定的模式。

注意：

1. SGI以malloc而非::operator new来配置内存（ 一个原因是历史因素，另一个原因是C++并未提供相应于realloc()的内存配 置操作）,因此，SGI不能直接使用C++的set_new_handler(),必须仿真一个类似的set_malloc_handler()。
2. SGI第一级配置器的allocate()和realloc()都是在调用malloc ()和realloc()不成功后，改调用oom_malloc()和oom_realloc()。后两者都有内循环，不断调用“内存不足处理例程”，期望在某次调用之后，获得足够的内存完成任务。但如果“内存不足处理例程”并未被客端设定，并未被客端设定， oom_malloc ()和oom_realloc()便老实地调用__THROW_BAD_ALLOC,丢出bad_alloc异常信息，或利用exit(1)终止程序。
3. 设计“内存不足处理例程”是客端的责任，设定“内存不足处理例程”也是客端的责任。“内存不足处理例程”解决问题的做法有特定的模式。

2.6 第二级配宣器__default_alloc_ ternplate剖析

第二级配置器多了一些机制，避免太多小额区块造成内存的碎片。小额区块带来不仅是内存碎片，配置时的额外负担(overhead)也是一个大问题，额外负担永远无法避免，毕竟系统要靠这多出来的空间来管理内存，如图所示。但是区块愈小，额外负担所占的比例就愈大，愈显得浪费。

SGI第二级配置器的做法是，

1. 区块超过128 bytes， 就移交第一级配置器处理。
2. 当区块小于128 bytes， 则以内存池(memory pool)管理， 此法 又称为次层配置(sub-allocation) : 每次配置一大块内存， 并维护对应之自由链表(free-list)。 若再有相同大小的内存需求，就直接从free-lists中拨出。
3. 客端释还小额区块，就由配置器回收到free-lists中， 且配置器除了负责配置， 也负责回收。
4. SGI第二级配置器可以主动将任何小额区块的 内存需求量上调至8的倍数（例如客端要求30 bytes, 就自动调整为32 bytes) 并维护16个free-lists, 各自管理大小分别为8, 16, 24, 32,40,48,56,64, 72, 80, 88, 96, 104, 112, 120, 128 bytes的小额区块。

free-lists的节点结构如下：

union obj {
	union obj* free_list_link;
	char client_data[1];
};

1. 为了维护链表（lists) , 每个节点需要额外的指针（指向下一 个节点）， 会造成额外负担。但已经有了解决办 法。

2. 上述obj所用的是union, 由于union之故，从其第一字段观之， obj可被视为一个指针，指向相同形式的另 一个obj；从其第二字段观之， obj可 被视为一个指针， 指向实际区块，如图所示。

3. 一物二用的结果是， 不会为了维 护链表所必须的指针而造成内存的另一种浪费（我们正在努力节省内存的开销呢）。 这种技巧在强型(strongly typed)语言如Java中行不通，但是在非强型语言如C++ 中十分普遍。
   下面是第二级配置器的部分实现内容：

enum {_ALIGN  8}; //小型区块的上调边界

enum {_MAX_BYTES 128}; //小型区块的上限

enum {_NFREELISTS =_MAX_BYTES/_ALGN}; // free-lists个数
//以下是第二级配置器
//注意， 无 "template型别参数” ，且第二参数完全没派上用场
//第一参数用于多线程环境下。 本书不讨论多线程环境
template <bool threads, int inst> 
class _default_alloc_template { 
private:
// ROUND_UP()将 bytes上调至8的倍数
static size_t ROUND_UP(size_t bytes) {
return (((bytes) + __ALIGN-1) & ~(__ALIGN - 1));
}
private:
union obj{
union obj * free_list_link;
char client_data[1];
};
private:
//16个free-lists
static obj * volatile free_list[__NFREELISTS];
//以下函数根据区块大小，决定使用第n号free-list。n从1起算
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"的区块
//如果配置nobjs个区块有所不便，nobjs可能会降低
static char *chunk_alloc(size_T size,int &nobjs);
// 区块分配状态
state static char *start_free; //内存池起始位置。只在chunk_alloc()中变化
static char *end_free; //内存池结束位置，只在chunk_alloc()中变化
static size_t heap_size; 
public:
static void* allocate(size_t n) { /*详述于后*/)
static void deallocate(void *p, size_t n) { /*详述十后*/}
static void* reallocate(void *p , size_t old_sz, size_t new_sz);
};
//以下是static data member的定义勹初值设定
template <bool threads,int inst>
char *__default_alloc_template<threads,inst>::start_free = 0;

template <bool threads,int inst>
char *__default_alloc_template<threads,inst>::end_free = 0;

template <bool threads,int inst>
size_t __default_alloc_template<threads,ints>::heap_size = 0;

template <bool threads,int inst>
__default_alloc_template<threads,ints>::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, };

2.7 空间配宣函数allocate()

1. 身为一个配置器，__default_alloc_template拥有配置器的标准接口函数 allocate ()。
2. 此函数首先判断区块大小，大于128bytes就调用第一级配置器;小 于128bytes就检查对应的freelist。
3. 如果freelist之内有可用的区块，就直接拿来 用，如果没有可用区块，就将区块大小上调至8倍数边界，然后调用refill(), 准备为free list重新填充空间

// n must be> 0 
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);
};

区块自free list调出的操作:

2.8 空间释放函数deallocate()

身为一个配置器,__default_alloc_ternplate拥有配置器标准接口函数deallocate ()。该函数首先判断区块大小，大与128bytes就调用第一级配置器，小与128 bytes就找出对应的free list, 将区块回收。

// p不可以是0
sta七 ic void deallocate(void *p, size_t n)
{
bj *q = (obj*)p;
obj *volatile* rny_free_list; 
//大于128就调用第一级配置器
if (n > (size_t) _MAX_BYTES) {
malloc_alloc::deallocate(p, n); return; 
}
//寻找对应的freelist 
my_free_list = free_list + FREELIST_INDEX(n); 
//调整free list, 回收区块
q -> free_list＿link = *my_free_list; 
*my_free_list=q;
}

区块回收纳入free list的操作:

2.9 重新填充free lists

前面讨论说过的allocate()。当它发现free list中没有可用区块了时，就调用refill (), 准备为free list重新填充空间。新的空间将取自内存池（经由chunk_alloc () 完成）。缺省取得20个新节点（新区块），但万一内存池不足，获得的节点数（区块数）可能小与20:

//返回一个大小为n的对象，并且有时候会为适当的freelist增加节点 
//假设n已经适当上调至8的倍数
template<bool threads, int inst>
void* _default_alloc_template<threads, inst>::refill(size_t n)
{
int nobjs = 20; 
//调用 chunk—alloc (), 尝试取得nobjs个区块作为free list的新节点 
//注意参数 nobjs是pass by reference 
char * chunk = chunk_alloc(n, nobjs}; 
obj *volatile * my_free_list; 
obj * result;
obj * current_obj, * next_obj; 
int i; 
//如果只获得一个区块，这个区块就分配给调用者用，freelist无新节点 
if (1 == nobjs) return(chunk); 
//否则准备调整freelist, 纳入新节点
my_free_list = free_list + FREELIST_INDEX(n); 
//以下在chunk空间内建立freelist 
result = (obj *)chunk; //这一块准备返回给客端
//以下导引freelist指向新配置的空间（取自内存池）
*my_free_list = next_obj = (obj *)(chunk+ n); 
//以下将freelist的各节点串接起来
for(i = 1; ;i++){//从1开始，因为第0个准备返回给客端
current_obj = next_obj; 
next_obj = (obj *)((char *) next_obj + n) ;
 if (nobJS -1 == 1.) {
current_obj-> free_list_link = O; 
break; 
} else { 
current_obj -> free_list_link = next_obj;
	}
}
return (result)
}

2.10 内存池(memorypool)

从内存池中取空间给freelist使用，是chunk_alloc()的工作：

//假设size已经适当上调至8的倍数
//注意参数nobjs是passby reference 
template<bool threads, int inst> 
char* 
_default_alloc—template<threads, inst>:: 
chunk_alloc(size_t size,int&nobjs) 
{
char* result; 
size_t total_bytes=size* nobjs; 
size_t bytes_left= end_free-start_free; //内存池剩余空间
if(bytes_left >= total_bytes){
//内存池剩余空间完全满足需求量 
result= start_free;
start_free += total—bytes;
 return(result);
 }
 else if (bytes_left >= size} {
//内存池剩余空间不能完全满足需求量，但足够供应一个（含）以上的区块
nobjs = bytes_left/size; 
total_bytes =size* nobjs; 
result= start_free; 
start_free+= total_bytes;
return(result);
}else{
//内存池剩余空间连一个区块的大小都无法提供
size_t bytes_to_get = 2 * total_bytes + ROUND_UP (heap_size >> 4} ;
 //以下试着让内存池中的残余零头还有利用价值
if (bytes_left > 0} {
//内存池内还有一些零头， 先配给适当的free list 
//首先寻找适当的freelist 
obj * vola口le*my_free_list = 
free_list + FREELIST_INDEX(bytes_left); 
//调整free list, 将内存池中的残余空间编入
((obj *)start_free) -> free_list_link = *my_free_list; 
*my_free_list = (obj *)start_free;
}
//配置heap空间， 用来补充内存池
start_free =(char*)malloc(bytes_to_get); 
if (0 == start_free} { 
II heap空间不足，malloc(}失败
1.nt 1.;
obj *volatile * my_free—list, *p; 
//试着检视我们手上拥有的东西。 这不会造成伤害。 我们不打算尝试配置 
//较小的区块，因为那在多进程(multi-process)机器上容易导致灾难
//以下搜寻适当的free list 
//所谓适当是指“尚有未用区块，且区块够大”之freelist
for (i = size; i <=__MAX_BYTES; i +=__ALIGN) { 
my_free_list = free_list + FREELIST_INDEX(i);
 p = *my_free_list; 
 if(0 !=p){//free list内尚有未用区块
 //调整free list以释出未用区块
*my_free_list = p -> free_list_link ; start_free = (char *}p;
end_free = start_free + 1.;
//递归调用自己， 为了修正nobjs
return(chunk_alloc(size, nobj s }); 
 //注意，任何残余零头终将被编人适当的free-list中备用
 	}
 }
 end_free = O; //如果出现意外（到处都没内存可用了）
//调用第一级配置器，看看out-of-memory机制能否尽点力
start_free= (char *)malloc_alloc::allocate(bytes_to_get);
//这会导致抛出异常(exception), 或内存不足的情况获得改善
}
heap_size += bytes_to_get; 
end_free = start_free + bytes_to_get; //递归调用自己， 为了修正nobjs
return(chunk_alloc(size, nobjs)); 
	}
}

上述的chunk_alloc ()函数以end_free - start_free来判断内存池的水量。

1. 如果水量充足， 就直接调出20个区块返回给free list。
2. 如果水量不足以提供20 个区块， 但还足够供应一个以上的区块， 就拨出这不足20个区块的空间出去。 这时候其pass by reference的nobjs参数将被修改为实际能够供应的区块数。
3. 如果内存池连一个区块空间都无法供应，对客端显然无法交待，此时便需利用malloc () 从heap中配置内存， 为内存池注入活水源头以应付需求。 新水量的大小为需求量 的两倍， 再加上一个随着配置次数增加而愈来愈大的附加量。

例如：如图所示：整个第二级空间配置器的设计

1. 开始，客端就调用chunk_alloc (32, 20), 于是malloc ()配置40个32 bytes区块， 其中第1个交出， 另19个交给 free_list(3] 维护 ，余20 个留给内存池 。
2. 接下来客端调用chunk_alloc(64,20), 此时free_list[7]空空如也， 必须向内存池要求支持。 内存池只够供应(32*20)/64=10个64 bytes区块， 就把这10个区块返回， 第1个交给客端， 余9个由free_list[7]维护。 此时内存池全空。
3. 接下来再调用 chunk_alloc(96, 20), 此时free_lis七 [11]空空如也， 必须向内存池要求支持， 而内存池此时也是空的，于是以malloc()配置40+n (附加量）个96 bytes区块， 其中第l个交出， 另19个交给free_list[11]维护， 余20+n (附加量）个区块 留给内存池…
4. 如果整个systemheap空间都不够了， malloc ()行动失败，chunk_alloc ()就四处寻找有无 “尚有未用区块， 且区块够大” 之free lists。 找到了就挖一块交出， 找不到就调用第一级配置器。 第 一级配置器其实也是使用malloc()来配置内存，但它有out-of-memory处理机制（类似new-handler机制），或许有机会释放其它的内存拿来此处使用。 如果可以， 就成功， 否则发出bad_alloc异常。

前面2.4提到配置器标准接口的simple_alloc:

template <class T,class Alloc>
class simple_alloc{
...
};

SGI 容器通常以这种方式来使用配置器:

template <class T,class Alloc  = alloc>//缺省使用alloc为配置器
class vector{
public:
typedef T value_type;
...
protected:
//专属之空间配置器， 每次配置一个元素大小
typedef simple_alloc<value_type, Alloc> data_allocator;
...
};

其中第二个template参数所接受的缺省参数alloc, 可以是第一级配置器， 也可以是第二级配置器。 不过，SGI STL已经把它设为第二级配置器。

3.内存基本处理工具

STL定义有五个全局函数，作用于未初始化空间上。这样的功能对于容器的实现很有帮助，我们会在第4章容器实现代码中，看到它们肩负的重任。

1. 前两个函数是 2.3节说过的用于构造的construct ()和用于析构的destroy(),
2. 另三个函数是 uninitialized_copy() ,uninitialized_fill (), uninitialized_fill_n () ,
   分别对应与高层次函数copy()、 fill()、 fill_n(),这些都是STL算法， 将在第6章介绍。
3. 使用本节的三个低层次函数， 应该包含, 不过 SGI把它们实际定义于<stl_uninitialized>。

3.1 uninitialized_copy

template<class Inputiterator, class Forwarditerator> 
ForwardIterator 
uninitia1ised_ocpy(InputIterator first， InputIterator last, 
ForwardIterator result);

1. uninitialized_copy ()够将内存的配置与对象的构造行为分离开来。
2. 如果作为输出目的地的[result, result+(last-first))范围内的每 一个迭代器都指向未初始化区域，则uninitialized_copy()会使用copy constructor , 给身为输入来源之［first,last）范围内的每一个对象产生一份复制品，放进输出 范围中。 换句话说， 针对输入范围内的每 一 个迭代器i, 该函数会调用 construct(&*(result+(i-first)),*i)， 产生i的复制品， 放置于输出范围的相对位置上。式中的construct()前面提过。

如果需要实现一个容器，uninitial ized_copy ()这样的函数会为你带来很大的帮助，因为容器的全区间构造函数(rangeconstructor)通常以两个步骤完成：

1. 配置内存区块，足以包含范围内的所有元素。

2. 使用uninitialized_copy(),在该内存区块上构造元素。

C++标准要求uninitalized_copy()具有"commit or rollback"语意，意思是要么“构造出所有必要元素”，要么（当有任何一个copy constructor失败时）”不构造任何东西"。

3.2 uninitialized fill

template <class ForwardJ;terator, class T> 
void uninitialized_fill (Forwarditerator first，Forwardlteratorlast,const T& x);

1. uninitialized_fill ()也能够使我们将内存配置与对象的构造行为分离开来。
2. 如果[first,last)范围内的每个迭代器都指向未初始化的内存，那么
   uninitialized_fill()会在该范围内产生X(上式第三参数）的复制品。换旬话说uninitialized_fill ()会针对操作范围内的每个迭代器i,调用 construct (&*i, x), 在l所指之处产生x的复制品。construct()前面讨论过。
3. 与uninitialized_copy()一样，uninitialized_fill ()必须具备"commit or rollback"语意，换句话说，它要么产生出所有必要元素，要么不产生任何元素。 如果有任何一个copy constructor丢出异常(exception),uninitialized_fill (),必须能够将已产生的所有元素析构掉。

3.3 uninitialized_fill_n

template <class Forwarditerator, class Size, class T> 
Forwarditerator 
uninitialized fill_n(Forward工teratorfirst，Sizen, const T&x);

1. uninitialized_fill_n ()能够使我们将内存配置与对象构造行为分离开来。它会为指定范围内的所有元素设定相同的初值。
2. 如果[first,first+n)范围内的每一个迭代器都指向未初始化的内存，那么uninitialized_fill_n()会调用copy constructor, 在该范围内产生X(上式第三参数）的复制品。也就是说，面对[first,first+n)范围内的每个迭代器 i, uninitialized_fill_n()会调用construct(&*i, x), 在对应位置处产生x 的复制品。construct()前面讨论过。
3. uninitialized_fill_n ()也具有"commitor rollback"语意：要么产生所有必要的元素，否则就不产生任何元素。如果任何一个copy constructor丢出异常(exception) , uninitialized_fill_n ()必须析构已产生的所有元素。

以下分别介绍这三个函数的实现法。其中所呈现的iterators(迭代器）、 value_type （）、_type_traits、_true_type、_false_type、is_POD_type 等实现技术，都将于第3章介绍。

（1).uninitialized_fill_n

首先是uninitialized_fill_n()的源代码。本函数接受三个参数：

1. 迭代器frrst指向欲初始化空间的起始处。

2. n表示欲初始化空间的大小。

3. X表示初值。

template <class ForwardIterator,class Size, class T> 
inline Forwarditerator uninitialized_fill_n (Forwarditerator first,Size n, const T& x) {
return uninitialized_fill_n(first,n, x, value_type(first)); //以上，利用value_type()取出first的value type 
}

这个函数的进行逻辑是，首先萃取出迭代器first的value type (详见第3 章），然后判断该型别是否为POD型别：

 template<class Forwardlterator, class Size, class T, class T1> 
inline ForwardIterator _uninitialized_fill_n (ForwardIterator first,Size n, const T& x, T1*)
{
//以下_type_traits<>技法，详见3.7节
typedef typename _type_traits<T1>::is_POD_type is_POD; 
return __uninitialized_fill_n_aux(first,n,X, is_POD()) ; 

POD意指Plain Old Data, 也就是标量型别(scalar types)或传统的C struct 型别。POD型别必然拥有trivial ctor / dtor /copy/ assignment函数，因此，我们可以对POD型别采用最有效率的初值填写手法，而对non-POD型别采取最保险安全的做法：

//如果copyconstrue口on等同于assignment,而且
// destructor是trivial,以下就有效
//如果是POD刑别，执行流程就会转进到以下函数。这是藉由functiontemplate II的参数推导机制而得
template <class Forwarditerator,class Size, class T> 
inline Forwarditerator 
__uninitialized_fill_n_aux(ForwardIterator first,Sizen, 
const T& x, _true_type) { 
returnfill_n(first,n, x); //交由高阶函数执行。见6.4.2节
}
//如果不是POD型别，执行流程就会转进到以下函数。这是藉由functiontemplate II的参数推导机制而得
template<class Forwarditerator, class Size, class T> 
Forwarditerator 
__uninitialized_fill_n_aux(Forwarditerator first, Size n, 
const T& x, _false_type) ( 
Forwarditerator cur= first;
//为求阅读顺畅，以下将原本该有的异常处理(exception handling)省略 
for (; n > 0; --n, ++cur) 
construct (&*cur, x);//见2.2.3节
return cur; 
}

(2) uninitialized_copy
下面列出uninitialized—copy()的源码。本函数接受三个参数：

1. 迭代器first指向输入端的起始位置。

2. 迭代器last指向输入端的结束位置（前闭后开区间）。

3. 迭代器result指向输出端（欲初始化空间）的起始处。

template <class Inputiterator, class Forwarditerator> inline ForwardIterator
uninitialized_copy(Inputiterator first, Input.Iterator last,ForwardIterator result){
return _uninitialized_copy(first,last, result, value_type(result));
//以上，利用value_type()取出first的valuetype 
}

这个函数的进行逻辑是，首先萃取出迭代器result的valuetype (详见第3 章），然后判断该型别是否为POD型别：

template <class Inputiterator, class Forwarditerator, class T> inline ForwardIterator
__uninitialized—copy(Inputiterator first, Inputiterator last,Forwarditerator result, T*) {
typedef typename _type_trait<T>::is_POD_type is_POD;
return __uninitialized_copy_aux(first, last, result, is_POD()); 
//以上，企图利用is_POD()所获得的结果，让编译器做参数推导
}

POD意指Plain Old Data, 也就是标量型别(scalartypes)或传统的C struct型别。POD型别必然拥有trivial ctor / dtor /copy/ assignment函数，因此，我们可以 对POD观别采用最有效率的复制手法，而对non-POD型别采取最保险安全的做法：

//如果copycons七rue巨on等同于assignment,而且
// destructor是trivial,以下就有效
//如果是POD型别，执行流程就会转进到以下函数。这是藉由func七iontemplate II的参数推导机制而得
template <class InputIterator,class Forwarditerator> 
inline ForwardIterator
__uninitialized_copy_aux(InputIterator first, InputIterator last, 
ForwardIterator result,
__true_type){ 
return copy(first, last, result); II调用STL算法copy()
}
//如果是non-POD型别，执行流程就会转进到以下函数．这是藉由functiontemplate II的参数推导机制而得
template <class InputIterator,class Forwardlterator> 
ForwardIterator
__uninitialized_copy_aux(InputIteratorfirst, InputIterator last, 
ForwardIterator result,
_false_type) { 
Forwarditerator cur= result; 

//为求阅读顺畅，以下将原本该有的异常处理(exceptionhandling)省略
 for (; first != last; ++first,++cur)
construct (&*cur, *first); //必须一个一个元素地构造，无法批量进行
 return cur; 
 }
}

针对cha户和wchar_t*两种型别， 可以采用最具效率的做法mernmove (直接移动内存内容）来执行复制行为。因此SGI得以为这两种型别设计一份特化版本。

//以下是针对cons七 char*的特化版本
inline char* uninitialized_copy(const char* first, const char* last,har* result){
memmove(result, first, last - first); 
return result + (last - first); 
}
//以下是针对const wchar_t*的特化版本
inline wchar_t* uninitialized_copy(const wchar_t* first, const wchar_ t* last,wchar_t* result) { 
memmove(result, first, sizeof(wchar_t) * (last - first));
return result + (last - first);
}

(3) uninitialized_fill

下面列出uninitialized_fill ()的源代码。 本函数接受三个参数：

1. 迭代器first指向输出端（欲初始化空间）的起始处。

2. 迭代器last指向输出端（欲初始化空间）的结束处（前闭后开区间）。

3. X 表示初值。

template <class Forwarditerator, class T> 
inline void uninitialized_fill (Forwarditerator first， Forwarditerator last,const T& x) { 
__uninitialized_fill(first, last, x, value_type(first));
}

这个函数的进行逻辑是，首先萃取出迭代器first的valuetype (详见第3章）， 然后判断该型别是否为POD型别：

template <class Forwarditerator, class T, class T1> 
inline void uninitialized_fill(Forwarditerator first, Forwarditerator last,const T& x, T1*) {
typedef typename _type_traits<T1>::is_POD_type is_POD; 
_uninitialized_fill_aux (first, last, x, is_POD ()) ; 
}

POD意指Plain Old Data, 也就是标董型别(scalar types)或传统的C struct型别。POD型别必然拥有trivial ctor / dtor /copy/ assignment函数， 因此， 我们可以对POD型别采用最有效率的初值填写手法， 而对non-POD型别采用最保险安全的做法：

//如果copyconstruction等同于assignrnen七，而且
// destructor是trivial,以下就有效
//如果是POD型别，执行流程就会转进到以下函数。这是藉由functiontemplate 
//的参数推导机制而得
template <class Forwarditerator, class T>
inline void 
__uniniialized_fill_aux(Forwarditeratorfirst, Forwarditerator last,const T&x, _true_type)
{
fill(first, last,x);//调用STL算法fill()
}
//如果是non-POD型别，执行流程就会转进到以下函数．这是藉由function template //的参数推导机制而得
template <class Forwarditerator, class T>
void 
__uninitialized_fill_aux(ForwardIterator first, Forwarditerator last,const T& x, _false_type)
{
Forwarditerator cur= first;
//为求阅读顺畅，以下将原本该有的异常处理(exceptionhandling)省略
for(; cur != last; ++cur) 
construct(&*cur, x) ; //必须一一个元素地构造，无法批量进行
 }
}

以图形显示本节三个函数对效率的特殊考虑，三个内存基本函数的泛型版本与特化版本：