为C++标准库容器写自己的内存分配程序

以下是引用片段：

#ifndefMY_ALLOCATOR_H_

#defineMY_ALLOCATOR_H_

#include"stdafx.h"

#include<limits>

#include<iostream>

namespacehappyever

{

enum{NODENUMS=2};

union_Obj

{

union_Obj*M_free_list_link;

charM_client_data[1];

};

typedefunion_ObjObj;

struct_Cookie

{

intiShmKey;/*共享内存键值*/

intiShmID;/*iShmKey对应的shmid*/

intiSemKey;/*锁信号键值*/

intiSemID;/*锁信号标识*/

intiTotalsize;/*容器总容量*/

void*pStartall;/*共享内存自身地址*/

char*pStartfree;/*自由空间的开始地址*/

char*pEndfree;/*自由空间的结束地址*/

intiUseNum[NODENUMS];

/*用来存放free_list中节点的size*/

shortsFreelistIndex[NODENUMS];

/*存放分配内存节点的链表*/

Obj*uFreelist[NODENUMS];

};

typedefstruct_CookieCookie;

//Obj;

//Cookie;

staticCookie*pHead=NULL;

template<classT>

classMyAlloc

{

private:

staticconstintALIGN=sizeof(Obj);

intround_up(intbytes);

intfreelist_index(intbytes);

intfreelist_getindex(intbytes);

char*chunk_alloc(intsize,int*nobjs);

void*refill(intnum,intn);

public:

//typedefinitions

typedefTvalue_type;

typedefT*pointer;

typedefconstT*const_pointer;

typedefT&reference;

typedefconstT&const_reference;

typedefstd::size_tsize_type;

typedefstd::ptrdiff_tdifference_type;

template<classU>

structrebind

{

typedefMyAlloc<U>other;

};

pointeraddress(referencevalue)const

{

return&value;

}

const_pointeraddress(const_referencevalue)const

{

return&value;

}

MyAlloc()throw()

{

std::cout<<"MyAlloc"<<std::endl;

}

MyAlloc(constMyAlloc&x)throw()

{

std::cout<<"constMyAlloc"<<std::endl;

}

template<classU>

MyAlloc(constMyAlloc<U>&x)throw()

{

std::cout<<"constMyAlloc<U>"<<std::endl;

}

~MyAlloc()throw()

{

std::cout<<"~MyAlloc"<<std::endl;

}

size_typemax_size()constthrow()

{

returnstd::numeric_limits<std::size_t>::max()/sizeof(T);

}

//voidPrintFreelistAndCookie();

pointerallocate(size_typenum,constvoid*=0)

{

pointerret=0;

Obj**my_free_list;

Obj*result;

intindex;

//printmessageandallocatememorywithglobalnew

std::cerr<<"allocate"<<num<<"element(s)"

<<"ofsize"<<sizeof(T)<<std::endl;

index=freelist_index(sizeof(T));

if(index>=NODENUMS)

{

returnNULL;

}

my_free_list=pHead->uFreelist+index;

//Lock(semid,LOCK_NUM);

result=*my_free_list;

if(result==0)

{

ret=(pointer)refill((int)num,round_up(sizeof(T)));

}

else

{

*my_free_list=result->M_free_list_link;

ret=(pointer)result;

}

//UnLock(semid,LOCK_NUM);

pHead->iUseNum[index]=pHead->iUseNum[index]+(int)num;

if(0==ret)

{

std::cerr<<"allocmemoryfail!"<<std::endl;

exit(1);

}

std::cerr<<"allocatedat:"<<(void*)ret<<std::endl;

PrintFreelistAndCookie();

returnret;

}

voidconstruct(pointerp,constT&value)

{

//initializememorywithplacementnew

new((void*)p)T(value);

}

voiddestroy(pointerp)

{

//destroyobjectsbycallingtheirdestructor

p->~T();

}

voiddeallocate(pointerp,size_typenum)

{

Obj**my_free_list;

Obj*q;

intindex;

index=freelist_getindex(sizeof(T));

if(index>=NODENUMS)

{

std::cerr<<"deallocatememoryfail!"<<std::endl;

exit(1);

}

my_free_list=pHead->uFreelist+index;

q=(Obj*)p;

//Lock(semid,LOCK_NUM);

/*这个地方可能会有问题*/

//for(inti=0;i<(int)num;i++)

{

q->M_free_list_link=*my_free_list;

*my_free_list=q;

}

//UnLock(semid,LOCK_NUM);

pHead->iUseNum[index]=pHead->iUseNum[index]-(int)num;

std::cerr<<"deallocate"<<num<<"element(s)"

<<"ofsize"<<sizeof(T)

<<"at:"<<(void*)p<<std::endl;

PrintFreelistAndCookie();

}

};

template<classT>

intMyAlloc<T>::round_up(intbytes)

{

inti;

i=bytes;

if(bytes<ALIGN)

{

i=ALIGN;

}

std::cout<<"round_up:bytes="<<bytes<<",return="<<i<<std::endl;

returni;

};

template<classT>

intMyAlloc<T>::freelist_index(intbytes)

{

inti;

for(i=0;i<NODENUMS;i++)

{

if(pHead->sFreelistIndex[i]==bytes)

break;

}

if(i>=NODENUMS)

{

for(i=0;i<NODENUMS;i++)

{

if(pHead->sFreelistIndex[i]==0)

{

pHead->sFreelistIndex[i]=bytes;

std::cout<<"freelist_index:bytes="<<bytes<<",return="<<i<<std::endl;

returni;

}

}

}

std::cout<<"freelist_index:bytes="<<bytes<<",return="<<i<<std::endl;

returni;

};

template<classT>

intMyAlloc<T>::freelist_getindex(intbytes)

{

inti;

for(i=0;i<NODENUMS;i++)

{

if(pHead->sFreelistIndex[i]==bytes)

break;

}

std::cout<<"freelist_getindex:bytes="<<bytes<<",return="<<i<<std::endl;

returni;

};

template<classT>

char*MyAlloc<T>::chunk_alloc(intsize,int*nobjs)

{

char*result;

intcounts=*nobjs;

inttotal_bytes=size*counts;

intbytes_left=int(pHead->pEndfree-pHead->pStartfree);

std::cout<<"chunk_alloc:total_bytes="<<total_bytes

<<",bytes_left="<<bytes_left<<std::endl;

if(bytes_left>=total_bytes)

{

result=pHead->pStartfree;

pHead->pStartfree+=total_bytes;

std::cout<<"chunk_alloc:total_bytes="<<total_bytes

<<",result="<<*result<<",start_free="<<&(pHead->pStartfree)<<std::endl;

}

elseif(bytes_left>=size)

{

counts=bytes_left/size;

total_bytes=size*counts;

result=pHead->pStartfree;

pHead->pStartfree+=total_bytes;

*nobjs=counts;

std::cout<<"chunk_alloc:total_bytes="<<total_bytes<<",nobjs="<<nobjs

<<",result="<<*result<<",start_free="<<&(pHead->pStartfree)<<std::endl;

}

else

{

/*还需要处理回收其他空闲freelist里面的空间*/

result=NULL;

}

return(result);

};

template<classT>

void*MyAlloc<T>::refill(intnum,intn)

{

intcounts=num;

int*nobjs=&counts;

char*chunk;

Obj**my_free_list;

Obj*result;

Obj*current_obj;

Obj*next_obj;

inti;

chunk=chunk_alloc(n,nobjs);

if(chunk==NULL)

{

return(chunk);

}

counts=*nobjs;

if(1==counts)

{

return(chunk);

}

my_free_list=pHead->uFreelist+freelist_index(n);

result=(Obj*)chunk;

*my_free_list=next_obj=(Obj*)(chunk+n*num);

for(i=1;;i++)

{

current_obj=next_obj;

next_obj=(Obj*)((char*)next_obj+n);

if(counts-1==i)

{

current_obj->M_free_list_link=0;

break;

}

else

{

current_obj->M_free_list_link=next_obj;

}

}

return(result);

};

/*这个函数可以改写成自己的共享内存分配函数*/

staticvoidInitShm()

{

inti,size=1000;

pHead=(Cookie*)malloc(sizeof(Cookie)+size);

pHead->iTotalsize=sizeof(Cookie)+size;

pHead->pStartall=pHead;

pHead->pStartfree=(char*)pHead+sizeof(Cookie);

pHead->pEndfree=(char*)pHead+pHead->iTotalsize;

for(i=0;i<NODENUMS;i++)

{

pHead->sFreelistIndex[i]=0;

pHead->uFreelist[i]=0;

pHead->iUseNum[i]=0;

}

}

staticvoidPrintFreelistAndCookie()

{

inti,j;

Obj*my_free_list;

std::cout<<"Cookieinfo:"<<std::endl;

std::cout<<"sizeof(structCookie)="<<sizeof(Cookie)<<std::endl;

std::cout<<"Totalsize="<<pHead->iTotalsize<<std::endl;

std::cout<<"UsedSize="<<int(pHead->pStartfree-(char*)pHead)<<std::endl;

std::cout<<"FreepoolSize="<<int(pHead->pEndfree-pHead->pStartfree)<<std::endl;

std::cout<<"Startall="<<&(pHead->pStartall)<<std::endl;

std::cout<<"Startfree="<<&(pHead->pStartfree)<<std::endl;

std::cout<<"Endfree="<<&(pHead->pEndfree)<<std::endl;

std::cout<<"nFreelistinfo:"<<std::endl;

for(i=0;i<NODENUMS;i++)

{

j=0;

std::cout<<"iUseNum["<<i<<"]="<<pHead->iUseNum[i]<<std::endl;

std::cout<<"FreelistIndex["<<i<<"]="<<pHead->sFreelistIndex[i]<<std::endl;

my_free_list=pHead->uFreelist[i];

if(my_free_list->M_client_data!=0)

{

while(my_free_list->M_client_data!=0)

{

j++;

my_free_list=my_free_list->M_free_list_link;

}

std::cout<<"free_list["<<i<<"];nodecounts="<<j<<std::endl;

}

}

}

template<classT1,classT2>

booloperator==(constMyAlloc<T1>&,constMyAlloc<T2>&)throw()

{

returntrue;

}

template<classT1,classT2>

booloperator!=(constMyAlloc<T1>&,constMyAlloc<T2>&)throw()

{

returnfalse;

}

}

