基于一个简单定长内存池的实现方法详解

就是泡妞的

就是泡妞的

2016-02-19 09:39

今天天气好晴朗处处好风光,好天气好开始,图老师又来和大家分享啦。下面给大家推荐基于一个简单定长内存池的实现方法详解,希望大家看完后也有个好心情,快快行动吧!

    主要分为 3 个部分,memoryPool 是管理内存池类,block 表示内存块,chunk 表示每个存储小块。它们之间的关系为,memoryPool 中有一个指针指向某一起始 block,block 之前通过 next 指针构成链表结构的连接,每个 block 包含指定数量的 chunk。每次分配内存的时候,分配 chunk 中的数据地址。

内存池设计文档

主要数据结构设计:

Block:
代码如下:

struct block {
    block * next;//指向下一个block指针
    unsigned int numofChunks;
    unsigned int numofFreeChunks;//剩余free的chunk数量
    unsigned int blockNum;//该block的编号
    char * data;
    queueint freepos; //记录可用chunk序号
};

MemoryPool:
代码如下:

class memoryPool {
    unsigned int initNumofChunks; //每个block的chunk数量
    unsigned int chunkSize;//每个chunk的数据大小
    unsigned int steps;//每次扩展的chunk数量
    unsigned int numofBlocks;//当前管理多少个blocks
    block * blocksPtr;//指向起始block
    block * blocksPtrTail;//指向末尾block
    block * firstHasFreeChunksBlock;//指向第一个不为空的block
};

Chunk:

ChunkNum:该 chunk 所在 block 里的编号

blockAddress: 该 chunk 所对应的 block,主要用于 free 这个 chunk 的时候,能够快速找到所属 block,并进行相应更新

data:实际供使用的数据起始位置

关键操作说明:

内存分配:

从 firstHasFreeChunksBlock 开始查找第一个有 free 位置的 block,如果找到,则则获取该 block 的 freepos 的队首元素,返回该元素序号对应的 chunk 的数据地址,并将 freepos 的队首元素弹出,其他相关属性更新。如果找不到,则新增 steps 个 chunk,再重复上面的过程。

内存释放:

传入待释放的地址指针p,通过对p的地址移动可以找到chunk中的 ChunkNum 和 blockAddress 两个数据,通过 blockAddress 可以找到该 chunk 所属的 block,然后将ChunkNum 添加到该 block 的 freepos 中,其他相应属性更新。

