前不久把STL细看了一遍,由于看得太“认真”,忘了做笔记,归纳和总结这步漏掉了。于是为了加深印象,打算重看一遍,并记录下来里面的一些实现细节。方便以后能较好的复习它。

空间配置器概述

以前在项目中运用STL一般都不会涉及到空间配置器,可是,在STL的实现中,空间配置器是重中之重,因为整个STL的操作对象都存放在容器之内,而容器一定需要配置空间以置放资料。所以,在阅读STL源码时,最先需要掌握的就是空间配置器,没了它,容器,算法怎么存在?

C++ STL的空间配置器将内存的配置、释放和对象的构造和析构分开,内存配置操作由alloc::allocate()负责,内存释放由alloc::deallocate()负责;对象构造操作由::construct()负责,对象的析构操作由::destroy()负责。首先放一张思维导图来概述一下STL的整个空间配置器概览。

空间配置器
空间配置器

对象的构造和析构

个人觉得看源码只需要图和代码注释即可,所以本篇博客图片较多!对着图来看代码效率会高很多!

构造和析构
构造和析构

下面是源代码:

#include <new.h>        // 需要placement new的原型
// -----------------构造函数---------------------------------//
// 使用placement new在已经分配的内存上构造对象
template <class T1, class T2>
inline void construct(T1* p, const T2& value)
{
  new (p) T1(value);//将value设定到指针p所指的空间上
}

// -----------------析构函数---------------------------------//
// -----------第一个版本:接受一个指针--------------------------//
// 调用成员的析构函数, 需要类型具有non-trivial destructor
template <class T>
inline void destroy(T* pointer)
{
    pointer->~T();
}

// -----------第二个版本:接受两个迭代器------------------------//
template <class ForwardIterator>
inline void destroy(ForwardIterator first, ForwardIterator last)
{
  __destroy(first, last, value_type(first));
}
// 首先是两个特化版本
inline void destroy(char*, char*) {}
inline void destroy(wchar_t*, wchar_t*) {}

// 析构一组对象, 用于具有non-trivial destructor
template <class ForwardIterator>
inline void
__destroy_aux(ForwardIterator first, ForwardIterator last, __false_type)
{
  for ( ; first < last; ++first)
    destroy(&*first);
}

// 如果没有类型non-trivial destructor, 则使用此函数
template <class ForwardIterator>
inline void __destroy_aux(ForwardIterator, ForwardIterator, __true_type) {}

// 使用traits技术, 判断类型是否就有non-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());
}

内存的配置和释放

在内存配置方面,STL分为两级配置器,当请求的内存大于128b的时候调用第一级配置器,当请求的内存小于等于128b的时候调用第二级配置器。先来看看下面这张表,大概就能知道第一级和第二级配置器主要干了些什么,其他的一些细节如内存池是怎么工作的,下面会给出具体解释。

内存配置
内存配置

第一级配置器

首先我们来看第一级配置器的源码:

template <int inst>  
class __malloc_alloc_template  
{  
private:
	//调用malloc函数不成功后调用
	static void *oom_malloc(size_t);

	//调用realloc函数不成功后调用 
	static void *oom_realloc(void *, size_t);

	//类似于C++的set_new_handle错误处理函数一样,如果不设置,在内存不足时,返回THROW_BAD_ALLOC
	#ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG  
		static void (* __malloc_alloc_oom_handler)();  
	#endif  

	public:  
	//直接调用malloc来分配内存
	static void * allocate(size_t n)  
	{  
	 void *result = malloc(n);  
	 if (0 == result) result = oom_malloc(n);  //如果分配失败,则调用oom_malloc()
	 return result;  
	}  
 	//第一级配置器直接调用free来释放内存
	static void deallocate(void *p, size_t /* n */)  
	{ 
		free(p); 
	}  
	//直接调用reallloc来分配内存
	static void * reallocate(void *p, size_t /* old_sz */, size_t new_sz)  
	{  
	 void * result = realloc(p, new_sz);  
	 if (0 == result) result = oom_realloc(p, new_sz);  //如果realloc分配不成功,调用oom_realloc()
	 return result;  
	}  

