allocator是容器的空间分配器，负责对容器进行空间申请和释放。
allocator的必要接口
allocator::value_type
allocator::pointer
allocator::const_pointer
allocator::reference
allocator::const_reference
allocator::size_type
allocator::difference_type
allocator::rebind
allocator::allocator()
allocator::allocator(const allocator&)
template<class U> allocator::allocator(const allocator<U>&)
allocator::~allocator()
pointer allocator::address(reference x) const
const_pointer allocator::address(const_reference x) const
pointer allocator::allocate(size_type n, const void* = 0)
void allocator::deallocate(pointer p, size_type n)
size_type allocator::max_size() const
void allocator::construct(pointer p, const T& x)
void allocator::destory(pointer p)
设计一个简单的空间配置器
template<class T>
inline T* _allocate(ptrdiff_t size, T*){
set_new_handler(0);
T* tmp = (T*)(::operator new((size_t)(size * sizeof(T))));
if(tmp == 0){
cerr << "out of memory" << endl;
exit(1);
}
return tmp;
}
template<class T>
inline void _deallocate(T* buffer){
::operator delete(buffer);
}
template<class T1, class T2>
inline void _construct(T1* p, const T2& value){
new(p) T1(value);
}
template<class T>
inline void _destory(T* ptr){
ptr->~T();
}
template<class T>
class allocator {
public:
typedef T value_type;
typedef T* pointer;
typedef const T* const_pointer;
typedef T& reference;
typedef const T& const_reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type
template<class U>
struct rebind{
typedef allocator<U> other;
};
pointer allocate(size_type n, const void* hint=0){
return _allocate((difference_type)n, (pointer)0);
}
void deallocate(pointer p, size_type n) { _deallocate(p); }
void construct(pointer p, const T& value){
_construct(p, value);
}
void destory(pointer p) { _destory(p); }
pointer address(reference x) { return (pointer)&x; }
const_pointer const_address(const_reference x) { return (const_pointer)&x; }
size_type max_size() const {
return size_type(UINT_MAX/sizeof(T));
}
}
SGI空间配置器
SGI有标准的空间配置器，但是不用。因为效率不佳。SGI只使用自己特殊的空间配置器。
stl将allocator::allocate负责内存配置，allocator::construct负责对象构建；allocator::destory负责对象析构，allocator::deallocate负责内存释放。
memory —–> <stl_construct.h> 包含全局函数construct和destory
memory —–> <stl_alloc.h> 包含allocate和deallocate
memory —–> <stl_uninitialized.h> 用来进行填充或者复制数据到内存中
合理高效的为容器元素分配空间并初始化数据是allocate的重要作用。
construct和destory的实现
#include<new.h> //使用placement new，需要包含该文件。placement new是重载operator new的一个标准、全局的版本，它不能被自定义的版本代替。作用：创建对象(调用该类的构造函数)但是不分配内存,而是在已有的内存块上面创建对象。用于需要反复创建并删除的对象上,可以降低分配释放内存的性能消耗。
template<class T1, class T2>
inline void construct(T1 *P, const T2& value){
new(p) T1(value); //使用placement new函数，唤起对象的构造函数
}
template<class T>
inline void destory(T* pointer){
pointer->~T(); //调用元素的析构函数
}
template<class ForwardIterator>
inline void destory(ForwardIterator first, ForwardIterator last){
__destory(first, last, value_type(first)); //判断元素类型，以便进行高效操作
}
template<class ForwardIterator, class T>
inline void __destory(ForwardIterator first, ForwardIterator last, T*){
typedef typename __type_traits<T>::has_trivial_destructor trivial_destructor; //萃取出该类型的析构函数是否为trivial(可以理解为成员变量是否开辟了堆空间)
__destroy_aux(first, last, trivial_destructor());
}
template<class ForwardIterator>
inline void __destory_aux(ForwardIterator first, ForwardIterator last, __false_type){
for(; first < last; ++first){
destory(&*first);
}
}
template<class ForwardIterator>
inline void __destory_aux(ForwardIterator first, ForwardIterator last, __true_type) {}
SGI中的std::alloc
SGI设计了双层级配置器，第一级配置器直接使用malloc和free，第二级配置器则视情况采用不同的策略：当配置区块超过128bytes时，视为“足够大”，调用第一级配置器；当配置区块小于128byte时，为了降低额外负担（申请一块内存时，需要额外内存cookie来记录内存的大小），便采用memory pool整理方式，使用第二级配置器。
并且，SGI为自己的配置器封装了接口，使能够符合STL规格：
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 void deallocate(T* p, size_t n){
if(0 != n){
Alloc::deallocate(p, n * sizeof(T));
}
}
}
第一级配置器 __malloc_alloc_template剖析
#if 0
#include<new>
#define __THROW_BAD_ALLOC throw bad_alloc
#elif !defined(__THROW_BAD_ALLOC)
#include<iostream.h>
#define __THROW_BAD_ALLOC cerr<< "out of memory" <<endl; exit(1)
#endif
template<int inst> //这里的非类型参数没有用处
class __malloc_alloc_template{
private: //用来处理内存不足的情况
static void *oom_malloc(size_t);
static void *oom_realloc(void*, size_t);
static void (* __malloc_alloc_oom_handler)(); //static void* __malloc_alloc_oom_handler();
public:
static void* allocate(size_t n){
void * result = malloc(n); //直接使用malloc
if(0 == result){
result = oom_malloc(n);
}
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，先判断当前的指针是否有足够的连续空间，如果有，扩大mem_address指向的地址，并且将mem_address返回，如果空间不够，先按照newsize指定的大小分配空间，将原有数据从头到尾拷贝到新分配的内存区域，而后释放原来mem_address所指内存区域（注意：原来指针是自动释放，不需要使用free），同时返回新分配的内存区域的首地址。即重新分配存储器块的地址
if(0 == result){
result = oom_realloc(p, new_sz);
}
return result;
}
static void (* set_malloc_handler(void (*f)()))() { //接受客户自定义的handler,返回值为函数指针
void (*old)() = __malloc_alloc_oom_handler;
__malloc_alloc_oom_handler = f;
return(old);
}
template<int inst>
static void (* __malloc_alloc_template<inst>::__malloc_alloc_oom_handler)() = 0;
template<int inst>
static void* __malloc_alloc_template<inst>::oom_malloc(size_t){
void (*my_malloc_handler)();
void *result;
for(;;){ //不断尝试，直至分配成功
my_malloc_handler = __malloc_alloc_oom_handler;
if(0 == my_alloc_handler) { //若客户没有定义的handler，那么便给系统抛出错误
__THROW_BAD_ALLOC;
}
(*my_malloc_handler)(); //客户定义了handler，便运行
result = malloc(n); //handler处理之后，尝试再次分配内存
if(result){
return result;
}
}
}
template<int inst>
static void* __malloc_alloc_template<inst>::oom_realloc(void*, size_t){
void (*my_malloc_handler)();
void *result;
for(;;){
my_malloc_handler = __malloc_alloc_oom_handler;
if(0 == my_alloc_handler) { //若客户没有定义的handler，那么便给系统抛出错误
__THROW_BAD_ALLOC;
}
(*my_malloc_handler)(); //客户定义了handler，便运行
result = realloc(n); //handler处理之后，尝试再次分配内存
if(result){
return result;
}
}
}
};
第二级配置器 __default_alloc_template 剖析
避免太多小区块造成内存的碎片，但是更重要的是每次为元素申请内存时，都会有cookie记录内存大小。如果多次申请小区块，那么就会导致cookie的消耗极大。
为了方便管理，SGI配置器会主动将任何小额区块的内存需求量上调至8的倍数，因为配置器维护了16个free-list，各自管理大小8，….128byte的小额区块。free-list的节点结构如下：
union obj {
union obj* free_list_link;
char cleint_data[1]; //使用union减少内存的使用
}；
配置器的实现
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));
}
private:
union obj {
union obj* free_list_link;
char cleint_data[1];
};
private:
static obj* volatile free_list[__NFRESSLISTS]; //创建__NFRESSLISTS个free_list
static size_t FREELIST_INDEX(size_t bytes){ //根据元素类型的大小确定在那个list中
return (((bytes) + __ALIGN - 1) / __ALIGN - 1);
}
static void* refill(size_t n) { //申请内存的中介
int nobjs = 20;
char *chunk = chunk_alloc(n, nobjs); //找到内存池给该free_list分配空间
obj* volatile * 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); //有多个区块申请成功，加到free_list上
result = (obj*)chunk;
}
static char* chunk_alloc(size_t size, int &nobjs); //配置一大块空间，可容纳nobjs个大小为size的区块
static char* start_free; //内存池起始位置
static char* end_free; //内存池结束位置
static size_t heap_size; //内存池的大小
public:
static void* allocate(size_t n){
obj* volatile * my_free_list;
obj* result;
if(n > (size_t) __MAX_BYTES){
return (malloc_alloc::allocate(n));
}
my_free_list = free_list + FREELIST_INDEX(n); //定位到该尺寸的free_list,拿到“头指针”
result = *my_free_list;
if(result == 0){ //free_list还未初始化或者已经没有多余的内存
void* r = refill(ROUND_UP(N)); //找refill申请内存
return r;
}
*my_free_list = result->free_list_link;
return result;
}
static void deallocate(void* p, size_t n){
obj* q = (obj*)p;
obj* volatile * my_free_list;
obj* result;
if(n > (size_t) __MAX_BYTES){
malloc_alloc::deallocate(p, n);
return;
}
my_free_list = free_list + FREELIST_INDEX(n); //定位到该尺寸的free_list,拿到“头指针”
q->free_list_link = *my_free_list;
*my_free_list = q;
}
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};
chunk_alloc
template<bool threads, int inst>
char* __default_alloc_template<threads, inst>::chunk_alloc(size_t size, int& nobjs){ //nobjs是引用类型，可以告诉refill分配了多少个区块
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;
}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); //直接申请2倍客户端需要的内存
if(bytes_left > 0){ //把内存池中剩余的容量放在合适的free_list中
obj* volatile * 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* volatile* my_free_list, *p;
for(i = size; i <= __MAX_BYTES; i += __ALIGN){ //在原有的free_lists上找到比申请free_list区块大的free_list,如果这些free_list中有空间，可以借过来
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);
}
}
- free_lists是一个包含了16个free_list链表头指针的数组。
- 每一个free_list是一个有自己区块尺寸规格的链表，并且每个链表是使用头插法进行区块增加的。取出区块也是在头部。不包含没有数据的头节点，头指针直接指向第一个区块。
- free_lists初始化都为空，也就是说每个free_list都是空。
内存基本处理工具
- construct
- destory
- uninitialized_copy
- uninitialized_fill
- uninitialized_fill_n
后面三个函数可以使内存配置和对象的构造行为分离开。它们会调用construct来copy对象到相应迭代器所在的内存空间中。