STL之空间配置器

柔情只为你懂 2022-06-12 10:47 204阅读 0赞

最近在看侯捷老师写的STL源码剖析，想通过看优秀的代码来提高自己的编程水平。  
首先STL提供了六大组件，彼此可以套用使用。  
借助一张从书上截的图来表明：  
![这里写图片描述][SouthEast]  
Container通过Allocator来获取数据存储空间  
Algorithms通过迭代器来获取Container的内容，Functors可以协助Algorithms完成不同策略变化  
Adapter可以修饰或者套接Functor由此可见在STL中空间配置器是非常重要的。

简单分析下为什么需要使用空间配置器？  
使用空间配置器的原因就是为了解决外碎片  
![这里写图片描述][SouthEast 1]  
而且我们在使用STL容器的时候，比如vector我们可能需要不断的去申请内存，频繁的申请小块内存效率是非常低的。而STL是非常重视效率的，因此就有了空间配置器来解决这个问题。

STL空间配置器的框架设计

![这里写图片描述][SouthEast 2]  
![这里写图片描述][SouthEast 3]

首先设计一级空间配置器  
它使用了 \_\_malloc\_alloc\_template一个模板类来实现一级空间配置器的功能，在这里我可以根据STL给出的简单的模拟实现它，通过这种方式来了解它到底是如何实现的。

typedef void(*HANDLE_FUNC)();//HANDLE_FUNC代表一个函数指针
    template <int inst>
    class __Malloc_Alloc_Template
    {
    public:
        //static void(*set_malloc_handler(void(*f)()))()源码给出的形式,返回值和参数类型都是函数指针
        static HANDLE_FUNC SetMallocHandler(HANDLE_FUNC f)//既然在OOM_MALLOC里使用了句柄，那么就要设置
        {
            HANDLE_FUNC old = _handle;
            _handle = f;
            return old;
        }//用户来设置句柄，但是不建议，容易陷入死循环
        static void* OOM_Malloc(size_t size)
        {
            while (1)
            {
                if (_handle == 0)
                {
                    throw bad_alloc();
                }
                _handle();//如果设置了句柄，那么就会一直循环，直到申请到了，才会退出
                void *ret = malloc(size);
                if (ret)
                {
                    return ret;
                }
            }
        }
        static void* Allocate(size_t size)//直接调用malloc
        {
            void*ret = malloc(size);
            if (ret == 0)//表示一级空间配置器调用malloc没有申请到内存
            {
                ret = OOM_Malloc(size);//失败了并没有直接返回，而是继续调用OOM_MALLOC
            }
        }
        static void Deallocate(void* p, size_t n)//释放一级空间配置器申请的内存
        {
            free(p);
        }
    private:
        static HANDLE_FUNC _handle;
    };

上述就是简单的一级空间配置器的设计，当然STL设计的还有realloc在这里我只是简单的模拟实现以下，没有写realloc;

二级空间配置器的设计相较于一级空间配置器的实际就复杂一些  
![这里写图片描述][SouthEast 4]  
他申请内存并不是直接先问系统索要见下图的过程：  
![这里写图片描述][SouthEast 5]  
小细节：  
![这里写图片描述][SouthEast 6]

