STL——空間配置器

     __malloc_alloc_template分配器:該分配器是對(duì)malloc、realloc以及free的封裝：

    當(dāng)調(diào)用malloc和realloc申請(qǐng)不到內(nèi)存空間的時(shí)候，會(huì)改調(diào)用oom_malloc()和oom_realloc()，這兩個(gè)函數(shù)會(huì)反復(fù)調(diào)用用戶傳遞過來的out of memory handler處理函數(shù)，直到能用malloc或者realloc申請(qǐng)到內(nèi)存為止。

如果用戶沒有傳遞__malloc_alloc_oom_handler，__malloc_alloc_template會(huì)拋出__THROW_BAD_ALLOC異常。所以，內(nèi)存不足的處理任務(wù)就交給類客戶去完成。

__default_alloc_template分配器

　　這個(gè)分配器采用了內(nèi)存池的思想，有效地避免了內(nèi)碎片的問題（順便一句話介紹一下內(nèi)碎片和外碎片：內(nèi)碎片是已被分配出去但是用不到的內(nèi)存空間，外碎片是由于大小太小而無(wú)法分配出去的空閑塊）。

　如果申請(qǐng)的內(nèi)存塊大于128bytes，就將申請(qǐng)的操作移交__malloc_alloc_template分配器去處理；如果申請(qǐng)的區(qū)塊大小小于128bytes時(shí)，就從本分配器維護(hù)的內(nèi)存池中分配內(nèi)存。

　　分配器用空閑鏈表的方式維護(hù)內(nèi)存池中的空閑空間。

#include<iostream>
#include<stdarg.h>
using namespace std;


#define __DEBUG__
static string GetFileName(const string& path)
{
	char ch = '/';
#ifdef _WIN32
	ch = '\\';
#endif
	size_t pos = path.rfind(ch);
	if (pos == string::npos)
		return path;
	else
		return path.substr(pos + 1);
} 
// 用于調(diào)試追溯的trace log
inline static void __trace_debug(const char* function,
const char * filename, int line, char* format, ...)
{
#ifdef __DEBUG__
		// 輸出調(diào)用函數(shù)的信息
		fprintf(stdout, "【%s:%d】 %s", GetFileName(filename).c_str(), line, function);
	// 輸出用戶打的trace信息
	va_list args;
	va_start(args, format);
	vfprintf(stdout, format, args);
	va_end(args);
#endif
} 
#define __TRACE_DEBUG(...) \
__trace_debug(__FUNCTION__, __FILE__, __LINE__, __VA_ARGS__);
typedef void(*MallocAllocHandler)();
template <int inst>
class MallocAllocTemplate
{
protected:
	static	MallocAllocHandler _handler;
	static void* Oom_Malloc(size_t n)
	{
		MallocAllocHandler handler = NULL;
		void* ret = NULL;
		while (1)
		{
			handler = _handler;
			if (handler == NULL)
			{
				cout << "out of memory" << endl;
				//exit(1);
			}
			(*handler)();
			ret = malloc(n);
			if (ret)
				return ret;
		}
	}
public:
	static void * Allocate(size_t n)
	{
		void *result = malloc(n);
		if (0 == result) result = Oom_Malloc(n);
		__TRACE_DEBUG("調(diào)用一級(jí)空間配置器開辟內(nèi)存：ptr:%p,size:%u\n", result,n);
		return result;
	}

