STL之空间配置器allocator

摘要

C++STL的空间配置器将内存的分配、释放,对象的构造、析构都分开执行,内存分配由alloc::allocate()负责,内存的释放由alloc::deallocate()负责;对象的构造由::construct()负责,对象的析构由::destroy()负责。

构造和析构:construct()和destroy()

下面为源码和注释:

#include <new.h>	//使用placement new

//使用placement new在已经分配的内存上构造对象
template <class T1, class T2>
inline void construct(T1* p, const T2& value) {
new (p) T1(value);
}
//第一个版本,接受一个指针
//调用对象的析构函数,它需要有non-trivial destructor
template <class T>
inline void destroy(T* pointer) {
pointer->~T();
} //第二个版本
//针对迭代器为char*和wchar_t*的特化版本
inline void destroy(char*, char*) {}
inline void destroy(wchar_t*, wchar_t*) {} //接受两个迭代器,找出元素的类型
template <class ForwardIterator>
inline void destroy(ForwardIterator first, ForwardIterator last) {
__destroy(first, last, value_type(first));
} //判断元素的类型是否有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());
} //元素的类型有non-trivial destructor
template <class ForwardIterator>
inline void
__destroy_aux(ForwardIterator first, ForwardIterator last, __false_type) {
for ( ; first < last; ++first)
destroy(&*first);
} //元素的类型有trivial destructor
template <class ForwardIterator>
inline void __destroy_aux(ForwardIterator, ForwardIterator, __true_type) {}

空间的配置和释放: std::alloc

在内存配置方面,STL分为两级配置器,当请求的内存大于128bytes的时候调用第一级配置器,当请求的内存小于等于128bytes的时候调用第二级配置器。如图:

STL之空间配置器allocator

第一级配置器源码:

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);
}
}; // 以下是针对内存分配失败后的处理
//首先,将__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); // 如果分配成功则返回指针
}
}

第二级配置器源码:

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 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, };
// The 16 zeros are necessary to make version 4.1 of the SunPro
// compiler happy. Otherwise it appears to allocate too little
// space for the array. public: //空间配置函数allocate()
static void * allocate(size_t n)
{
//指向freelist的指针
obj * __VOLATILE * my_free_list;
obj * __RESTRICT result;
//区块size大于128就调用一级配置器,n已被上调至8的倍数
if (n > (size_t) __MAX_BYTES) {
return(malloc_alloc::allocate(n));
}
//寻找freelists中适当的一个
my_free_list = free_list + FREELIST_INDEX(n);
result = *my_free_list;
//没有找到可用的freelist,就重新填充freelist
if (result == 0) {
void *r = refill(ROUND_UP(n));
return r;
}
//调整freelist
*my_free_list = result -> free_list_link;
return (result);
}; //空间释放函数deallocate()
//p不能为nullptr
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;
}
//找到对应的freelist
my_free_list = free_list + FREELIST_INDEX(n);
//调整freelist,回收区块
q -> free_list_link = *my_free_list;
*my_free_list = q;
} } ; //内存池函数chunk_allco()
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);
}
//余量不能完全满足需求,但至少能供应1个区块
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) {
//内存池还有一些零头
//寻找适当的freelist
obj * __VOLATILE * my_free_list =
free_list + FREELIST_INDEX(bytes_left);
//调整freelist,将内存池中剩余内存编入
((obj *)start_free) -> free_list_link = *my_free_list;
*my_free_list = (obj *)start_free;
}
//用malloc配置空间,补充内存池
start_free = (char *)malloc(bytes_to_get);
//malloc失败
if (0 == start_free) {
int i;
obj * __VOLATILE * my_free_list, *p;
// Try to make do with what we have. That can't
// hurt. We do not try smaller requests, since that tends
// to result in disaster on multi-process machines.
//不打算配置更小区块,那在多进程机器上会有灾难,无法让其他进程获取内存
//检查freelist中的可用空间,且区块足够大
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));
//任何剩余零头将被编入适当的freelist以备用
// Any leftover piece will eventually make it to the
// right free list.
}
}
//分配失败,就调用一级分配器分配,期待异常处理函数提供帮助
end_free = 0; // In case of exception.
start_free = (char *)malloc_alloc::allocate(bytes_to_get);
// This should either throw an
// exception or remedy the situation. Thus we assume it
// succeeded.
}
heap_size += bytes_to_get;
end_free = start_free + bytes_to_get;
//内存池更新完毕,重新分配内存
return(chunk_alloc(size, nobjs));
}
} //重新填充freelists
template <bool threads, int inst>
void* __default_alloc_template<threads, inst>::refill(size_t n)
{
//20个区块
int nobjs = 20;
//调用chunk_alloc(),尝试取nobjs个区块作为freelist的新节点
//nobjs为引用传递
char * chunk = chunk_alloc(n, nobjs);
obj * __VOLATILE * my_free_list;
obj * result;
obj * current_obj, * next_obj;
int i;
//若内存池只够分配1个区块,直接返回,freelist无新节点
if (1 == nobjs) return(chunk);
//否则,定位freelist,准备纳入新节点
my_free_list = free_list + FREELIST_INDEX(n);
//在chunk这段空间建立freelist
result = (obj *)chunk;
//略过第一个小区块
*my_free_list = next_obj = (obj *)(chunk + n);
//将freelist的各个节点串接起来
//从第一个开始,第0个返回给客户
for (i = 1; ; i++) {
current_obj = next_obj;
next_obj = (obj *)((char *)next_obj + n);
if (nobjs - 1 == i) {
//尾节点指针域为nullptr
current_obj -> free_list_link = 0;
break;
} else {
current_obj -> free_list_link = next_obj;
}
}
//串接完成并返回
return(result);
}
上一篇:Java 之继承和 final 关键字


下一篇:STL源码剖析——空间配置器Allocator#2 一/二级空间配置器