【STL】模拟实现二级空间配置器

小鱼儿 2022-05-23 13:25 191阅读 0赞

### 二级空间配置器的实现原理 ###

二级空间配置器，当配置空间大于128字节时，调用[一级空间配置器][Link 1]；当配置空间小于128字节时，采用了复杂的内存池整理方式，又称为**次层配置**：每次配置一大块内存，并维护16个自由链表(free list)，下次再使用相同大小的内存时，则直接从free list中得到。如果用户释放了小块空间，free list还负责回收。同时，为了方便管理，16个自由链表维护的空间大小均是88的整数倍，8,16,24,32……

1.  若free list中有区块，就拿来用；
2.  如果没有可以用的空间，则调用`refill()`函数，准备为free list重新填充空间；
3.  新的空间将取自内存池(由`chunk_alloc()`函数完成)，缺省得到20个相同大小的空间，若不够20个但够至少1个，则将这些都拨出去；但是如果一个都不够时，则利用malloc()函数从heap中分配；
4.  若malloc失败，则调用一级空间配置器，一级空间配置器中有针对空间不足的处理方式。  
    ![这里写图片描述][70]

--------------------

以上便是二级空间配置器的大致原理了，如果没有看懂，没关系，下面我们用流程图的形式将每个函数的实现过程大致画出来。

### 二级空间配置器主要功能流程图 ###

**空间配置：**  
![这里写图片描述][70 1]  
![这里写图片描述][70 2]  
![这里写图片描述][70 3]  
**空间释放：**  
![这里写图片描述][70 4]  
二级空间配置器的实现代码，见本文末。

--------------------

### 二级空间配置器与一级空间配置器 ###

![这里写图片描述][70 5]  
为了使配置器可以符合STL的标准，SGI将其进行了封装，封装成simple\_alloc接口：

template <class T, class Alloc>
    class SimpleAlloc
    {
    public:
         static T* Allocate(size_t n)// 开辟n个大小为T的空间
         {
              return (0 == n) ? 0 : (T*)Alloc::Allocate(sizeof(T)*n);
         }
         static T* Allocate(void)// 开辟n个大小为T的空间
         {
              return (T*)Alloc::Allocate(sizeof(T));
         }
         static void DeAllocate(void* p, size_t n)
         {
              if(n != 0)
                   Alloc::DeAllocate(p, n*sizeof(T));
         }
         static void DeAllocate(void* p)
         {
              return Alloc::DeAllocate(p, sizeof(T));
         }
    };

--------------------

### 对象的构造与析构 ###

之前我们说C++中内存的配置与释放分为两步：对于配置空间，第一步是申请空间，第二步是调用相应的构造函数；对于释放空间，第一步是调用析构函数，第二步是释放空间。而SGI将这两步分开进行，**空间的配置与释放由`alloc::allocate()`和`alloc::deallocate()`完成；对象的构造和析构由`::construct()`和`::destoty()`完成。**  
　　以上的一级空间配置器和二级空间配置器都是空间的配置与释放，下面便是`::construct()和::destoty()`的实现，这两个函数均是全局函数。  
　　  
construct是使用了定位new表达式：

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

destory有两个版本：  
　　一是接受一个指针，将指针所指之物析构掉  
　　二是接受一个迭代器区间，将区间之内的对象析构掉  
区间内的对象（使用到了类型萃取，[戳这里查看][Link 2]），如果是内置类型，则不需要做什么，如果是自定义类型（深拷贝的对象），则调用版本一的函数析构。

template <class T>
    void Destory(T* p)
    {
         p->~T();
    }
    template <class Iterator>
    void Destory(Iterator first, Iterator end)
    {
         _Destory(first, end, TypeTraits<Iterator::ValueType>::PODType);
    }
    template <class Iterator>
    void _Destory(Iterator first, Iterator end, Falsetype)
    {}
    template <class Iterator>
    void _Destory(Iterator first, Iterator end, Truetype)
    {
         while (first != end)
         {
              Destory(&(*first));
              first++;
         }
    }

--------------------

### 二级空间配置器的实现函数 ###