	static void Deallocate(void *p, size_t n)
	{
		free(p);
		__TRACE_DEBUG("調(diào)用一級(jí)空間配置器釋放內(nèi)存：ptr:%p,size:%u\n", p, n);
	}
	static void(*SetMallocHandler(MallocAllocHandler f))()
	{
		void(*old)() = _handler;
		_handler = f;
		return(old);
	}
};
template<int inst> MallocAllocHandler MallocAllocTemplate<inst>::_handler = NULL;
template <bool threads, int inst>
class DefaultAllocTemplate
{
	enum { ALIGN = 8 };
	enum { MAX_BYTES = 128 };
	enum { NFREELISTS = MAX_BYTES / ALIGN };
	union Obj {
		union Obj * _freeListLink;
		char _clientData[1];    /* The client sees this.        */
	};
	static Obj * volatile _freeList[NFREELISTS];//指針數(shù)組
	static char *_startFree;
	static char *_endFree;
	static size_t _heapSize;
	static  size_t FreeListIndex(size_t bytes) {
		return (((bytes)+ALIGN - 1) / ALIGN - 1);
	}
	static size_t RoundUp(size_t bytes) {
		return (((bytes)+ALIGN - 1) & ~(ALIGN - 1));
	}
	static char* chunkAlloc(size_t n, int& nobjs)
	{
		char* ret = NULL;
		size_t totalBytes = n*nobjs;
		size_t freeLeft = _endFree - _startFree;
		if (freeLeft >= totalBytes)
		{
			ret = _startFree;
			_startFree += totalBytes;
			__TRACE_DEBUG("內(nèi)存池足夠分配空間：ptr:%p,size:%u\n", ret, totalBytes);
			return(ret);
		}
		else if (freeLeft >= n)
		{
			nobjs = freeLeft / n;
			totalBytes = n*nobjs;
			ret = _startFree;
			_startFree += totalBytes;
			__TRACE_DEBUG("內(nèi)存池只有空間：ptr:%p,size:%u\n", ret, totalBytes);
			return(ret);
		}
		else
		{
			size_t bytesOfGet = 2 * totalBytes + RoundUp(_heapSize >> 4);
			//將剩下的小塊內(nèi)存掛載
			if (freeLeft > 0)
			{
				Obj* myFreeList = _freeList[FreeListIndex(freeLeft)];
				((Obj*)_startFree)->_freeListLink = myFreeList;
				_freeList[FreeListIndex(freeLeft)] = (Obj*)_startFree;
			}
			_startFree =(char*) malloc(bytesOfGet);
			if (_startFree == NULL)
			{
				Obj* myFreeList, *p;
				for (int i = n; i < MAX_BYTES; i += ALIGN)
				{
					myFreeList = _freeList[FreeListIndex(i)];
					if (myFreeList != NULL)
					{
						p = myFreeList;
						myFreeList = myFreeList->_freeListLink;
						_startFree = (char*)p;
						_endFree = _startFree + i;
						return chunkAlloc(n, nobjs);//會(huì)進(jìn)入else if
					}
				}
				//空閑鏈表無(wú)比n大的內(nèi)存
				_endFree = NULL;//防止_startFree返回0，而_endFree為一個(gè)很大的值，誤認(rèn)為有內(nèi)存池內(nèi)存可分配
				_startFree = (char*)MallocAllocTemplate<0>::Allocate(bytesOfGet);
			}
			_heapSize += bytesOfGet;
			_endFree = _startFree + bytesOfGet;
			return chunkAlloc(n, nobjs);//會(huì)進(jìn)if
		}
	}
	static void* Refill(size_t n)
	{
		int nobjs = 20;
		char * chunk = chunkAlloc(n, nobjs);
		Obj* volatile * myFreeList;
		Obj* ret;
		Obj * currentObj=NULL, *nextObj=NULL;
		int i;
		if (1 == nobjs)  return(chunk);
		myFreeList = _freeList + FreeListIndex(n);
		ret = (Obj *)chunk;
		*myFreeList = nextObj = (Obj *)(chunk + n);
		/*for (i = 1;; i++) {
			currentObj = nextObj;
			nextObj = (Obj *)((char *)nextObj + n);
			if (nobjs - 1 == i)
			{
				currentObj->freeListLink = 0;
				break;
			}
			else
			{
				currentObj->freeListLink = nextObj;
			}
		}*/
		//
		for (i = 0; i < nobjs - 1; ++i)
		{
			currentObj = nextObj;
			nextObj = nextObj + 1;
			currentObj->_freeListLink = nextObj;
		}
		__TRACE_DEBUG("掛載空間到自由鏈表\n");
		currentObj->_freeListLink = NULL;
		return ret;
	}
public:
	static void Deallocate(void* p, size_t size)
	{
		if (size > MAX_BYTES)
		{
			MallocAllocTemplate<0>::Deallocate(p, size);
			__TRACE_DEBUG("調(diào)用一級(jí)空間配置器釋放內(nèi)存：ptr:%p,size:%u\n",p,size);
		}
		else
		{
			Obj * myFreeList = _freeList[FreeListIndex(size)];
			((Obj*)p)->_freeListLink = myFreeList;
			_freeList[FreeListIndex(size)] = (Obj*)p;
			__TRACE_DEBUG("掛載到自由鏈表釋放內(nèi)存：ptr:%p,size:%u\n", p, size);
		}
	}
	static void * Allocate(size_t n)
	{
		Obj * volatile * myFreeList;
		Obj * result;
		if (n > MAX_BYTES)
		{
			return(MallocAllocTemplate<1>::Allocate(n));
		}
		myFreeList = _freeList + FreeListIndex(n);
		result = *myFreeList;
		if (result == NULL)
		{
			void* ret = Refill(RoundUp(n));
			__TRACE_DEBUG("分配空間：ptr:%p\n", ret);

			return ret;
		}
		*myFreeList = result->_freeListLink;
		__TRACE_DEBUG("從自由鏈表直接?。簆tr:%p,size:%u\n", result,n);

		return result;
	}
};
template<bool threads,int inst> 
typename DefaultAllocTemplate<threads, inst>::Obj*  volatile DefaultAllocTemplate<threads, inst>::_freeList[DefaultAllocTemplate<0, 0>::NFREELISTS] = { 0 };//指針數(shù)組
template<bool threads,int inst>
char* DefaultAllocTemplate<threads, inst>::_startFree = NULL;
template<bool threads, int inst>
char* DefaultAllocTemplate<threads, inst>::_endFree = NULL;
template<bool threads, int inst>
size_t DefaultAllocTemplate<threads, inst>::_heapSize = 0;
# ifdef __USE_MALLOC

