STL in C++11 (Allocator 5)

我們現(xiàn)在終于要結(jié)束分配器部分的內(nèi)容了叁怪，這是 Allocator 的最后一篇文章了。上次我們還留下了兩個函數(shù)沒有實現(xiàn): refill() 與 chunk_alloc()辜膝。

refill(std::size_t block_size)
refill()在 free_list 的內(nèi)存塊不足時使用，用來為 free_list 填充內(nèi)存塊。其中 block_size 代表需要填充的塊的大小篡诽。我們接下來看一下代碼吧：

template<typename T>
T *free_list_allocator<T>::refill(std::size_t block_size)
{
    //默認分配16塊內(nèi)存
    std::size_t num = 16;
    //chunk指向新內(nèi)存的起始地址
    char *chunk = chunk_alloc(block_size, num);   //num passed by reference

    if (num == 1) {
        return reinterpret_cast<T*>(chunk);
    }

    auto target_free_list = free_list + free_list_index(block_size);
    //第一塊內(nèi)存作為結(jié)果返回
    T *result = reinterpret_cast<T*>(chunk);
    --num;

    obj *cur_obj, *next_obj;
    chunk += block_size;
    cur_obj = reinterpret_cast<obj*>(chunk);
    cur_obj->free_list_link = nullptr;
    --num;
    *target_free_list = cur_obj;

    while (num > 0)
    {
        chunk += block_size;
        next_obj = reinterpret_cast<obj*>(chunk);
        next_obj->free_list_link = nullptr;
        --num;
        cur_obj->free_list_link = next_obj;
        cur_obj = next_obj;
    }

    return result;
}

refill() 其實并不負責(zé)實際的內(nèi)存申請，而是交給chunk_alloc負責(zé)榴捡。refill() 只需獲取指向新內(nèi)存的指針就可以了杈女。而 num 由于是引用傳遞，在調(diào)用 chunk_alloc 后就代表實際上獲取的內(nèi)存塊的數(shù)量吊圾。如果只有1塊的話碧信，我們直接返回就行了。

如果我們成功獲取多塊內(nèi)存街夭，就需要將第2塊之后的內(nèi)存插入到對應(yīng)的 free_list 當(dāng)中砰碴。具體的分塊操作就是每次對指針自增 block_size，這樣每次指針就是每塊內(nèi)存的首地址了板丽。

再來看具體代碼

    obj *cur_obj, *next_obj;
    chunk += block_size;
    cur_obj = reinterpret_cast<obj*>(chunk);
    cur_obj->free_list_link = nullptr;
    --num;
    *target_free_list = cur_obj;

cur_obj 表示當(dāng)前塊的首指針呈枉， next_obj 則指向下一塊內(nèi)存。我們首先對 chunk 加上 block_size埃碱，這時chunk就指向第二塊內(nèi)存了猖辫，再將 chunk 賦值給 cur_obj。同時我們?yōu)橄鄳?yīng)的 free_list 添加內(nèi)存塊砚殿，將 target_free_list 內(nèi)的元素設(shè)為 cur_obj啃憎。注意此時cur_obj是 target_free_list的第一個內(nèi)存塊。

接下來的循環(huán)代碼：

while (num > 0)
{
    chunk += block_size;
    next_obj = reinterpret_cast<obj*>(chunk);
    next_obj->free_list_link = nullptr;
    --num;
    cur_obj->free_list_link = next_obj;
    cur_obj = next_obj;
}

我們每次都先將 chunk 指針往后移 block_size 個單位似炎，用 next_obj 指向它辛萍。同時將 cur_obj 的 free_list_link 設(shè)為 next_obj（前一個內(nèi)存塊指向后一個內(nèi)存塊）。借助這個循環(huán)羡藐，我們就將chunk指向的內(nèi)存全部加入到 free_list 當(dāng)中了贩毕。

chunk_alloc(std::size_t block_size, std::size_t& num)

template<typename T>
char *
free_list_allocator<T>::chunk_alloc(std::size_t block_size, std::size_t& num)
{
    char *result;
    /*
    total_byte: 總共需要的byte
    left_byte: 內(nèi)存池剩余的byte
    */
    std::size_t total_byte = block_size * num;
    std::size_t left_byte = end_pool - start_pool;

    if (left_byte > total_byte)
    {
        result = start_pool;
        start_pool += total_byte;
        return result;
    }
    else if (left_byte > block_size)
    {
        //num: 實際分配的塊的個數(shù)
        num = left_byte / block_size;
        result = start_pool;
        start_pool += num * block_size;
        return result;
    }
    else
    {
        //內(nèi)存池新大小
        std::size_t byte_to_get = 2 * total_byte + round_up(heap_size >> 4);

        if (left_byte > 0) {
            //將最后的空間分配出去
            obj *new_head = reinterpret_cast<obj*>(start_pool);
            auto target_free_list = free_list + free_list_index(left_byte);

            new_head->free_list_link = *target_free_list;
            *target_free_list = new_head;

            start_pool = end_pool = nullptr;
        }

        start_pool = static_cast<char*>(malloc(byte_to_get));
        if (start_pool == nullptr) {
            obj **target_free_list;
            obj *head;      //指向 free_list 的第一個內(nèi)存塊

            /*
            遍歷塊大小大于 block_size 的 free_list 以
            獲取空閑的內(nèi)存塊加入到內(nèi)存池中
            */
            for (std::size_t i = block_size + ALIGN; i <= MAX_BLOCK_SIZE; i += ALIGN) {
                
                target_free_list = free_list + free_list_index(i);
                head = *target_free_list;

                if (head != nullptr) {
                    /*
                    如果有空閑塊則加入到內(nèi)存池中
                    */
                    *target_free_list = head->free_list_link;
                    start_pool = reinterpret_cast<char*>(head);
                    end_pool = start_pool + i;
                    return chunk_alloc(block_size, num);
                }

            }

            start_pool = reinterpret_cast<char*>(
                    malloc_allocator<T>::allocate(byte_to_get / sizeof(T)));
        }

        end_pool = start_pool + byte_to_get;
        heap_size += byte_to_get;
        return chunk_alloc(block_size, num);
    }
}

