包括一级空间配置器 和 二级空间配置器

#pragmaonce#include<iostream>usingnamespacestd;/*————————————*//*一级空间配置器*//*————————————*/typedefvoid(*ALLOC_OOM_FUN)();//函数指针template<intinst>//这个模板参数并没有使用，是预留的class__MallocAllocTemplate{private:staticALLOC_OOM_FUN__sMallocAllocOomHandler;//句柄函数，如果设置了，空间分配失败就会调用它staticvoid*OomMalloc(size_tn){ALLOC_OOM_FUNMyMallocHandler;void*result;/*1:分配内存成功，直接返回2:分配失败，则检查是否有设置处理的MyMallocHandler，如果有，则调用它以后再尝试分配，并不断重复，直到分配成功如果没有，则直接结束程序*/for(;;){MyMallocHandler=__sMallocAllocOomHandler;if(MyMallocHandler){MyMallocHandler();void*ret=malloc(n);if(ret){returnret;}}else{throwbad_alloc();}}returnresult;}staticvoid*OomRealloc(void*p,size_tn){/*步骤同上*/ALLOC_OOM_FUNMyMallocHandler;for(;;){MyMallocHandler=__sMallocAllocOomHandler;if(MyMallocHandler){MyMallocHandler();void*ret=realloc(p,n);if(ret){returnret;}}else{throwbad_alloc();}}}public:staticvoid*Allocate(size_tn){//__TRACE_DEBUG("n:%u\n",n);void*result=malloc(n);//第一级配置器直接使用mallocif(NULL==result)//0==result{result=OomMalloc(n);}returnresult;}staticvoidDeallocate(void*p,size_t/*n*/){//TRACE_DEBUG("(p:%p)\n".p);free(p);//第一级配置器直接使用free()}staticvoid*Reallocate(void*p,size_t/*old_sz*/,size_tnew_sz){void*result=realloc(p,new_sz);if(NULL==result){result=OomRealloc(p,new_sz);returnresult;}returnresult;}/*设置句柄函数的函数函数名：SetMallocHandler参数：名为f的函数指针(指向要设置的新句柄)返回值：函数指针（指向原来的句柄函数）*/staticvoid(*SetMallocHandler(void(*f)()))(){void(*old)()=__sMallocAllocOomHandler;__sMallocAllocOomHandler=f;returnold;}};//将句柄函数指针初始化为空template<intinst>ALLOC_OOM_FUN__MallocAllocTemplate<inst>::__sMallocAllocOomHandler=NULL;/*————————————*//*二级空间配置器*//*————————————*/template<boolthreads,intinst>//这两个模板参数同样并没有使用，是预留的class__DefaultAllocTemplate{public:enum{__ALIGN=8};//排列基准值(间隔)enum{__MAX_BYTES=128};//最大值,上限enum{__NFREELISTS=__MAX_BYTES/__ALIGN};//自由链表的个数//自由链表(FreeLists)结点unionObj{unionObj*_FreeListLink;//指向下一个内存块的指针charClientData[1];//客户端可见(测试用)};staticObj*volatile_FreeList[__NFREELISTS];//自由链表staticchar*_StartFree;//内存池起始位置staticchar*_EndFree;//内存池结束位置staticsize_t_HeapSize;//从系统堆分配的内存的总大小public://空间配置函数staticvoid*Allocate(size_tn){//__TRACE_DEBUG("(n;%n)\n",n);//如果n>__MAX_BYTES就直接在一级空间配置器中获取内存//否则在二级空间配置器中获取内存if(n>(size_t)__MAX_BYTES){return__MallocAllocTemplate<0>::Allocate(n);}void*ret=NULL;size_tindex=FREELIST_INDEX(n);//1、如果自由链表中没有内存，通过Refill填充//2、如果自由链表中有，则返回一个结点块的内存//ps:多线程环境需要考虑加锁Obj*head=_FreeList[index];if(head==NULL){returnRefill(ROUND_UP(n));}else{//__TRACE_DEBUG("自由链表取内存:_FreeList[%s]\n",index);_FreeList[index]=head->_FreeListLink;returnhead;}}//空间释放函数staticvoidDeallocate(void*p,size_tn){//__TRACE_DEBUG("(释放p:%p,n:%u)\n",p,n);//若n>__MAX_BYTES则直接还给一级配置器//否则放回自由链表if(n>__MAX_BYTES){__MallocAllocTemplate<0>::Deallocate(p,n);}else{//ps:多线程要考虑加锁size_tindex=FREELIST_INDEX(n);//头插回自由链表Obj*tmp=(Obj*)p;((Obj*)p)->_FreeListLink=_FreeList[index];_FreeList[index]=tmp;}}staticvoid*Reallocate(void*p,size_told_sz,size_tnew_sz){void*result;size_tcopy_sz;//内存块较大，改用一级空间配置器if(old_sz>(size_t)__MAX_BYTES&&new_sz>__MAX_BYTES){return__MallocAllocTemplate<0>::Reallocate(p,old_sz,new_sz);}//修改前和修改后的大小相同，不用修改if(ROUND_UP(old_sz)==ROUND_UP(new_sz)){returnp;}//否则，分配一块空间，并将原来空间的数据拷贝至新空间result=Allocate(new_sz);copy_sz=new_sz>old_sz?old_sz:new_sz;//如果new_sz小于old_sz会丢失数据memcpy(result,p,copy_sz);Deallocate(p,old_sz);//拷贝完后,释放原来的空间returnresult;}private://将bytes上调至8的倍数staticsize_tROUND_UP(size_tbytes){return((bytes+__ALIGN-1)&~(__ALIGN-1));//位运算，保证效率比如14：14+7=21(0x00010101)和(0x1000)进行&,结果是:(0x00010000)即16}//选择使用哪个自由链表staticsize_tFREELIST_INDEX(size_tbytes){return((bytes+__ALIGN-1)/__ALIGN-1);}private://获得大块内存填充到自由链表中staticvoid*Refill(size_tn){//__TRACE_DEBUG("(n:%u)\n",n);//分配nbytes的内存，如果不够则能分配多少是多少intnobjs=20;//一次要获得的数目(一大块内存)char*chunk=ChunkAlloc(n,nobjs);//试图获得nobjs块内存，每块内存的大小为n，并把实际获得的内存数赋予nobjs//如果只分配到一块，则直接返回这块内存if(nobjs==1){returnchunk;}Obj*result;Obj*cur;size_tindex=FREELIST_INDEX(n);//根据n选择要存放的链表result=(Obj*)chunk;//把剩余的块链链接到自由链表上面cur=(Obj*)(chunk+n);_FreeList[index]=cur;for(inti=2;i<nobjs;++i){cur->_FreeListLink=(Obj*)(chunk+n*i);cur=cur->_FreeListLink;}cur->_FreeListLink=NULL;returnresult;}staticchar*ChunkAlloc(size_tsize,int&nobjs){char*result;size_tTotalBytes=size*nobjs;size_tBytesLeft=_EndFree-_StartFree;//内存池的剩余空间/*1、内存池中内存足够，即BytesLeft>=TotalBytes时，直接从内存池中取出2、内存池中的内存不足，但足够一块时，即Bytesleft>=size时，也直接取出来3、内存池中内存连一块内存也不够的时候，从系统堆中分配大块内存到内存池中*/if(BytesLeft>=TotalBytes)//1{//__TRACE_DEBUG("内存池中内存足够分配%d个对象\n",nobjs);result=_StartFree;_StartFree+=TotalBytes;returnresult;}elseif(BytesLeft>=size)//2{//__TRACE_DEBUG("内存池中内存不够分配%d个对象，只能分配%d个对象\n",nobjs,BytesLeft/size);result=_StartFree;nobjs=BytesLeft/size;_StartFree+=nobjs*size;}else//3{//如果内存中还有小块剩余内存(零头)，则将它头插到合适的自由链表if(BytesLeft>0){size_tindex=FREELIST_INDEX(BytesLeft);((Obj*)_StartFree)->_FreeListLink=_FreeList[index];_FreeList[index]=((Obj*)_StartFree);_StartFree=NULL;//__TRACE_DEBUG("将内存池中剩余的空间，分配给_FreeList[%d]\n",index);}//从系统堆分配两倍+已分配的_HeapSize/8的内存分配到内存池中size_tBytesToGet=2*TotalBytes+ROUND_UP(_HeapSize>>4);_StartFree=(char*)malloc(BytesToGet);//__TRACE_DEBUG("内存池空间不足，系统堆分配%ubytes内存\n",BytesToGet);//如果在堆中内存分配失败，则尝试到自由链表中更大的节点中分配if(_StartFree==NULL){//TRACE_DEBUG("系统堆已经没有足够内存在自由链表中查找\n");//为什么要从大小为size的链表中开始找呢？因为如果是多线程，有可能刚好其他线程//有释放大小为size的内存，也就是说，大小为size的链表有可能有内存可以用//所以从大小为size的链表开始向后找for(inti=size;i<=__MAX_BYTES;i+=__ALIGN){Obj*head=_FreeList[FREELIST_INDEX(size)];if(head)//找到了有可用的内存，将它摘下来{_StartFree=(char*)head;head=head->_FreeListLink;_EndFree=_StartFree+i;returnChunkAlloc(size,nobjs);}}_EndFree=0;//防止异常，防止野指针//在自由链表中也没找到，则退到一级空间配置器，希望句柄函数能做一些处理，以得到内存//__TRACE_DEBUG("系统堆和自由链表中都没有内存了，调到在一级配置器里做最后的尝试\n");_StartFree=(char*)__MallocAllocTemplate<0>::Allocate(BytesToGet);}//从系统堆分配的总字节数(可用于下次分配时进行调节)_HeapSize+=BytesToGet;_EndFree=_StartFree+BytesToGet;//递归调用获取内存returnChunkAlloc(size,nobjs);}returnresult;}};//对类内部的静态成员进行初始化char*__DefaultAllocTemplate<false,0>::_StartFree=NULL;char*__DefaultAllocTemplate<false,0>::_EndFree=NULL;size_t__DefaultAllocTemplate<false,0>::_HeapSize=0;typedeftypename__DefaultAllocTemplate<false,0>::ObjObj;Obj*volatile__DefaultAllocTemplate<false,0>::_FreeList[]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,};