转载

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