SGI STL一级二级空间配置器代码剖析笔记

       STL不仅是一个可复用组件库，而且是一个包罗算法与数据结构的软件框架。说到框架本身就有庞大，稳定，完整而可扩展的含义。因此学习STL源码不仅可以帮助我们编写良好代码的习惯，而且能够让我们熟悉算法，数据结构，我们也会受到这种编程思维影响，在编写代码时考虑全方面，可复用，高效的情况。只要好好的分析，一定能收获很多。我也是菜鸟一只，在这里想将自己看的与想的记录与分享！

我剖析的是SGL 版本的STL，读的书是候捷的书。

STL六大组件：空间配置器，容器，迭代器，算法，仿函数，配置器。

容器：各种数据结构，vector，list，deque，set，map用来存放数据。

算法：各种常见算法，sort，search，copy，erase。STL算法是一种function template。

迭代器:扮演的角色是容器与算法的粘合剂，是所谓的“泛型指针”。 共5种类型，从实现角度看，迭代器实现了operator*，operator->,operator++,operator--等指针操作重载的class temlpate。

为什么是粘合剂？根据我的理解，在算法的实现上面看，算法本身的实现与数据的存储无关。既算法的思维是不变的，不会因为你存的数据不同算法不同。因此设计迭代器在数据与算法之间架起了一个桥梁。

仿函数：类似函数，作为算法的一种策略。

配接器：一种修饰容器，或者仿函数，或迭代器接口的东西，。

空间配置器：负责空间的分配与管理，此篇文章就讨论一下空间配置器。（没有考虑多线程的情况）

一级空间配置器__malloc_alloc_template：

首先这个类中一共有下面几个函数：

除了几个函数之外还有个静态变量：

static void (*_malloc_alloc_oomhandler)();  //函数指针

一级空间配置中，比较重要的是set_new_handler机制的模拟实现。在vc中不支持这个机制，在vs中支持。在这里他模拟了此实现。

主要在这里就是分析这个set_new_handler机制的主要实现。

static void (*set_malloc_handler(void(*f)()))()
{
    void (*old)()= _malloc_alloc_oomhandler;
	_malloc_alloc_oomhandler = f;
	return *old;
}

_malloc_alloc_oomhandler是一个函数指针，开始赋值为空。(静态变量在类外初始化)

set_malloc_handler() 函数的参数是函数指针，接收_malloc_alloc_oomhandler类型的函数指针。我们可以看见函数实现中，为_malloc_alloc_oomhandler赋予了一个函数地址，相当于为set_new_handler机制提供了处理函数。

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_oomhandler; //等待用户设置处理函数 set_new_handler
		if(0 == my_malloc_handler)
		{
			__THROW_BAD_ALLOC;
		}
		(*my_malloc_handler)();
		result = malloc(n);
		if(result)
			return result;
	}
}

从上面的代码中我们可以看见 如果当 _malloc_alloc_oomhandler为空时，函数会直接抛出异常，如果不为空，则会指向所指向函数。这是在oom_malloc()函数执行，当执行到这里时，已经说明在申请空间时不能正常申请，转而调用处理函数，或者抛出异常。

画出一级空间配置器执行流程图：

二级空间配置器：

类声明如下：

enum{__ALIGN = 8};
enum{__MAX_BYTES=128};
enum{__NFREELISTS =__MAX_BYTES / __ALIGN}; //free-list个数

template<bool threads,int inst>
class __default_alloc_template
{
private:
	static size_t ROUND_UP(size_t bytes) //将bytes上调为8的倍数
	{
		return (((bytes)+__ALIGN-1)&~(__ALIGN-1));
	}
	static size_t FREELIST_INDEX(size_t bytes) // 由bytes计算其应该使用free_list的下标
	{
		return (((bytes)+__ALIGN-1) / __ALIGN-1);
	}
private:
	union obj //free_list 节点构造
	{
		union obj *free_list_link;
		char client_data[1];
	};
	static void *refill(size_t n); //申请空间，返回一个大小为n的对象
    //配置一大块空间，大小为nobjs个size,如果配置nobjs个区块不便，nobjs可能会降低
	static char* chunk_alloc(size_t size,int &nobjs);
	static obj *free_list[__NFREELISTS]; //自由链表数组 
private:
	static char *start_free; //内存池起始位置
	static char *end_free;   //内存池结束位置
	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);
};
//为静态成员变量初始化
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,inst>::heap_size = 0;
template<bool threads,int inst>
__default_alloc_template<threads,inst>::obj*__default_alloc_template<threads,inst>::free_list[__NFREELISTS]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};

