STL源码剖析 空间配置器 查漏补缺

• SGI STL 使用了专属的 拥有层级配置的 特殊的空间配置器
• SGI STL 提供了 一个标准的空间配置器的接口 叫做 simple_alloc

• 使用的时候 std::vectoriv；std::alloc 采用默认的形式
• 为了精密分工，STL a llo c a to r决定将这两阶段操作区分开来。内存配置操作 由 alloc： al locate ()负责，内存释放操作由alloc : : deallocate ()负责；对象构造操作由：：construct:()负责，对象析构操作由：；destroy负责

• new算式内含两阶段操作： (1 )调 用 ::operator new配置内存; ⑵ 调 用Foo：：Foo()构造对象内容。
• delete算式也内含两阶段操作：(1)调用Foo:~Foo ()将对象析构；(2 ) 调 用 ::operator delete释放内存。

• c++11——type_traits 类型萃取 - 农民伯伯-Coding - 博客园
• C++ STL __type_traits解析 - 知乎

#include         //for placement new
#include     //for ptrdiff_t size_t
#include     //for exit
#include     //for UINT_MAX
#include    //for cerr
#include 

using namespace std;
template
struct __type_traits {
    typedef __true_type this_dummy_member_must_be_first;
    typedef __false_type has_trivial_default_constructor;
    typedef __false_type has_trivial_copy_constructor;
    typedef __false_type has_trivial_assignment_constructor;
    typedef __false_type has_trivial_destructor;
    typedef __false_type is_POD_type;
};

template
inline void _construct(T1 *p,const T2& value){
    new(p) T1 (value);  //placement new; 调用T1::T1(value)
}


//以下是 destroy() 第一版本 接收一个指针
template 
inline void _destroy(T* ptr){
    ptr->~T(); //调用 ~T()
}


//如果元素的型别(value_type)有non_trivial destructor
template 
inline void __destroy_aux(ForwardIterator first,ForwardIterator last,
                          std::__false_type){
    for( ; first < last;++first){
        destroy(&*first); //调用destroy的第一个版本
    }
}
//如果元素的型别(value_type)有trivial destructor
template 
inline void __destroy_aux(ForwardIterator,ForwardIterator,std::true_type){}

//判断元素的型别(value type) 是否有 trivial destructor
template 
inline void __destroy(ForwardIterator first,ForwardIterator last,T*){
    typedef typename __type_traits::has_trivial_destructor trivial_destructor;
    __destroy_aux(first,last,trivial_destructor());
}

//destroy()第二版本 接收两个迭代器 这个函数设法找出元素的型别
//进而使用 __Type_traits<> 求取适当的措施
template 
inline void destroy(ForwardIterator first,ForwardIterator last){
//    __destroy()
}



inline void destroy(char*,char*){}
inline void destroy(wchar_t *,wchar_t *){}

•  第二版本的接受first和last两个迭代器 准备将[first，last)范围内的元素都析构掉，但是如果这段范围很大，对于每一个元素的析构 都 无关痛痒(即 trivial destructor类型的)，对于效率是一种损失。
• 因此 需要进行偏特化的操作，在执行析构函数之前进行类型的判断。如果是 true_type 什么都不做直接结束，如果是false_type的类型，使用循环的方式，针对每个元素使用 第一个版本的destroy()函数进行析构释放
• 问题：如何实现上述的 value_type() 和 __type_traits<> ？？

• 对象构造之前的空间配置和对象析构之后的空间的释放 由 负责

设计思路

• 向系统的heap 申请内存空间
• 考虑 多线程状态
• 考虑内存不足的应对措施
• 考虑小型区块可能造成的内存碎片问题
• 代码举例 排除了 多线程的处理

设计思想

• 考虑到小型区块造成的内存破碎问题，SGI设计了双层级配置器，第一层级使用malloc()和free(),第二层级视情况 采用不同的策略。
• 当配置的区块超过128bytes时 视为足够大 使用第一层级配置器
• 当配置的区块小于128bytes时 为了降低额外的负担，使用memory pool的方式
• alloc并不接受任何 template型别的参数
• 无论alloc使用的是第一级或者第二级配置器 都需要外包一层接口

#ifdef __USE_MALLOC
typedef __malloc_alloc_template<0>malloc_alloc;
typedef malloc_alloc alloc;  //令alloc为第一级配置器

//令alloc为第二级配置器
typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS,0>alloc;

