为C++标准库容器写自己的内存分配程序(页 1) - 编程语言 - 我爱电脑技术论坛打造最好的电脑自学交流论坛

不和人说话 发表于 2008-4-4 11:54

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

根据sgi 的STL源码的二级分配算法改写的内存池分配程序，只要稍微修改就可以实现共享内存方式管理，使用C++标准库容器中的map，set，multimap，multiset测试通过，vector测试通不过，原因是在内存回收的时候考虑的比较简单，vector每次分配内存个数不固定，回收也不固定，这样的话，程序还需要继续完善。
Z{:L2b&x%f{o?C
　　内存池管理程序源码如下：'G4E7if#X@-v

以下是引用片段：[Cob0O Xs
#ifndef MY_ALLOCATOR_H_ !iS*J]$T
#define MY_ALLOCATOR_H_
#include "stdafx.h" CQ@G$t/vE5F;J.l
#include <limits> ?c]+S-ly
#include <iostream> l$k(dbL[-IF*D%J
namespace happyever
{ R/QfGjl,F9g
  enum { NODENUMS = 2 };
  union _Obj
  { Yb+F$T4s~
union _Obj* M_free_list_link; h,g$T O7k|'d\
char M_client_data[1];    c,g I3@M N7Hz
  } ;
  typedef union _Obj Obj;
  struct _Cookie
  { 2i$xmaF.\*n8i
int iShmKey;       /* 共享内存键值 */
int iShmID;       /* iShmKey对应的shmid */ xL,y0|*R9U
int iSemKey;       /* 锁信号键值 */
int iSemID;       /* 锁信号标识 */
int iTotalsize; /* 容器总容量 */ o+qTA2k#t
void* pStartall; /* 共享内存自身地址 */ I7L'X0d0b0i f
char* pStartfree;  /* 自由空间的开始地址*/
char* pEndfree; /* 自由空间的结束地址*/ g Q:XxdsYlT
int iUseNum[NODENUMS]; w6MK B@)je
/*用来存放free_list中节点的size*/ .hGO3l*_:j
short sFreelistIndex[NODENUMS];
/*存放分配内存节点的链表*/ sp!J w\R
Obj* uFreelist[NODENUMS];
  };
  typedef struct _Cookie Cookie; (KL| Z m1Z
  //Obj; &q2B,k?H8|(C-e
  //Cookie; q$?CrW
  static Cookie *pHead = NULL;
  template <class T>
  class MyAlloc  -~/c7H2fT3Veq\
  {
  private: #R'FI/](_CH^ b!o`)y
static const int ALIGN = sizeof(Obj); WK|x/lx`u+YN'S b
int round_up(int bytes);
int freelist_index(int bytes);
int freelist_getindex(int bytes);
char* chunk_alloc(int size, int *nobjs); 1dnB6u q+a)K
void* refill(int num,int n);
  public:
// type definitions
typedef T       value_type;
typedef T*    pointer;
typedef const T* const_pointer;
typedef T&    reference; wM9b9M%\
typedef const T& const_reference; n._SIb)l
typedef std::size_t size_type; ~$XHE1i B-P*h~V
typedef std::ptrdiff_t difference_type; -G|Hx"^zo
template <class U>
struct rebind
{
   typedef MyAlloc<U> other; $I{!p4pFF
}; 3]4uzs-X"t6Ev
pointer address (reference value) const
{
   return &value;
}
const_pointer address (const_reference value) const
{ 4c^NCY:|&E_h.^
   return &value; k&HLKWTQ;?K5H
}
MyAlloc() throw()
{ i4}Dh1X \
   std::cout<<"MyAlloc"<<std::endl; "A)K3f9y0^7t(r"C
}
MyAlloc(const MyAlloc& x) throw()  $alRs7p
{ _n0V.@d']k
   std::cout<<"const MyAlloc"<<std::endl; -v:Q@AzyTN3T
}
template <class U> +f&ZMi}
MyAlloc (const MyAlloc<U>& x) throw() BrKL j.^gJ
{
   std::cout<<"const MyAlloc<U>"<<std::endl; 0Jj)@lt
} \LfP(p6JQ
~MyAlloc() throw()  QVYIq!ui1N
{ |%sfaa6`5m(L9T
   std::cout<<"~MyAlloc"<<std::endl;
} T| }K _ T1E
size_type max_size () const throw()
{ ovU`Q:c
   return std::numeric_limits<std::size_t>::max() / sizeof(T);
}
//void PrintFreelistAndCookie(); 3oa1Q.}/YZ"hh0q+X1l
pointer allocate (size_type num, const void* = 0)
{
   pointer ret = 0;
   Obj** my_free_list; n1k[:U_@B
   Obj* result;
   int index; 0A3p!HX5Fw7E2_:c!|a
   // print message and allocate memory with global new
   std::cerr << "allocate " << num << " element(s)"
      << " of size " << sizeof(T) << std::endl; 3Id C/c8]5gk~s\
   index = freelist_index(sizeof(T));
   if(index >= NODENUMS)
   {
      return NULL;
   }
   my_free_list = pHead->uFreelist + index;
   //Lock(semid,LOCK_NUM); '\QD5W Ebwrzh
   result = *my_free_list; [&mi?Wb
   if (result == 0) ^.a$w@yh
   {
      ret = (pointer)refill((int)num, round_up(sizeof(T)));
   } s \)e.b)U:HBk+k;\n
   else
   {
      *my_free_list = result->M_free_list_link;
      ret = (pointer)result;
   } 2N5` ^'L6V'u0uh OG
   //UnLock(semid,LOCK_NUM); I:s8W%a@u*W/H
   pHead->iUseNum[index] = pHead->iUseNum[index] + (int)num; /?:X{hKY$g6[ h7L
   if(0 == ret)
   { "} \-Vij4R(C
      std::cerr << "alloc memory fail!" << std::endl;
      exit(1);
   }
   std::cerr << " allocated at: " << (void*)ret << std::endl;
   PrintFreelistAndCookie(); l/po;Q[ @ z*R O
   return ret; %LL&a3L#|DK}F
}
void construct (pointer p, const T& value)
{ ,N Ebs4Z_
   // initialize memory with placement new B'uT3Pr9A F&b#in
   new((void*)p)T(value); 6\?aU/R%z
}
void destroy (pointer p)
{ /e(}"dPK&W]Q
   // destroy objects by calling their destructor 0\ Lw f&F?7z
   p->~T(); bBelL.UFQ$r
} 8K1r%z La$}W}N
void deallocate (pointer p, size_type num)
{
   Obj** my_free_list;
   Obj* q ;
   int index; 9o7AH Byr?!]3e
   index = freelist_getindex(sizeof(T));
   if(index >= NODENUMS)
   {
      std::cerr << "deallocate memory fail!" << std::endl;
      exit(1); Y2XbV1xN-~!u-{K
   }
   my_free_list = pHead->uFreelist + index;
   q = (Obj*) p; ]b6fo7^Y"P
   //Lock(semid,LOCK_NUM);
   /*这个地方可能会有问题*/ UR`po}z
   //for(int i=0 ;i<(int)num ; i++)
   { 5ZA}ODX&B
      q->M_free_list_link = *my_free_list;
      *my_free_list = q;
   }
   //UnLock(semid,LOCK_NUM); X}he(M,u
   pHead->iUseNum[index] = pHead->iUseNum[index] - (int)num;

   std::cerr << "deallocate " << num << " element(s)"
      << " of size " << sizeof(T)
      << " at: " << (void*)p << std::endl; jF)vZ4N5I5bLe
   PrintFreelistAndCookie(); "Ep{"K%kGw0h:R$O%f
}
  };
  template <class T> iv5wm\K3|{ V4D"n
  int MyAlloc<T>::round_up(int bytes)
  {
int i;
i = bytes;
if(bytes < ALIGN) I`PK[
{ [*Xq|[ jF6T
   i = ALIGN; K3P4EX"EQ
}
std::cout<<"round_up:bytes="<<bytes<<" , return="<<i<<std::endl;
return i; 7yt#x'[ox
  }; yFvmq*H\S&n3_,_
  template <class T> H {6W9w#R
  int MyAlloc<T>::freelist_index(int bytes)
  { *u:k(@Qy"Z)XJy
int i; o[+I;jw H-md4S
for(i=0 ; i< NODENUMS ; i++) q*p~[*D/x0N@y
{ w/_eK}iT
   if(pHead->sFreelistIndex[i] == bytes)
      break;
} R2Fg)T"[
if(i >= NODENUMS) 9E!U| V ]
{
   for(i=0 ; i< NODENUMS ; i++) B5u4]"v2g:XqB
   { ,L(dqW:\%D9H}J
      if(pHead->sFreelistIndex[i] == 0) E_.I,Ei_
      { /a:q*Ui7tfqD
      pHead->sFreelistIndex[i] = bytes; E D9k8q/~:ld+H|
      std::cout<<"freelist_index:bytes="<<bytes<<" , return="<<i<<std::endl; z)M5B#x!Q
      return i; ,\1c/g6k {3^
      } 2aJN ufNW
   } 8mh(y~Q$Ha
} d\HH%g5s6?jI
std::cout<<"freelist_index:bytes="<<bytes<<" , return="<<i<<std::endl;
return i; /e2Q?t1_
  }; JCIY1S'u
  template <class T> .F0K8^-e*mDm%R
  int MyAlloc<T>::freelist_getindex(int bytes) J2GB+ScNs
  {
int i; 4UtX"s1s
for(i=0 ; i< NODENUMS ; i++)
{ 0O D/mY(h
   if(pHead->sFreelistIndex[i] == bytes)
      break;
}
std::cout<<"freelist_getindex:bytes="<<bytes<<" , return="<<i<<std::endl; o&z rR,mV6K
return i;
  }; hk$t*a1]I#|H bQ
  template <class T> (k)_'m s-D*N8|/wIU
  char* MyAlloc<T>::chunk_alloc(int size, int *nobjs)
  { lni$Iz"wB"?@Z
char* result; YAB$xKM@#F
int counts = *nobjs;
int total_bytes = size * counts; (w!G:Fi%n|7u}
int bytes_left = int(pHead->pEndfree - pHead->pStartfree); &{Jlg)F*~
std::cout<<"chunk_alloc:total_bytes = "<<total_bytes Vo/xo,im8p`
   <<",bytes_left = "<<bytes_left<<std::endl;
if (bytes_left >= total_bytes) 8Ug/?2uT-U
{
   result = pHead->pStartfree; '|;n:P'A} Q)z1ue
   pHead->pStartfree += total_bytes;
   std::cout<<"chunk_alloc:total_bytes = "<<total_bytes
      <<",result = "<<*result<<",start_free = "<<&(pHead->pStartfree)<<std::endl; 3M9}:^:W,p1_$H^o
}
else if (bytes_left >= size)
{ *Y F'x_ f%W Dz
   counts = bytes_left/size;
   total_bytes = size * counts;
   result = pHead->pStartfree;
   pHead->pStartfree += total_bytes; DK D3Wzq'u7}I y
   *nobjs = counts; ad)`~3^W-D0X
   std::cout<<"chunk_alloc:total_bytes = "<<total_bytes<<",nobjs = "<<nobjs
      <<",result = "<<*result<<",start_free = "<<&(pHead->pStartfree)<<std::endl; oJr'l?4?_
} ,KFjWO#Q Ui0x
else
{
   /*还需要处理回收其他空闲freelist里面的空间*/
   result = NULL; Zyx!gV
} d8F.pDp'_W
return(result);
  };
  template <class T>
  void* MyAlloc<T>::refill(int num,int n) RP` rEu
  { \~;N$}@q%JFTL
int counts = num;
int *nobjs = &counts;
char* chunk; MT%a}:E#C
Obj** my_free_list; ld~*G iO9^(E$v
Obj* result;
Obj* current_obj; J6Wpp(N;\'b$d
Obj* next_obj;
int i;
chunk = chunk_alloc(n, nobjs); KbnxH6N6E+O`+e
if(chunk == NULL)
{ Jk+j Vl[Z
   return(chunk); Y!{!s*M#_AM8l
}
counts = *nobjs;
if (1 == counts)
{ V_9pL3e*bA
   return(chunk); V,lc(C-`Z
}
my_free_list = pHead->uFreelist + freelist_index(n); &Dj_yp*F?;}k
result = (Obj*)chunk;
*my_free_list = next_obj = (Obj*)(chunk + n*num); 3Ow!mL c_Qm
for (i = 1; ; i++)
{
   current_obj = next_obj; 9hD5nxV?\m
   next_obj = (Obj*)((char*)next_obj + n); !Q#snaE{6BT U
   if (counts - 1 == i)
   {
      current_obj->M_free_list_link = 0; 4U2l(^o.},J
      break; yzG'Y3GT,Q)RYU
   } ~J4I"Bg LMzt
   else
   {
      current_obj->M_free_list_link = next_obj; $y+oJ%x]]}
   } M?"`h0T{ ye4x
}
return(result);
  }; el8^H9O3R
/*这个函数可以改写成自己的共享内存分配函数*/ ^/@Ioy#H(u t
static void InitShm()
  { ?2w*D?v&NO8H0F
int i,size=1000;
pHead = (Cookie*)malloc(sizeof(Cookie)+size); E4@*]?b9ZG#t
pHead->iTotalsize = sizeof(Cookie)+size; 'g/o!Q*FKR9k;m
pHead->pStartall  = pHead; .IAWD.?#j+N"B ~l
pHead->pStartfree = (char*)pHead + sizeof(Cookie); *XW1k&yM9}^$ygD2W
pHead->pEndfree = (char*)pHead + pHead->iTotalsize; Wh.\&X;yH.jU
for(i=0 ; i <NODENUMS ; i++)
{
   pHead->sFreelistIndex[i]=0; 6U"t$q3b |\X-O!dB+H H
   pHead->uFreelist[i]=0;
   pHead->iUseNum[i]=0; gzE2t p:hC9C1n
} #w h*y[)AQ'C3ug
  }
  static void PrintFreelistAndCookie()
  { ,h6|T%P6x/w3l$POV
int i,j; -X~8\7\8}N1y#?.Q{,wy2Y#f
Obj* my_free_list;
std::cout<<"Cookie info :"<<std::endl;
std::cout<<"sizeof(struct Cookie) = "<<sizeof(Cookie)<<std::endl; uQyB_$J:E
std::cout<<"Totalsize    = "<<pHead->iTotalsize<<std::endl; dp!~Pmn
std::cout<<"UsedSize    = "<<int(pHead->pStartfree-(char*)pHead)<<std::endl; bo(}{.z0b
std::cout<<"FreepoolSize  = "<<int(pHead->pEndfree - pHead->pStartfree)<<std::endl;
std::cout<<"Startall    = "<<&(pHead->pStartall)<<std::endl; j/R*M"x4JX'l
std::cout<<"Startfree    = "<<&(pHead->pStartfree)<<std::endl; H)zIuc~%s#m
std::cout<<"Endfree    = "<<&(pHead->pEndfree)<<std::endl;
std::cout<<"nFreelist info :"<<std::endl;
for(i=0 ; i<NODENUMS ; i++) y?K8?n-HX}7YQ
{
   j=0; 7i3w%T1mJX(`:y.z
   std::cout<<"iUseNum["<<i<<"] = "<<pHead->iUseNum[i]<<std::endl;
   std::cout<<"FreelistIndex["<<i<<"] = "<<pHead->sFreelistIndex[i]<<std::endl;
   my_free_list = pHead->uFreelist[i]; p9@%l7z#?)_&a
   if(my_free_list->M_client_data != 0)
   { d |kd M!TYdD
      while(my_free_list->M_client_data != 0)
      { tvzw"PE
      j++;
      my_free_list = my_free_list->M_free_list_link;
      } .Aqp)c.x0oh
      std::cout<<"free_list["<<i<<"]; node counts="<<j<<std::endl; j-B.C'P(f9HxI5z%nFWz
   } F)F;{ cQ1x6n[#U
} "zO{6W,Zba
  } `G^ rY E,of
  template <class T1, class T2>
  bool operator== (const MyAlloc<T1>&,const MyAlloc<T2>&) throw()
  {
return true;
  }
  template <class T1, class T2>
  bool operator!= (const MyAlloc<T1>&,const MyAlloc<T2>&) throw()  s x:p'AI)Jn#_
  { ,uTI,MW
return false; .vM,G8Ye'L5fE
  } )i8Y?[%a6r
}
#endif /*MY_ALLOCATOR_H_*/ 8qX4PAAE3IN%D
测试程序的源码如下： *t:a ^,CM,_ S

// MyStl.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h" 0PNnH(I7i"}
#include <map> !Ql-s)~@:P3l
#include <vector>
#include <string> N$P:R/~F/H$`1kU'T
#include <utility>
#include <iostream>
#include "MyAlloc.h" g Lu/v_!z [G
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
  happyever ::InitShm();
  multimap<string,int,less<string>,happyever ::MyAlloc<string> > m; Cqglcq\D
  m.insert(make_pair(string("Harry"), 32)); U.Iw+Z3|8b8h2U4n0o(c
  m.insert(make_pair(string("Mary"), 59)); 4C9x"Y8NU?*L,?f1Yo
  m.insert(make_pair(string("Roger"), 18));
  m.insert(make_pair(string("Nancy"), 37)); ?q+\7M!q9zS
  m.insert(make_pair(string("Mary"), 23));
u[&W(Z-A A'y7E `J2g
  typedef multimap<string,int,less<string>,happyever ::MyAlloc<string> >::iterator Iter;
  for (Iter p = m.begin(); p != m.end(); p++)
  { .[&a0m(T7C\OD?tP_
cout << p->first << "," << p->second << endl;
  }
  Iter p = m.find("Harry"); Sl,PJLZ4H1X?qG
  m.erase(p);
  /*p = m.find("Harry");
  cout << "Harry is: " << p->second << "." << endl;*/

  for (Iter p = m.begin(); p != m.end(); p++)
  {
cout << p->first << "," << p->second << endl; f[j"o2d({PR1w(x
  }
w8jv WP{8j4iM5`6K3z
  return 0; Jv-o[e6o |S7}
} /o7Oez3m;q
以上程序在vs2005，vc6上测试通过。使用MinGW编译的时候只需要去掉vc的预编译头文件 m3l6nzx%Oc Ul
#include "stdafx.h" %yNQg{!vY R)dr
^o~*w!\ m

　　即可。

　　以上程序只要稍微修改，就可以实现共享内存的管理，可以方便的使用标准库提供的容器。加上信号量的锁机制。1r BSYk#e$Zi3~t)jk#D
@-Hr;_3wo1\
　　以上为了学习而改写的SGI的stl二级分配算法实现的。以上代码存在一定的局限性。我另外完整实现了共享内存管理的STL标准的alloctor程序，使用posix信号量加锁。目前应用在aix的xlC编译环境下。因为源码涉及公司的商业秘密，所以不能公开。但基本上以上源码已经体现了自己管理内存的完整思路，供这方面需求的朋友一起学习研究用。

页: [1]

我爱电脑技术论坛's Archiver

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