STL源码-配置器(allocator)

2019年4月15日 0 条评论 300 次阅读 0 人点赞

完整代码见: LiTianxiong/Standard-Template-Library

配置器(allocator)作用

配置器为容器配置空间, 一般情况下是在内存中配置空间, 但是如有必要也可以自定义配置器, 让它从磁盘等位置获取空间

配置器标准接口

四部分, 配置空间, 构造对象, 析构对象, 释放空间

template<class T>
    class Allocator
    {
        public:
        typedef T               value_type;
        typedef T*              pointer;
        typedef const T*        const_pointer;
        typedef T&              reference;
        typedef const T&        const_reference;
        typedef size_t          size_type;
        typedef ptrdiff_t       difference_type;

        template<class U>
            struct rebind
            {
                typedef Allocator<U> other;
            };

        pointer allocate(size_type n, const void* hint=0);

        void deallocate(pointer p, size_type n);

        void construct(pointer p, const T& value) ;

        void destroy(pointer p) ;

        pointer address(reference x) ;

        const_pointer address(const_reference x) ;

        size_type max_size() const ;
    };

构造与析构

构造

只有一个版本, 直接通过指针调用其构造函数

    inline void _construct(T1* p, const T2& value)
    {
        ::new (p) T1(value);
    }

析构

析构函数有两个版本, 针对trivial的类型进行了优化, 这里说的trivial类型指的是没有自定义析构函数的类型;

有自定义析构函数意味着对象在析构时需要进行一些必要的工作, 例如释放内存等等, 对于这类对象我们必须要调用其析构函数;

而对于没有自定义析构函数的对象, 我们可以不必析构, 而直接释放其内存即可;

判断trivial

我这里直接使用了C++自带的type_traits库函数:

#include <type_traits>
...

bool is_trivial = std::is_trivially_destructible<decltype(*first)>::value;
template <typename T>
inline void _destroy(T* pointer)
{
    pointer->~T();
}

// destroy第二版本, 析构一个区间的对象
template <typename ForwardIterator>
    inline void _destroy(ForwardIterator first, ForwardIterator last)
{
    bool is_trivial = std::is_trivially_destructible<decltype(*first)>::value;
    if(is_trivial) {}
    else 
    {
        for(; first<last; ++first) _destroy(&*first);
    }
}

内存的配置与释放

SGI使用了两层配置器

对于大于128bytes的配置区块, 直接从堆中获取内存

对于小于128bytes的配置区块, 由于每次从系统中配置内存都需要额外的空间来管理配置的内存, 配置的内存越小, 这部分额外空间占比越大, 越显得浪费. 所以SGI使用了内存池管理这些碎片内存, 使用16个链表分别管理8, 16, 24...128大小的内存块, 每次申请小于等于128的内存时候, 从链表中取出相应的内存块来使用, 链表内存不够了, 在从内存池申请内存, 内存池不够了才会向系统申请内存;

一级配置器

    
    // 一级配置器
class base_alloc
{
    public:
    static void * allocate(size_t n)
    {
        void * result = ::operator new(n);
        return result;
    }
    static void deallocate(void * p, size_t)
    {
        ::operator delete(p);
    }

};

直接向系统申请内存

二级配置器

大于128直接调用以及配置器, 小于等于128从自由链表中获取空间

如果自由链表为空, 使用refill函数, refill将会从内存池中获取最多20个节点的空间, 返回一个, 然后将剩余的挂到自由链表上去供以后使用

释放空间也是一样, 大于128直接交给一级配置器处理, 否则将内存放回自由链表

// 辅助函数, 将bytes上调值8的倍数
static size_t ROUND_UP(size_t bytes)
{
    return ( (bytes+__ALIGN-1) & (~(__ALIGN-1)) );
}
// 辅助函数, 根据区块大小决定使用哪个free-list
static size_t FREELIST_INDEX(size_t bytes)
{
    return ((bytes+__ALIGN-1)/__ALIGN - 1);
}


static void * allocate(size_t n)
{
    obj * volatile * my_free_list;
    obj * result;

    if(n > (size_t)__MAX_BYTES) return base_alloc::allocate(n);

    my_free_list = free_list + FREELIST_INDEX(n);
    result = *my_free_list;
    if(nullptr == result)
    {
        void * r = refill(ROUND_UP(n));
        return r;
    }
    *my_free_list = result->free_list_link;
    return result;
}

static void deallocate(void *p, size_t n)
{
    obj * q = (obj *) p;
    obj * volatile * my_free_list;

    if(n > (size_t)__MAX_BYTES) 
    {
        base_alloc::deallocate(p, n);
        return ;
    }

    my_free_list = free_list + FREELIST_INDEX(n);
    q->free_list_link = *my_free_list;
    *my_free_list = q;
}

自由链表(free_list)

