STL-空间配置器(allocator)
STL的空间配置器作为STL六大部件的重要组成部分,它总是隐藏在一切组件的背后.它主要负责动态空间的分配、释放等管理工作。整个STL的操作对象(所有的数值)都存放在容器之内,而容器一定需要配置空间以置放资料。而这就是空间配置器(allocator)的职责了.
一.SGI的空间配置器—std::alloc
STL allocator将内存分配/释放和对象构造/析构区分开来.内存配置操作由alloc::allocate()负责,内存释放由alloc::deallocate()负责;对象构造操作由::construct()负责,对象析构操作由::destroy()负责.
STL标准表格告诉我们,配置器定义于<memory>中,SGI<memory>内含两个文件:
#include <stl_alloc.h> //负责内存空间的配置与释放
#include <stl_construct.h> //负责对象内容的构造与析构
1.构造和析构基本工具:construct()和destroy()
#include <new.h> //欲使用placement new,需先包含此文件 template<class T1,class T2>
inline void construct(T1* p,const T2& value){
new (p) T1(value); //placement new;调用T1::T1(value);
} //以下是destroy()第一版本,接受一个指针
template<class T>
inline void destroy(T* pointer){
pointer->~T();//调用dtor ~T()
} 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_trait<T>::has_trivial_destructor trivial_destructor;
__destroy_aux(first,last,trivial_destructor());
} //如果元素的数值型别(value_type)有non-trivial destructor
template <class ForwardIterator>
inline void __destroy_aux(ForwardIterator first,ForwardIterator last,__false_type){
for(;first<last;first++) destroy(&*first);
} template <class ForwardIterator>
inline void __destroy_aux(ForwardIterator first,ForwardIterator last,__true_type){} inline void destroy(char*,char*){}
inline void destroy(wchar_t*,wchar_t*){}
2.空间的配置与释放
SGI是以malloc()和free()完成内存的配置与释放.考虑到小型区块所可能造成的内存破碎问题,SGI设计了双层级配置器。第一级配置器直接使用malloc()和free(),第二级配置器则视情况采用不同的策略:当配置区块超过128bytes时,视之为"足够大",便调用第一级配置器;当配置区块小于128bytes时,视之为"过小",为了降低额外负担,便采用memory pool整理方式,而不再求助于第一级配置器。
无论alloc被定义为第一级或第二级配置器,SGI还为它再包装了一个接口,使配置器的接口更符合STL规格。
template <class T,class Alloc>
class simple_alloc{
public:
static T* allocate(size_t n){
return ==n?:(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(n!=) Alloc::deallocate(p,n*sizeof(T));
} static void deallocate(T* p){
Alloc::deallocate(p,sizeof(T));
}
};
其内部四个成员函数其实都是单纯的转调用,调用传递给配置器(可能是第一级也可能是第二级)的成员函数。SGI STL容器全部都是使用这个simple_alloc接口。
2.1 第一级配置器 __malloc_alloc_template剖析
//注意,无"template型别参数",inst完全没有派上用场
template<int inst>
class __malloc_alloc_template{
private:
//以下都是函数指针,所代表的函数将用来处理内存不足的情况
//oom:out of memory
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);
if(==result) result=oom_malloc(n);
return result;
} static void deallocate(void* p,size_t /*n*/){
free(p);
} static void* reallocate(void* p,size_t old_sz,size_t new_sz){
void* result=realloc(p,new_sz);
if(==result) oom_realloc(p,new_sz);
return result;
} //以下仿真C++的set_new_handler()
static void (*set_malloc_handler(void (*f)()))(){
void (*old)()=__malloc_alloc_oom_handler;
__malloc_alloc_oom_handler=f;
return (old);
}
}; void (*__malloc_alloc_template<int>::__malloc_alloc_oom_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_oom_handler;
if(==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(size_t n){
void (*my_malloc_handler)();
void* result; for(;;){ //不断尝试释放、分配、释放、分配...
my_malloc_handler=_malloc_alloc_oom_handler;
if(==my_malloc_handler) {__THROW_BAD_ALLOC;}
(*my_malloc_handler)();//调用处理例程,企图释放内存
result=realloc(p,n); //再次尝试分配内存
if(result) return (result);
}
}
所谓c++ new handler机制是,当系统在内存配置需求无法被满足时,调用一个你指定的函数。也就是说,一旦::operator new无法完成任务,在丢出std::bad_alloc异常状态时,会先调用用户所指定的例程。
2.1 第二级配置器 __default_alloc_template剖析
SGI第二级配置器的做法是,如果区块足够大,超过128bytes时,就移交第一级配置器处理。当区块小于128bytes时,则以内存池(memory pool)管理:每次配置一大块内存,并维护对应之自由链表(free-list)。下次若再有相同大小的内存需求,就直接从free-list中取出。如果客户端释还小额区块,就由配置器回收到free-list中。为了方便管理,SGI第二级配置器会主动将任何小额区块的内存需求量上调至8的倍数,并维护16个free-list,各自管理大小分别为8,16,24,32,40,48,56,64,72,80,88,96,104,112,120,128bytes的区块。
//free-lists的节点结构如下:
union obj{
union obj* free_list_link;
char client_data[]; //The client sees this
};
第二级配置器的部分源码:
//free-lists的节点结构如下:
union obj{
union obj* free_list_link;
char client_data[]; //The client sees this
}; enum {__ALIGN=};//小型区块的上调边界
enum {__MAX_BYTES=}; //小型区块的上限
enum {__NFREELISTS=__MAX_BYTES/__ALIGN}; //free-lists的个数 //以下是第二级配置器
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-) & ~(__ALIGN-));
} private:
union obj{ //free-lists的节点构造
union obj* free_list_link;
char client_data[];
}; private:
//16个free-lists
static obj* volatile free_list[__NFREELISTS];
//以下函数根据区块大小,决定使用第n号free-lists.n从1开始
static size_t FREELIST_INDEX(size_t bytes){
return ((bytes)+__ALIGN-)/__ALIGN-);
} //返回一个大小为n的对象,并可能加入大小为n的其他区块到free list
static void* refill(size_t n);
//配置一大块空间,可容纳nobjs个大小为"size"的区块
static char* chunk_alloc(size_t size,int &nobjs); //chunk allocation state
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);
}; //以下是static data memeber的定义与处置设定
template <bool threads,int inst>
char* __default_alloc_template<threads,inst>::start_free=; template <bool threads,int inst>
char* __default_alloc_template<threads,inst>::end_free=; template <bool threads,int inst>
size_t __default_alloc_template<threads,inst>::heap_size=;
最新文章
- IT技术风向标
- CodeIgniter 3 源码学习笔记《一》
- BestCoder Round #87 1002 Square Distance[DP 打印方案]
- 如何查看文件是dos格式还是unix格式的?
- android开发中遇到的各种问题收集--不定期更新
- [转贴]从零开始学C++之STL(二):实现一个简单容器模板类Vec(模仿VC6.0 中 vector 的实现、vector 的容量capacity 增长问题)
- javascript社交平台分享-新浪微博、QQ微博、QQ好友、QQ空间、人人网
- Windows平台的JDK安装(转)
- 【Xamarin 开发 IOS --IOS 页面导航概念Segue】
- AspNetPager常用属性及一些样式
- 老李案例分享:Weblogic性能优化案例
- cookie创建,删除
- awk匹配某一段内容,打印第一段
- [LeetCode] Implement Magic Dictionary 实现神奇字典
- SQL 2012 Always On 为 MSCRMSqlClrLogin SQL 登录名创建非对称密钥时报语法错误
- hyperopt自动调参
- hue报错StructuredException: timed out (code THRIFTSOCKET): None的处理
- Ext.js入门:Window对象与FormPanel(六)
- sysctl.conf文件详解
- VMware Workstation 虚拟机的服务启动项