#endif/*MY_ALLOCATOR_H_*/

测试程序的源码如下：

//MyStl.cpp:定义控制台应用程序的入口点。Tw.wiNGWit.Com

//

#include"stdafx.h"

#include<map>

#include<vector>

#include<string>

#include<utility>

#include<iostream>

#include"MyAlloc.h"

usingnamespacestd;

int_tmain(intargc,_TCHAR*argv[])

{

happyever::InitShm();

multimap<string,int,less<string>,happyever::MyAlloc<string>>m;

m.insert(make_pair(string("Harry"),32));

m.insert(make_pair(string("Mary"),59));

m.insert(make_pair(string("Roger"),18));

m.insert(make_pair(string("Nancy"),37));

m.insert(make_pair(string("Mary"),23));

typedefmultimap<string,int,less<string>,happyever::MyAlloc<string>>::iteratorIter;

for(Iterp=m.begin();p!=m.end();p++)

{

cout<<p->first<<","<<p->second<<endl;

}

Iterp=m.find("Harry");

m.erase(p);

/*p=m.find("Harry");

cout<<"Harryis:"<<p->second<<"."<<endl;*/

for(Iterp=m.begin();p!=m.end();p++)

{

cout<<p->first<<","<<p->second<<endl;

}

return0;

}

以上程序在vs2005，vc6上测试通过。使用MinGW编译的时候只需要去掉vc的预编译头文件

#include"stdafx.h"

即可。

以上程序只要稍微修改，就可以实现共享内存的管理，可以方便的使用标准库提供的容器。加上信号量的锁机制。

以上为了学习而改写的SGI的stl二级分配算法实现的。以上代码存在一定的局限性。我另外完整实现了共享内存管理的STL标准的alloctor程序，使用posix信号量加锁。目前应用在aix的xlC编译环境下。因为源码涉及公司的商业秘密，所以不能公开。但基本上以上源码已经体现了自己管理内存的完整思路，供这方面需求的朋友一起学习研究用。