	//异常处理函数,即内存分配失败后的处理
	static void (* set_malloc_handler(void (*f)()))()  
	{  
	 void (* old)() = __malloc_alloc_oom_handler;  
	 __malloc_alloc_oom_handler = f;  
	 return(old);  
	}  
};   

从上述源码中可以看到,STL的第一级配置器仅仅是调用了malloc,free等函数,然后增加了内存分配错误下的异常处理函数,下面我们就通过源码来看看在内存分配失败后,STL是怎么处理的。

// 以下是针对内存分配失败后的处理
//首先,将__malloc_alloc_oom_handler的默认值设为0
template <int inst>  
void (* __malloc_alloc_template<inst>::__malloc_alloc_oom_handler)() = 0;  
#endif  

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_malloc_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);  // 如果分配成功则返回指针
	}  
}  

第二级配置器

当申请内存小于128b的时候,会调用第二级配置器。第二级配置器有一个内存池和一个对应的自由链表,其定义如下:

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

这里有一个技巧,如果使用union的第一个成员,则指向另一个相同的union obj;而如果使用第二个成员,则指向实际的内存区域,这样一来,既实现了链表结点只用一个指针的大小空间,却能同时做索引和指向内存区域。

这里的这个技巧我觉得有必要解释一下,首先client_data是一个常量指针,指向client_data[0],然后client_data[0]和free_list_link共用同一段内存,我们在使用这个union的时候,先让client_data指向实际的内存区域,然后将free_list_link(也就是client_data[0])赋值为下一个结点的地址,注意这里我只是修改了client_data[0],client_data并没有修改,而是始终指向实际内存。

我们先来看看第二级配置器的部分源码,然后再去分析其中每个函数的功能。

enum {__ALIGN = 8};   //小型区块的上调边界
enum {__MAX_BYTES = 128};  //小型区块的上限
enum {__NFREELISTS = __MAX_BYTES/__ALIGN};   //free-lists个数

//第一参数用于多线程,这里不做讨论。
template <bool threads, int inst>  
class __default_alloc_template  
{  
private:
	// 此函数将bytes的边界上调至8的倍数
	static size_t ROUND_UP(size_t bytes)  
	{  
	return (((bytes) + __ALIGN-1) & ~(__ALIGN - 1));  
	}  
private:    
	// 此union结构体上面已经解释过了
	union obj  
	{  
	union obj * free_list_link;  
	char client_data[1];
	};  
private: 
	//16个free-lists
	static obj * __VOLATILE free_list[__NFREELISTS];
	// 根据待待分配的空间大小, 在free_list中选择合适的大小  
	static  size_t FREELIST_INDEX(size_t bytes)  
	{  
	return (((bytes) + __ALIGN-1)/__ALIGN - 1);  
	}
	// 返回一个大小为n的对象,并可能加入大小为n的其它区块到free-lists
	static void *refill(size_t n);  
	// 配置一大块空间,可容纳nobjs个大小为“size”的区块
	// 如果配置nobjs个区块有所不便,nobjs可能会降低,所以需要用引用传递
	static char *chunk_alloc(size_t size, int &nobjs);  
	// 内存池  
	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); //空间重新配置函数
}

// 一些静态成员变量的初始化
// 内存池起始位置  
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 * __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, };  

看完上面这一堆源码,你可能早就头晕眼花,一脸懵逼了,没事,我再来用一张思维导图来帮你理一理思绪:

二级配置器1
二级配置器1

接下来又是枯燥的源码时间!相信有上面这张图,看源码的思路就比较清晰了。

空间配置函数allocate()

借用《STL源码剖析》里面的一张图,来说明空间配置函数的调用过程:(看图放松,放松完继续看源码!别偷懒)

空间配置函数
空间配置函数

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);  
};  

重新填充函数refill()

