C++ STL空间配置源码分析以及实现一

class alloc{
//............
}

template<class T>
class allocator{
//..................
}

template <class T, class Alloc = allocator<T>>
class SimpleVec{
//.....
}

　　if 用户申请空间 > 128:
　　    调用一级空间配置器
　　else:
       调用二级空间配置器

class alloc{
private:
   enum EAlign{ ALIGN = 8};//小型区块的上调边界
   enum EMaxBytes{ MAXBYTES = 128};//小型区块的上限，超过的区块由malloc分配
//free-lists的个数
   enum ENFreeLists{ NFREELISTS = (EMaxBytes::MAXBYTES / EAlign::ALIGN)}; 
enum ENObjs{ NOBJS = 20};//每次增加的节点数
private:
   //free-lists的节点构造
   union obj{
      union obj *next;
      char client[1];
   };

   static obj *free_list[ENFreeLists::NFREELISTS];
private:
   static char *start_free;//内存池起始位置
   static char *end_free;//内存池结束位置
   static size_t heap_size;//
private:
   //将bytes上调至8的倍数，例如 (1, 3, 7) -> 8, (9, 13) -> 16
   static size_t ROUND_UP(size_t bytes){
      return ((bytes + EAlign::ALIGN - 1) & ~(EAlign::ALIGN - 1));
   }
   //根据区块大小，决定使用第n号free-list，n从0开始计算
   //例如 (1, 3, 7) -> 0, (9, 13) -> 1
   static size_t FREELIST_INDEX(size_t bytes){
      return (((bytes)+EAlign::ALIGN - 1) / EAlign::ALIGN - 1);
   }
   //返回一个大小为n的对象，并可能加入大小为n的其他区块到free-list
   static void *refill(size_t n);
   //配置一大块空间，可容纳nobjs个大小为size的区块
   //如果配置nobjs个区块有所不便，nobjs可能会降低
   static char *chunk_alloc(size_t size, size_t& nobjs, int print_count=1);

public:
   static void *allocate(size_t bytes);//分配内存
   static void deallocate(void *ptr, size_t bytes);//内存回收
   // 回收旧内存，分配新内存
   static void *reallocate(void *ptr, size_t old_sz, size_t new_sz);
};

// 将任意的整数调整为8的倍数

void test_or_align(){
    int a =(5 + 8 - 1) & ~(8 - 1);
    int b =(9 + 8 - 1) & ~(8 - 1);
    int c =(13 + 8 - 1) & ~(8 - 1);
    int d =(17 + 8 - 1) & ~(8 - 1);
    cout<<a<<endl;  // 8  （5 -》 8）
    cout<<b<<endl;  // 16  （9 -》 16）
    cout<<c<<endl;  // 16   （13 -》 16）
    cout<<d<<endl;  // 24    （17 -》 24）
}

void test_freelist_index(){
    size_t bytes = 5;
    size_t idx = (((bytes) + EAlign::ALIGN - 1) / EAlign::ALIGN - 1);
    std::cout<<idx<<endl;  //0

    bytes = 13;
    idx = (((bytes) + EAlign::ALIGN - 1) / EAlign::ALIGN - 1);
    std::cout<<idx<<endl; // 1

}

char *alloc::start_free = 0;
char *alloc::end_free = 0;
size_t alloc::heap_size = 0;

alloc::obj *alloc::free_list[alloc::ENFreeLists::NFREELISTS] = {
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
};

void *alloc::allocate(size_t bytes){

    if (bytes > EMaxBytes::MAXBYTES){//分配大于128字节的内存，直接分配返回
        printf("%sallocate size: %d greater than 128, use malloc\n", s4space.c_str(), bytes);
        return malloc(bytes);
    }
    size_t round_up = ROUND_UP(bytes);//输出round up的大小(这里没有意义仅仅输出查看)
    printf("allocate size: %d. after round up size is: %d \n", bytes, round_up);

 //定位bytes应该分配到那个链表中
    size_t index = FREELIST_INDEX(bytes);
    obj *list = free_list[index];
    if (list){//此list还有空间给我们
        printf("free_list has free node, index is: %d\n", index);
        free_list[index] = list->next;//使当前空闲节点指向下一个
        return list;
    }
    else{//此list没有足够的空间，需要从内存池里面取空间
        return refill(ROUND_UP(bytes));
    }
}

1. 当需要的内存 > 128字节，分配器alloc直接free对应的内存
2. 当小于 128 字节，则直接在free_list里面查找看是否有内存可用
3. 2中如果满足不了，则需要在内存池中获取
至于refill后面我们在看。

void alloc::deallocate(void *ptr, size_t bytes){
    if (bytes > EMaxBytes::MAXBYTES){//大于128的节点直接free释放
        free(ptr);
    }
    else{//小于128的节点重新分配给free_list(不释放内存)
        size_t index = FREELIST_INDEX(bytes);
        obj *node = static_cast<obj *>(ptr);
        node->next = free_list[index];
        free_list[index] = node;
    }
}

1 > 128字节的直接free
2 < 128字节，首先定位到free_list然后指针移位即可

