C++的allactor

https://zhuanlan.zhihu.com/p/693267319

1 双层内存配置器

SGI设计了两层的配置器，也就是第一级配置器和第二级配置器。同时为了自由选择，STL又规定了 __USE_MALLOC 宏，如果它存在则直接调用第一级配置器，不然则直接调用第二级配置器。SGI未定义该宏，也就是说默认使用第二级配置器。

1.1 一级内存配置器

直接调用malloc和free来配置释放内存，简单明了。

template<int Inst>
class __MallocAllocTemplate //一级空间配置器
{
    typedef void (*OOM_HANDLER)();
private:
    //these funs below are used for "OOM" situations
    //OOM = out of memory
    static void* OOM_Malloc(size_t n); //function
    static void* OOM_Realloc(void *p, size_t newSZ); //function
    static OOM_HANDLER OOM_Handler; //function pointer

public:
    static void* Allocate(size_t n)
    {
        void* ret = malloc(n);
        if (ret == NULL)
            ret = OOM_Malloc(n);
        return ret;
    }

    static void Deallocate(void* p, size_t n)
    {
        free(p);
    }

    static void* Reallocate(void* p, size_t oldSZ, size_t newSZ)
    {
        void* ret = realloc(p, newSZ);
        if (ret == NULL)
            ret = OOM_Realloc(p, newSZ);
        return ret;
    }
    //static void (* set_malloc_handler(void (*f)()))()
    //参数和返回值都是函数指针void (*)()
    static OOM_HANDLER SetMallocHandler(OOM_HANDLER f)
    {
        OOM_HANDLER old = OOM_Handler;
        OOM_Handler = f;
        return old;
    }
};

//让函数指针为空
template<int Inst>
void (*__MallocAllocTemplate<Inst>::OOM_Handler)() = NULL;

template<int Inst>
void* __MallocAllocTemplate<Inst>::OOM_Malloc(size_t n)
{
    void* ret = NULL;
    void(*myHandler)() = NULL;
    for (;;)
    {
        myHandler = OOM_Handler;
        if (myHandler == NULL)
            throw bad_alloc();
        (*myHandler)();
        ret = malloc(n);
        if (ret != NULL)
            return ret;
    }
}

template<int Inst>
void* __MallocAllocTemplate<Inst>::OOM_Realloc(void* p, size_t newSZ)
{
    void* ret = NULL;
    void(*myHandler)() = NULL;
    for (;;)
    {
        myHandler = OOM_Handler;
        if (myHandler == NULL)
            throw bad_alloc();
        (*myHandler)();
        ret = realloc(p, newSZ);
        if (ret != NULL)
            return ret;
    }
}


typedef __MallocAllocTemplate<0> MallocAlloc; //一级空间配置重命名

1.2 二级内存配置器

1.如果用户需要的区块大于128，则直接调用第一级空间配置器
2.如果用户需要的区块大于128，则到自由链表中去找

如果自由链表有，则直接去取走
不然则需要装填自由链表（Refill）

1.2.1 自由链表

在这里插入图片描述
自由链表是一个指针数组，它的数组大小为16，每个数组元素代表所挂的区块大小，比如free _ list[0]代表下面挂的是8bytes的区块，free _ list[1]代表下面挂的是16bytes的区块…….依次类推，直到free _ list[15]代表下面挂的是128bytes的区块

同时我们还有一个被称为内存池地方，以start _ free和 end _ free记录其大小，用于保存未被挂在自由链表的区块，它和自由链表构成了伙伴系统。

1.2.2 工作原理

如果用户需要是一块n字节的区块，且n <= 128（调用第二级配置器），此时Refill填充是这样的：

系统会自动将n字节扩展到8的倍数，再将RoundUP（n）传给Refill。
用户需要n字节，且自由链表中没有，因此系统会向内存池申请nobjs * n大小的内存块，默认nobjs=20
如果内存池大于 nobjs * n，那么直接从内存池中取出
如果内存池小于nobjs * n，但是比一块大小n要大，那么此时将内存最大可分配的块数给自由链表，并且更新nobjs为最大分配块数x （x < nobjs）
如果内存池连一个区块的大小n都无法提供，那么首先先将内存池残余的零头给挂在自由链表上，然后向系统heap申请空间，申请成功则返回，申请失败则到自己的自由链表中看看还有没有可用区块返回
如果连自由链表都没了最后会调用一级配置器。

3 自定义内存配置器

// TODO:为vector写一个内存配置器，当空间大于1000时直接从堆分配内存


#include <memory>
#include <vector>
#include <iostream>
 
// 自定义内存配置器
template <typename T>
class CustomAllocator : public std::allocator<T> {
public:
    // 分配内存
    T* allocate(std::size_t n) {
        if (n * sizeof(T) > 1000) {
            // 大于1000字节时，使用堆分配
            return static_cast<T*>(::operator new(n * sizeof(T)));
        } else {
            // 小于或等于1000字节时，使用默认分配
            return std::allocator<T>::allocate(n);
        }
    }
 
    // 释放内存
    void deallocate(T* p, std::size_t n) {
        if (n * sizeof(T) > 1000) {
            // 大于1000字节时，使用堆释放
            ::operator delete(p);
        } else {
            // 小于或等于1000字节时，使用默认释放
            std::allocator<T>::deallocate(p, n);
        }
    }
};
 
int main() {
    // 使用自定义内存配置器的vector
    std::vector<int, CustomAllocator<int>> vec;
    vec.push_back(1); // 应该使用默认分配方式（通常很小）
    vec.push_back(2); // 同上
    vec.resize(1024); // 应该使用堆分配方式（因为1024 * sizeof(int) > 1000）
    vec.resize(1); // 应该再次使用默认分配方式（因为1 * sizeof(int) <= 1000）
    return 0;
}