stl_空间配置器

空间配置器

空间配置器: 用来分配内存。它并不会给我们直接使用，而是在容器之后默默工作。

在c++中，一般使用new
在c++中，一般使用new来来分配内存，同时并调用构造函数来完成值得初始化，但在stl中，这两步是分开的
首先有空间配置器来分配内存，然后调用construct函数来完成在指定内存完成值得初始化。
构造可以调用place new 来在指定的内存空间来声明对象，和初始化值。但是毕竟类才需要调用构造，
有的对象并不需要使用构造函数。使用简单的内存拷贝就能达到目的。

sgi中使用的默认的空间配置器是alloc。 alloc有两种不同的方式来分配内存。当所申请的空间大于128B的时候
直接调用c语言中的malloc来来申请内存, free来释放内存，而小于128B的空间，就在内存池中分配。

空间配置器标准接口

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::allocator(const allocator<U>&)
allocator::~allocator()   //析构
pointer allocator::address(reference x) const  //返回某个对象的地址
pointer allocator::allocate(size_type n, const void* = 0) //配置空间，足以存储n个T对象
void allocator::deallocate(pointer p, size_type n)  //归还先前配置的空间
size_type allocator::max_size() const     //返回可以配置的最大值
void allocator::construct(pointer p, const T&x)  //相当于new((void *) p) T(x)
void allocator::destroy(pointer p)       //相当于p->~T()

sgi中的空间配置器

sgi中使用alloc作为默认的空间配置器，但是该配置器并不真正符合标准接口。但是sgi中是默认使用alloc的
在sgi中:
stl_construct.h 定义了construct()和destroy()
stl_alloc.h 定义了一二级空间配置器，名为alloc
stl_uninitialized.h 定义了一些全局函数用来填充或者复制内存数据。
stl_initialized_copy
stl_initialized_fill()
stl_initialized_fill_n()

construct()和destroy()

template <class T1, class T2>
inline void construct(T1* p, const T2& value) {
    new (p) T1(value);
}


//第一种版本，接受一个对象指针，直接调用对象的析构
template <class T>
inline void destroy(T *pointer) {
    pointer->~T();
}

//第二个版本, 接受两个迭代器，通过萃取，来判定迭代器指向的对象是否需要调用析构函数
//所以分别是__true_type 和__false_type 两个版本。
template <class ForwardIterator>
inline void destroy(ForwardIterator first, ForwardIterator last) {
    __destroy(first, last, value_type(first));
}

template <class ForwardIterator, class T>
inline void __destroy(ForwardIterator first, ForwardIterator last, T *) {
    typedef typename __type_traits<T>::has_trival_destructor trivial_destructor;
    __destroy_aux(first, last, trivial_destructor());
}

template <class ForwardIterator>
inline void __destroy_aux(ForwardIterator, ForwardIterator, __true_type) {}

template <class ForwardIterator>
inline void __destroy_aux(ForwardIterator, ForwardIterator, __false_type) {
    for ( ; first < last; ++first)
        destroy(&*first);
}

一级空间配置器

一级空间配置器
__malloc_alloc_template
一级空间配置器直接使用了c中的malloc() free() realloc()

template <int inst>
class __malloc_alloc_template {

public:
static void * allocate(size_t n)
{
    void *result = malloc(n);
    if (0 == result) result = oom_malloc(n);
    return result;
}

static void deallocate(void *p, size_t)
{
    free(p);
}
static void *reallocate(void *p, size_t , size_t new_sz)
{
    void *result = realloc(p, new_sz);
    if (0 == result) result = oom_realoc(p, new_sz);
    return result;
}

static void (* set_malloc_handler(void (*f)()))()
{
    void (* old)() = __malloc_alloc_oom_handler;
    __malloc_alloc_oom_handler =f;
    return (old)
}
private:

static void *oom_malloc(size_t);

static void *oom_realloc(void *, size_t);
};

二级空间配置器

__default_alloc_template
二级空间配置器采用的是内存池的方式。
先自动将申请的空间拓展到8的倍数。
二级空间配置器8， 16， 24， 32， 40， 48， 56， 64， 72， 80， 88， 96， 104， 112， 120， 128

class __default_alloc_template {

private:
    enum {__ALIGN = 8};
    enum {__MAX_BYTES = 128};
    enum {__NFREELISTS = __MAX_BYTES/__ALIGN};

    static size_t ROUND_UP(size_t bytes) {        //将实际申请的空间上调至8的倍数
        return (((bytes) + __ALIGN - 1) & ~(__ALIGN - 1));
    }
__PRIVATE:
    union obj {
        union obj * free_list_link;     //采用共用体，当空闲的时候使用obj
        char client_data[1];            //使用的时候使用client_data
    };
private:
    static obj * __VOLATILE free_list[_NFREELISTS];
    static size_t FREELIST_INDEX(size_t bytes) {    //根据内存大小来判定所属于哪一条空闲链
        return (((bytes) + _ALIGN - 1) / __ALIGN - 1);
    }
    static void *refill(size_t n);  //当某一条空闲链为空，就再申请一片
    static char *chunk_alloc(size_ t size, int &nobjs);
    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);
};

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>
char *__default_alloc_template<threads, inst>::heap_size = 0;

allocate

static void * allocate(size_t n){

    obj * volatile * my_free_list;
    obj * result;
    if (n > (size_t) __MAX_BYTES) {
        return (malloc_alloc::allocate(n));  //当申请大小大于128就调用一级空间配置器
    }
    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));
    }
    //挂链，调整free list
    *my_free_list = result->free_list_link;
    return (result);
}

deallocate