typedef MallocAllocTemplate<0> Alloc;
typedef MallocAllocTemplate<0> Alloc;
# else
typedef DefaultAllocTemplate<0, 0> Alloc;
typedef DefaultAllocTemplate<0, 0> Alloc;
#endif

template<class T, class Alloc>
class SimpleAlloc
{
public:
	static T *Allocate(size_t n) { return 0 == n ? 0 : (T*)Alloc::Allocate(n*sizeof(T)); }
	static T *Allocate(void) { return (T*)Alloc::Allocate(sizeof(T)); }
	static void Deallocate(T* p, size_t n) { if (0 != n) Alloc::Deallocate(p, n*sizeof(T)); }
	static void Deallocate(T *p){ Alloc::Deallocate(p, sizeof(T)); }
	//將調(diào)用傳遞給配置器的成員函數(shù)，可能是第一級(jí)也可能是第二級(jí)
};
void Test1()
{
	//MallocAllocTemplate<1> d;
	////int *p=(int*)MallocAllocTemplate<1>::Allocate(sizeof(int));
	//int *p=(int*)d.Allocate(sizeof(int));
	//*p = 2;
	//cout << *p << endl;
	//d.Deallocate(p, sizeof(int));
	//DefaultAllocTemplate<0, 0> a;
	//int* p1 = (int*)a.Allocate(sizeof(int));
	//*p1 = 3;
	//cout << *p1 << endl;
	//typedef MallocAllocTemplate<0> Alloc;
	// 測(cè)試調(diào)用一級(jí)配置器分配內(nèi)存
	cout << " 測(cè)試調(diào)用一級(jí)配置器分配內(nèi)存 " << endl;
	char*p1 = SimpleAlloc< char, Alloc>::Allocate(129);
	SimpleAlloc<char, Alloc>::Deallocate(p1, 129);
	// 測(cè)試調(diào)用二級(jí)配置器分配內(nèi)存

	cout << " 測(cè)試調(diào)用二級(jí)配置器分配內(nèi)存 " << endl;
	char*p2 = SimpleAlloc< char, Alloc>::Allocate(128);
	char*p3 = SimpleAlloc< char, Alloc>::Allocate(128);
	char*p4 = SimpleAlloc< char, Alloc>::Allocate(128);
	char*p5 = SimpleAlloc< char, Alloc>::Allocate(128);
	SimpleAlloc<char, Alloc>::Deallocate(p2, 128);
	SimpleAlloc<char, Alloc>::Deallocate(p3, 128);
	SimpleAlloc<char, Alloc>::Deallocate(p4, 128);
	SimpleAlloc<char, Alloc>::Deallocate(p5, 128);
	for (int i = 0; i < 21; ++i)
	{
		printf(" 測(cè)試第%d次分配 \n", i + 1);
		char*p = SimpleAlloc< char, Alloc>::Allocate(128);
	}
}
// 測(cè)試特殊場(chǎng)景
void Test2()
{
	cout << " 測(cè)試內(nèi)存池空間不足分配個(gè) " << endl;
	// 8*20->8*2->320
	char*p1 = SimpleAlloc< char, Alloc>::Allocate(8);
	char*p2 = SimpleAlloc< char, Alloc>::Allocate(8);
	cout << " 測(cè)試內(nèi)存池空間不足， 系統(tǒng)堆進(jìn)行分配 " << endl;
	char*p3 = SimpleAlloc< char, Alloc>::Allocate(12);
}
void Test3()
{
	cout << " 測(cè)試系統(tǒng)堆內(nèi)存耗盡 " << endl;
	SimpleAlloc<char, Alloc>::Allocate(1024 * 1024 * 1024);
	//SimpleAlloc<char, Alloc>::Allocate(1024*1024*1024);
	SimpleAlloc<char, Alloc>::Allocate(1024 * 1024);
	// 不好測(cè)試， 說明系統(tǒng)管理小塊內(nèi)存的能力還是很強(qiáng)的。
	for (int i = 0; i < 100000; ++i)
	{
		char*p1 = SimpleAlloc< char, Alloc>::Allocate(128);
	}
}

運(yùn)行截圖：