// 其中__TRACE_DEBUG(...)是测试函数，与函数的实现无关。
    typedef Default_Alloc_Template<0> _Alloc;
    
    template <int inst>
    class Default_Alloc_Template
    {
    private:
        enum { __ALIGN = 8 };
        enum { __MAX_BYTES = 128 };
        enum { __NFREE_LISTS = __MAX_BYTES / __ALIGN };
        union OBJ
        {
            union OBJ* free_list_link;
            char client[1];
        };
        static OBJ* free_list[__NFREE_LISTS];
        static char* start_free;
        static char* end_free;
        static size_t heap_size;
        static size_t ROUND_UP(size_t bytes)
        {
            return ((bytes + __ALIGN - 1) & ~(__ALIGN - 1));// 向上调整至8的倍数
        }
        static size_t FREELIST_INDEX(size_t bytes)
        {
            return ((bytes + __ALIGN - 1) / __ALIGN - 1);// 计算相应的下标
        }
    public:
        static void* Allocate(size_t n)
        {
            if (n > __MAX_BYTES)
            {
                __TRACE_DEBUG("一级空间配置申请%d字节内存\n", n);
                return MallocAllocTemplate<0>::Allocate(n);
            }
            int index = FREELIST_INDEX(n);
            OBJ* result = free_list[index];
            if (result == 0)
            {
                __TRACE_DEBUG("自由链表中没有%d的空间，去内存池申请内存\n", n);
                void* r = ReFill(ROUND_UP(n));
                __TRACE_DEBUG("内存池申请内存成功，返回给用户%d字节的内存\n", n);
                return r;
            }
            __TRACE_DEBUG("二级空间配置器有内存，申请到了%d内存\n", n);
            free_list[index] = result->free_list_link;
            return result;
        }
        static void DeAllocate(void* p, size_t n)
        {
            if (n > __MAX_BYTES)
            {
                __TRACE_DEBUG("一级空间配置器释放内存%d\n", n);
                MallocAllocTemplate<0>::DeAllocate(p, n);
                return;
            }
            int index = FREELIST_INDEX(n);
            __TRACE_DEBUG("二级空间配置器释放内存%d\n", n);
            ((OBJ*)p)->free_list_link = free_list[index];
            free_list[index] = ((OBJ*)p);
        }
    
        static void* ReFill(size_t n);
        static char* ChunkAlloc(size_t size, int &nonjs);
    };
    
    template <int inst>
    char* Default_Alloc_Template<inst>::start_free = NULL;
    template <int inst>
    char* Default_Alloc_Template<inst>::end_free = NULL;
    template <int inst>
    size_t Default_Alloc_Template<inst>::heap_size = 0;
    template <int inst>
    typename Default_Alloc_Template<inst>::OBJ* Default_Alloc_Template<inst>::free_list[
        Default_Alloc_Template<inst>::__NFREE_LISTS] = { 0 };
    
    template <int inst>
    void* Default_Alloc_Template<inst>::ReFill(size_t n)// 向内存池要内存
    {
        int nobjs = 20;
        __TRACE_DEBUG("向内存池申请20个%d大小的内存\n", n);
        char* chunk = ChunkAlloc(n, nobjs);// 向内存池要20个n个字节的内存，其中1个给用户，19个给链表挂上
    
        if (nobjs == 1)
        {
            __TRACE_DEBUG("向内存池只申请到了1个%d的内存\n", n);
            return chunk;
        }
        int index = FREELIST_INDEX(n);
        OBJ* cur = (OBJ*)(chunk + n);
        OBJ* next = (OBJ*)((char*)cur + n);
        __TRACE_DEBUG("向内存池申请到了%d个%d大小的内存，将一个返回给用户，其余%d个挂到自由链表中\n", nobjs, n, nobjs-1);
        while (--nobjs)
        {
            cur->free_list_link = free_list[index];
            free_list[index] = cur;
            cur = next;
            next = (OBJ*)((char*)next + n);
        }
        return chunk;
    }
    template <int inst>
    char* Default_Alloc_Template<inst>::ChunkAlloc(size_t size , int &nobjs)
    {
        char* result = NULL;
        size_t total_bytes = size * nobjs;  // 需要nobjs个size大小的内存
        size_t bytes_left = end_free - start_free; // 内存池剩余内存
    
        if (bytes_left >= total_bytes)// 内存池的内存足够
        {
            result = start_free;
            start_free += total_bytes;
            __TRACE_DEBUG("内存池有足够的内存:%d\n", total_bytes);
            return result;
        }
        else if (bytes_left >= size)// 内存池只够一个或以上个size大小的内存
        {
            result = start_free;
            nobjs = bytes_left / size;
            total_bytes = nobjs * size;
            start_free += total_bytes;
            __TRACE_DEBUG("内存池有%d个%d大小的内存:共%d字节\n", nobjs, size, total_bytes);
            return result;
        }
        else // 内存池一个size大小的内存都没有
        {
            size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4); //内存池的内存不够，需要向系统要这么多内存
            // 先将内存池的剩余内存放置链表中
            if (bytes_left > 0)
            {
                __TRACE_DEBUG("内存池一个%d的空间都没有，先将内存池剩余内存放置自由链表\n", size);
                ((OBJ*)start_free)->free_list_link = free_list[bytes_left];
                free_list[bytes_left] = (OBJ*)start_free;
            }
            start_free = (char*)malloc(bytes_to_get); // 向系统要内存
            __TRACE_DEBUG("内存池向系统要%d内存\n", bytes_to_get);
            if (start_free == 0)// 系统内存不够
            {
                // 去链表里找能用的内存
                for (int i = size; i < __MAX_BYTES; i += __ALIGN)
                {
                    if (free_list[i] != NULL)
                    {
                        start_free = (char*)free_list[i];
                        end_free = start_free + i;
                        free_list[i] = free_list[i]->free_list_link;
                    }
                    __TRACE_DEBUG("系统没有足够内存，在自由链表找内存\n");
                }
                end_free = 0; // 如果底下的调用抛出异常，start_free返回0，end_free不置0就会出问题
                __TRACE_DEBUG("系统没有足够内存，自由链表没有足够内存，去以及空间配置器找内存\n");
                start_free = (char*)MallocAllocTemplate<0>::Allocate(bytes_to_get); // 山穷水尽，采用一级空间配置器
            }
            heap_size += bytes_to_get; // 调整heap_size
            end_free = start_free + bytes_to_get; // 一般至此，内存池已经有内存了，递归调用，给内存池分配内存，更新nobjs
            return ChunkAlloc(size, nobjs);
        }
    }

[Link 1]: https://blog.csdn.net/wei_cheng18/article/details/80378755
[70]: /images/20220523/bde61beffb944e4eb0d6a0027c40d9df.png
[70 1]: /images/20220523/5529ffc11a784755ac941549fe503650.png
[70 2]: /images/20220523/6229dd9c854e490b936753379114de3d.png
[70 3]: /images/20220523/79c4bf1263a245ccadc15b58713b7747.png
[70 4]: /images/20220523/2621a4a889e74d54bb974fa1329f0b77.png
[70 5]: /images/20220523/9ec815e280194025bac5c55a0b313aa6.png
[Link 2]: https://blog.csdn.net/wei_cheng18/article/details/78446551