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

LOK 发表于 2008-4-18 10:46

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

根据sgi 的STL源码的二级分配算法改写的内存池分配程序，只要稍微修改就可以实现共享内存方式管理，使用C++标准库容器中的map，set，multimap，multiset测试通过，vector测试通不过，原因是在内存回收的时候考虑的比较简单，vector每次分配内存个数不固定，回收也不固定，这样的话，程序还需要继续完善。\,lb6G@Eb[%p`
F2z-ccp"s
　　内存池管理程序源码如下：^[r:MC?)j;y
l&h#A)G_
以下是引用片段： U?x4`m}O1@
#ifndef MY_ALLOCATOR_H_
#define MY_ALLOCATOR_H_
#include "stdafx.h" :~F~~5KGRq"q6?
#include <limits> 1MNuP7QvvS
#include <iostream>
namespace happyever  @6Ypk z8q,Sud s
{
  enum { NODENUMS = 2 };
  union _Obj
  { -zi1Blk2jN'v2J
union _Obj* M_free_list_link; {p2oB9hL8p
char M_client_data[1];    g+Yh$|$]7}A_
  } ; n UF:gsQ,ZW
  typedef union _Obj Obj; T4Qt#b-G(QDl:W
  struct _Cookie [BP EL&v(p
  { !Q@:B/Ez(E
int iShmKey;       /* 共享内存键值 */
int iShmID;       /* iShmKey对应的shmid */ _Ee({f-h W
int iSemKey;       /* 锁信号键值 */ IC4JO?P"NV-y%W[z'e
int iSemID;       /* 锁信号标识 */
int iTotalsize; /* 容器总容量 */ d-U V(Mh;fe
void* pStartall; /* 共享内存自身地址 */
char* pStartfree;  /* 自由空间的开始地址*/
char* pEndfree; /* 自由空间的结束地址*/ i3\&rb3{a,]3R
int iUseNum[NODENUMS]; jxCTI%Z
/*用来存放free_list中节点的size*/ CP:X8qW3T)cVP
short sFreelistIndex[NODENUMS];
/*存放分配内存节点的链表*/
Obj* uFreelist[NODENUMS]; &k5H1Y};B*f ?JrY
  };
  typedef struct _Cookie Cookie; +t9a+d+zf
  //Obj; wPUn[(g/g9{9}P
  //Cookie; +e{T8A-F/mCs _
  static Cookie *pHead = NULL; FRpn|d%\%M
  template <class T> Ym4MAB+W2C7ieq
  class MyAlloc
  { /u6|lQ.D%f%c3~)r
  private: 8cv}8R2t oMh.zM
static const int ALIGN = sizeof(Obj);
int round_up(int bytes); 8isZ'ua)WQ+@
int freelist_index(int bytes); A$F\6Y@c8T
int freelist_getindex(int bytes); 8[)w_z6W_om
char* chunk_alloc(int size, int *nobjs);
void* refill(int num,int n); 1|g/LN:iNi+oiEVQ
  public:
// type definitions
typedef T       value_type; /V G-EX9fZF0^y
typedef T*    pointer; ?QVS8_'v
typedef const T* const_pointer;
typedef T&    reference; (K(ox*X(iU;[
typedef const T& const_reference; 1h f g3H-_
typedef std::size_t size_type; Vt6Cc'H9w#RM(^L
typedef std::ptrdiff_t difference_type; N!XD&I8|A
template <class U>
struct rebind
{ g7r4a-N,D&fn?
   typedef MyAlloc<U> other; %jX1Hqtn5C
}; ?3T)P`7Y,HL
pointer address (reference value) const  jE Q8og%L`UU
{ 9T"D,QF;Uz-I-wNb
   return &value; j'nrH%G\
} (~i}Lbj;`
const_pointer address (const_reference value) const
{ slO `nmX
   return &value;
} !LcWg(W/M's3sIx
MyAlloc() throw()
{ 0f p*yq9q*Sal
   std::cout<<"MyAlloc"<<std::endl; f2Ft7koI8^
}
MyAlloc(const MyAlloc& x) throw()
{
   std::cout<<"const MyAlloc"<<std::endl; hMX,G} H:H,H|
}
template <class U>
MyAlloc (const MyAlloc<U>& x) throw() ]KI;f'_'^'T U
{ 5i)wA'| t}
   std::cout<<"const MyAlloc<U>"<<std::endl;
}
~MyAlloc() throw()
{
   std::cout<<"~MyAlloc"<<std::endl; ;}y$?:r2aL@v?
} A wp,o/tz*Yp;S
size_type max_size () const throw()  /J7}`&a$cv
{
   return std::numeric_limits<std::size_t>::max() / sizeof(T); 8i%l9`B8s
}
//void PrintFreelistAndCookie(); P8G'Z ?n{9bu
pointer allocate (size_type num, const void* = 0)
{
   pointer ret = 0; "]X x d.u!\M]
   Obj** my_free_list; +a;g~5k#OP)c2x
   Obj* result;
   int index;
   // print message and allocate memory with global new
   std::cerr << "allocate " << num << " element(s)"
      << " of size " << sizeof(T) << std::endl;
   index = freelist_index(sizeof(T));
   if(index >= NODENUMS) 7g8|}!y4I6NK
   { Z)fp |5~ `
      return NULL; NS_@M2`A3I
   } }$l ~q*By n u
   my_free_list = pHead->uFreelist + index;
   //Lock(semid,LOCK_NUM); +a/v-LfA9a@ b
   result = *my_free_list;
   if (result == 0)
   {
      ret = (pointer)refill((int)num, round_up(sizeof(T))); Hs f%}(k~zk
   }
   else ~QXI|d
   { +`;gfe'[
      *my_free_list = result->M_free_list_link; j8F2w ?Cdv
      ret = (pointer)result; [;d9I#c vj
   }
   //UnLock(semid,LOCK_NUM);
   pHead->iUseNum[index] = pHead->iUseNum[index] + (int)num;
   if(0 == ret)
   { #YPn%be-Tm:~6li
      std::cerr << "alloc memory fail!" << std::endl;
      exit(1);
   } )}3M\'S%Vj
   std::cerr << " allocated at: " << (void*)ret << std::endl;
   PrintFreelistAndCookie();
   return ret; zFw }/L
}
void construct (pointer p, const T& value)
{ akiH$Ah
   // initialize memory with placement new )}UOF"Z~/H
   new((void*)p)T(value);
} @Tp\e$I[.Vn_.U
void destroy (pointer p)  Vg%ovk;inz
{ yA;p9K?[/mV-vb
   // destroy objects by calling their destructor yB9Rd1{F5mjxtz.K
   p->~T();
} 6fH B:b.J-o6{
void deallocate (pointer p, size_type num)  *xE? Q k,r0FH[smp`
{
   Obj** my_free_list;
   Obj* q ; X6EbJvIymwF
   int index;
   index = freelist_getindex(sizeof(T)); {&Ld8b rn
   if(index >= NODENUMS) /ywxm^'I
   {
      std::cerr << "deallocate memory fail!" << std::endl;
      exit(1); c/u-q3J]$G?.r
   }
   my_free_list = pHead->uFreelist + index;
   q = (Obj*) p; b8fZ0RQ3EkT
   //Lock(semid,LOCK_NUM);
   /*这个地方可能会有问题*/ `4X5GQ3F[d
   //for(int i=0 ;i<(int)num ; i++) &AP3V.IBT{
   {
      q->M_free_list_link = *my_free_list;
      *my_free_list = q; .U8c[?f
   } BGE)t&t5i BG
   //UnLock(semid,LOCK_NUM);
   pHead->iUseNum[index] = pHead->iUseNum[index] - (int)num;

   std::cerr << "deallocate " << num << " element(s)" d;Ib([&ic9G:F
      << " of size " << sizeof(T) f*e#hDfCo
      << " at: " << (void*)p << std::endl; brn:d2|}(Po+j
   PrintFreelistAndCookie();
}
  };
  template <class T> a"?5`4hb
  int MyAlloc<T>::round_up(int bytes)
  {
int i; Pp{o,zA
i = bytes; #ir&Rae\
if(bytes < ALIGN)
{
   i = ALIGN; ;_6B'Qk G]V
}
std::cout<<"round_up:bytes="<<bytes<<" , return="<<i<<std::endl; j$x1X$x4wO,q
return i;
  }; q3hzWa
  template <class T> A0Wr,C3jg)Nr(C@~
  int MyAlloc<T>::freelist_index(int bytes) )V7w?BiUY&s ^
  { y^u?6^ S]!o/q
int i; fso6O0eZ*_R v
for(i=0 ; i< NODENUMS ; i++)
{ } ?WkW
   if(pHead->sFreelistIndex[i] == bytes)
      break;
}
if(i >= NODENUMS)
{
   for(i=0 ; i< NODENUMS ; i++)
   {
      if(pHead->sFreelistIndex[i] == 0) :Q!E2]8V1~ }
      { u|g`:v{z
      pHead->sFreelistIndex[i] = bytes; hB i&j!h
      std::cout<<"freelist_index:bytes="<<bytes<<" , return="<<i<<std::endl;
      return i; e[hBlIp_'X7H!PO
      }
   } $G6`wr8B7c2`
}
std::cout<<"freelist_index:bytes="<<bytes<<" , return="<<i<<std::endl; 0q I)Y'a^
return i;
  }; P4rb%C#Z/xR)Q4}%b+W]
  template <class T>
  int MyAlloc<T>::freelist_getindex(int bytes) b*ex7Kai ~ ?
  {
int i; i!z/T|yd
for(i=0 ; i< NODENUMS ; i++)
{
   if(pHead->sFreelistIndex[i] == bytes) |5v"@:C9[W7O@\D
      break;
}
std::cout<<"freelist_getindex:bytes="<<bytes<<" , return="<<i<<std::endl;
return i; #JT7UO`} C:O
  };
  template <class T>
  char* MyAlloc<T>::chunk_alloc(int size, int *nobjs)
  { &BkyK)u:Q?.C
char* result; s]E K}k*`{-su3F
int counts = *nobjs; $t8e8T$LCW+|n
int total_bytes = size * counts;
int bytes_left = int(pHead->pEndfree - pHead->pStartfree); Kb7SFr'}
std::cout<<"chunk_alloc:total_bytes = "<<total_bytes
   <<",bytes_left = "<<bytes_left<<std::endl;
if (bytes_left >= total_bytes)
{ 8e)X$G)m2i-K
   result = pHead->pStartfree; *fBK5]1PMt
   pHead->pStartfree += total_bytes; nl,}Uy{#S3~ b
   std::cout<<"chunk_alloc:total_bytes = "<<total_bytes
      <<",result = "<<*result<<",start_free = "<<&(pHead->pStartfree)<<std::endl; eIL2??"f3F~
}
else if (bytes_left >= size) n!XcX@{q&]kn
{ 9d3n0dC9v_@-U
   counts = bytes_left/size; `k2d-u*u(Q~
   total_bytes = size * counts; I~$?P/?$h8ey
   result = pHead->pStartfree; 7vVrK'i
   pHead->pStartfree += total_bytes; qG;a+p#NxuD!]
   *nobjs = counts; +cd$IO^9v
   std::cout<<"chunk_alloc:total_bytes = "<<total_bytes<<",nobjs = "<<nobjs
      <<",result = "<<*result<<",start_free = "<<&(pHead->pStartfree)<<std::endl; `EE2q6lH4_}
}
else
{ H3w_EkH
   /*还需要处理回收其他空闲freelist里面的空间*/
   result = NULL;
} ;X\sB#?v.E$G%e
return(result); 3fO9K9[N%Z&hQ
  };
  template <class T>
  void* MyAlloc<T>::refill(int num,int n)
  { #^_]#g ]K-U
int counts = num;
int *nobjs = &counts; qo6i};~l(v vNT
char* chunk; JBH+@ ~9P~
Obj** my_free_list;
Obj* result;
Obj* current_obj;
Obj* next_obj;
int i;
chunk = chunk_alloc(n, nobjs); .b0i'wFu*ZY
if(chunk == NULL) jpw3XjTf~
{
   return(chunk);
} n1`t+eK:] [,g
counts = *nobjs; :Bf2@0V:B.X&|)[
if (1 == counts)
{
   return(chunk); ]4RO(w8{V
}
my_free_list = pHead->uFreelist + freelist_index(n);
result = (Obj*)chunk; vvqk1j5Y
*my_free_list = next_obj = (Obj*)(chunk + n*num);
for (i = 1; ; i++) )M4WC[&s
{ ){ ZNq2a*A0j
   current_obj = next_obj; 8h'\de-Qq*V
   next_obj = (Obj*)((char*)next_obj + n);
   if (counts - 1 == i)
   { '^(Uuw5z;g'C
      current_obj->M_free_list_link = 0; IsW:U!S#G*}q
      break; 5\%z-Dt*pa5i a
   } u*bQE*S5a6y,]
   else Mc#ldP.U ^b
   {
      current_obj->M_free_list_link = next_obj; fSz ^!XDrbM(u
   } G8xQ(Q"l2T-f
} K-vlr:`0K:Np
return(result);
  };
/*这个函数可以改写成自己的共享内存分配函数*/
static void InitShm() #tV]Rsy'Kh
  {
int i,size=1000; 0JI-L+{$x
pHead = (Cookie*)malloc(sizeof(Cookie)+size); 4}"To0K/y/t
pHead->iTotalsize = sizeof(Cookie)+size; N!nka#uRj;P8v
pHead->pStartall  = pHead; D0aY/F|._4j$M
pHead->pStartfree = (char*)pHead + sizeof(Cookie);
pHead->pEndfree = (char*)pHead + pHead->iTotalsize; ]:f[~O\
for(i=0 ; i <NODENUMS ; i++) 1H)vi5zgC$N9OT
{ Z]SD*T$V!\G
   pHead->sFreelistIndex[i]=0;
   pHead->uFreelist[i]=0; }iA#Gx O l&H
   pHead->iUseNum[i]=0;
} "{g:W*It3F*A
  }
  static void PrintFreelistAndCookie()
  {
int i,j; %d L7]H`o M]J
Obj* my_free_list;
std::cout<<"Cookie info :"<<std::endl; !|p*bx;t$L&hJ,~t n9M
std::cout<<"sizeof(struct Cookie) = "<<sizeof(Cookie)<<std::endl;
std::cout<<"Totalsize    = "<<pHead->iTotalsize<<std::endl; NCl6wC8i2M/oc
std::cout<<"UsedSize    = "<<int(pHead->pStartfree-(char*)pHead)<<std::endl;
std::cout<<"FreepoolSize  = "<<int(pHead->pEndfree - pHead->pStartfree)<<std::endl; a&x*h V H0^6MR5] L%A
std::cout<<"Startall    = "<<&(pHead->pStartall)<<std::endl;
std::cout<<"Startfree    = "<<&(pHead->pStartfree)<<std::endl;
std::cout<<"Endfree    = "<<&(pHead->pEndfree)<<std::endl;
std::cout<<"nFreelist info :"<<std::endl;
for(i=0 ; i<NODENUMS ; i++) `(l e/`F-q6gwj
{ ;jj@ip
   j=0; C*|j]$L @,L!z
   std::cout<<"iUseNum["<<i<<"] = "<<pHead->iUseNum[i]<<std::endl;
   std::cout<<"FreelistIndex["<<i<<"] = "<<pHead->sFreelistIndex[i]<<std::endl; u(l#d8]l@am
   my_free_list = pHead->uFreelist[i];
   if(my_free_list->M_client_data != 0)
   { If%l2O }b3f
      while(my_free_list->M_client_data != 0) @#BSx%d m Bn3r1iY
      { IsnRob8j
      j++;
      my_free_list = my_free_list->M_free_list_link; HiDbQ+H
      } lV1D#\8R9H:R&O({^
      std::cout<<"free_list["<<i<<"]; node counts="<<j<<std::endl; 3W0v4a&hY(v
   } Z8@.cr3@`Qa
}
  }
  template <class T1, class T2>
  bool operator== (const MyAlloc<T1>&,const MyAlloc<T2>&) throw()  {|K%p`(H
  {
return true; ~ QxP|Z)ZJX
  }
  template <class T1, class T2>
  bool operator!= (const MyAlloc<T1>&,const MyAlloc<T2>&) throw()
  {
return false; GXXt QyR d&w%r
  } OfM6~0QNq
}
#endif /*MY_ALLOCATOR_H_*/
测试程序的源码如下：
T/XQ0kM2}I
// MyStl.cpp : 定义控制台应用程序的入口点。 )Nn8[!f`nR
//
#include "stdafx.h"
#include <map>
#include <vector> 9nmY3[8p [
#include <string>
#include <utility>
#include <iostream>
#include "MyAlloc.h"
using namespace std; f,bZF OXIY
int _tmain(int argc, _TCHAR* argv[]) DHk7^ }
{ #G4S4_ Vb4q
  happyever ::InitShm();
  multimap<string,int,less<string>,happyever ::MyAlloc<string> > m;
  m.insert(make_pair(string("Harry"), 32)); o#MB1Z(?bBA
  m.insert(make_pair(string("Mary"), 59)); p8pz2Y |*]I
  m.insert(make_pair(string("Roger"), 18));
  m.insert(make_pair(string("Nancy"), 37));
  m.insert(make_pair(string("Mary"), 23));
'~(C7LWO#e sVp*of-u
  typedef multimap<string,int,less<string>,happyever ::MyAlloc<string> >::iterator Iter; ;Dn2h+oJ-r KY.Rk
  for (Iter p = m.begin(); p != m.end(); p++) 9[:}S9PX$e
  { 4PD+r[+[%i6f
cout << p->first << "," << p->second << endl; yqH$D v
  }
  Iter p = m.find("Harry");
  m.erase(p);
  /*p = m.find("Harry"); ^9H_S:]*D5F7On5c
  cout << "Harry is: " << p->second << "." << endl;*/

  for (Iter p = m.begin(); p != m.end(); p++) /xcW$q}tOA
  { !nl'cKh
cout << p->first << "," << p->second << endl; $VH.`8GZ7C3{$Y?k
  }

  return 0; 6Q&oi:rnm5ZdM(|
}
以上程序在vs2005，vc6上测试通过。使用MinGW编译的时候只需要去掉vc的预编译头文件 Es/y\3NU6e4_E
#include "stdafx.h"

　　即可。
0fcu6G8^6q}d
　　以上程序只要稍微修改，就可以实现共享内存的管理，可以方便的使用标准库提供的容器。加上信号量的锁机制。/k7xQk)N-D
t4x o{zn
　　以上为了学习而改写的SGI的stl二级分配算法实现的。以上代码存在一定的局限性。我另外完整实现了共享内存管理的STL标准的alloctor程序，使用posix信号量加锁。目前应用在aix的xlC编译环境下。因为源码涉及公司的商业秘密，所以不能公开。但基本上以上源码已经体现了自己管理内存的完整思路，供这方面需求的朋友一起学习研究用。

页: [1]

我爱电脑技术论坛's Archiver

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