chunk_alloc()可以說是整個分配器中最復(fù)雜的函數(shù)了，但是耐下心來也是可以理解的仆嗦。chunk_alloc()負責(zé)向系統(tǒng)申請內(nèi)存辉阶，并且返回其首地址。

還記得在類中之前聲明的靜態(tài)變量嗎，現(xiàn)在正是使用它們的時候了

//內(nèi)存池起始位置
static char *start_pool;
//內(nèi)存池結(jié)束位置
static char *end_pool;
static std::size_t heap_size;

我們先考慮簡單的2種情況

if (left_byte > total_byte)
{
    result = start_pool;
    start_pool += total_byte;
    return result;
}
else if (left_byte > block_size)
{
    //num: 實際分配的塊的個數(shù)
    num = left_byte / block_size;
    result = start_pool;
    start_pool += num * block_size;
    return result;
}

當(dāng)有足夠的內(nèi)存時谆甜，便直接分配垃僚。將 start_pool 賦值給 result，同時 start_pool 后移 total_byte 單位规辱。如果內(nèi)存池剩余空間不足冈在，但是至少還能分配1個塊，我們就把剩余的空間盡可能分配出去按摘。通過 left_byte / block_size 計算最多還能分配多少塊包券。

但是當(dāng)內(nèi)存池連1個塊都分配不了時，就需要采取一些別的手段重新填充內(nèi)存池了炫贤。

//內(nèi)存池新大小
std::size_t byte_to_get = 2 * total_byte + round_up(heap_size >> 4);

if (left_byte > 0) {
    //將最后的空間分配出去
    obj *new_head = reinterpret_cast<obj*>(start_pool);
    auto target_free_list = free_list + free_list_index(left_byte);

    new_head->free_list_link = *target_free_list;
    *target_free_list = new_head;

    start_pool = end_pool = nullptr;
}

我們首先計算要重新給內(nèi)存池分配多少空間(byte_to_get)溅固。其中heap_size用來額外增加新內(nèi)存池大小，避免內(nèi)存池頻繁重新分配兰珍。heap_size的值根據(jù) byte_to_get 逐漸增加侍郭。接下來我們將內(nèi)存池中剩余的內(nèi)存加入到 free_list 中（不能浪費），這個時候內(nèi)存池已經(jīng)空空如也了掠河。下一步就要正式請求內(nèi)存了亮元。

start_pool = static_cast<char*>(malloc(byte_to_get));
if (start_pool == nullptr) {
    obj **target_free_list;
    obj *head;      //指向 free_list 的第一個內(nèi)存塊

    /*
    遍歷塊大小大于 block_size 的 free_list 以
    獲取空閑的內(nèi)存塊加入到內(nèi)存池中
    */
    for (std::size_t i = block_size + ALIGN; i <= MAX_BLOCK_SIZE; i += ALIGN) {
                
        target_free_list = free_list + free_list_index(i);
        head = *target_free_list;

        if (head != nullptr) {
            /*
            如果有空閑塊則加入到內(nèi)存池中
            */
            *target_free_list = head->free_list_link;
            start_pool = reinterpret_cast<char*>(head);
            end_pool = start_pool + i;
            return chunk_alloc(block_size, num);
        }

    }

    start_pool = reinterpret_cast<char*>(
        malloc_allocator<T>::allocate(byte_to_get / sizeof(T)));
}

我們借助 malloc() 申請空間。如果 malloc 也無法得到內(nèi)存的話會返回 nullptr唠摹。要是malloc也不行爆捞，那么我們現(xiàn)在該怎么辦呢？答案是尋找 free_list 中空閑的內(nèi)存塊勾拉。也許 free_list 中還有未被使用的內(nèi)存煮甥，我們可以嘗試把它們加入到內(nèi)存池中。

所以我們尋找大于 block_size 的空閑塊藕赞，將它加入內(nèi)存池成肘。再遞歸調(diào)用自身返回。調(diào)用自身是為了重新分配內(nèi)存給用戶斧蜕。因為我們現(xiàn)在只是為內(nèi)存池重新獲取了空間双霍，還沒有返回用戶需要的內(nèi)存。（也就是接下來調(diào)用的 chunk_alloc 會執(zhí)行前2個 if 分支）

那么我們連空閑塊都沒有的話又該如何批销？我們這個時候使用 malloc_allocator 來分配內(nèi)存洒闸。malloc_allocator可以借助 oom_handler來處理內(nèi)存不足的情況（如果有的話），亦或者直接拋出 bad_alloc 異常由用戶自己處理风钻。

在最后顷蟀，如果內(nèi)存池分配成功的話，便重新設(shè)置 end_pool 與 heap_size骡技，同時遞歸返回。

end_pool = start_pool + byte_to_get;
heap_size += byte_to_get;
return chunk_alloc(block_size, num);

好了，到現(xiàn)在有關(guān) Alloctor 的所有內(nèi)容都講完了布朦。我們已經(jīng)實現(xiàn)了自己的分配器 free_list_allocator囤萤，我們接下來可以借助它為接下來的容器分配內(nèi)存。下次應(yīng)該就是要介紹我們的第一個容器 vector 了是趴。

如果喜歡的話可以點個贊啊~

最后附上本篇文章的代碼地址：free_list_allocator.h

以及github地址：https://github.com/Puppas/STL-in-Cpp11