简单说下：设计内存池的目的主要是为了解决在一些特殊的场合（比如：网络编程时接受数据包）频繁的创建和销毁、造成的大量的内存碎片和降低效率。
在stl的内存池中可以看到、它的实现是利用了一个自由链表数组、obj** free_lists;数组中每个元素都是一个自由链表的头指针、它指向一个由多个内存块连成的链表。另外、每个链表中所包含的内存块的大小是固定的、stl中是从8开始到128byte结束、块与块间的大小间隔也是8、也就是8、16、24、32、40、48、56、64、72、80、88、96、104、112、120、128。那么free_lists链表数组的大小也就是16。
先看一下我按照stl中的方案实现的内存池代码：
//头文件
#pragma once
#include
#include
#include
using namespace std;
class cmemorypool
{
private:
const unsigned int align ;
const unsigned int maxbytes;
const unsigned int numberoffreelist;
const unsigned int numberofaddnodeeachtime;
union obj
{//使用共用体达到了，next连接节点的指针在分配之前作用为指向下一个节点、在分配之后作用为用户使用空间
union obj* next;
char client[1];
};
obj** freelists;
char* startpos;
char* endpos;
unsigned int heapsize; //内存池分配的总大小
char** ptrtoheadeachalloc; //每次内存池向系统申请空间时这里会记录一个首地址
size_t maxalloctime; //最大次数、用于记录
size_t alloctime; //向系统申请空间的次数
public:
cmemorypool(unsigned nalign = 8,unsigned nmaxbytes = 128,unsigned nnumberofaddnodeeachtime = 20);
virtual ~cmemorypool(void);
private:
size_t round_up(size_t size) {
return ((size align - 1) & ~(align - 1));
}
size_t freelist_index(size_t size) {
return (size align - 1) / align - 1;
}
protected:
void* allocate(size_t size);
void* refill(size_t size);
char* blockalloc(size_t size, size_t& num);
void deallocate(void* ptr, size_t size);
void close();
};
//源文件
#include "memorypool.h"
cmemorypool::cmemorypool(unsigned nalign,unsigned nmaxbytes ,unsigned nnumberofaddnodeeachtime)
:align(nalign),maxbytes(round_up(nmaxbytes)),numberoffreelist(nmaxbytes / nalign),
numberofaddnodeeachtime(nnumberofaddnodeeachtime),
freelists(new obj*[numberoffreelist]),startpos(null),endpos(null),heapsize(0),
ptrtoheadeachalloc((char**)malloc(50)),maxalloctime(50),alloctime(0)
{
for(size_t i = 0; i < numberoffreelist; i )
freelists[i] = null;
}
cmemorypool::~cmemorypool(void)
{
}
void cmemorypool::close()
{
for(size_t i = 0; i < alloctime; i ){
if(ptrtoheadeachalloc[i]){
free(ptrtoheadeachalloc[i]);
ptrtoheadeachalloc[i] = null;
}
}
if(ptrtoheadeachalloc){
free(ptrtoheadeachalloc);
ptrtoheadeachalloc = null;
}
if(freelists){
delete[] freelists;
freelists = null;
}
}
//分配指定大小内存
void* cmemorypool::allocate(size_t size)
{
if(size > maxbytes){
return malloc(size);
}
size_t index = freelist_index(size);
obj* node = freelists[index];
if(node){//自由链表中有节点
freelists[index]= node->next;
return node;
}
return refill(round_up(size));
}
//填充一个自由链表、返回头
void* cmemorypool::refill(size_t size)
{
size_t num = numberofaddnodeeachtime;
char* block = blockalloc(size,num);
obj** currposlst = null;
obj* nextnode = null;
obj* currnode = null;
if(num == 1){
return block;
}else{//将除第一个要返回的块外的所有块相连
currposlst = freelists freelist_index(size);
*currposlst = nextnode = reinterpret_cast(block size);
for(int i = 1;; i){
currnode = nextnode;
nextnode = reinterpret_cast(reinterpret_cast(currnode) size);
if(num - 1 == i){
nextnode->next = null;
break;
}else{
currnode->next = nextnode;
}
}
return block;
}
}
//分配内存块
char* cmemorypool::blockalloc(size_t size, size_t& num)
{
size_t neededsize = size * num;
size_t totalsize = endpos - startpos;
//情况一：如果内存池中有足够的空间、则直接将空间返回、头位置向后偏移
if(totalsize >= neededsize){
char* result = startpos;
startpos = neededsize;
return result;
}else if(totalsize >= size){
//情况二：如果空间足够一个或一个以上则直接分配、并修改num(实际分配的块数)
num = totalsize / size;
char* result = startpos;
startpos = num * size;
return result;
}else{
//情况三：内存池已经没有空间可以用来分配内存给自由链表了、则需要向系统申请空间
size_t allocsize = 2 * neededsize round_up(heapsize >> 4);
if(totalsize > 0){
//如果内存池中还有剩余空间、一定足够一个或多个最小块
obj** node = freelists freelist_index(totalsize);
reinterpret_cast(startpos)->next = *node;
*node = reinterpret_cast(startpos);
}
startpos = (char*)malloc(allocsize);
if(startpos == null){//分配失败、考虑从其他自由链表中取下一块内存(一个节点)用来应急
obj** currfreelst = null;
obj* node = null;
for(size_t i = size align; i <= maxbytes; i = align){
currfreelst = freelists freelist_index(i);
node = *currfreelst;
if(node){//该自由链表非空
*currfreelst = node->next; //将原空闲链表头向后移动一个节点
startpos = reinterpret_cast(node);
endpos = reinterpret_cast(node i);
return blockalloc(size,num); //重新分配
}
}
//执行到这、说明内存分配失败且没有足够大的空闲节点
throw bad_alloc();
}else{//分配成功、设置内存池指针、并且增加内存池总大小
if(alloctime == maxalloctime){
if(realloc(ptrtoheadeachalloc,maxalloctime 50) == null){
throw bad_alloc();
}
maxalloctime = 50;
}
ptrtoheadeachalloc[alloctime ] = startpos;
heapsize = allocsize;
endpos = startpos allocsize;
return blockalloc(size,num);
}
}
}
//释放内存
void cmemorypool::deallocate(void* ptr, size_t size)
{
if(size > maxbytes){//若大小大于最大内存块、直接使用free释放
free(ptr);
}else{//将内存重新挂到对应的自由链表上
reinterpret_cast(ptr)->next = freelists[freelist_index(size)];
freelists[freelist_index(size)] = reinterpret_cast(ptr);
}
} 简述一下它的实现步骤：
1、最开始的时候因为不知道要分配多大的空间、所以这是startpos – endpos为0、也就是内存池是空的。在分配时先到对应的free_list（申请空间与块大小最接近的链表）中寻找、是否有空间、如果没有再去内存池中寻找、然而这时内存池中也没有空间、那么就只能向系统申请空间了。如果成功：则进行相应的内存分配、并且将剩余部分内存（有一部分内存池自己留下了）分块“挂”在对应的free_list上。
2、如果在内存池向系统申请空间时失败了、那么为了“应急”就查找块大小比用户所申请的空间还大的链表中是否存在节点块、如果存在直接将它“拿下来”放到内存池中（也就是调整startpos和endpos）、再重新分配（这时内存池中已经有了空间所以就可以直接将它提供给用户了）。
有几点需要注意：
1、为什么obj节点要使用共用体？
stl源码剖析：从第一个变量看、可将obj视为一个指针指向相同形式的下一个obj、从第二个变量看、可将obj视为一个指针指向实际区块。
其意思就是：
struct obj
{
struct obj* next; //指向下一个节点（需要的）
char* data; //指向实际内存块的地址
};
union obj
{//共用一块空间4byte
union obj* next; //当使用next时、obj所代表的的就是指向下一个节点的指针
char data[1]; //当使用data时、obj本身就是实际的快空间
};这里再说下：柔性数组
struct node
{
int a;
char b[0];
};这时node的大小是4byte、因为b数组0长度。但是b数组的地址在node地址的下面也就是:
node* n = (node*)malloc(sizeof(node) 4); 这时连续多出来的4个字节的首地址就是b、还有:
char str[100];
node* p = (node*)str;字符串的前4个字节被a占用、后面的都被b所使用。
结构体柔性数组的地址是在整个node之后的、但是共用体柔性数组的地址就是node的首地址、柔性数组可表示可变长度的空间、所以上面obj中的data就是为了适应不同的块大小。因为它可以表示可变长度。
2、块大小必须大于或等于一个指针的大小、也就是align大于等于4。
那是因为每个节点其实就是分配的内存块的头部分的4个字节、如果内存块本身不能大于4那么也就不够将空间转换为obj。
下面是根据内存池实现的分配器：
#pragma once
#include
#include "memorypool.h"
/*模板不支持分离编译*/
template
class cmyallocator : public cmemorypool
{
private:
typedef size_t size_type;
public:
cmyallocator(unsigned nalign = 8,unsigned nmaxbytes = 128,unsigned nnumberofaddnodeeachtime = 20);
~cmyallocator(void);
public:
t* allocate();
t* allocate(size_type numoft);
void deallocate(t* ptr);
void deallocate(t* ptr,size_type num);
void construct(t* ptr);
void construct(t* ptr,const t& value);
void destroy(t* ptr);
void destroy(t* first,t* last);
void close();
};
template
cmyallocator::cmyallocator(unsigned nalign,unsigned nmaxbytes,unsigned nnumberofaddnodeeachtime)
:cmemorypool(nalign,nmaxbytes,nnumberofaddnodeeachtime)
{
}
template
cmyallocator::~cmyallocator(void)
{
}
template
t* cmyallocator::allocate()
{
return static_cast(cmemorypool::allocate(sizeof(t)));
}
template
t* cmyallocator::allocate(size_type numoft)
{
if(numoft == 0)
return null;
return static_cast(cmemorypool::allocate(sizeof(t) * numoft));
}
template
void cmyallocator::deallocate(t* ptr)
{
cmemorypool::deallocate(ptr,sizeof(t));
}
template
void cmyallocator::deallocate(t* ptr,size_type num)
{
if(num == 0)
return;
cmemorypool::deallocate(ptr,sizeof(t) * num);
}
template
void cmyallocator::construct(t* ptr)
{
new(ptr) t();
}
template
void cmyallocator::construct(t* ptr,const t& value)
{
new(ptr) t(value);
}
template
void cmyallocator::destroy(t* ptr)
{
ptr->~t();
}
template
void cmyallocator::destroy(t* first,t* last)
{
for(;first != last;first )
{
first->~t();
}
}
template
void cmyallocator::close()
{
cmemorypool::close();
}