STL源码剖析——内存配置器alloc
|
|
|
虽然STL的内存配置器在我们的实际应用中几乎不用涉及，但它却在STL的各种容器背后默默做了大量的工作，STL内存配置器为容器分配并管理内存。统一 的内存管理使得STL库的可用性、可移植行、以及效率都有了很大的提升，因此STL内存配置器是STL库中最重要的组成部分之一。
1、Constructor和Destroy
我们所习惯的C++内存空间分配动作如下：
delete操作符的动作也可以分为两部分：1. 调用对象的析构函数 (alloc::destroy 函数)；2. 释放对象占用的内存空间(alloc::deallocate 函数)
在STL库的空间配置器中，new和delete的这两个过程都是分开的，这还要归功于C++语言的placement new操作符（具体请参考C++Primer）。
construct源码
两个问题：
1. C++并不支持通过value_type来判断指针所指对象的类型，STL中通过什么来判断？
2. C++也不支持判断一个对象是否存在析构函数，STL如何来实现判断？
第一个问题参考头文件<stl_iterator.h>
第二个问题请参看文章：《神奇的__type_traits》
2、空间的分配与释放
SGI使用双 层配置器，如果分配的空间大于128bytes则采用第一级配置器，直接调用malloc(),free()；如果分配的空间小于128bytes则采用 复杂一点的memory pool方式。在SGI中一级配置器的实现依靠的是模板类__malloc_alloc_template，二级配置器依靠模板类 __default_alloc_template SGI STL中的几种配置器 1、__malloc_alloc_template是一个基础配置器，直接调用malloc和free来分配和释放空间，如果空间不够会调用handler处理过后再重新分配。__malloc_alloc_template配置器被作为一级配置器来使用。
template <int inst>
class __malloc_alloc_template {
private:
static void *oom_malloc(size_t);
// out of memory的情况下会调用此函数分配
static void *oom_realloc(void *,
size_t); // out of memory的情况下会调用此函数重新分配
static void (* __malloc_alloc_oom_handler)();
// out of memory情况下会如果这个handler存在就会被调用
public:
static void * allocate(size_t n)
{
void *result = malloc(n);
// 调用 普通的malloc函数直接分配
if (0 == result) result = oom_malloc(n);
// 如果分配失败才调用oom_malloc
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函数重新分配
if (0 == result) result = oom_realloc(p, new_sz);
// 如果失败就调用oom_realloc函数重新分配
return result;
}
static void (* set_malloc_handler(void (*f)()))()
// 为out of memory的情况设置handler
{
void (* old)() = __malloc_alloc_oom_handler;
__malloc_alloc_oom_handler = f;
return(old);
}
};
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)(); // 如果存在handler就先调用handler回收能够回收的内存
result = malloc(n); // 然后再尝试malloc
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)(); // 如果存在handler就先调用handler回收能够回收的内存
result = realloc(p, n); // 然后再尝试realloc
if (result) return(result);
}
}
typedef __malloc_alloc_template<0> malloc_alloc;
// STL的一级内存配置器
2.、__default_alloc_template也是一个基础配置器，和__malloc_alloc_template相比多了一下几个功能：
A. 多线程的支持，包括资源的加锁解锁
B. 分配空间的大小按8字节对齐
C. 如果分配的空间大于128字节，直接调用一级配置器的malloc_alloc::alloc函数来分配
D. 维护了16个自由空间的链表（free list），每个链表都链接了一串相等大小的自由空间，各个链表节点的自由空间大小不同，但都是8的倍数（8、16、24......96、104、112、120、128刚好16级）
E. 如果分配的空间小于128字节，找到一个链表，使得该链表节点的自由空间大小大于请求分配的空间而又与之大小最接近，从该链表中取出一个节点分配
F. 维护了一个memory pool，如果所有自由空间列表为空就会从记忆池中申请空间，记忆池尽量返回可用的空间。
__default_alloc_template 通常被作为二级配置器来使用，由于该类的代码非常繁杂，这里就不列出来了。有兴趣可以阅读STL的源代码。
|