Chinaunix首页 | 论坛 | 博客

Fosdccf.blog.chinaunix.net

首页　| 　博文目录　| 　关于我

sdccf

  • 博客访问： 103587243
  • 博文数量： 19283
  • 博客积分： 9968
  • 博客等级： 上将
  • 技术积分： 196062
  • 用 户 组： 普通用户
  • 注册时间： 2007-02-07 14:28
文章分类

全部博文（19283）

文章存档

2011年（1）

2009年（125）

2008年（19094）

2007年（63）

我的朋友
最近访客
推荐博文
相关博文
为C++标准库容器写自己的内存分配程序

分类： C/C++

2008-05-18 20:31:29

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

　　内存池管理程序源码如下：

以下是引用片段：
#ifndef MY_ALLOCATOR_H_
#define MY_ALLOCATOR_H_
#include "stdafx.h"
#include 
#include 
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 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 
    struct rebind 
    {
      typedef MyAlloc other;
    };
    pointer address (reference value) const 
    {
      return &value;
    }
    const_pointer address (const_reference value) const 
    {
      return &value;
    }
    MyAlloc() throw() 
    {
      std::cout<<"MyAlloc"<    }
    MyAlloc(const MyAlloc& x) throw() 
    {
      std::cout<<"const MyAlloc"<    }
    template 
    MyAlloc (const MyAlloc& x) throw()
    {
      std::cout<<"const MyAlloc"<    }
    ~MyAlloc() throw() 
    {
      std::cout<<"~MyAlloc"<    }
    size_type max_size () const throw() 
    {
      return std::numeric_limits::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 
  int MyAlloc::round_up(int bytes)
  {
    int i;
    i = bytes;
    if(bytes < ALIGN)
    {
      i = ALIGN;
    }
    std::cout<<"round_up:bytes="<    return i;
  };
  template 
  int MyAlloc::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="<          return i;
        }
      }
    }
    std::cout<<"freelist_index:bytes="<    return i;
  };
  template 
  int MyAlloc::freelist_getindex(int bytes)
  {
    int i;
    for(i=0 ; i< NODENUMS ; i++)
    {
      if(pHead->sFreelistIndex[i] == bytes)
        break;
    }
    std::cout<<"freelist_getindex:bytes="<    return i;
  };
  template 
  char* MyAlloc::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 = "<      <<",bytes_left = "<    if (bytes_left >= total_bytes)
    {
      result = pHead->pStartfree;
      pHead->pStartfree += total_bytes;
      std::cout<<"chunk_alloc:total_bytes = "<        <<",result = "<<*result<<",start_free = "<<&(pHead->pStartfree)<    }
    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 = "<        <<",result = "<<*result<<",start_free = "<<&(pHead->pStartfree)<    }
    else
    {
      /*还需要处理回收其他空闲freelist里面的空间*/
      result = NULL;
    }
    return(result);
  };
  template 
  void* MyAlloc::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     {
      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::cout<<"sizeof(struct Cookie) = "<    std::cout<<"Totalsize     = "<iTotalsize<    std::cout<<"UsedSize      = "<pStartfree-(char*)pHead)<    std::cout<<"FreepoolSize  = "<pEndfree - pHead->pStartfree)<    std::cout<<"Startall      = "<<&(pHead->pStartall)<    std::cout<<"Startfree     = "<<&(pHead->pStartfree)<    std::cout<<"Endfree       = "<<&(pHead->pEndfree)<    std::cout<<"nFreelist info :"<    for(i=0 ; i    {
      j=0;
      std::cout<<"iUseNum["<iUseNum[i]<      std::cout<<"FreelistIndex["<sFreelistIndex[i]<      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["<      }
    }
  }
  template 
  bool operator== (const MyAlloc&,const MyAlloc&) throw() 
  {
    return true;
  }
  template 
  bool operator!= (const MyAlloc&,const MyAlloc&) throw() 
  {
    return false;
  }
}
#endif /*MY_ALLOCATOR_H_*/
测试程序的源码如下：

// MyStl.cpp : 定义控制台程序的入口点。
//
#include "stdafx.h"
#include 
#include 
#include 
#include 
#include 
#include "MyAlloc.h"
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
  happyever ::InitShm();
  multimap,happyever ::MyAlloc > 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,happyever ::MyAlloc >::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编译环境下。因为源码涉及公司的商业秘密，所以不能公开。但基本上以上源码已经体现了自己管理内存的完整思路，供这方面需求的朋友一起学习研究用。

阅读(277) | 评论(0) | 转发(0) |
0

上一篇：VC++6.0中控制运行唯一实例

下一篇：C与C++中标准输入实现方式上的一点区别

给主人留下些什么吧！~~
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6