memory_pool.hpp

一个内存池的allocator,参考stl源码的内存池实现

#ifndef _MEMPOOL_HPP_
#define _MEMPOOL_HPP_

#include <cstddef>
#include <cstdio>
#include <string>
#include <stdexcept>
#include <iostream>

using namespace std;

namespace happycode
{
	struct mempool_out_of_blocksize : public runtime_error
        { mempool_out_of_blocksize(const string& s):runtime_error(s){};};

	struct mempool_out_of_memory : public runtime_error
        { mempool_out_of_memory(const string& s):runtime_error(s){};};
	
	struct mempool_init_error : public runtime_error
        { mempool_init_error(const string& s):runtime_error(s){};};

	struct mempool_out_of_range : public runtime_error
        { mempool_out_of_range(const string& s):runtime_error(s){};};


	template<int MIN_BLOCK_SIZE,int MAX_BLOCK_SIZE>
	class MemoryPool
	{
	enum{ALIGN=8};	//内存间隔为8
	enum{NFREELISTS=(MAX_BLOCK_SIZE-MIN_BLOCK_SIZE)/ALIGN + 1};
	enum{INIT_BLOCK_NUM=20};		//最小需要20块

	union obj {
		union obj * free_list_link;
		char client_data[1];
	};
	
	public:
		MemoryPool() {};
		~MemoryPool() {};

	public:
		void init_mem(const void *start,size_t size) throw(mempool_init_error);
		void *allocate(size_t n) throw(mempool_out_of_blocksize,mempool_out_of_memory);
		void *deallocate(void *p,size_t n) throw(mempool_out_of_blocksize,mempool_out_of_range);
		void *reallocate(void *p,size_t old_sz,size_t new_sz) throw(mempool_out_of_blocksize,mempool_out_of_memory,mempool_out_of_range);
		string dump();
	private:
		int _valid;

		char *_start_adr;	//起始地址
		char *_end_adr;	//结束地址
		char *_start_free; //空余起始
		char *_end_free;	//空余结束

		obj * volatile free_list[NFREELISTS];	//节点

	private:
		size_t ROUND_UP(size_t bytes) {
			return (((bytes) + ALIGN-1) & ~(ALIGN-1));
		}

		size_t FREELIST_INDEX(size_t bytes) {
			int val = bytes - MIN_BLOCK_SIZE;
			val = val>0?val:0;
			return val/ALIGN;
		}

		size_t minsize() {
			int size = INIT_BLOCK_NUM*(MIN_BLOCK_SIZE + MAX_BLOCK_SIZE)*NFREELISTS/2;
			return size*3/2;	//留有1/3为free_mem
		}

		void *refill(size_t n);
		char *chunk_alloc(size_t size,int &nobjs);
	};
/////////////////////////////////////////////////////////////////////////////////////
//  
// 实现
/////////////////////////////////////////////////////////////////////////////////////
	template<int MIN_BLOCK_SIZE,int MAX_BLOCK_SIZE>
	string MemoryPool<MIN_BLOCK_SIZE,MAX_BLOCK_SIZE>::dump()
	{
		char info1[36] = {0};
		sprintf(info1,"memory pool size:%d\n",_end_adr - _start_adr);
		char info2[36] = {0};
		sprintf(info2,"start address:%x  end address:%x\n",_start_adr,_end_adr);
		char info3[128] = {0};
		sprintf(info3,"min_block:%d,max_block:%d,free list num:%d,init block num:%d\n",
					MIN_BLOCK_SIZE,MAX_BLOCK_SIZE,NFREELISTS,INIT_BLOCK_NUM);
		char info4[36] = {0};
		sprintf(info4,"free memory size:%d,start address:%x\n",_end_free - _start_free,_start_free);
	
		string ret = string(info1) + string(info2) + string(info3) + string(info4);

		for(int i=0;i<NFREELISTS;i++) {
			obj *o = free_list[i];
			int count = 0;
			while(o!= NULL) {
				o = o->free_list_link;
				count += 1;
			}	

			char t[128] = {0};
			sprintf(t,"<list %d size %d>",i+1,count);
			ret += string(t);
		}

		ret += string("\n\n");
		return ret;
	}

	template<int MIN_BLOCK_SIZE,int MAX_BLOCK_SIZE>
	inline void MemoryPool<MIN_BLOCK_SIZE,MAX_BLOCK_SIZE>::init_mem(const void *start,size_t size) 
	throw(mempool_init_error)
	{
		int nlists = NFREELISTS;
		int b_num = INIT_BLOCK_NUM;
	
		int min_size = minsize();
		if ( min_size > size ) {
			char tmp[128]= {0};
			sprintf(tmp,"memory size too little:%d,need %d for min\n",size,min_size);
			throw mempool_init_error(tmp);
		}
		
		_start_adr = (char *)(const_cast<void *>(start));	//起始地址
		_end_adr = _start_adr + size;	//结束地址

		char *pos = _start_adr;
		int block_size = MIN_BLOCK_SIZE;
		for(int i=0;i<nlists;i++) {
			free_list[i] = (obj *)pos;
			obj *o = free_list[i];	//the first block
			int bcount = 0;

			while(bcount < b_num-1) {
				o->free_list_link = (obj *)((char *)o + block_size);
				o = o->free_list_link;
				bcount += 1;
			}

			o->free_list_link = NULL;	//the last

			pos += block_size * b_num;
			block_size+=ALIGN;
		}

		_start_free = pos;		// free pool
		_end_free = _end_adr;

		_valid = 1;
	};


