STL空间配置器

一级空间配置器
#ifndef _MALLOC_ALLOC_TEMPLATE_H
#define _MALLOC_ALLOC_TEMPLATE_H

#if 0
#include<new>
#define __THROW_BAD_ALLOC throw bad_alloc
#elif !defined(_THROW_BAD_ALLOC)
#include<iostream>
using namespace std;
#define __THROW_BAD_ALLOC cerr<<" of memory"<<endl;exit(1)
#endif
template<int inst>
class __malloc_alloc_template{
private:
	static void *oom_malloc(size_t);
	static void *oom_realloc(void *,size_t);
	static void(* __malloc_alloc_oom_handler)();
public:
	static void *alloc(size_t n)
	{
      void *result = malloc(n);
	  if(0 == result)
		  result = oom_malloc(n);
	  return result;
	}
	static void deallocate(void *p,size_t)
	{
		free(p);
	}
	static void *reallocate(void *p,size_t old_sz,size_t new_sz )
	{
		void *result = realloc(p,new_sz);
		if(0 == result)result = oom_realloc(p,new_sz);
		return result;
	}
	static void(* set_malloc_oom_handler(void (*f) ()))()//它怎么分析？
	{
		void (*old)() = __malloc_alloc_oom_handler; 
		__malloc_alloc_oom_handler =f;
		return (old);
	}
};
template<int inst>
void(* __malloc_alloc_template<inst>::__malloc_alloc_oom_handler)()=0;
template<int inst>
void * __malloc_alloc_template<inst>::oom_malloc(size_t n)
{
	void (* my_malloc_handler)();
	void *result;
	for(;;)
	{
		my_malloc_handler = __malloc_alloc_oom_handler;
		if(0==my_malloc_handler){__THROW_BAD_ALLOC;}
		(*my_malloc_handler)();
		if(result) return(result);
	}
}
template<int inst>
void * __malloc_alloc_template<inst>::oom_realloc(void *p,size_t n)
{
	void (* my_malloc_handler)();
	void * result;
	for(;;)
	{
		my_malloc_handler = __malloc_alloc_oom_handler;
		if( 0==my_malloc_handler){__THROW_BAD_ALLOC;}
		(* my_malloc_handler)();
		result = realloc(p,n);
		if(result)return(result);
	}
}
#endif
二级配置器
#ifndef _DEFAULT_ALLOC_TEMPLATE_H
#define _DEFAULT_ALLOC_TEMPLATE_H
enum{_ALIGN =8};//小型区块的上调边界
enum{_MAX_BYTES=128};//小型区块的上限
enum{_NFREELISTS=_MAX_BYTES/_ALIGN};//free_list的个数；
template<bool threads,int inst>
class _default_alloc_template{
private:
	static size_t ROUND_UP(size_t bytes)//把bytes上调至8的倍数
	{
		return ((bytes+_ALIGN-1)&~(_ALIGN-1));
	}
private:
	union obj{
		union obj* free_list_link;
		char client_data[1];
	};
private:
	static obj* volatile free_list[_NFREELISTS];//数组里面存放的是obj类型的指针；
	//以下函数根据区块大小，决定使用第n号freelist,从0算起；
	static size_t FREELIST_INDEX(size_t bytes)
	{
		return (((bytes)+_ALIGN-1)/_ALIGN-1);
	}
	static void *refill(size_t n);
	static char *chunk_alloc(size_t size,int &nobjs);
	static char *start_free;
	static char *end_free;
	static size_t heap_size;
public:
	static void* allocate(size_t n);
	static void deallocate(void *p,size_t n);
	static void *reallocate(void *p,size_t old_sz,size_t new_sz);

};
template <bool threads,int inst>
char *_default_alloc_template<threads,inst>::start_free =0;
template<bool threads,int inst>
char *_default_alloc_template<threads,inst>::end_free=0;
template<bool threads,int inst>
size_t _default_alloc_template<threads,inst>::heap_size=0;
template<bool threads,int inst>
typename _default_alloc_template<threads,inst>::obj* volatile _default_alloc_template<threads,inst>::free_list[_NFREELISTS]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
template<bool threads,int inst>
void *_default_alloc_template<threads,inst>::allocate(size_t n)
{
	obj *volatile *my_free_list;
	obj *result;
	if(n >(size_t)_MAX_BYTES)
	{
		return (__malloc_alloc_template<0>::alloc(n));
	}
	my_free_list = free_list+FREELIST_INDEX(n);
	result =*my_free_list;
	if(result == 0)
	{
		void *r = refill(ROUND_UP(n));
		return r;
	}
	*my_free_list = result->free_list_link;
	return (result);
}
template<bool threads,int inst>
void _default_alloc_template<threads,inst>::deallocate(void *p,size_t n)
{
	obj* q =(obj *)p;
	obj * volatile * my_free_list;
	if(n >(size_t)_MAX_BYTES){
		__malloc_alloc_template::deallocate(p,n);
		return ;
	}
	my_free_list = free_list +FREELIST_INDEX(n);
	q->free_list_link = *my_free_list;
	*my_free_list =q;
}
template<bool threads,int inst>
void* _default_alloc_template<threads,inst>::refill(size_t n)
{
	int nobjs= 20;
	char *chunk = chunk_alloc(n,nobjs);
	obj * volatile *my_free_list;
	obj *result;
	obj *current_obj,*next_obj;
	int i;
	if(1==nobjs)return (chunk);
	my_free_list = free_list +FREELIST_INDEX(n);//这里的n已经是上调到8的倍数了；
	result = (obj*)chunk;//内存的类型是什么？
	*my_free_list = next_obj =(obj*)(chunk+n);//拿freelist中的指针指向这块申请的内存，为的是把第一块内存返还给客户使用
	for(i =1;;i++)//把内存以链表的形式存储起来；
	{
		current_obj = next_obj;
		next_obj= (obj*)((char *)next_obj+n);
		if(nobjs-1==i)//i已经增加到了所分配的内存区块的最大值；
		{
			current_obj->free_list_link = 0;
			break;
		}
		else
		{
			current_obj->free_list_link = next_obj;//free_list_link如何在在申请的内存中存在；
		}
	}
}
template<bool threads,int inst>
char *_default_alloc_template<threads,inst>::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 >=total_bytes)//如果内存池的剩余内存足够多，
	{
		char *result;
		result = start_free;
		start_free = start_free+total_bytes;
		return(result);
	}
	else if(bytes_left >=size)//内存池内存不够nobjs*size，但是够一个以上的区块/；
	{
		nobjs = bytes_left/size;//看剩下的内存还够几个区块就把这几个区块返回给客户；
		total_bytes=size*nobjs;
		result=start_free;
		start_free=start_free+total_bytes;//修改内存池的起始地址；
		return result;
	}else//内存池中的内存连一块都不够了
	{
		size_t bytes_to_get = 2*total_bytes+ROUND_UP(heap_size>>4);//为了后面malloc开辟的次数会越来越少；
		if(bytes_left >0){//内存池还有一些零散的内存，先找到适合这点内存的的freelist;
			obj *volatile *my_free_list = free_list+FREELIST_INDEX(bytes_left);
			((obj*)start_free)->free_list_link = *my_free_list;//就是把内存中遗留的一点内存给freelist,内存的起始位置是start_free;
			*my_free_list=(obj*)start_free;
		}
		start_free=(char*)malloc(bytes_to_get);//它在这里开辟空间了，后面却没有释放内存？它是如何释放内存的？
		if(0 == start_free){
			obj *volatile *my_free_list,*p;
			for(int i=size;i<=_MAX_BYTES;i+= _ALIGN)
			{
				//在freelist的其他结点中还存在内存就拿过来用；
				my_free_list = free_list+FREELIST_INDEX(i);
				p=*my_free_list;
				if(0!=p)
				{
					*my_free_list = p->free_list_link;
					start_free =(char *)p;
					end_free = start_free+i;
					return (chunk_alloc(size,nobjs));
				}
			}
		end_free = 0;//如果出现意外，调用第一级配置器，看看out_of_memory;
		start_free = (char *)__malloc_alloc_template<0>::alloc(bytes_to_get);
	}
	heap_size += bytes_to_get;
	end_free = start_free+bytes_to_get;
	return (chunk_alloc(size,nobjs));
  }
}
#endif
主函数
#if 1
#include"__malloc_alloc_template.h"
#include"__default_alloc_template.h"
#include<iostream>
using namespace std;
int main()
{
	int *p = (int*)_default_alloc_template<0,0>::allocate(6);
	return 0;
}
#endif