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

　2008-03-08 21:38:03　来源：WEB开发网　　　

核心提示：根据sgi 的STL源码的二级分配算法改写的内存池分配程序，只要稍微修改就可以实现共享内存方式治理，为C++标准库容器写自己的内存分配程序，使用C++标准库容器中的map，set，但基本上以上源码已经体现了自己治理内存的完整思路，供这方面需求的朋友一起学习研究用，multimap，multiset测试通过

　　根据sgi 的STL源码的二级分配算法改写的内存池分配程序，只要稍微修改就可以实现共享内存方式治理，使用C++标准库容器中的map，set，multimap，multiset测试通过，vector测试通不过，原因是在内存回收的时候考虑的比较简单，vector每次分配内存个数不固定，回收也不固定，这样的话，程序还需要继续完善。　　内存池治理程序源码如下：以下是引用片段：
#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编译环境下。因为源码涉及公司的商业秘密，所以不能公开。但基本上以上源码已经体现了自己治理内存的完整思路，供这方面需求的朋友一起学习研究用。