#endif

template
class simple_alloc{
public:
    static T* allocate(std::size_t n){
        return 0==n?0:(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!=0){
            Alloc::deallocate(p,n * sizeof(T));
        }
    }
    static void deallocate(T* p){
        Alloc::deallocate(p,sizeof(T));
    }
};

• 内部的四个函数本质上是 单纯的转接调用的关系 调用传递给配置器的(可能是第一级别 也可能是 第二级别)
• SGI STL容器都使用 这个simple_alloc的接口

template 
class vector{
protected:
    //专属空间配置器 每次分配一个元素的大小
    typedef simple_alloc data_allocator;
    
    void deallocate(){
        if(){
            data_allocator::deallocate(start,end_of_storage - start);
        }
    }
};

#if 0
#   include
#   define __THROW_BAD_ALLOC throw bad_alloc
#elif !defined(__THROW_BAD_ALLOC)
#   include
#   define __THROW_BAD_ALLOC std::cerr << "out of memory" << std::endl; exit(1);
#endif

//malloc-based allocator 通常比稍后介绍的default alloc要慢
//但是它是线程安全的 thread-safe，并对于空间的运用比较高效
//以下是第一级别配置器
//无“template 型别参数” 至于非型别参数 inst 完全没有用到
template 
class __malloc_alloc_template{
private:
    //以下内容都是函数指针，所代表的函数用于处理内存不足的情况
    //oom : out of memory
    static void *oom_malloc(std::size_t);
    static void *oom_realloc(void*,std::size_t);
    static void (* __malloc_alloc_oom_handler)();
public:
    static void* allocate(std::size_t n){
        void * result = malloc(n);//第一级配置器 直接使用malloc进行内存的分配
        //当无法满足内存分配的需求的时候，使用oom_malloc()
        if(result == 0){
            result = oom_malloc(n);
        }
        return result;
    }

    static void deallocate(void* p,size_t ){
        free(p); //第一级配置器 直接使用 free()进行释放
    }

    static void* reallocate(void* p,size_t ,size_t new_size){
        void *result = realloc(p,new_size); //第一级别配置器直接使用realloc()
        //以下无法满足需求的时候 改用oom_realloc()
        if (0==result){
            result = oom_realloc(p,new_size);
        }
        return result;
    }
    //以下是仿真C++的set_new_handler(),换句话说 你可以通过他指定自己的out_of_handler
    static void(*set_malloc_handler(void (*f)()))(){
        void (* old)() = __malloc_alloc_oom_handler;
        __malloc_alloc_oom_handler = f;
        return (old);
    }

};
//malloc_alloc out_of_memory handling
//初始化为0
template 
void (* __malloc_alloc_template::__malloc_alloc_oom_handler)() = 0;

