305-STL的空间配置器(1)-蒲公英云

在这里插入图片描述

头文件专门用于管理内存，内存的申请和释放（我们可以想象成operator new）
头文件，专门管理某个内存空间中的构建或者析构对象。
头文件是对大块内存的填充和拷贝

在这里插入图片描述
在多线程情况下，需要加锁和解锁。

当这个内存块的大小大于128字节，我们认为这个块足够大，把它交给第一级配置器（直接使用malloc和free）去配置。
当这个内存块的大小小于128字节，我们认为这个块小，为了降低额外负担（我们malloc分配一块内存时，真实的情况是，系统分配的内存大小远大于我们申请的大小，包含了4字节的上越界标记，4字节的下越界标记和28字节的头部信息，造成内存和时间效率降低），，我们把它交给内存池，第二级配置器。
在这里插入图片描述

封装第一级配置器

包装了C语言的malloc ,free , realloc

#ifndef YHP_ALLOC_H
#define YHP_ALLOC_H
#include<iostream>
namespace yhp
{
#if 0
#include<new>
#define __THROW_BAD_ALLOC throw std::bad_alloc;
#elif !defined(__THREAD_BAD_ALLOC)//如果没有定义 ，就打印内存溢出 
//#include<iostream>
#define __THROW_BAD_ALLOC std::cerr<<"out of memory"<<std::endl; exit(1)
#endif
//第一级配置器 
template<int inst>
class __malloc_alloc_template
{
private:
    static void *oom_malloc(size_t n)//分配n个空间 
    //要么能申请到空间然后走人，要么抛出异常 
    {
        void * result = NULL;
        void (*my_malloc_handler)() = NULL;
        for(;;)//无限循环 
        {
            my_malloc_handler = __malloc_alloc_oom_handler;
            if(NULL == my_malloc_handler)
            {
                __THROW_BAD_ALLOC;//调用宏，抛出异常 
            }
            (*my_malloc_handler)();
//回调函数，1、释放更多的空间2、指明新的释放函数3、如果没有指明新的释放函数把程序结束掉 
            result = malloc(n);
            if(result != NULL)
            {
                return result;//成功了，内存的返回 
            }
        }
    }
    static void *oom_realloc(void *p,size_t new_sz)//追加内存的分配 
    {
        void * result = NULL;
        void (*my_malloc_handler)() = NULL;
        for(;;)
        {
            my_malloc_handler = __malloc_alloc_oom_handler;
            if(NULL == my_malloc_handler)
            {
                __THROW_BAD_ALLOC;
            }
            (*my_malloc_handler)();
            result = realloc(p,new_sz);
            if(result != NULL)
            {
                return result;
            }
        }
    }
    static void (*__malloc_alloc_oom_handler)();//函数指针 
public:
    static void *allocate(size_t n)//n是字节个数，不是元素的个数，内存的分配 
    {
        void *result = malloc(n);
        if(NULL == result)
        {
            result = oom_malloc(n);
        }
        return result;
    }
    static void deallocate(void *p,size_t n)//释放内存空间 
    {
        free(p);
    }
    static void *reallocate(void *p,size_t old_sz,size_t new_sz)//追加内存空间 
    {
        void *result = realloc(p,new_sz);
        if(NULL == result)
        {
            result = oom_realloc(p,new_sz);
        }
        return result;
    }
    static void (*set_malloc_handler(void (*f)()) )() 
    {
        void (*old)() = __malloc_alloc_oom_handler;
        __malloc_alloc_oom_handler = f;
        return old;
    }
};
template<int inst>
void (*__malloc_alloc_template<inst>::__malloc_alloc_oom_handler)() = NULL;
///
typedef __malloc_alloc_template<0>   malloc_alloc;

测试代码如下
在这里插入图片描述

如果我们在程序的运行过程中，内存不足了怎么办？

进入主函数之前，p1,p2指向相应的申请的内存空间。
在这里插入图片描述
我们写了一个函数yhp，把p1释放掉，把第二个函数rj放进去，
rj这个函数的作用是释放p2，如果释放空间后，把空放进去。

然后我们书写主函数

在这里插入图片描述
运行程序，我们看到，首先调用set_malloc_handler，把这个函数指针指向hp这个函数，申请空间的时候，调动malloc，如果我把result置为空，要调动oom_malloc，my_malloc_handler获得了hp的指针，不为空，调动hp的函数释放更多的空间，把rj这个函数注册进去，假设我再把result置为空，没有申请到空间，my_malloc_handler获得了rj的指针，不为空，再调动rj的释放内存函数，malloc再申请，我们又给个result=0，my_malloc_handler变成了空，调动宏，打印了错误，程序退出，内存用完了。
也就是说，先开始估算这个程序所需要的内存，直接先占领，我的程序在运行的过程中，如果内存不足，通过oom_malloc，调动回调函数，首先指向hp函数，释放内存，再申请空间，释放内存，如果还要申请，为空了，就确实是内存用完了。
注意：rj的函数里直接置为空放进去。防止如果再调用回调函数，那个回调函数中又占用了空间，但是内存不足，从而造成了死循环。

第二级配置器

在这里插入图片描述

如下图，最上面的一排数字代表内存的大小。下排的数字代表数组的下标

在最开始的时候，都是空。假设我们需要12个字节，选取 1下标对应的16个字节的内存块，没有找到，我们就先malloc 16*20 *2=640个字节的内存空间，进行注水，提取出320字节，把16个字节给给用户，剩下19个16字节块变成一个块一个块，一个块大小为16个字节，以链表的形式，链起来，头结点指向1下标的位置，如果我们还需要16个字节，就使用链表的头删，
在这里插入图片描述
这样比malloc速度快多了，而且这16个字节是没有上越界下越界标记和头部信息的。
如果我们需要40个字节，下标4的位置为空，STL就要把剩下的320字节分了，40乘以20大于320,320除以40是8，刚好分配8个块出去。把第一个块给用户，剩下的字节划分为7个块，划分成一块一块大小为40字节，以链表的形式链到4下标的位置。如果我们又需要70字节，找到8下标，为空，池子里面没有水了，就再malloc 72x20x2个字节的内存块，注水，把池子分为一部分操作。

函数实现的解释

在这里插入图片描述

obj是一个联合体，类型成员

free_list

第二适配器的代码实现

//第二级适配器 
enum {
     __ALIGN = 8};//起始块的大小，8的倍数 
enum {
     __MAX_BYTES = 128};//最大字节个数是128 
enum {
     __NFREELISTS = __MAX_BYTES / __ALIGN }; //自由链的大小是16
template<bool threads,int ints>//是否是多线程 
class __default_alloc_template//默认空间配置器 
{
private:
    union obj//这个结构就是一个一个的块 
    {
        union obj * free_list_link;// 相当于next，链 
        char client_data[1];//客户 
    };
private:
    static obj * volatile free_list[__NFREELISTS];//从内存查，数组下标0 1 ... 15
    static char *start_free;//指向池子的开头 
    static char *end_free;//指向池子的结尾 
    static size_t heap_size;//累计从堆区申请的空间大小 
    static size_t ROUND_UP(size_t bytes)//变成8的倍数 
    {
        return (bytes + __ALIGN - 1) & ~(__ALIGN - 1);
    }
    static size_t FREELIST_INDEX(size_t bytes)//计算申请空间大小的对应块的大小，返回下标 
    {
        return (bytes + __ALIGN -1) / __ALIGN  - 1;
    }
    static char *chunk_alloc(size_t size,int &nobjs)//往池子里注水 
    {
    //                              16       20
        char *result = NULL;
        size_t total_bytes = size * nobjs; //总的大小 
        size_t bytes_left = end_free - start_free;//大小 
        if(bytes_left >= total_bytes) // 满足了20块
        {
            result = start_free;
            start_free = start_free + total_bytes;
            return result;
        }else if(bytes_left >= size) //不够20个块，看看能不能足够1块
        {
            nobjs = bytes_left / size;//新的块 
            total_bytes = size*nobjs; //新的大小 
            result = start_free;
            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(NULL == start_free)//通过malloc申请空间失败了 
            {
                obj * volatile * my_free_list = NULL;
                for(int i = size ; i <= __MAX_BYTES; i += __ALIGN )//每次加8，扫描 
                {
                    my_free_list = free_list + FREELIST_INDEX(i);
                    obj * p = *my_free_list;
                    if(p != NULL)//不为空 
                    {
                        *my_free_list = p->free_list_link;
                        start_free = (char*)p;
                        end_free = start_free + i;
                        return chunk_alloc(size,nobjs);//是原来池子上的内存 
                    }
                }
                start_free = (char*)malloc_alloc::allocate(bytes_to_get);
            }
            end_free = start_free + bytes_to_get;
            heap_size += bytes_to_get;
            return chunk_alloc(size,nobjs);
        }
    }
    static void *refill(size_t n) //把池子里的空间拿出来进行分块，链起来， n byte num ; n % 8 == 0;
    {
        int nobjs = 20;
        char *chunk = chunk_alloc(n,nobjs);//注水20个块 
        if(1 == nobjs)
        {
            return chunk;//?
        }
        obj * volatile * my_free_list = NULL;
        obj * result = (obj*)chunk;
        obj * current_obj = NULL, *next_obj = NULL;
        int i = 0;
        my_free_list = free_list + FREELIST_INDEX(n);
        *my_free_list = next_obj = (obj*)(chunk + n);
        for(i = 1; ; ++i)
        {
            current_obj = next_obj;
            next_obj = (obj*)((char*)next_obj + n);
            if(i == nobjs - 1)
            {
                current_obj->free_list_link = NULL;
                break;
            }
            current_obj->free_list_link = next_obj;
        }
        return result;
    }
public:
    static void *allocate(size_t n)// 申请空间，n byte num;
    {
        if(n > (size_t)__MAX_BYTES)//大于128 
        {
            return malloc_alloc::allocate(n);//调用第一级适配器 
        }
        obj * volatile * my_free_list = NULL;//二级指针 
        obj * result = NULL;//一级指针 
        my_free_list = free_list + FREELIST_INDEX(n); 
        result = *my_free_list;
        if(NULL == result)
        {
            void *r = refill(ROUND_UP(n));// n 12 = 16
            return r;
        }
        *my_free_list = result->free_list_link;
        return result;
    }
    static void deallocate(void *p,size_t n)//释放空间 
    {
        if(n > (size_t) __MAX_BYTES)
        {
            malloc_alloc::deallocate(p,n);
            return ;
        }
        obj *q = (obj*)p;//把块还回去 
        obj * volatile * my_free_list = free_list + FREELIST_INDEX(n);//12//16
        q->free_list_link = *my_free_list;
        *my_free_list = q;//把块链接起来 
        return ;
    } // malloc realloc , 
    static void *reallocate(void *p,size_t old_sz,size_t new_sz)//追加空间 
    {
        if(old_sz > __MAX_BYTES && new_sz > __MAX_BYTES)
        {
            return malloc_alloc::reallocate(p,old_sz,new_sz);
        }
        if(ROUND_UP(old_sz) == ROUND_UP(new_sz))// 12 14 // 16
        {
            return p;//足够了，不需要重新分配 
        }
        // old_sz < 128  new_sz < 128;
        //    >               <
        //   <                >
        size_t sz = old_sz < new_sz ? old_sz:new_sz;
        void *s = allocate(new_sz);//调动一级适配器 
        memmove(s,p,sz);
        deallocate(p,old_sz);//释放p 
        return s;
    }
};
template<bool threads,int ints>
typename __default_alloc_template<threads,ints>::obj * volatile
__default_alloc_template<threads,ints>::free_list[__NFREELISTS]={
    NULL}; 
template<bool threads,int ints>
char * __default_alloc_template<threads,ints>::start_free = NULL;
template<bool threads,int ints>
char * __default_alloc_template<threads,ints>::end_free = NULL;
template<bool threads,int ints>
size_t __default_alloc_template<threads,ints>::heap_size = 0;

书写

#ifndef YHP_CONSTRUCT_H
#define YHP_CONSTRUCT_H
#include"yhp_iterator.h"
#include"yhp_type_traits.h"
namespace yhp
{
template<class T1,class T2>
inline void construct(T1 *p,const T2 &val)//带参数的构造函数 
{
    new(p) T1(val);//构建对象并初始化，定位new 
}
template<class T>
inline void construct(T *p)//不带参数的构造函数 
{
    new(p)  T();
}
template<class T>
inline void destroy(T *p)//销毁函数 
{
    p->~T();
}
template<class _FI>
inline void destroy(_FI _F, _FI _L)
{
    __destroy(_F,_L,value_type(_F));
}
template<class _FI,class T>
inline void __destroy(_FI _F,_FI _L , T *)
{
    __type_traits<T>();
    typedef typename __type_traits<T>::has_trivial_destructor  dest;
    __destroy_aux(_F,_L,dest());
}
template<class _FI>
inline void __destroy_aux(_FI _F,_FI _L , __true_type)
{
    }
template<class _FI>
inline void __destroy_aux(_FI _F,_FI _L , __false_type)
{
    for(; _F != _L; ++_F)
    {
        destroy(&*_F);
    }
}
}
#endif