(本文来源于图老师网站,更多请访问http://m.tulaoshi.com/bianchengyuyan/)

使用方法:
代码如下:

memoryPool * mp = new memoryPool (256);  
  char * s = (char *)mp-allocate();
  // 一些操作
  mp-freeMemory(s);    
  delete mp;

不足:

没考虑线程安全问题,该实现方案在单线程下可以正常运行。

程序源代码:
代码如下:

#include iostream
#include queue
#include string.h
#include ctime
using namespace std;

struct block {
    block * next;
    unsigned int numofChunks;//指向下一个block指针
    unsigned int numofFreeChunks;//剩余free的chunk数量
    unsigned int blockNum;//该block的编号
    char * data;
    //记录可用chunk序号
    queueint freepos;
    block(unsigned int _numofChunks ,unsigned int _chunkSize, unsigned int _blockNum){
        numofChunks =  _numofChunks;
        numofFreeChunks = _numofChunks;
        blockNum = _blockNum;
        next = NULL;
        data = new char [numofChunks * (sizeof(unsigned int) + sizeof(void *) + _chunkSize)];
        char * p = data;
        //每个chunk的结构:4byte的chunk序号 + 4byte的所属block地址 + 真正的数据
        for(int i=0;inumofChunks;i++){
            char * ptr = p + i * (_chunkSize +  sizeof(unsigned int) + sizeof(void *));
            unsigned int * num = (unsigned int *)(ptr);
            *num = i;
            ptr += sizeof(void *);
            int * blockpos = (int *) ptr;
            *blockpos = (int)this;
            freepos.push(i);
        }
    }
    ~block(){
        delete [] data;
    }
};

class memoryPool {
public :
    memoryPool(unsigned int _chunkSize = 256, unsigned int _initNumofChunks = 4096, unsigned int _steps = 64){
        initNumofChunks = _initNumofChunks;
        chunkSize = _chunkSize;
        steps = _steps;
        numofBlocks = steps;
        //创建内存池时,初始化一定数量的内存空间
        block * p = new block(initNumofChunks, chunkSize, 0);
        blocksPtr = p;
        for(int i=1;isteps;i++){
            p-next = new block(initNumofChunks, chunkSize, i);
            p = p-next;
            blocksPtrTail = p;
        }
        firstHasFreeChunksBlock = blocksPtr;
    }
    ~memoryPool(){
        block  * p = blocksPtr;
        while(blocksPtr!=NULL){
            p = blocksPtr-next;
            delete blocksPtr;
            blocksPtr = p;
        }
    }

    /*
    从firstHasFreeChunksBlock开始查找第一个有free位置的block,
    如果找到,则则获取该block的freepos的对首元素,
    返回该元素序号对应的chunk的数据地址,并将freepos的队首元素弹出,
    其他相关属性更新。如果找不到,则新增steps个chunk,再重复上面的过程。
    */
    void * allocate(){
        block * p = firstHasFreeChunksBlock;
        while(p != NULL && p-numofFreeChunks = 0) p = p-next;
        if(p == NULL){
            p = blocksPtrTail;
            increaseBlocks();
            p = p-next;
            firstHasFreeChunksBlock = p;
        }
        unsigned int pos =  p-freepos.front();
        void * chunkStart = (void *)(p-data + pos * (chunkSize +  sizeof(unsigned int) + sizeof(void *)));
        void * res = chunkStart + sizeof(unsigned int) + sizeof(void *);
        p-freepos.pop();
        p-numofFreeChunks --;
        return res;
    }

    void increaseBlocks(){
        block * p = blocksPtrTail;
        for(int i=0; isteps; i++){
            p-next = new block(initNumofChunks, chunkSize, numofBlocks);
            numofBlocks++;
            p = p-next;
            blocksPtrTail = p;
        }
    }
    /*
    传入待释放的地址指针_data,
    通过对_data的地址移动可以找到chunk中的ChunkNum和blockAddress两个数据,
    通过blockAddress可以找到该chunk所属的block,
    然后将ChunkNum添加到该block的freepos中,其他相应属性更新。
    */
    void freeMemory(void * _data){
        void * p = _data;
        p -= sizeof(void *);
        int * blockpos = (int *) p;
        block * b = (block *) (*blockpos);
        p -= sizeof(unsigned int);
        int * num = (int *) p;
        b-freepos.push(*num);
        b-numofFreeChunks ++;
        if (b-numofFreeChunks 0 && b-blockNum firstHasFreeChunksBlock-blockNum)
            firstHasFreeChunksBlock = b;
    }

private :
    unsigned int initNumofChunks; //每个block的chunk数量
    unsigned int chunkSize;//每个chunk的数据大小
    unsigned int steps;//每次扩展的chunk数量
    unsigned int numofBlocks;//当前管理多少个blocks
    block * blocksPtr;//指向起始block
    block * blocksPtrTail;//指向末尾block
    block * firstHasFreeChunksBlock;//指向第一个不为空的block
};

//test
void echoPositionNum(char * p){
    p -= (sizeof(void *) + sizeof(unsigned int));
    int * num = (int *) p;
    cout*numendl;
}

(本文来源于图老师网站,更多请访问http://m.tulaoshi.com/bianchengyuyan/)

//测试
void test0(){
    memoryPool mp;
    char * s1 = (char *)mp.allocate();
    char * s2 = (char *)mp.allocate();

    char str [256];
    char str2 [256];
    char str3 [256];
    for(int i=0; i255; i++) {
        str[i] = 'a';str2[i] = 'b';str3[i] = 'c';
    }
    str[255] = '';
    str2[255] = '';
    strcpy(s1,str);
    strcpy(s2,str2);
    str3[255] = '';
    echoPositionNum(s1);

    couts1endl;
    mp.freeMemory(s1);
    echoPositionNum(s2);
    couts2endl;
    char * s3 = (char *)mp.allocate();
    strcpy(s3,str3);

    echoPositionNum(s3);
    couts3endl;

}

void test1(){
    clock_t clock_begin = clock();
    const int N = 50000;
    char * s[N];
    int round = 100;
    while(round=0){
        round --;
        for(int i=0;iN;i++){
            s[i] = new char[256];
        }
        for(int i=0;iN;i++){
             delete [] s[i];
        }
    }
    clock_t clock_end = clock();
    cout"Time costt"clock_end - clock_beginendl;
}

void test2(){

    memoryPool mp(256);
    clock_t clock_begin = clock();
    const int N = 50000;
    char * s[N];
    int round = 100;
    while(round=0){
        round --;
        for(int i=0;iN;i++){
            s[i] = (char *)mp.allocate();
        }
        for(int i=0;iN;i++){
            mp.freeMemory(s[i]);
        }
    }
    clock_t clock_end = clock();
    cout"Time costt"clock_end - clock_beginendl;

}
int main()
{
    test0();
    test1();
    test2();
    return 0;
}

运行结果:

image

展开更多 50%)
分享

猜你喜欢

基于一个简单定长内存池的实现方法详解

编程语言 网络编程
基于一个简单定长内存池的实现方法详解

JAVA进阶:一个简单Thread缓冲池的实现

编程语言 网络编程
JAVA进阶:一个简单Thread缓冲池的实现

s8lol主宰符文怎么配

英雄联盟 网络游戏
s8lol主宰符文怎么配

基于C中一个行压缩图的简单实现代码

编程语言 网络编程
基于C中一个行压缩图的简单实现代码

基于第一个PhoneGap(cordova)的应用详解

Web开发
基于第一个PhoneGap(cordova)的应用详解

lol偷钱流符文搭配推荐

英雄联盟 网络游戏
lol偷钱流符文搭配推荐

基于Java内存溢出的解决方法详解

编程语言 网络编程
基于Java内存溢出的解决方法详解

一个简单的基于XML的模块集成框架

Web开发
一个简单的基于XML的模块集成框架

lolAD刺客新符文搭配推荐

英雄联盟
lolAD刺客新符文搭配推荐

java中把汉字转换成简拼的实现代码

java中把汉字转换成简拼的实现代码

JSP Servelet 数据源连接池的配置

JSP Servelet 数据源连接池的配置
下拉加载更多内容 ↓