	template<int MIN_BLOCK_SIZE,int MAX_BLOCK_SIZE>
	inline void *MemoryPool<MIN_BLOCK_SIZE,MAX_BLOCK_SIZE>::allocate(size_t n) 
	throw(mempool_out_of_blocksize,mempool_out_of_memory)
	{
		assert(_valid!=0);


		cout << "allocate for :" << n << endl;

		obj * volatile * my_free_list;
		obj * result;

		if ( n > (size_t)MAX_BLOCK_SIZE ) {
			char tmp[128]= {0};
			sprintf(tmp,"block size too large:%d,max size:%d\n",n,MAX_BLOCK_SIZE);
			throw mempool_out_of_blocksize(tmp);
		}		

		my_free_list = free_list + FREELIST_INDEX(n);
		result = *my_free_list;
		if ( result == 0 ) {
			void *r = refill(ROUND_UP(n));
			if ( r == NULL )
				throw mempool_out_of_memory("out of memory pool");

			return r;
		}

		*my_free_list = result->free_list_link;
		return result;
	};

	template<int MIN_BLOCK_SIZE,int MAX_BLOCK_SIZE>
	inline void *MemoryPool<MIN_BLOCK_SIZE,MAX_BLOCK_SIZE>::deallocate(void *p,size_t n) 
	throw(mempool_out_of_blocksize,mempool_out_of_range)
	{
		assert(_valid!=0);

		cout << "deallocate for:" << n << endl;
	
		if ( n > (size_t)MAX_BLOCK_SIZE ) {
			char tmp[128]= {0};
			std::sprintf(tmp,"block size too large:%d,max size:%d\n",n,MAX_BLOCK_SIZE);
			throw mempool_out_of_blocksize(tmp);
		}

		if ( !(((char *)p>=_start_adr)&&((char *)p+n<=_end_adr)) )
			throw mempool_out_of_range("address out of memory pool range");

		obj *q = (obj *)p;
		obj * volatile * my_free_list;

		my_free_list = free_list + FREELIST_INDEX(n); 
		q->free_list_link = *my_free_list;
		*my_free_list = q;
	};

	template<int MIN_BLOCK_SIZE,int MAX_BLOCK_SIZE>
	inline void *MemoryPool<MIN_BLOCK_SIZE,MAX_BLOCK_SIZE>::reallocate(void *p,size_t old_sz,size_t new_sz) 
	throw(mempool_out_of_blocksize,mempool_out_of_memory,mempool_out_of_range)
	{
		void *result;
		size_t copy_sz;

		result = allocate(new_sz);
		copy_sz = new_sz > old_sz?old_sz:new_sz;
		::memcpy(result,p,copy_sz);

		//防止mem leak
		try {
			deallocate(p,old_sz);
		} catch(...) {
			deallocate(result,new_sz);
			throw;
		}

		return result;
	};

	template<int MIN_BLOCK_SIZE,int MAX_BLOCK_SIZE>
	inline void *MemoryPool<MIN_BLOCK_SIZE,MAX_BLOCK_SIZE>::refill(size_t n)
	{
		int nobjs = 20;

		char * chunk = chunk_alloc(n,nobjs); //nobjs is in-out para ,by reference

		if ( nobjs <= 1 )
			return chunk;

		//调整free list
		obj * volatile * my_free_list = free_list + FREELIST_INDEX(n);
		obj * result = (obj *)chunk;

		obj * next_obj,*current_obj;
		*my_free_list = next_obj = (obj *)(chunk + n);

		for(int i=1;;i++) {
			current_obj = next_obj;
			next_obj = (obj *)((char *)next_obj + n);
			if ( nobjs -1 == i) {
				current_obj->free_list_link = 0;
				break;
			} else {
				current_obj->free_list_link = next_obj;
			}
		}

		return result;
	};

	template<int MIN_BLOCK_SIZE,int MAX_BLOCK_SIZE>
	inline char *MemoryPool<MIN_BLOCK_SIZE,MAX_BLOCK_SIZE>::chunk_alloc(size_t size,int &nobjs)
	{
		char *result;
		size_t total_bytes = size*nobjs;
		size_t bytes_left = _end_free - _start_free;

		if ( bytes_left < size)	//not enough to even 1 obj
			return NULL;

		if ( bytes_left >= total_bytes) {
			result = _start_free;
			_start_free += total_bytes;
			return result;
		}

		//不能完全满足要求
		nobjs = bytes_left/size;
		total_bytes = size*nobjs;
		result = _start_free;
		_start_free += total_bytes;
		return result;
	};
}
#endif