template <bool threads, int inst>
    class __DefaultAlloceTemplate { 
    public:
        static  size_t FREELIST_INDEX(size_t bytes)//计算这n个字节对应的自由链表的下标
        {
            return (((bytes)+__ALIGN - 1) / __ALIGN - 1);//STL非常注重效率
        }
        static size_t  ROUND_UP(size_t bytes)
        {
            return ((bytes)+__ALIGN - 1)&(~(__ALIGN - 1));//变成8的倍数
        }
        static char* Chunk(size_t n, size_t &nobjs)
        {
            //__TRACE_DEBUG("到memory pool期望取%u个%u bytes对象\n", nobjs, n);
            size_t total_bytes = n*nobjs;//向内存池索要的总字节数，分三种情况
            size_t left_bytes = _endfree - _startfree;//内存池中剩余的字节数
            if (total_bytes <= left_bytes)//说明一次就可以直接从内存池中拿到n*nobjs个字节
            {
                //__TRACE_DEBUG("memory pool拥有足够%u个对象的内存\n", nobjs)
                char *ret = _startfree;
                _startfree += total_bytes;
                return ret;
            }
            else if (left_bytes>n)//说明内存池中不足n*njobs个字节，但是足够n个
            {
                //__TRACE_DEBUG("memory pool只有%u个对象的内存\n", nobjs);
                nobjs = left_bytes/n; //实际能申请nobjs个
                total_bytes = n*nobjs;
                char *ret = _startfree;
                _startfree += total_bytes;
                return ret;
            }
            else//说明内存池中连n个都不够
            {
                //__TRACE_DEBUG("memory pool连一个%ubytes的对象都没有\n", n);
                if (left_bytes > 0)//说明内存池中还有剩余的虽然不足n个字节，必须先处理掉，才能给内存池重新分配空间
                {
                    size_t index = FREELIST_INDEX(left_bytes);
                    ((Obj*)(_startfree))->free_list_link = _freeList[index];
                    _freeList[index] = (Obj*)_startfree;
                }
                //说明要为狭义内存池分配空间了
                size_t byteToGets = total_bytes * 2 + ROUND_UP(_heapsize >> 4);
                //__TRACE_DEBUG("到系统申请%u bytes给memory pool\n", byteToGets);
                _startfree = (char*)malloc(byteToGets);
                if (_startfree == NULL)//说明内存已经吃紧，到更大的自由链表中去获取空间
                {
                    //__TRACE_DEBUG("到系统申请内存失败\n", n);
                    for (size_t i = FREELIST_INDEX(n); i < __NFREELISTS; ++i)
                    {
                        if (_freeList[i])
                        {
                            Obj*ret = _freeList[i];
                            _freeList[i] = ret->free_list_link;
                            _startfree = (char*)ret;
                            _endfree = _startfree + (i + 1)*__ALIGN;
                            return Chunk(n, nobjs);
                        }
                    }
                    //如果还是没有分配到内存，也不要灰心，继续调用一级空间配置器
                    _startfree = (char*)__Malloc_Alloc_Template<0>::Allocate(byteToGets);
                }
                //说明一定分配内存成功了
                _heapsize = _heapsize + byteToGets;
                _endfree = _startfree + byteToGets;
                return Chunk(n, nobjs);
            }
        }
        static void* Allocate(size_t n)
        {
            if (n > __MAX_BYTES)
            {
                return __Malloc_Alloc_Template<0>::Allocate(n);
            }
            //__TRACE_DEBUG("调用二级空间配置器申请%u bytes\n", n);
            size_t index = FREELIST_INDEX(n);//计算在自由链表下对应的下标
            if (_freeList[index])//说明自由链表不空
            {
                //__TRACE_DEBUG("在自由链表第%d个位置取一个对象\n", index);
                Obj *ret = _freeList[index];
                _freeList[index] = ret->free_list_link;
                return ret;
            }
            //说明自由链表对应的位置没有存储空间，此时我们需要去问内存池索要；
            else
            {
                return Refill(ROUND_UP(n));
            }
        }
        static char* Refill(size_t n)//实际上返回我们需要的，并且将剩余的挂在相应的自由链表下面
        {
            size_t nobjs = 20;
            char *ret=Chunk(n, nobjs);//真正向内存池索要数据
            //__TRACE_DEBUG("到memory pool申请到%u个对象，一个返回使用，剩余挂到自由链表下面\n", nobjs);
            if (nobjs == 1)
            {
                return ret;
            }
            else
            {
                size_t index = FREELIST_INDEX(n);
                _freeList[index] = (Obj*)(ret+n);
                Obj*cur = _freeList[index];
                for (size_t i = 2; i < nobjs; ++i)
                {
                    Obj*next =(Obj*)((char*)cur+n);
                    cur->free_list_link = next;
                    cur = next;
                }
                cur->free_list_link = NULL;
                return ret;
            }
        }
        static void Deallocate(void* ptr, size_t n)
        {
            if (n > __MAX_BYTES)
            {
                __Malloc_Alloc_Template<0>::Deallocate(ptr, n);
            }
            else//并没有真正的释放，而是挂在了自由链表下面
            {   
                size_t  index = FREELIST_INDEX(n);
                //__TRACE_DEBUG("将释放的对象挂到freeList[%u]\n", index);
                ((Obj*)ptr)->free_list_link = _freeList[index];
                _freeList[index] = (Obj*)ptr;
            }
        }
    private:
        enum { __ALIGN = 8 };
        enum { __MAX_BYTES = 128 };
        enum { __NFREELISTS = __MAX_BYTES / __ALIGN };
        union Obj {
            union Obj * free_list_link;
            char client_data[1];    /* The client sees this. */
        };//管理自由链表
    
        //狭义内存池
        static Obj*_freeList[__NFREELISTS];
        static char*_startfree;
        static char*_endfree;
        static size_t _heapsize;
    };

[SouthEast]: /images/20220612/5a5eec8123d344ea994cf5e1840ad2fe.png
[SouthEast 1]: /images/20220612/ba840b4c3dc3452ab853227cb319c762.png
[SouthEast 2]: /images/20220612/2e69107f5dbc465f884bbf64f2659e07.png
[SouthEast 3]: /images/20220612/66f53b16469044d1b5c70adc85d53cad.png
[SouthEast 4]: /images/20220612/c60d3706fac840af985c82ce0acf3a40.png
[SouthEast 5]: /images/20220612/19d3885f66044602b8551a1c195d3719.png
[SouthEast 6]: /images/20220612/75c40ad4edda48af93eb1d9575dff9e0.png