template 
void* __malloc_alloc_template::oom_malloc(std::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 
void *__malloc_alloc_template::oom_realloc(void *p, std::size_t n) {
    void (* my_malloc_handler)() = __malloc_alloc_oom_handler;
    void * result;
    if(0 == my_malloc_handler){
        __THROW_BAD_ALLOC;
    }
    (*my_malloc_handler)();//调用处理例程，企图释放内存
    result = realloc(p,n);//再次尝试配置内存
    if (result){
        return result;
    }
}

//以下直接将参数 inst 指定为0
typedef __malloc_alloc_template<0>malloc_alloc;

•  第一级配置器 使用malloc、free、realloc等C函数执行内存的配置、释放、重新配置，并实现了类似C++ newhandler的机制 ，但是不能直接使用C++的new handler的机制 因为他并没有使用 ::operator new的方式来配置内存
• C++ 的new handler的机制是 要求系统在内存配置需求无法被满足的时候 调用一个用户自定义的函数 即 ::operator new无法完成任务 抛出std::bad_alloc异常状态之前 先调用客户指定的处理例程 。这个处理的例程 被称作new handler
• 第一级配置器  allocate（）和 reallocate（）都会在调用malloc 和 realloc不成功之后 改用 oom_malloc 和 oom_realloc 后者函数内设定一个循环，不断调用 内存不足处理的程序  ，期望某一次可以得到足够的内存。如果未指定例程 便会调用 __THROW_BAD_ALLOC 抛出bad_alloc异常信息，或者使用 exit(1) 终止程序

• 第二级配置器 使用机制 避免造成内存的碎片 
• 额外负担 无法避免 涉及到操作系统的内存管理；但是区块越小，显现的 额外的负担的比例就会越来越大，就会显得浪费

•  大于128转交第一级配置器，小于128使用内存池管理。
• 次层配置：每次配置大内存，维护对应的自由链表，下次若有相同大小的内存需求，直接从自由链表中拨出
• 配置器 负责内存的释放和回收 
• 第二级配置器的小额区块的内存空间是以8的倍数进行划分，划分的时候 会自动将需求量上调至8的倍数
• 维护16个free_lists 各自管理 8 16 24 32 40 48 56 64 72 80 88 96 104 112 120 128

union obj{
    union obj * free_list_link;
    char client_data[1];// The client sees this
};

• 维护链表是需要 额外的指针 造成额外的负担
• 考虑到 obj 使用的是union，可以视为一个指针 指向相同类型的另外一个obj ； obj也可以视为一个指针 指向实际的区块  一物二用

enum {__ALIGN = 8}; //小型区块的上调边界
enum {__MAX_BYTES = 128};//小型区块的上限
enum {__NFREELISTS = __MAX_BYTES/__ALIGN};//free-lists的个数

using namespace std;
//以下是第二级配置器
//注意：无 template型别参数 且第二参数哇怒气按没有被派上用场
//第一参数用于多线程的环境 本示例 暂未涉及
template 
class __default_alloc_template{
private:
    //ROUND_UP() 将bytes上调至8的倍数
    static size_t ROUND_UP(size_t bytes){
        return (((bytes) + __ALIGN - 1) & ~(__ALIGN-1));
    }

private:
    union obj{    //free-lists 节点构造
        union obj * free_list_link;
        char client_data[1];// The client sees this
    };
private:
    //16个free-lists
    static obj * volatile free_list[__NFREELISTS];
    //以下函数根据区块的大小 决定使用第 n 号free-list，n从1开始算起
    static size_t FREELIST_INDEX(size_t bytes){
        return (((bytes) + __ALIGN-1)/__ALIGN-1);
    }
    //返回一个大小为n的对象 并可能加入大小为n 的其他区块到free list
    static void* refill(size_t n);
    //配置一大块区间 可以容纳nobjs个“size”大小的区块
    //如果配置nobjs个大小的区块有所不方便 ，可以降低nobjs
    static char * chunk_alloc(size_t size,int &objs);
    //Chunk allocation state
    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){}
};

//以下是static data member 的定义与初值的设定
template 
char* __default_alloc_template::start_free = 0;

template 
char* __default_alloc_template::end_free = 0;

template 
size_t __default_alloc_template::heap_size = 0;

template 
typename __default_alloc_template::obj * volatile
__default_alloc_template::free_list[__NFREELISTS] =
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};

• 这个函数首先判断区块的大小 ，大于128 使用第一级配置器，小于128 检查对应的 free list。如果free list之内有可用的区块 就直接拿来使用
• 如果没有可用的区块，就将区块大小上调至8的倍数边界 使用refill（）准备为free list填充空间 

template 
void* __default_alloc_template::allocate(size_t n) {
    obj* volatile *my_free_list;
    obj* result;
    //大于128就调用第一级配置器
    if(n>(size_t)__MAX_BYTES){
        return (malloc_alloc::allocate(n));
    }
    //寻找16个free lists中适当的一个
    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));
        return r;
    }
    //调整free list
    *my_free_list = result->free_list_link;
    return result;
}

• 注意事项：类里面声明的静态函数 不能带有{} ，否则后期实现函数逻辑的时候 编译不通过
• 只有用户自定义的类型作为函数的返回值的时候 需要使用typename关键字

template 
void __default_alloc_template::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;
    }
    //寻找对应的free list
    my_free_list = free_list + FREELIST_INDEX(n);
    //调整free list 回收区块
    q->free_list_link = *my_free_list;
    *my_free_list = q;
    
}

• 当 free list中没有可用的区块的时候 需要调用 refill() 函数 为free list重新填充空间，新的空间将取自内存池(通过chunk_alloc完成 )
• 缺省获得 20个新节点，万一内存池空间不足 获得的节点数可能 小于20

