史上最骚のSTL空间分配器(续)

内存池

从内存池中取空间给free list用，是chunk_alloc()的工作。

如果在内存池完全充足的情况下，chunk_alloc()会直接返回空间。

	char *result;
  size_t total_bytes = size * nobjs;
  size_t bytes_left = end_free - start_free;

  if(bytes_left > total_bytes){ // memory pool is enough.
    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);
  }

重新调整nobjs，然后将能够返回的所有区块返回。

如果连一个区块都不能提供的话，则考虑向内存malloc一块，以补充内存池。

else{
  size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);

并且需要malloc的size应该是total_bytes的两倍。

在开始malloc之前，先对内存池中的零头进行利用。调整free list。

 if (bytes_left > 0){
   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;
 }

然后开始malloc。

start_free = (char *)malloc(bytes_to_get);

如果没有异常的话，可以将申请到的内存处理一下然后返回了。

heap_size += bytes_to_get;
end_free = start_free + bytes_to_get;
return (chunk_alloc(size, nobjs)); // adjust nobjs

如果对内存的申请不成功，即system heap已经耗尽，那么我们只能对我们现有的东西进行检视。

if (start_free == 0){
    int i;
    obj *volatile *my_free_list, *p;
    for (i = size; i <= __MAX_BYTES;i+=__ALIGN){ // 搜寻适当的free list
      my_free_list = free_list + FREELIST_INDEX(i);
      p = *my_free_list;
      if (p != 0){
        *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); // 调用第一级配置器，赌一把。
}

代码

完整的chunk_alloc：

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){ // memory pool is enough.
        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);
        if (bytes_left > 0){
            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 (start_free == 0){
            int i;
            obj *volatile *my_free_list, *p;
            for (i = size; i <= __MAX_BYTES;i+=__ALIGN){
                my_free_list = free_list + FREELIST_INDEX(i);
                p = *my_free_list;
                if (p != 0){
                    *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));
    }
}

测试

至此，一个史上最骚的内存池就这么诞生了。但是我们还是按照惯例来测试一下这个池子好不好使。第一次使用的时候以为是直接使用__default_alloc_template，

#include <vector>
...
vector<int,mystl::__default_alloc_template<0,0>> iv(ia,ia+5);

报错，报了一吨。而且是没法debug的那种。根本找不到错误在哪里。

后来找了个tinystl源码看了看，原来是需要给一层包装(allocator.h)才行。另外debug了一下，alloc.h有以下改动。

typedef __default_alloc_template<0, 0> alloc;

template<>
char *alloc::start_free = 0;

template<>
char *alloc::end_free = 0;

template<>
size_t alloc::heap_size = 0;

template<>
alloc::obj *volatile alloc::free_list[__NFREELISTS] =
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,};

包装用的头文件直接抄defalloc.h，然后将alloc加到模版声明中去即可。附allocator.h

#ifndef DEFALLOC_H
#define DEFALLOC_H

#include <new>
#include <stddef.h>
#include <stdlib.h>
#include <limits.h>
#include <iostream>
#include <algorithm>
#include "alloc.h"

using namespace std;

namespace mystl{

template <class T,class Alloc = mystl::alloc>
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;



    pointer allocate(size_type size){
        return (pointer)Alloc::allocate((difference_type)size); // 需要将指针转换一下
    }

    void deallocate(pointer p){
        Alloc::deallocate(p,0);
    }

    void deallocate(pointer p,size_type n){
        Alloc::deallocate(p,n);
    }

    pointer address(reference x){
        return (pointer) &x;
    }

    const_pointer const_address(const_reference x){
        return (const_pointer) &x;
    }

    size_type init_page_size(){
        return max(size_type(1),size_type(4096/sizeof(T)));
    }

    size_type max_size(){
        return max(size_type(1),size_type(UINT_MAX/sizeof(T)));
    }

}; // end of class allocator

template<>
class allocator<void>{
public:
    typedef void* pointer;
};


} // end of namespace
#endif

然后就可以愉快地使用内存池啦。

// demo.cpp
#include <vector>
#include <iostream>
#include "allocator.h"

using namespace std;

int main(){
    int ia[5] = {0,1,2,3,4};
    unsigned int i;
    unsigned int size;

    vector<int,mystl::allocator<int>> iv(ia,ia+5);
    size = iv.size();
    for(i=0;i<size;i++){
        cout<<iv[i]<<" ";
    }
    cout<<endl;
    return 0;
}

# surager @ ubuntu in ~/MyTinySTL [9:01:25] 
$ cd "/home/surager/MyTinySTL/" && g++ 'test.cpp' -o 'test' -Wall -g -O2 -static-libgcc -std=c++17 -fexec-charset=GBK && "/home/surager/MyTinySTL/"test
0 1 2 3 4 

总结

对stl内存分配的学习虽然不是重点，但是对于源码的理解以及对内存分配的深入还是很有意义的。这个内存池不仅让我收获了源码的逻辑严谨性，而且让我知道了数据结构在内存中所占的比较重要的地位。

另外，这只是stl学习的第一步，还需要努力。