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

秒速五厘米 2022-05-24 03:47 145阅读 0赞

### 空间配置器 ###

**STL的六大组件：容器、迭代器、适配器、仿函数、算法、空间配置器。**  
　　关于容器、迭代器、适配器、仿函数和算法，我们之前都有一定的了解。至于空间配置器，它是负责空间配置与管理，它是隐藏在一切组件背后的东西，因为STL的整个操作对象都在容器中，而容器的实现是一定需要空间配置器的。  
　　  
　　SGI STL的配置器与众不同，与标准规范也不同，其名称是alloc，而且不接受任何参数。SGI也定义了一个符合部分标准，名为allocator的配置器，但SGI自己从未使用过，也不建议我们使用。主要是因为效率不高，他仅仅是把C++的`::operator new和::operator delete`做了一层薄薄的封装。  
　　  
　　SGI有自己的效率高的配置器供其内部使用。我们习惯的C++中的内存配置操作和释放操作是分为两步的：

*  对于内存配置，首先调用::operator new配置内存，再调用构造函数来构造对象内容。
 *  对于释放内存，首先调用析构函数，将对象析构，再调用::operator delete将空间释放。

**为了精密分工，将这两步操作区分开来，内存配置由alloc:allocate()负责，内存释放由alloc:deallocate()负责；对象构造由::construct()负责，对象析构由::destory()负责。**  
　  
对于空间配置和空间释放，再设计时需要考虑如下问题：

1.  小块内存带来内存碎片的问题；
2.  小块内存频繁申请会带来性能问题；malloc在开辟空间的时候，空间会带有一些附加的信息，这样，如果频繁申请小块内存，这些额外的信息会带来很大的负担；
3.  容易造成内存泄漏的问题；
4.  代码复用率低；
5.  如果申请空间失败，缺少相应的应对措施；

**SGI STL中的空间配置器主要分为两级**，一级空间配置器适用于申请大于128字节的空间，直接向系统申请；如果小于128字节，则去内存池中申请。一级空间配置器主要是封装了malloc和free，增加了\_malloc\_alloc\_oom\_handle处理机制。这里主要介绍一级空间配置器，二级空间配置器下次介绍。

### STL中的源码： ###

template <int inst>
    class __malloc_alloc_template {
    
    private:
    
    static void *oom_malloc(size_t); //函数声明
    
    static void *oom_realloc(void *, size_t);  //函数声明
    
    #ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG
        static void (* __malloc_alloc_oom_handler)();
    #endif
    
    public:
    
    static void * allocate(size_t n) //申请空间，主要是对malloc的封装
    {
        void *result = malloc(n);
        if (0 == result) result = oom_malloc(n); //如果申请失败，就调用oom_malloc函数
        return result;
    }
    
    static void deallocate(void *p, size_t /* n */)  //释放空间，对free的封装
    {
        free(p);
    }
    
    static void * reallocate(void *p, size_t /* old_sz */, size_t new_sz)  // 主要是对realloc的封装，扩大空间
    {
        void * result = realloc(p, new_sz);
        if (0 == result) result = oom_realloc(p, new_sz);  //如果申请失败，调用oom_realloc函数
        return result;
    }
    
    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
    
    #ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG
    template <int inst>
    void (* __malloc_alloc_template<inst>::__malloc_alloc_oom_handler)() = 0;
    #endif
    
    template <int inst>
    void * __malloc_alloc_template<inst>::oom_malloc(size_t n) //如果malloc失败，那么一定是空间不够，
                                                      //此时，需要调用用户写的处理函数，释放掉不用的空间
    {
        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 <int inst>
    void * __malloc_alloc_template<inst>::oom_realloc(void *p, 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 = realloc(p, n);
            if (result) return(result);
        }
    }

看一下这段代码`static void (* set_malloc_handler(void (*f)()))()`  
首先这是一个函数指针，函数名为`set_malloc_handler`  
函数的参数为`void (*f)()`，显然也是一个函数指针  
去掉函数名和参数后，剩下的返回值`static void (*)()`，显然还是一个函数指针  
所以这个函数指针，它指向的函数的返回值和参数都是一个函数指针。

我们画一个图来理清整体思路：  
![这里写图片描述][70]

下面是我们的模拟实现：

#include <malloc.h>
    #include <iostream>
    using namespace std;
    
    typedef void(*pMallocHandle)();  //为了方便编写代码，定义pMallocHandle为“没有参数，返回值为void*”的函数指针类型
    template <int inst>
    class MallocAllocTemplate
    {
    public:
        static void* Allocate(size_t size)  //申请空间
        {
            void* result = malloc(size);
            if (result == NULL)
                result = OOM_Malloc(size);
            return result;
        }
    
        static void DeAllocate(void* p/*, size_t size*/)    //释放空间
        {
            free(p);
        }
    
        static void* ReAllocate(void* p/*, size_t oldSize*/, size_t newSize)
        {
            void* result = realloc(p, newSize);
            if (NULL == result)
                result = OOM_Realloc(p, newSize);
            return result;
        }
    
        static pMallocHandle setMallocHandle(pMallocHandle mallocHandle)
        {
            pMallocHandle old = _mallocHandle;
            _mallocHandle = mallocHandle;
            return old;
        }
    private:
    
        static void* OOM_Malloc(size_t size)
        {
            pMallocHandle mallocHandle;
            for (;;)
            {
                mallocHandle = _mallocHandle;
                if (mallocHandle == NULL)
                    throw std::bad_alloc();
                mallocHandle();
                void* res = malloc(size);
                if (res)
                    return res;
            }
        }
    
        static void* OOM_Realloc(void* p, size_t size)
        {
            pMallocHandle mallocHandle;
            for (;;)
            {
                mallocHandle = _mallocHandle;
                if (mallocHandle == NULL)
                    throw std::bad_alloc();
                mallocHandle();
                void* res = realloc(p, size);
                if (res)
                    return res;
            }
        }
    private:
        static pMallocHandle _mallocHandle;
    };
    pMallocHandle MallocAllocTemplate<0>::_mallocHandle = NULL;
    //测试函数，测试代码是否可以运行成功
    void Handle()
    {           //我设置的内存不够的处理函数，再此并没有具体的释放别的内存，只是为了说明问题
        cout << "空间不足" << endl;
    }
    typedef MallocAllocTemplate<0> MallocAlloc;
    void test()
    {
        int* p = (int*)MallocAlloc::Allocate(sizeof(int)* 5);
        for (int i = 0; i < 5; i++)
            p[i] = i;
        int* tmp = (int*)MallocAlloc::ReAllocate(p, sizeof(int)* 10);
        p = tmp;
        for (int i = 0; i < 10; i++)
            p[i] = i;
        MallocAlloc::DeAllocate(p);
    
        MallocAlloc::setMallocHandle(Handle);
        p = (int*)MallocAlloc::Allocate(191234456789);
        MallocAlloc::DeAllocate(p);
    }

关于更为精彩的二级空间配置器，下次再做了解。

[70]: /images/20220524/2524ab2e7be64646986bcebdc8ca5080.png