static deallocate(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);
    q->free_list_link = *my_free_list; //头插,挂链
    *my_free_list = q;
    return 0;
}

refill函数

template <bool threads, int inst>
void * __default_alloc_template<threads, inst>::refill(size_t n)
{
     int nobjs = 20;
     //chunk_alloc从内存池中申请内存。
     char * chunk = chunk_alloc(n, nobjs);
     obj *volatile *my_free_list;
     obj *result;
     obj *current_obj, *next_obj;

     //如果只获得一个区块，这个却快就分配给调用者用，free_list无新节点
     if (1 == nobjs) return (chunk);
     //否则调整free_list,插入新的节点
     my_free_list = free_list + FREELIST_INDEX(n);

     result = (obj *)chunk; //这一块准备返回给客户端
     *my_free_list = next_obj = (obj *)(chunk + n);
     //将剩下的所有节点挂链
     for (i = 1; ; i++) {
         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);
}

内存池管理

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) {
        //内存池中剩余的内存能够分配nobjs个节点
        result = start_free;
        start_free += total_bytes;
        return (result);
    } else if (bytes_left >= size) {
        //内存池中的剩余空间不能分配所有，但是能够分配一个以上
        nobjs = bytes_left / size;
        total_bytes = size * nobjs;
        result = start_size;
        start_free += total_bytes;
        return (result);
    } else {
        //内存池中的内存不够分配一个
        //计算接下来要分配的空间大小 需求的两倍加上
        size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);
        if (bytes_left > 0) {
           //把剩下的零头分配给合适的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)
    }
}

内存基本处理工具

uninitialized_copy

将first和last之间的元素拷贝到result开始的空间。

template <class InputIterator, class ForwardIterator>
ForwardIteratoruninitialized_copy(InputIterator first, InputIterator last,                   ForwardIterator result) {
uninitialized_copy(InputIterator first, InputIterator last,                   ForwardIterator result)
                   ForwardIterator result)
 
     typedef typename __type_traits<T>::is_POD_type is_POD;
     return __uninitialized_copy_aux(first, last, result, is_POD());
 }
template <class InputIterator, class ForwardIterator>
__uninitialized_copy_aux(InputIterator first, InputIterator last,
                       ForwardIterator result,
                       __true_type) {
    copy(first, last, result);
}
template <class InputIterator, class ForwardIterator>
__uninitialized_copy_aux(InputIterator first, InputIterator last,
                       ForwardIterator result,
                       __false_type) {
   for (; first != last; ++first, ++cur)
       construct(&*cur, *first);
   return cur;
}

当迭代器所指向的对象为true_type 就直接调用函数来进行拷贝，否则需要对每个元素进行构造

uninitialized_fill

将first到last之间的元素以x来初始化
通过萃取出迭代器所指向元素的值得类型来作出不同的操作
true_type直接调用函数fill，false_type需要分别调用每个的构造函数
同时对char和wchar_t 类型分别生成特别的版本

template <class ForwardIterator, class T>
void uninitialized_fill(ForwardIterator first, ForwardIterator last,                        const T& x){
                        const T& x)

    __unitialalized_fill(first, last, x, value_type(first));
}
template <class ForwardIterator, class T, class T1>
inline void uninitialized_fill(ForwardIterator first, ForwardIterator last,                              const T& x, T1*) {
                              const T& x, T1*)
    typedef typename __type_traits<T1>::is_POD_type is_POD();
    __uninitialized_fill_aux(first, last, x, is_POD());
}
template <class ForwardIterator, class T>
inline void
__uninitialized_fill_aux(ForwardIterator first, ForwardIterator last,
                         const T&x, __true_type)
{
    fill(first, last, x);
}
template <class ForwardIterator, class T>
void
__uninitialized_fill_aux(ForwardIterator first, ForwardIterator last,
                         const T& x, __false_type)
{
    ForwardIterator cur = first;
    for (; cur != last; ++cur)
        construct(&*cur, x);
}
//针对char 和wchar_t的特化版本，直接调用memmove函数
inline char* uninitialized_copy(const char *first, const char* last,                                char * result) {
                                char * result)
    memmove(result, first, last - first);
    return result + (last - first);
}
inline wchar_t* uninitialized_copy(const wchar_t *first, const wchar_t *last,                                   wchar_t* result) {
                                   wchar_t* result)
    memmove(result, first, sizeof(wchar_t) * (last - first));
    return result + (last - first);
}

uninitialized_fill_n

该函数的作用:
将迭代器first之后n个单元初始化为x。
通过萃取出迭代器所指向元素的值得类型来作出不同的操作。

template <class ForwardIterator, class Size, class T>
ForwardIteratoruninitialized_fill_n(ForwardIterator first, Size n, const T &x){
uninitialized_fill_n(ForwardIterator first, Size n, const T &x)

    return __uninitialized_fill_n(first, n, x, value_type(first));
}
template <class ForwardIterator, class Size, class T>
inline ForwardIterator __unitiallized_fill_n(ForwardIterator first, Size n,
                                             const T& x, T1 *)
{
    typedef typename __type_traits<T1>::is_POD_type is_POD;
    return __uninitialized_fill_n_aux(first, n, x, is_POD());
}
template <class ForwardIterator, class Size, class T>
inline ForwardIterator
__unitialized_fill_n_aux(ForwardIterator first, Size n,
                        const T& x, __true_type) {
    return fill_n(first, n, x);
}
template <class ForwardIterator, class Size, class T>
inline ForwardIterator
__unitialized_fill_n_aux(ForwardIterator first, Size n,
                         const T& x, __false_type) {
    for ( ; n > 0; --n, ++cur)
        construct(&*cur, x);
    return cur;
}