//返回一个大小为n的对象，并且有的时候会适当的位free list增加节点
//假设n已经上调为8的倍数
template 
void* __default_alloc_template::refill(size_t n) {
    int nobjs = 20;
    //调用chunk_alloc() 尝试获取nobjs个区块作为free list的新的节点
    //注意参数nobjs是pass by reference的方式
    char* chunk = chunk_alloc(n,nobjs);
    obj* volatile * my_free_list;
    obj* result;
    obj* current_obj,*next_obj;
    int i;
    //如果只获得一个区块 这个区块就会被分配给调用者使用 free list无新的节点
    if (1 == nobjs){
        return chunk;
    }
    //否则准备调整free list 纳入新的节点
    my_free_list = free_list + FREELIST_INDEX(n);
    //在chunk空间内 建立free list
    result = (obj*) chunk;   //这一块准备返回给客户端
    //以下导引free list指向新的配置的空间（取自内存池）
    *my_free_list = next_obj = (obj*)(chunk +n);
    //以下将free list的各个节点串接起来
    for(i=1;;i++){ //从1开始 因为第0个将会返回给客户端
        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);
}

• 从内存池取空间 给free list使用  是chunk alloc函数的作用

//假设n已经上调为8的倍数
//注意参数nobjs是pass by reference

template 
char* __default_alloc_template::chunk_alloc(size_t size, int &nobjs) {
    char* result;
    size_t total_bytes = size * nobjs;
    size_t byte_left = end_free - start_free;//内存池剩余空间
    if (byte_left >= total_bytes){
        //内存池的空间满足需求量
        result = start_free;
        start_free += total_bytes;
        return result;
    } else if(byte_left >= size){
        //内存池存储的空间不能完全满足需求，但是足够供应一个 （含）以上的区块
        nobjs = byte_left/size; //可以满足的数量
        total_bytes = nobjs * size;
        result = start_free;
        start_free += total_bytes;
        return (result);
    } else{
        //内存池剩余的空间连一个区块的大小都无法满足
        size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);
        //以下内容试着从内存池 残余中 寻找
        if (byte_left > 0){
            //内存中还存在部分的内存空间 但是这个内存空间小于一个size 但是大于0
            //首先找到适当的free list
            obj* volatile* my_free_list = free_list + FREELIST_INDEX(byte_left);
            //调整free list 将内存池中的残余空间全部编入到 free list里面
            ((obj *)start_free)->free_list_link = *my_free_list;
            *my_free_list = (obj*) start_free;
        }
        //配置heap空间 用于填充内存池
        start_free = (char*)malloc(bytes_to_get);
        if (0 == start_free){
            //heap空间不足 malloc失败
            int i;
            obj* volatile * my_free_list,*p;
            //尝试检视手上具备的东西 这不会造成伤害 我们不打算进一步进行配置较小的区块
            //因为在多进程的机器上容易导致灾难
            //以下代码的目的是搜寻适当( 尚有未用的区块，且区块够大 )的free list
            for (i = size;i <= __MAX_BYTES;i+- __ALIGN ) {
                my_free_list = free_list + FREELIST_INDEX(i);
                p = *my_free_list;
                if (p!=0){//free list 内尚有未用的区块
                    //调整free list 释放未使用的区块
                    *my_free_list = p->free_list_link;
                    start_free = (char*)p;
                    end_free = start_free + i;
                    //递归调用自己 为了修正nobjs
                    return (chunk_alloc(size,nobjs));
                    //注意：任何残余的领头 终将被编入适当的free list中作为备用
                }
            }
            end_free = 0;//如果出现意外(山穷水尽 到处无内存可以使用)
            //调用第一级配置器 寄希望于第一级配置器 希望out-of-memory机制可以出一份力
            start_free = (char*) malloc_alloc::allocate(bytes_to_get);
            //这会抛出异常(exception) 或内存不足的情况获得改善
        }
        heap_size += bytes_to_get;
        end_free = start_free + bytes_to_get;
        //递归调用自己 为了修正 nobjs
        return (chunk_alloc(size,nobjs));
    }
}

• 使用 end_free - start_free 判断内存池的容量，如果空间充足直接调出20个区块返回给free_list
• 如果不足20个 但是大于1个以上的容量 先提供可以满足的区块 ，递归更新 (pass by reference的nobjs修改为实际可以提供的区块数)
• 如果一个都不可以满足  使用malloc从heap中配置内存 为内存池注入活水，新水量的大小是需求量的2倍，还需要加上随着配置次数增加愈来愈大的附加量

