简单说下:设计内存池的目的主要是为了解决在一些特殊的场合(比如:网络编程时接受数据包)频繁的创建和销毁、造成的大量的内存碎片和降低效率。
在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 <cstdio>
#include <cstdlib>
#include <string>
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<Obj*>(block + size);
for(int i = 1;;++i){
currNode = nextNode;
nextNode = reinterpret_cast<Obj*>(reinterpret_cast<char*>(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<Obj*>(startPos)->next = *node;
*node = reinterpret_cast<Obj*>(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<char*>(node);
endPos = reinterpret_cast<char*>(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<Obj*>(ptr)->next = FreeLists[FREELIST_INDEX(size)];
FreeLists[FREELIST_INDEX(size)] = reinterpret_cast<Obj*>(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 <new>
#include "MemoryPool.h"
/*模板不支持分离编译*/
template<class T>
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<class T>
CMyAllocator<T>::CMyAllocator(unsigned nAlign,unsigned nMaxBytes,unsigned nNumberOfAddNodeEachTime)
:CMemoryPool(nAlign,nMaxBytes,nNumberOfAddNodeEachTime)
{
}
template<class T>
CMyAllocator<T>::~CMyAllocator(void)
{
}
template<class T>
T* CMyAllocator<T>::allocate()
{
return static_cast<T*>(CMemoryPool::allocate(sizeof(T)));
}
template<class T>
T* CMyAllocator<T>::allocate(size_type numOfT)
{
if(numOfT == 0)
return NULL;
return static_cast<T*>(CMemoryPool::allocate(sizeof(T) * numOfT));
}
template<class T>
void CMyAllocator<T>::deallocate(T* ptr)
{
CMemoryPool::deallocate(ptr,sizeof(T));
}
template<class T>
void CMyAllocator<T>::deallocate(T* ptr,size_type num)
{
if(num == 0)
return;
CMemoryPool::deallocate(ptr,sizeof(T) * num);
}
template<class T>
void CMyAllocator<T>::construct(T* ptr)
{
new(ptr) T();
}
template<class T>
void CMyAllocator<T>::construct(T* ptr,const T& value)
{
new(ptr) T(value);
}
template<class T>
void CMyAllocator<T>::destroy(T* ptr)
{
ptr->~T();
}
template<typename T>
void CMyAllocator<T>::destroy(T* first,T* last)
{
for(;first != last;first++)
{
first->~T();
}
}
template<typename T>
void CMyAllocator<T>::close()
{
CMemoryPool::close();
}