Lexer的設計--中(3)

設計一個小型的記憶體池以及鏈表

上一節擼到萬事俱備只欠真正的lex, 但是lex的作用是將源代碼轉化為Token流, 用什麼保存Token? 這就涉及到我們要接觸的第一個數據結構—鏈表, 雖然標準庫中很多容器都可以承擔鏈表的任務, 但是我說過出於鍛煉原因, 我會儘量不使用stl中的容器, 所以我決定自己擼一個鏈表出來, 既然之後大多數的容器都要自己擼, 乾脆連記憶體池也一併擼一個出來, 所以這一節的兩個目的就是 : 記憶體池以及基於這個記憶體池的鏈表.

我個人接觸記憶體池的時間不長, 準確的說我目前腦袋裡面只有兩中記憶體池的思路, 一種是sgi stl記憶體池,我之前有一篇文章專門對這種記憶體池做過講解, 但是這裡我會使用另外一種較為簡易的記憶體池模型, 因為我認為sgi stl準確來說可以支持頻繁地不同大小的記憶體分配, 而我這裡會使用一種簡化的思路, 使之每一個記憶體池只支持單一大小的記憶體分配. 這種記憶體池也是從別人那裡學過來的, 簡圖差不多是這樣.

然後源代碼差不多是這樣...

#ifndef FRED_MEMORYPOOL_H
#define FRED_MEMORYPOOL_H

#include <cstdio>
#include <cstdlib>
#include <vector>

template <typename T, size_t NumberForOneNode = 32>
class MemoryPool{
private:
    struct node{
        void* space;
        node* next;
    };
    node *head, *tail;
    size_t left;
    void* cur;

protected:
    MemoryPool():left(NumberForOneNode){
        tail = head = new node;
        head->next = 0;
        cur = head->space = static_cast<T*>(malloc(sizeof(T) * NumberForOneNode));
    }

    //Big three
    MemoryPool(const MemoryPool&) = delete;
    MemoryPool& operator=(const MemoryPool& rhs) = delete;
    ~MemoryPool();

    void* allocate();
};

template <typename T, size_t NumberForOneNode>
MemoryPool<T, NumberForOneNode>::~MemoryPool() {
    while(true) {
        if (head == tail) {
            free(head->space);
            delete head;
            return;
        }
        auto temp = head;
        head = head->next;
        free(temp->space);
        delete temp;
    }
}

template <typename T, size_t NumberForOneNode>
void* MemoryPool<T, NumberForOneNode>::allocate() {
    if(left--){
        auto re = cur;
        cur = reinterpret_cast<char*>(cur) +sizeof(T);
        return re;
    }

    left = NumberForOneNode;
    auto newNode = new node;
    newNode->next = 0;
    tail = tail->next = newNode;
    cur = newNode->space = static_cast<T*>(malloc(sizeof(T) * NumberForOneNode));
    allocate();
}

#endif //FRED_MEMORYPOOL_H

圖上的變數和代碼裡面的變數名字都是統一的, 很好理解...

這個記憶體池的最後一步, 是在這個記憶體池的基礎上, 再套一層封裝.

#ifndef FRED_ALLOCATOR_H
#define FRED_ALLOCATOR_H


#include "MemoryPool.h"

template <typename T, size_t NumberForOneNode = 32>
class Allocator : private MemoryPool<T, NumberForOneNode> {
private:
    void* buffer[NumberForOneNode];
    size_t left;

public:
    Allocator():left(0){};

    void* allocator(){
        if(left){
            return buffer[--left];
        }
        else{
            return MemoryPool<T, NumberForOneNode>::allocate();
        }
    }

    void deallocator(T* ptr){
       ptr->~T();
       if(left == NumberForOneNode){
            //full
            return;
       }       
        buffer[left++] = ptr;
    }
};

#endif //FRED_ALLOCATOR_H

思想其實很簡單, 就是如果有空間被送回, 並不直接交還給系統, 而是用這個叫做buffer的數組存著, 如果之後再有需要, 優先從數組中取, 其實這裡用vector要比buffer更好, 但是如果想要重利用的空間規模不大的話, buffer也夠用, 就算這個buffer也不會記憶體泄漏, 只是有一些空間被浪費了, 等到維護這個allocator的類卒了, 空間還是要被釋放的.

如果想看這個記憶體池的原版本實現, 可以看這裡

原版本實現

有了記憶體池, 根據我們的需求我們只需要一個鏈表.

#ifndef FRED_LINKLIST_H
#define FRED_LINKLIST_H

#include "MemoryPool/Allocator.h"

template <typename T>
class LinkList{
private:
    struct node{
        T item;
        struct node* next;
    };
    Allocator<node> allocator;
    node* head;
    node* cur;
    size_t size;

public:
    LinkList():head(0), cur(0), size(0){}
    LinkList(const LinkList&) = delete;
    LinkList& operator=(const LinkList&) = delete;
    ~LinkList(){
        for(auto temp = head; temp != cur; temp = temp->next){
            allocator.deallocator(temp);
        }
        allocator.deallocator(cur);
    }

    void pushBack(const T& item){
        if(cur) {
            cur = cur->next = reinterpret_cast<node*>(new(allocator.allocator())T(item));
        }else {
            cur = head = reinterpret_cast<node*>(new(allocator.allocator())T(item));
        }
        ++size;
        cur->next = 0;
    }

    node* getHead() const {
        return head;
    }
};

#endif //FRED_LINKLIST_H

對於這個鏈表功能和實現都很簡單, 這裡唯一要說可能有些人不知道new可以指定空間進行初始化, 不知道的可以去網上看一下, 這是placement new而我們一般使用的帶有記憶體分配的叫做plain new...

大概就是這麼多, 這個禮拜在成都玩, 可能更新地比較慢...