服务器之家:专注于服务器技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|Java教程|ASP教程|编程技术|正则表达式|C/C++|IOS|C#|Swift|Android|VB|R语言|JavaScript|易语言|vb.net|

服务器之家 - 编程语言 - C/C++ - 基于一个简单定长内存池的实现方法详解

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

2020-11-25 11:09C++教程网 C/C++

本篇文章对一个简单定长内存池的实现方法进行了详细的分析介绍。需要的朋友参考下

    主要分为 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;
    queue<int> 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 中,其他相应属性更新。

使用方法:

复制代码 代码如下:

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序号
    queue<int> 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;i<numofChunks;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;i<steps;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; i<steps; 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<<*num<<endl;
}

//测试
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; i<255; i++) {
        str[i] = 'a';str2[i] = 'b';str3[i] = 'c';
    }
    str[255] = '\0';
    str2[255] = '\0';
    strcpy(s1,str);
    strcpy(s2,str2);
    str3[255] = '\0';
    echoPositionNum(s1);

    cout<<s1<<endl;
    mp.freeMemory(s1);
    echoPositionNum(s2);
    cout<<s2<<endl;
    char * s3 = (char *)mp.allocate();
    strcpy(s3,str3);

    echoPositionNum(s3);
    cout<<s3<<endl;

}

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;i<N;i++){
            s[i] = new char[256];
        }
        for(int i=0;i<N;i++){
             delete [] s[i];
        }
    }
    clock_t clock_end = clock();
    cout<<"Time cost\t"<<clock_end - clock_begin<<endl;
}

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;i<N;i++){
            s[i] = (char *)mp.allocate();
        }
        for(int i=0;i<N;i++){
            mp.freeMemory(s[i]);
        }
    }
    clock_t clock_end = clock();
    cout<<"Time cost\t"<<clock_end - clock_begin<<endl;

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


运行结果:

 

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

延伸 · 阅读

精彩推荐
  • C/C++C/C++经典实例之模拟计算器示例代码

    C/C++经典实例之模拟计算器示例代码

    最近在看到的一个需求,本以为比较简单,但花了不少时间,所以下面这篇文章主要给大家介绍了关于C/C++经典实例之模拟计算器的相关资料,文中通过示...

    jia150610152021-06-07
  • C/C++详解c语言中的 strcpy和strncpy字符串函数使用

    详解c语言中的 strcpy和strncpy字符串函数使用

    strcpy 和strcnpy函数是字符串复制函数。接下来通过本文给大家介绍c语言中的strcpy和strncpy字符串函数使用,感兴趣的朋友跟随小编要求看看吧...

    spring-go5642021-07-02
  • C/C++C++之重载 重定义与重写用法详解

    C++之重载 重定义与重写用法详解

    这篇文章主要介绍了C++之重载 重定义与重写用法详解,本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下...

    青山的青6062022-01-04
  • C/C++C语言实现电脑关机程序

    C语言实现电脑关机程序

    这篇文章主要为大家详细介绍了C语言实现电脑关机程序,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...

    xiaocaidayong8482021-08-20
  • C/C++学习C++编程的必备软件

    学习C++编程的必备软件

    本文给大家分享的是作者在学习使用C++进行编程的时候所用到的一些常用的软件,这里推荐给大家...

    谢恩铭10102021-05-08
  • C/C++C语言中炫酷的文件操作实例详解

    C语言中炫酷的文件操作实例详解

    内存中的数据都是暂时的,当程序结束时,它们都将丢失,为了永久性的保存大量的数据,C语言提供了对文件的操作,这篇文章主要给大家介绍了关于C语言中文件...

    针眼_6702022-01-24
  • C/C++深入理解goto语句的替代实现方式分析

    深入理解goto语句的替代实现方式分析

    本篇文章是对goto语句的替代实现方式进行了详细的分析介绍,需要的朋友参考下...

    C语言教程网7342020-12-03
  • C/C++c++ 单线程实现同时监听多个端口

    c++ 单线程实现同时监听多个端口

    这篇文章主要介绍了c++ 单线程实现同时监听多个端口的方法,帮助大家更好的理解和学习使用c++,感兴趣的朋友可以了解下...

    源之缘11542021-10-27