mxh1998 2008-3-26 22:54
为C 标准库容器写自己的内存分配程序
根据sgi 的STL源码的二级分配算法改写的内存池分配程序，只要稍微修改就可以实现共享内存方式管理，使用C 标准库容器中的map，set，multimap，multiset测试通过，vector测试通不过，原因是在内存回收的时候考虑的比较简单，vector每次分配内存个数不固定，回收也不固定，这样的话，程序还需要继续完善。
内存池管理程序源码如下：<?xml:namespace prefix = std /><std::endl;< p><std::endl;< p><std::endl;< p><std::endl;< p><std::size_t><?xml:namespace prefix = sizeof(Cookie)<<std /><sizeof(Cookie)<<std::endl;< p><std::endl;< p><std::endl;< p><std::endl;< p><std::endl;< p><std::endl;< p><std::endl;< p><std::endl;< p><MAP>
以下是引用片段：
#ifndefMY_ALLOCATOR_H_
#defineMY_ALLOCATOR_H_
#include"stdafx.h[/img]#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)[/img]<<"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)[/img]<<"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:定义控制台应用程序的入口点。
//
#include"stdafx.h[/img]#include<map>
#include<vector>
#include<string>
#include<utility>
#include<iostream>
#include"MyAlloc.h[/img]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编译环境下。因为源码涉及公司的商业秘密，所以不能公开。但基本上以上源码已经体现了自己管理内存的完整思路，供这方面需求的朋友一起学习研究用。</MAP></std::endl;<></std::endl;<></std::endl;<></std::endl;<></std::endl;<></std::endl;<></std::endl;<></sizeof(Cookie)<<std::endl;<></std::size_t></std::endl;<></std::endl;<></std::endl;<></std::endl;<>