主要分為 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;
}
運行結果：