• 例子：假设程序一开始客户端 就调用 chunk_alloc（32，20），此刻内存池和free_list里面均没有可用的内存空间，所以使用malloc() 配置40个32byte区块，使用malloc分配的内存空间是需求的两倍。其中第一个 32byte交出，19个给free_list [3] 进行维护，其余的20个留给内存池。
• 客户端 使用 chunk_alloc（64，20），此刻free_list [7]没有内存 ，向内存池提出申请 ；内存池此刻具备的内存 (32 * 20)，所以只可以提供 (32 * 20)/64 = 10个64位区块，返回10个区块，第一个交给客户端，剩余的9个由 free_list [7]。此刻内存池全空
• 客户端调用chunk_alloc（96，20）此刻free_list [11]和内存池全为空，需要使用malloc分配内存，分配40+n个96bytes区块，将第一个交出，另外19个交给free_list [11]维护，其余的20+n 的容量交给内存池
• 假设system heap空间不足了 (无法为内存池注入 活水),malloc()行动失败，chunk_malloc()就需要四处寻找合适的内存。找到了就挖一块，这个是从free_list上面去挖内存，找不到就需要第一级配置器。
• 第一级配置器本质上还是使用malloc() 进行内存的配置，考虑到前提 system heap已经没有内存了，为啥同样使用malloc这里就可以了呢？因为 第一配置器具备out-free-memory处理机制(类似new-handler机制) 就有机会去释放其余地方多余的内存，进行内存的分配和使用。如果可以就成功，如果不可以就返回bad_malloc的异常。

template
class simple_alloc{
            
};
//SGI 通常使用这种方式来使用配置器
template //缺省使用alloc为配置器
class vector{
public:
    typedef T value_type;
protected:
    //专属空间配置器  每次配置一个元素的大小
    typedef simple_allocdata_allocator;
};

• 其中 第二个template参数所接受的缺省参数值alloc 可以是第一级配置器 也可以是第二级配置器
• 不过SGI STL已经将其设定为第二级配置器 

#if 0
#   include
#   define __THROW_BAD_ALLOC throw bad_alloc
#elif !defined(__THROW_BAD_ALLOC)
#   include
#   define __THROW_BAD_ALLOC std::cerr << "out of memory" << std::endl; exit(1);
#endif

//malloc-based allocator 通常比稍后介绍的default alloc要慢
//但是它是线程安全的 thread-safe，并对于空间的运用比较高效
//以下是第一级别配置器
//无“template 型别参数” 至于非型别参数 inst 完全没有用到
template 
class __malloc_alloc_template{
private:
    //以下内容都是函数指针，所代表的函数用于处理内存不足的情况
    //oom : out of memory
    static void *oom_malloc(std::size_t);
    static void *oom_realloc(void*,std::size_t);
    static void (* __malloc_alloc_oom_handler)();
public:
    static void* allocate(std::size_t n){
        void * result = malloc(n);//第一级配置器 直接使用malloc进行内存的分配
        //当无法满足内存分配的需求的时候，使用oom_malloc()
        if(result == 0){
            result = oom_malloc(n);
        }
        return result;
    }

    static void deallocate(void* p,size_t ){
        free(p); //第一级配置器 直接使用 free()进行释放
    }

    static void* reallocate(void* p,size_t ,size_t new_size){
        void *result = realloc(p,new_size); //第一级别配置器直接使用realloc()
        //以下无法满足需求的时候 改用oom_realloc()
        if (0==result){
            result = oom_realloc(p,new_size);
        }
        return result;
    }
    //以下是仿真C++的set_new_handler(),换句话说 你可以通过他指定自己的out_of_handler
    static void(*set_malloc_handler(void (*f)()))(){
        void (* old)() = __malloc_alloc_oom_handler;
        __malloc_alloc_oom_handler = f;
        return (old);
    }

};
//malloc_alloc out_of_memory handling
//初始化为0
template 
void (* __malloc_alloc_template::__malloc_alloc_oom_handler)() = 0;

