主要分为 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 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
#include
#include
#include
using namespace std;
struct block {
block * next;
unsigned int numofChunks;//指向下一个block指针
unsigned int numofFreeChunks;//剩余free的chunk数量
unsigned int blockNum;//该block的编号
char * data;
//记录可用chunk序号
queue 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;inext;
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 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; inext = 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