template <bool threads, int inst>  
void* __default_alloc_template<threads, inst>::refill(size_t n)  
{  
	int nobjs = 20;  //	默认获取20个
	char * chunk = chunk_alloc(n, nobjs);  //找内存池要空间
	obj * volatile * my_free_list;  
	obj * result;  
	obj * current_obj, * next_obj;  
	int i;  
	// 如果内存池仅仅只够分配一个对象的空间, 直接返回即可  
	if(1 == nobjs) return(chunk);  
	// 内存池能分配更多的空间,调整free_list纳入新节点
	my_free_list = free_list + FREELIST_INDEX(n);

	// 在chunk的空间中建立free_list  
	result = (obj *)chunk;
	*my_free_list = next_obj = (obj *)(chunk + n); //导引free_list指向新配置的空间(取自内存池)

	for(i = 1; ; i++) {	//从1开始,因为第0个返回给客端
		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);//返回头指针
}  

内存池函数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_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);//返回起始地址
    }  
    // 如果内存池中剩余的容量不够分配, 但是能至少分配一个节点时,  
    // 返回所能分配的最多的节点, 返回start_free指向的内存块  
    // 并且重新设置内存池起始点  
    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);  
        // 将剩余的内存分配给指定的free_list[FREELIST_INDEX(bytes_left)]  
        if (bytes_left > 0) {  
        	//内存池内还有一些零头,先分给适当的free_list
        	//寻找适当的free_list
            obj * __VOLATILE * 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;  
        }  
        start_free = (char *)malloc(bytes_to_get);  
        // 分配失败, 搜索原来已经分配的内存块, 看是否有大于等于当前请求的内存块  
        if (0 == start_free) {// heap里面空间不足,malloc失败
            int i;  
            obj * __VOLATILE * my_free_list, *p;  
            // 试着检查检查free_list中的可用空间,即尚有未用的空间,且区块够大  
            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));  
                    //任何剩余零头将被编入适当的free_list以留备用 
               }  
            }  
 
        // 再次失败, 直接调用一级配置器分配, 期待异常处理函数能提供帮助  
        // 不过在我看来, 内存分配失败进行其它尝试已经没什么意义了,  
        // 最好直接log, 然后让程序崩溃  
        end_free = 0;
        	//调用第一级配置器,看看out-of-memory机制能不能起点作用
            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));  
    }  
}

内存释放函数deallocate()

内存释放函数会将释放的空间交还给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) {  
		malloc_alloc::deallocate(p, n);  
		return;  
	}
	// 寻找适当的free_list  
	my_free_list = free_list + FREELIST_INDEX(n);  
	// 调整free_list,回收区块
	q -> free_list_link = *my_free_list;  
	*my_free_list = q;  
}

配置器的使用

通过以上的图和源代码,基本上将STL的两层配置器讲完了,接下来就来熟悉一下怎么使用配置器。

STL将上述配置器封装在类simple_alloc中,提供了四个用于内存操作的借口函数,分别如下:

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)); }
};

接下来就示范在vector中是怎么使用它的。

template <class T, class Alloc = alloc>  //alloc被默认为第二级配置器
class vector {
public:
	typedef T value_type;
  	//...
protected:
	// 专属的空间配置器,每次只分配一个元素的大小
	typedef simple_alloc<value_type, Alloc> data_allocator;

	// 在释放内存的时候直接调用借口函数即可
	void deallocate(){
		if(...){
			data_allocator::deallocate(start , end_of_storage - start);
		}
	}
};

至此,STL的空间配置器的原理和使用都已讲述完毕,读者们是否懂了呢? 没懂就戳下方的联系方式或者留言说出你的疑惑吧!

About Me

由于本人也是初学,在写作过程中,难免有错误的地方,读者如果发现,请在下面留言指出。

最后,如有疑惑或需要讨论的地方,可以联系我,联系方式见我的个人博客about页面,地址:About Me

另外,本人的第一本gitbook书已整理完,关于leetcode刷题题解的,点此进入One day One Leetcode

欢迎持续关注!Thx!