二级空间配置器设计巧妙，它与一级配置器规定当申请空间大于128字节时，由一级空间配置器负责申请空间，当申请空间字节小于128时，由二级空间配置器负责。而二级空间配置值将128字节大小分成了16组，每组都是一个自由链表。每组各自管理大小分别是8,16,24,32.。。。。128bytes的大小区块。

例如当申请5个字节时，则会在free_list[0]中为其分配空间。计算过程为 ： FREELIST_INDEX（8）计算出来其应该在数组下标为0的自由链表中分配空间。

下面讲解函数:

allocate函数:

template<bool threads,int inst>
void *__default_alloc_template<threads,inst>::allocate(size_t n)
{
	obj ** my_free_list;
	obj *result;
	if(n > (size_t)__MAX_BYTES)
	{
		cout<<"调用一级空间配置器"<<endl;
		return (malloc_alloc::allocate(n));
	}
	my_free_list = free_list+FREELIST_INDEX(n);
	result = *my_free_list;
	if(NULL == result)
	{
		void *r = refill(ROUND_UP(n));
		return r;
	}
	*my_free_list = result->free_list_link;
	return result;
}

allocate函数流程： 申请空间： 当申请空间字节大于128字节 调用一级空间配置器。否则调用FREELIST_INDEX()函数让指针指向适当的数组元素地址，然后将数组中保存的自由链表地址赋值给result，既result指向了自由链表。如果自由链表为空，那么就调用refill()函数（此处调用了ROUND_UP()函数，申请空间大小都为8的倍数）去填充空间，然后将申请到的空间返回。如果不为空，则说明这个位置有相同大小可用的块(>=1块)。则进行头删操作(链表头删，将第一块分配出去)，然后返回result。

refill()函数:

template<bool threads,int inst>
void *__default_alloc_template<threads,inst>::refill(size_t n)
{
	int nobjs =20;
	//调用chunk_alloc尝试取得nobjs区块作为free_list的新节点
	char *chunk = chunk_alloc(n,nobjs);
	obj **my_free_list;
	obj *result;
	obj *current_obj,*next_obj;
	int i;
	
	if(1 == nobjs)
		return chunk;
	my_free_list = free_list+FREELIST_INDEX(n);
	result = (obj*)chunk;
	*my_free_list =next_obj=(obj*)(chunk+n);
	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;
}

refill()函数流程: 设置nobjs =20，表示需要申请nobjs块size大小的空间。在二级空间配置器中，如果当某个自由链表为空，则会默认 为它在内存池中申请20块size大小的空间。这个大小会随着真实剩余空间改变。

                         调用chunk_alloc(size,nobjs)函数，真正的空间配置函数，去分配nobjs*size大小空间。然后返回空间的首地址。

                         如果nobjs为1，注意，nobjs的参数传递是引用，可以在函数里面改变。也就是因为空间不足，实际只申请了一块大小空间。虽然少，但是够我们这一次用了。然后直接返回。

                         否则 调用函数FREELIST_INDEX()函数让指针指向适当的数组元素地址(存的是指向自由链表的指针)，接下来的工作就是将申请来的空间分割成块，块的大小就是你要申请空间的最小8的倍数。然后返回首个块地址(这个块就不会在自由链表中，因为已经分配出去了)。

chunk_alloc函数(分配空间函数)：

template<bool threads,int inst>
char* __default_alloc_template<threads,inst>::chunk_alloc(size_t size,int &nobjs)
{
	char *result;
	size_t total_size = size *nobjs;
	size_t bytes_left = end_free - start_free; //内存池剩余空间
	if(bytes_left >=total_size) //完全够分配
	{
		result = start_free;
		start_free += total_size;
		return result;
	}
	else if(bytes_left >=total_size)  //只够分配一个或多个。不够size个
	{
		nobjs = bytes_left /size;
		total_size = size*nobjs;
		result = start_free;
		start_free +=total_size;
		return result;
	}
	else   //内存池一个都不能分配
	{
		size_t  bytes_to_get = 2*total_size+ROUND_UP(heap_size>>4);
		//回收零头
		if(bytes_left >0)
		{
			obj **my_free_list;
			my_free_list = free_list+FREELIST_INDEX(bytes_left);
			//头插
			((obj*)start_free)->free_list_link = *my_free_list;
			*my_free_list = (obj*)start_free;
		}
		start_free = (char*)malloc(bytes_to_get);  //向内存申请空间
		if(0 == start_free)
		{
			int i;
			obj **my_free_list,*p;
			for( i =size;i<__MAX_BYTES;i+=__ALIGN)
			{
				my_free_list = free_list+FREELIST_INDEX(i);
				p = *my_free_list;
				if(0 != p)
				{
					*my_free_list = p->free_list_link;
					start_free = (char*)p;
					end_free = start_free+i;
					return (chunk_alloc(size,nobjs));
				}
			}
			end_free = 0;
			start_free = (char*)malloc_alloc::allocate(bytes_to_get);
		}
		heap_size +=bytes_to_get;
		end_free = start_free+bytes_to_get;
		return chunk_alloc(size,nobjs); //修正nobjs
	}
}