template 
void* __malloc_alloc_template::oom_malloc(std::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 
void *__malloc_alloc_template::oom_realloc(void *p, std::size_t n) {
    void (* my_malloc_handler)() = __malloc_alloc_oom_handler;
    void * result;
    if(0 == my_malloc_handler){
        __THROW_BAD_ALLOC;
    }
    (*my_malloc_handler)();//调用处理例程，企图释放内存
    result = realloc(p,n);//再次尝试配置内存
    if (result){
        return result;
    }
}

//以下直接将参数 inst 指定为0
typedef __malloc_alloc_template<0>malloc_alloc;



enum {__ALIGN = 8}; //小型区块的上调边界
enum {__MAX_BYTES = 128};//小型区块的上限
enum {__NFREELISTS = __MAX_BYTES/__ALIGN};//free-lists的个数

using namespace std;
//以下是第二级配置器
//注意：无 template型别参数 且第二参数哇怒气按没有被派上用场
//第一参数用于多线程的环境 本示例 暂未涉及
template 
class __default_alloc_template{
private:
    //ROUND_UP() 将bytes上调至8的倍数
    static size_t ROUND_UP(size_t bytes){
        return (((bytes) + __ALIGN - 1) & ~(__ALIGN-1));
    }

private:
    union obj{    //free-lists 节点构造
        union obj * free_list_link;
        char client_data[1];// The client sees this
    };
private:
    //16个free-lists
    static obj * volatile free_list[__NFREELISTS];
    //以下函数根据区块的大小 决定使用第 n 号free-list，n从1开始算起
    static size_t FREELIST_INDEX(size_t bytes){
        return (((bytes) + __ALIGN-1)/__ALIGN-1);
    }
    //返回一个大小为n的对象 并可能加入大小为n 的其他区块到free list
    static void* refill(size_t n);
    //配置一大块区间 可以容纳nobjs个“size”大小的区块
    //如果配置nobjs个大小的区块有所不方便 ，可以降低nobjs
    static char * chunk_alloc(size_t size,int &nobjs);
    //Chunk allocation state
    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);
};

//以下是static data member 的定义与初值的设定
template 
char* __default_alloc_template::start_free = 0;

template 
char* __default_alloc_template::end_free = 0;

template 
size_t __default_alloc_template::heap_size = 0;

template 
typename __default_alloc_template::obj * volatile
__default_alloc_template::free_list[__NFREELISTS] =
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};

template 
void* __default_alloc_template::allocate(size_t n) {
    obj* volatile *my_free_list;
    obj* result;
    //大于128就调用第一级配置器
    if(n>(size_t)__MAX_BYTES){
        return (malloc_alloc::allocate(n));
    }
    //寻找16个free lists中适当的一个
    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));
        return r;
    }
    //调整free list
    *my_free_list = result->free_list_link;
    return result;
}

template 
void __default_alloc_template::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;
    }
    //寻找对应的free list
    my_free_list = free_list + FREELIST_INDEX(n);
    //调整free list 回收区块
    q->free_list_link = *my_free_list;
    *my_free_list = q;
}

//返回一个大小为n的对象，并且有的时候会适当的位free list增加节点
//假设n已经上调为8的倍数
template 
void* __default_alloc_template::refill(size_t n) {
    int nobjs = 20;
    //调用chunk_alloc() 尝试获取nobjs个区块作为free list的新的节点
    //注意参数nobjs是pass by reference的方式
    char* chunk = chunk_alloc(n,nobjs);
    obj* volatile * my_free_list;
    obj* result;
    obj* current_obj,*next_obj;
    int i;
    //如果只获得一个区块 这个区块就会被分配给调用者使用 free list无新的节点
    if (1 == nobjs){
        return chunk;
    }
    //否则准备调整free list 纳入新的节点
    my_free_list = free_list + FREELIST_INDEX(n);
    //在chunk空间内 建立free list
    result = (obj*) chunk;   //这一块准备返回给客户端
    //以下导引free list指向新的配置的空间（取自内存池）
    *my_free_list = next_obj = (obj*)(chunk +n);
    //以下将free list的各个节点串接起来
    for(i=1;;i++){ //从1开始 因为第0个将会返回给客户端
        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);
}

//假设n已经上调为8的倍数
//注意参数nobjs是pass by reference

template 
char* __default_alloc_template::chunk_alloc(size_t size, int &nobjs) {
    char* result;
    size_t total_bytes = size * nobjs;
    size_t byte_left = end_free - start_free;//内存池剩余空间
    if (byte_left >= total_bytes){
        //内存池的空间满足需求量
        result = start_free;
        start_free += total_bytes;
        return result;
    } else if(byte_left >= size){

    }

}

• STL 源码剖析 空间配置器_CHYabc123456hh的博客-CSDN博客