程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 為C++標准庫容器寫自己的內存分配程序

為C++標准庫容器寫自己的內存分配程序

編輯：C++入門知識

　　根據sgi 的STL源碼的二級分配算法改寫的內存池分配程序，只要稍微修改就可以實現共享內存方式治理，使用C++標准庫容器中的map，set，multimap，multiset測試通過，vector測試通不過，原因是在內存回收的時候考慮的比較簡單，vector每次分配內存個數不固定，回收也不固定，這樣的話，程序還需要繼續完善。　　內存池治理程序源碼如下：<？XML:namespace prefix = std /><？xml:namespace prefix = sizeof(Cookie)< 以下是引用片段：
　　#ifndef MY_ALLOCATOR_H_
　　#define MY_ALLOCATOR_H_
　　#include "stdafx.h"
　　#include <limits>
　　#include <iostream>
　　namespace happyever
　　{
　　  enum { NODENUMS = 2 };
　　  union _Obj
　　  {
　　    union _Obj* M_free_list_link;
　　    char M_client_data[1];
　　  } ;
　　  typedef union _Obj Obj;
　　  strUCt _Cookie
　　  {
　　    int iShmKey;        /* 共享內存鍵值 */
　　    int iShmID;         /* iShmKey對應的shmid */
　　    int iSemKey;        /* 鎖信號鍵值 */
　　    int iSemID;         /* 鎖信號標識 */
　　    int iTotalsize;    /* 容器總容量 */
　　    void* pStartall;   /* 共享內存自身地址 */
　　    char* pStartfree;  /* 自由空間的開始地址*/
　　    char* pEndfree;    /* 自由空間的結束地址*/
　　    int iUseNum[NODENUMS];
　　    /*用來存放free_list中節點的size*/
　　    short sFreelistIndex[NODENUMS];
　　    /*存放分配內存節點的鏈表*/
　　    Obj* uFreelist[NODENUMS];
　　  };
　　  typedef struct _Cookie Cookie;
　　  //Obj;
　　  //Cookie;
　　  static Cookie *pHead = NULL;
　　  template <class T>
　　  class MyAlloc
　　  {
　　  private:
　　    static const int ALIGN = sizeof(Obj);
　　    int round_up(int bytes);
　　    int freelist_index(int bytes);
　　    int freelist_getindex(int bytes);
　　    char* chunk_alloc(int size, int *nobjs);
　　    void* refill(int num,int n);
　　  public:
　　    // type definitions
　　    typedef T        value_type;
　　    typedef T*       pointer;
　　    typedef const T* const_pointer;
　　    typedef T&       reference;
　　    typedef const T& const_reference;
　　    typedef std::size_t    size_type;
　　    typedef std::ptrdiff_t difference_type;
　　    template <class U>
　　    struct rebind
　　    {
　　      typedef MyAlloc<U> other;
　　    };
　　    pointer address (reference value) const
　　    {
　　      return &value;
　　    }
　　    const_pointer address (const_reference value) const
　　    {
　　      return &value;
　　    }
　　    MyAlloc() throw()
　　    {
　　      std::cout<<"MyAlloc"<<std::endl;
　　    }
　　    MyAlloc(const MyAlloc& x) throw()
　　    {
　　      std::cout<<"const MyAlloc"<<std::endl;
　　    }
　　    template <class U>
　　    MyAlloc (const MyAlloc<U>& x) throw()
　　    {
　　      std::cout<<"const MyAlloc<U>"<<std::endl;
　　    }
　　    ~MyAlloc() throw()
　　    {
　　      std::cout<<"~MyAlloc"<<std::endl;
　　    }
　　    size_type max_size () const throw()
　　    {
　　      return std::numeric_limits<std::size_t>::max() / sizeof(T);
　　    }
　　    //void PrintFreelistAndCookie();
　　    pointer allocate (size_type num, const void* = 0)
　　    {
　　      pointer ret = 0;
　　      Obj** my_free_list;
　　      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)
　　      {
　　        return NULL;
　　      }
　　      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 << "alloc memory fail!" << std::endl;
　　        exit(1);
　　      }
　　      std::cerr << " allocated at: " << (void*)ret << std::endl;
　　      PrintFreelistAndCookie();
　　      return ret;
　　    }
　　    void construct (pointer p, const T& value)
　　    {
　　      // initialize memory with placement new
　　      new((void*)p)T(value);
　　    }
　　    void destroy (pointer p)
　　    {
　　      // destroy objects by calling their destructor
　　      p->~T();
　　    }
　　    void deallocate (pointer p, size_type num)
　　    {
　　      Obj** my_free_list;
　　      Obj* q ;
　　      int index;
　　      index = freelist_getindex(sizeof(T));
　　      if(index >= NODENUMS)
　　      {
　　        std::cerr << "deallocate memory fail!" << std::endl;
　　        exit(1);
　　      }
　　      my_free_list = pHead->uFreelist + index;
　　      q = (Obj*) p;
　　      //Lock(semid,LOCK_NUM);
　　      /*這個地方可能會有問題*/
　　      //for(int i=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)"
　　        << " of size " << sizeof(T)
　　        << " at: " << (void*)p << std::endl;
　　      PrintFreelistAndCookie();
　　    }
　　  };
　　  template <class T>
　　  int MyAlloc<T>::round_up(int bytes)
　　  {
　　    int i;
　　    i = bytes;
　　    if(bytes < ALIGN)
　　    {
　　      i = ALIGN;
　　    }
　　    std::cout<<"round_up:bytes="<<bytes<<" , return="<<i<<std::endl;
　　    return i;
　　  };
　　  template <class T>
　　  int MyAlloc<T>::freelist_index(int bytes)
　　  {
　　    int i;
　　    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;
　　          return i;
　　        }
　　      }
　　    }
　　    std::cout<<"freelist_index:bytes="<<bytes<<" , return="<<i<<std::endl;
　　    return i;
　　  };
　　  template <class T>
　　  int MyAlloc<T>::freelist_getindex(int bytes)
　　  {
　　    int i;
　　    for(i=0 ; i< NODENUMS ; i++)
　　    {
　　      if(pHead->sFreelistIndex[i] == bytes)
　　        break;
　　    }
　　    std::cout<<"freelist_getindex:bytes="<<bytes<<" , return="<<i<<std::endl;
　　    return i;
　　  };
　　  template <class T>
　　  char* MyAlloc<T>::chunk_alloc(int size, int *nobjs)
　　  {
　　    char* result;
　　    int counts = *nobjs;
　　    int total_bytes = size * counts;
　　    int bytes_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;
　　    }
　　    else if (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 <class T>
　　  void* MyAlloc<T>::refill(int num,int n)
　　  {
　　    int counts = num;
　　    int *nobjs = &counts;
　　    char* chunk;
　　    Obj** my_free_list;
　　    Obj* result;
　　    Obj* current_obj;
　　    Obj* next_obj;
　　    int i;
　　    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);
　　  };
　　/*這個函數可以改寫成自己的共享內存分配函數*/
　　static void InitShm()
　　  {
　　    int i,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;
　　    }
　　  }
　　  static void PrintFreelistAndCookie()
　　  {
　　    int i,j;
　　    Obj* my_free_list;
　　    std::cout<<"Cookie info :"<<std::endl;
　　    std::cout<<"sizeof(struct Cookie) = "<<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<<"nFreelist info :"<<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<<"]; node counts="<<j<<std::endl;
　　      }
　　    }
　　  }
　　  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()
　　  {
　　    return false;
　　  }
　　}
　　#endif /*MY_ALLOCATOR_H_*/
　　測試程序的源碼如下：
　　
　　// MyStl.cpp : 定義控制台應用程序的入口點。
　　//
　　#include "stdafx.h"
　　#include <map>
　　#include <vector>
　　#include <string>
　　#include <utility>
　　#include <iostream>
　　#include "MyAlloc.h"
　　using namespace std;
　　int _tmain(int argc, _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));
　　
　　  typedef multimap<string,int,less<string>,happyever ::MyAlloc<string> >::iterator Iter;
　　  for (Iter p = m.begin(); p != m.end(); p++)
　　  {
　　    cout << p->first << "," << p->second << endl;
　　  }
　　  Iter p = m.find("Harry");
　　  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;
　　  }
　　
　　  return 0;
　　}
　　以上程序在vs2005，vc6上測試通過。使用MinGW編譯的時候只需要去掉vc的預編譯頭文件
　　#include "stdafx.h"
　　　　即可。　　以上程序只要稍微修改，就可以實現共享內存的治理，可以方便的使用標准庫提供的容器。加上信號量的鎖機制。　　以上為了學習而改寫的SGI的stl二級分配算法實現的。以上代碼存在一定的局限性。我另外完整實現了共享內存治理的STL標准的alloctor程序，使用posix信號量加鎖。目前應用在aix的xlC編譯環境下。因為源碼涉及公司的商業秘密，所以不能公開。但基本上以上源碼已經體現了自己治理內存的完整思路，供這方面需求的朋友一起學習研究用。