这里巧妙的运用了union的性质, 让一个union obj作为链表节点, 这样就不需要额外使用一个指针的空间, 而是直接使用让这个内存块作为一个union, union第一字段是一个obj*, 第二字段是一个char*;

从第一字段看, 这个union是一个obj*指针, 指向链表的下一节点

从第二字段看, 是一个指针, 指向本区块的内存

这这样相当于将区块内存直接当了链表指针用, 没有使用额外的空间来维护链表

union obj
{
    union obj * free_list_link;
    char client_data[1];
};

static obj * volatile free_list[__NFREELISTS];

refill

static void * refill(size_t n)
{
    int nobjs = 20;
    char * chunk = chunk_alloc(n, nobjs);
    obj * volatile * my_free_list;
    obj * result;
    obj * current_obj, * next_obj;
    int i;
    #ifdef DEBUG
    cout << "DEBUG refil" << endl;
    cout<< endl << (obj*)chunk << " " << nobjs << endl;
    #endif

    //只获得了一个区块
    if(nobjs == 1) return chunk;

    // 调整free_list, 纳入新节点
    my_free_list = free_list + FREELIST_INDEX(n);
    result = (obj*) chunk;

    *my_free_list = next_obj = (obj*)(chunk+n);
    for(i=1; ;++i)
    {
        current_obj = next_obj;
        next_obj = (obj*)((char*)next_obj+n);
        if(nobjs-1 == i)
        {
            current_obj->free_list_link = nullptr;
            break;
        }
        else current_obj->free_list_link = next_obj;

        #ifdef DEBUG
        cout << current_obj << " " << next_obj<< endl;
        #endif
    }
    return result;
}

内存池

内存池使用两个指针维护可用的内存

如果内存池中的内存不够了, 向系统申请空间, 申请的大小为所需要空间的两倍, 在加上一个heap_size>>4, heap_size为至今为止向系统申请的空间的总和, 这样做是为了让每次申请的空间都比上一次大一些, 减少向系统申请的次数.

如果向申请内存失败, 则将自由链表中的足够大的节点回内存池, 再次申请

如果自由链表中也没有空间了, 那叫只能抛出异常了

static char *start_free;
static char *end_free;
static size_t heap_size; // 作用见chunk_allo函数

        
// 配置一大块空间, 可容纳nobjs个大小为size的区块
// 如果空间不够但足够供应一个及一个以上的区块, 那就只供应能供应的数量, 并将nobj的值改变为供应数量
static char *chunk_alloc(size_t size, int &nobjs)
{
    #ifdef DEBUG
    cout << "chunk_alloc DEBUG" << endl;
    cout<< endl << size << " " << nobjs << endl;
    cout << "(" << (void*)start_free << "-" << (void*)end_free << endl;
    #endif

    char * result;
    size_t total_bytes = size*nobjs;
    size_t bytes_left = end_free - start_free;

    if(bytes_left >= total_bytes)
    {
        result = start_free;
        start_free += total_bytes;
        return result;
    }
    else if(bytes_left >= size)
    {
        nobjs = bytes_left/size;
        total_bytes = size*nobjs;
        result = start_free;
        start_free += total_bytes;
        return result;
    }
    else 
    {
        //一个区块都无法提供
        // 需要新配置空间的大小=2倍请求的空间+一个数值
        // 其中ROUND_UP(heap_size>>4)这一项的目的是让每次配置空间都比之前大一些
        size_t bytes_to_get = 2*total_bytes + ROUND_UP(heap_size>>4);
        #ifdef DEBUG
        cout << "DEBUG chunk" << endl;
        cout<< endl << "bytetoget" << bytes_to_get << " "  << endl;
        #endif
        // 让内存池中的空间利用起来(放到free_list中)
        if(bytes_left > 0)
        {
            // volatile 锁住 *my_free_list, 也就是free_list数组中的个元素
            // 网上说是为了多线程情况
            // 但volatile并不能保证多线程下不被别的线程改变, 可能是个历史遗留问题
            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;
        }

        // 从堆中获取内存
        try
        {
            start_free = (char*) ::operator new(bytes_to_get);
        }
        // catch(std::bad_alloc)
        catch(std::bad_alloc e)
        {
            int i;
            obj *volatile *my_free_list, *p;
            for(i=size; i<=__MAX_BYTES; i+=__ALIGN)
            {
                my_free_list = free_list + FREELIST_INDEX(i);
                p = *my_free_list;
                if(p != nullptr)
                {
                    *my_free_list = p->free_list_link;
                    start_free = (char*)p;
                    end_free = start_free+i;
                    #ifdef DEBUG
                    cout << "ddd" <<endl;   
                    #endif
                    return chunk_alloc(size, nobjs);
                }
            }
            end_free = 0;
            throw e;
        }
        heap_size += bytes_to_get;
        end_free = start_free+bytes_to_get;
        return chunk_alloc(size, nobjs);

    }
}

litmxs

这个人太懒什么东西都没留下

文章评论(0)