//返回一个大小为n的对象，并且有时候会为适当的free list增加节点
//假设bytes已经上调为8的倍数
void *alloc::refill(size_t bytes){
    size_t nobjs = ENObjs::NOBJS; // 默认为free_list bytes节点分配20个元素空间
    //从内存池里取，nobjs可能没有20个，因此参数是引用
    char *chunk = chunk_alloc(bytes, nobjs);
    obj **my_free_list = 0;
    obj *result = 0;
    obj *current_obj = 0, *next_obj = 0;
    printf("%srefill %d, objs\n", s4space.c_str(), nobjs);

    if (nobjs == 1){//取出的空间只够一个对象使用
        return chunk;
    }
    else{
        my_free_list = free_list + FREELIST_INDEX(bytes);
        result = (obj *)(chunk);//首个节点直接返回
//剩余的节点分配到对应的free_list中去
        *my_free_list = next_obj = (obj *)(chunk + bytes);
        //将取出的多余的空间加入到相应的free list里面去
        for (int i = 1;; ++i){
            current_obj = next_obj;
            next_obj = (obj *)((char *)next_obj + bytes);
            if (nobjs - 1 == i){
                current_obj->next = 0;//最后一个指针next 赋值null
                break;
            }
            else{
                current_obj->next = next_obj;
            }
        }
        return result;
    }
}

//假设bytes已经上调为8的倍数
char *alloc::chunk_alloc(size_t bytes, size_t& nobjs, int print_count){
    char *result = 0;
    size_t total_bytes = bytes * nobjs;
    size_t bytes_left = end_free - start_free;//当前有多少剩余的内存
    printf("%schunk_alloc round: %d,  need total_bytes: %d,  bytes_left: %d\n",
           s4space.c_str(), print_count, total_bytes, bytes_left);

    if (bytes_left >= total_bytes){//内存池剩余空间完全满足需要
        result = start_free;
        start_free = start_free + total_bytes;
        printf("%schunk_alloc round: %d, cater all, return %d objs bytes_left: %d >= total_bytes: %d\n",
               s8space.c_str(), print_count, nobjs, bytes_left, total_bytes);

        return result;
    }//内存池剩余空间不能完全满足需要，但足够供应一个或以上的区块
    else if (bytes_left >= bytes){
        nobjs = bytes_left / bytes;
        total_bytes = nobjs * bytes;

        result = start_free;
        start_free += total_bytes;
        printf("%schunk_alloc round: %d, cater part, return %d objs, size: %d return %d bytes\n",
               s8space.c_str(), print_count, nobjs, bytes, total_bytes);

        return result;
    }
    else{//内存池剩余空间连一个区块的大小都无法提供，重新申请
        size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);
        printf("%schunk_alloc round: %d, malloc %d\n",
               s8space.c_str(), print_count, bytes_to_get);

        if (bytes_left > 0){//将原有的剩余的bytes分配给free_list
            obj **my_free_list = free_list + FREELIST_INDEX(bytes_left);
            ((obj *)start_free)->next = *my_free_list;
            *my_free_list = (obj *)start_free;
        }
// start_free 重新分配
        start_free = (char *)malloc(bytes_to_get);
        heap_size += bytes_to_get;
        end_free = start_free + bytes_to_get;//每次只会递归一次
        return chunk_alloc(bytes, nobjs, ++print_count);
    }
}

1. 默认的返回给free_list 20个bytes，如果有则直接返回，
   没有则能返回多少个bytes就返回多少个。

2. 满足不了1，则内存中申请需要内存的两倍。

void test_alloc_2(){
    void * ptr;
    size_t n = 10;
    ptr = alloc::allocate(n);
    cout<<"\n===========================\n"<<endl;
    void * ptr2;
    size_t n2 = 18;
    ptr2 = alloc::allocate(n2);

    cout<<"\n===========================\n"<<endl;
    void * ptr3;
    size_t n3 = 10;
    ptr3 = alloc::allocate(n3);

    cout<<"\n===========================\n"<<endl;
    void * ptr5;
    size_t n5 = 7;
    ptr5 = alloc::allocate(n5);

    cout<<"\n===========================\n"<<endl;
    void * ptr4;
    size_t n4 = 26;
    ptr4 = alloc::allocate(n4);

    cout<<"\n===========================\n"<<endl;
    void * ptr6;
    size_t n6 = 47;
    ptr6 = alloc::allocate(n6);

    cout<<"\n===========================\n"<<endl;
    void * ptr7;
    size_t n7 = 5;
    ptr7 = alloc::allocate(n7);

    alloc::deallocate(ptr, n);
    alloc::deallocate(ptr2, n2);
    alloc::deallocate(ptr3, n3);
    alloc::deallocate(ptr4, n4);
    alloc::deallocate(ptr5, n5);
    alloc::deallocate(ptr6, n6);
    alloc::deallocate(ptr7, n7);
}

allocate size: 18. after round up size is: 24
chunk_alloc round: 1,  need total_bytes: 480,  bytes_left: 320
chunk_alloc round: 1, cater part, return 13 objs, size: 24 return 312 bytes
refill 13, objs

allocate size: 10. after round up size is: 16
free_list has free node, index is: 1