chunk_alloc函数过程： 进入函数后，首先计算需要申请空间的大小 total_size，然后计算了内存池空间的大小bytes_left。

                               当内存池剩余空间大小等于 需求大小空间时，哪我们可以直接分配。让result指向start_free(指向内存池空间开始)，

然后将start_free +=total_size；改变内存池起始位置。(返回的是整块空间)

                              当内存池剩余空间大小不足分配total_size大小时，哪我们可以减少申请的空间。计算新的nobjs大小，改变内存池首地址位置，然后返回申请到空间首地址。

                              当内存池剩余空间不足分配块空间时，我们只能向堆申请空间。不过在此之前我们依然有措施可能申请到空间。注意的是在向堆申请空间时，一般都是申请2倍空间(用一半，此时内存池所剩无几，用做内存池补充)。回收零头，将内存池中无法分配出一个块的内存挂到合适的自由链表中去。采用同样是头插方式。然后向堆申请空间，申请成功后，改变heap_size大小，让start_free指向新的内存池地址，改变end__ree指向，然后递归调用chunk_alloc()，做法非常高明，这样调用后，此时内存池中已经有足够的空间，这时就会为其分配适当的空间然后返回。但是这是在向堆区申请空间成功后，如果失败，说明系统内存没有足够的空间，此时就会在块足够大的自由链表下面去寻找一块空间。将找到的块在其自由链表中取出，然后充当为内存池。然后继续递归调用chunk_alloc()，修正nobjs。如果在自由链表中依然没有找到可以用的空间，此时已经是山穷水尽，但是二级配置器采用了调用一级配置器的方法，不是都没有空间了吗？调用一级有用吗？ 答案是可能有用，因为一级空间配置器中有一个处理函数，它可能会帮我们省出内存空间。

 deallocate函数（空间回收函数）:

template<bool threads,int inst>
void __default_alloc_template<threads,inst>::deallocate(void *p,size_t n)
{
	obj *q = (obj*)p;
	obj **my_free_list;
	if(n > __MAX_BYTES)
	{
		malloc_alloc::deallocate(p,n);
		return;
	}
	my_free_list = free_list+FREELIST_INDEX(n); //头插
	q->free_list_link = *my_free_list;
	*my_free_list = q;
}

   deallocate函数（空间回收函数）:当回收的空间大于128个字节后，调用一级回收函数。当小于128字节通过FREELIST_INDEX(n)函数找到合适的自由链表，然后依然是头插，将空间p插入到自由链表中，至此空间回收完成。

同样画一个流程图来理解二级空间配置器顶点执行过程：

在我看来应该要把分配空间和申请空间区别出来，分配空间的意思是在已经有的空间中分配出一部分，申请空间是指向系统申请空间。在二级空间配置器中，只有在chunk_allic()函数中不能分配足够大的块时，向系统申请空间，其他情况都是在自由链表和内存池中分配空间。

讲了这么多，也只是大概把空间配置器的过程讲清楚，其中更有一些实现技巧，也是对c语言基础知识的考验。读源码不仅可以补充语法基础，也能让我们看出这些经典代码考虑问题的全面，复用性强的特点。我们不仅要学习语法，更深层的磨炼，更要学习这种思维。

其还实现了一个接口，可以通过接口来调用一二级空间配置器。

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(sizeof(T));
	}
	static void deallocate(T *p,size_t n)
	{
		if(0 != n)
			Alloc::deallocate(p,n*sizeof(T));
	}
	static void deallocate(T *p)
	{
		Alloc::deallocate(p,sizeof(T));
	}
};

我上面贴的代码是不全的，需要空间配置器完整部分代码的请到这里来下载：

https://github.com/hjh1997/info_bak/tree/STL

希望大家能够一起学习，一起进步！能分享自己的学习经验与想法，多多讨论！！