STL中空間配置器(allocator)的簡單實(shí)現(xiàn)

包括一級空間配置器 和 二級空間配置器

#pragma once
#include <iostream>
using namespace std;


/*————————————*/
/*         一級空間配置器           */
/*————————————*/


typedef void(*ALLOC_OOM_FUN)();   //函數(shù)指針

template <int inst>					//這個(gè)模板參數(shù)并沒有使用，是預(yù)留的
class __MallocAllocTemplate
{
private:
	static ALLOC_OOM_FUN __sMallocAllocOomHandler;		//句柄函數(shù)，如果設(shè)置了，空間分配失敗就會(huì)調(diào)用它

	static void* OomMalloc(size_t n)
	{
		ALLOC_OOM_FUN MyMallocHandler;
		void *result;
		/*
			1:分配內(nèi)存成功，直接返回
			2:分配失敗，則檢查是否有設(shè)置處理的MyMallocHandler，
			   如果有，則調(diào)用它以后再嘗試分配，并不斷重復(fù)，直到分配成功
			   如果沒有，則直接結(jié)束程序
		*/
		for (;;)
		{
			MyMallocHandler = __sMallocAllocOomHandler;
			if (MyMallocHandler)
			{
				MyMallocHandler();
				void *ret = malloc(n);
				if (ret)
				{
					return ret;
				}
			}
			else
			{
				throw bad_alloc();
			}
		}
		return result;
	}

	static void* OomRealloc(void *p, size_t n)
	{
		/*
			步驟同上
		*/
		ALLOC_OOM_FUN MyMallocHandler;
		for (;;)
		{
			MyMallocHandler = __sMallocAllocOomHandler;
			if (MyMallocHandler)
			{
				MyMallocHandler();
				void *ret = realloc(p, n);
				if (ret)
				{
					return ret;
				}
			}
			else
			{
				throw bad_alloc();
			}
		}
	}

public:
	static void* Allocate(size_t n)
	{
		//__TRACE_DEBUG("n:%u\n", n);
		void *result = malloc(n);	//第一級配置器直接使用malloc
		if (NULL == result)		// 0 == result
		{
			result = OomMalloc(n);
		}
		return result;
	}

	static void Deallocate(void *p, size_t /* n */)
	{
		//TRACE_DEBUG("(p:%p)\n". p);
		free(p);		//第一級配置器直接使用free()
	}

	static void*Reallocate(void *p, size_t/*old_sz*/, size_t new_sz)
	{
		void *result = realloc(p, new_sz);
		if (NULL == result)
		{
			result = OomRealloc(p, new_sz);
			return result;
		}
		return result;
	}

	/*
		設(shè)置句柄函數(shù)的函數(shù)
		函數(shù)名：SetMallocHandler
		參數(shù)：名為f的函數(shù)指針(指向要設(shè)置的新句柄)
		返回值：函數(shù)指針（指向原來的句柄函數(shù)）
	*/
	static void(*SetMallocHandler(void(*f)()))()
	{
		void(*old)() = __sMallocAllocOomHandler;
		__sMallocAllocOomHandler = f;
		return old;
	}

};

//將句柄函數(shù)指針初始化為空
template<int inst>
ALLOC_OOM_FUN __MallocAllocTemplate<inst>::__sMallocAllocOomHandler = NULL;



/*————————————*/
/*         二級空間配置器           */
/*————————————*/



template<bool threads, int inst>	//這兩個(gè)模板參數(shù)同樣并沒有使用，是預(yù)留的
class __DefaultAllocTemplate
{
public:
	enum { __ALIGN = 8 };												//排列基準(zhǔn)值(間隔)
	enum { __MAX_BYTES = 128 };									//最大值,上限
	enum { __NFREELISTS = __MAX_BYTES / __ALIGN };	//自由鏈表的個(gè)數(shù)
													//自由鏈表(FreeLists)結(jié)點(diǎn)
	union Obj
	{
		union Obj *_FreeListLink;		//指向下一個(gè)內(nèi)存塊的指針
		char ClientData[1];   //客戶端可見(測試用)
	};

	static Obj* volatile _FreeList[__NFREELISTS];   //自由鏈表
	static char* _StartFree;										//內(nèi)存池起始位置
	static char* _EndFree;									//內(nèi)存池結(jié)束位置
	static size_t _HeapSize;									//從系統(tǒng)堆分配的內(nèi)存的總大小

public:
	//空間配置函數(shù)
	static void* Allocate(size_t n)
	{
		//__TRACE_DEBUG("(n ;%n)\n", n);

		//如果 n > __MAX_BYTES 就直接在一級空間配置器中獲取內(nèi)存
		//否則在二級空間配置器中獲取內(nèi)存

		if (n > (size_t)__MAX_BYTES)
		{
			return __MallocAllocTemplate<0>::Allocate(n);
		}

		void *ret = NULL;
		size_t index = FREELIST_INDEX(n);

		//1、如果自由鏈表中沒有內(nèi)存，通過Refill填充
		//2、如果自由鏈表中有，則返回一個(gè)結(jié)點(diǎn)塊的內(nèi)存
		//ps: 多線程環(huán)境需要考慮加鎖

		Obj *head = _FreeList[index];
		if (head == NULL)
		{
			return Refill(ROUND_UP(n));
		}
		else
		{
			//__TRACE_DEBUG("自由鏈表取內(nèi)存 : _FreeList[%s]\n", index);
			_FreeList[index] = head->_FreeListLink;
			return head;
		}
	}

	//空間釋放函數(shù)
	static void Deallocate(void *p, size_t n)
	{
		//__TRACE_DEBUG("(釋放 p : %p, n : %u)\n", p, n);

		//若 n > __MAX_BYTES則直接還給一級配置器
		//否則放回自由鏈表
		if (n > __MAX_BYTES)
		{
			__MallocAllocTemplate<0>::Deallocate(p, n);
		}
		else
		{
			//ps : 多線程要考慮加鎖
			size_t index = FREELIST_INDEX(n);
			//頭插回自由鏈表
			Obj *tmp = (Obj*)p;
			( (Obj*)p ) ->_FreeListLink = _FreeList[index];
			_FreeList[index] = tmp;
		}
	}
	static void* Reallocate(void *p, size_t old_sz, size_t new_sz)
	{
		void *result;
		size_t copy_sz;

		//內(nèi)存塊較大，改用一級空間配置器
		if (old_sz > (size_t)__MAX_BYTES && new_sz > __MAX_BYTES)
		{
			return __MallocAllocTemplate<0>::Reallocate(p, old_sz, new_sz);
		}

		//修改前和修改后的大小相同，不用修改
		if (ROUND_UP(old_sz) == ROUND_UP(new_sz))
		{
			return p;
		}

		//否則，分配一塊空間，并將原來空間的數(shù)據(jù)拷貝至新空間
		result = Allocate(new_sz);
		copy_sz = new_sz > old_sz ? old_sz : new_sz;		//如果new_sz 小于 old_sz 會(huì)丟失數(shù)據(jù)
		memcpy(result, p, copy_sz);
		Deallocate(p, old_sz);	//拷貝完后, 釋放原來的空間
		return result;
	}

private:
	//將bytes上調(diào)至8的倍數(shù)
	static size_t ROUND_UP(size_t bytes)
	{
		return ((bytes + __ALIGN - 1) & ~(__ALIGN - 1));
		//位運(yùn)算，保證效率  比如14： 14 + 7 =  21 (0x0001 0101)    和  (0x1000) 進(jìn)行 & ,結(jié)果是: (0x0001 0000) 即 16
	}

	//選擇使用哪個(gè)自由鏈表
	static size_t FREELIST_INDEX(size_t bytes)
	{
		return((bytes + __ALIGN - 1) / __ALIGN - 1);
	}

private:
	//獲得大塊內(nèi)存填充到自由鏈表中
	static void* Refill(size_t n)
	{
		//__TRACE_DEBUG("(n : %u)\n", n);

		//分配n bytes的內(nèi)存，如果不夠則能分配多少是多少
		int nobjs = 20;	//一次要獲得的數(shù)目(一大塊內(nèi)存)
		char *chunk = ChunkAlloc(n, nobjs);		//試圖獲得nobjs塊內(nèi)存，每塊內(nèi)存的大小為n，并把實(shí)際獲得的內(nèi)存數(shù)賦予nobjs

		//如果只分配到一塊，則直接返回這塊內(nèi)存
		if (nobjs == 1)
		{
			return chunk;
		}

		Obj *result;
		Obj *cur;
		size_t index = FREELIST_INDEX(n);		//根據(jù)n選擇要存放的鏈表
		result = (Obj*)chunk;

		//把剩余的塊鏈鏈接到自由鏈表上面
		cur = (Obj*)(chunk + n);
		_FreeList[index] = cur;
		for (int i = 2; i < nobjs; ++i)
		{
			cur->_FreeListLink = (Obj*)(chunk + n * i);
			cur = cur->_FreeListLink;
		}
		cur->_FreeListLink = NULL;
		return result;
	}

	static char* ChunkAlloc(size_t size, int &nobjs)
	{
		char *result;
		size_t TotalBytes = size * nobjs;
		size_t BytesLeft = _EndFree - _StartFree;   //內(nèi)存池的剩余空間

		/*
			1、內(nèi)存池中內(nèi)存足夠，即BytesLeft >= TotalBytes時(shí)，直接從內(nèi)存池中取出
			2、內(nèi)存池中的內(nèi)存不足，但足夠一塊時(shí)，即 Bytesleft >= size時(shí)，也直接取出來
			3、內(nèi)存池中內(nèi)存連一塊內(nèi)存也不夠的時(shí)候，從系統(tǒng)堆中分配大塊內(nèi)存到內(nèi)存池中
		*/
		if (BytesLeft >= TotalBytes)		//1
		{
			//__TRACE_DEBUG("內(nèi)存池中內(nèi)存足夠分配 %d 個(gè)對象\n", nobjs);
			result = _StartFree;
			_StartFree += TotalBytes;
			return result;
		}
		else if (BytesLeft >= size)		//2
		{
			//__TRACE_DEBUG("內(nèi)存池中內(nèi)存不夠分配 %d 個(gè)對象， 只能分配  %d 個(gè)對象 \n", nobjs, BytesLeft / size);
			result = _StartFree;
			nobjs = BytesLeft / size;
			_StartFree += nobjs * size;

		}
		else											//3
		{
			//如果內(nèi)存中還有小塊剩余內(nèi)存(零頭)，則將它頭插到合適的自由鏈表
			if (BytesLeft > 0)
			{
				size_t index = FREELIST_INDEX(BytesLeft);
				((Obj*)_StartFree)->_FreeListLink = _FreeList[index];
				_FreeList[index] = ((Obj*)_StartFree);
				_StartFree = NULL;
				//__TRACE_DEBUG("將內(nèi)存池中剩余的空間，分配給 _FreeList[%d] \n", index);
			}

			//從系統(tǒng)堆分配兩倍+已分配的 _HeapSize / 8 的內(nèi)存分配到內(nèi)存池中
			size_t BytesToGet = 2 * TotalBytes + ROUND_UP(_HeapSize >> 4);
			_StartFree = (char*)malloc(BytesToGet);
			//__TRACE_DEBUG("內(nèi)存池空間不足，系統(tǒng)堆分配 %u bytes 內(nèi)存\n", BytesToGet);


			// 如果在堆中內(nèi)存分配失敗，則嘗試到自由鏈表中更大的節(jié)點(diǎn)中分配
			if (_StartFree == NULL)
			{
				//TRACE_DEBUG("系統(tǒng)堆已經(jīng)沒有足夠內(nèi)存  在自由鏈表中查找\n");
				//為什么要從大小為size的鏈表中開始找呢？因?yàn)槿绻嵌嗑€程，有可能剛好其他線程
				//有釋放大小為size的內(nèi)存，也就是說，大小為size的鏈表有可能有內(nèi)存可以用
				//所以從大小為size的鏈表開始向后找
				for (int i = size; i <= __MAX_BYTES; i += __ALIGN)
				{
					Obj *head = _FreeList[FREELIST_INDEX(size)];
					if (head) //找到了有可用的內(nèi)存，將它摘下來
					{
						_StartFree = (char*)head;
						head = head->_FreeListLink;
						_EndFree = _StartFree + i;
						return ChunkAlloc(size, nobjs);
					}
				}

				_EndFree = 0;  //防止異常，防止野指針

				//在自由鏈表中也沒找到，則退到一級空間配置器，希望句柄函數(shù)能做一些處理，以得到內(nèi)存

				//__TRACE_DEBUG("系統(tǒng)堆和自由鏈表中都沒有內(nèi)存了，調(diào)到在一級配置器里做最后的嘗試\n");
				_StartFree =(char*) __MallocAllocTemplate<0>::Allocate(BytesToGet);
			}

			//從系統(tǒng)堆分配的總字節(jié)數(shù)(可用于下次分配時(shí)進(jìn)行調(diào)節(jié))
			_HeapSize += BytesToGet;
			_EndFree = _StartFree + BytesToGet;

			//遞歸調(diào)用獲取內(nèi)存
			return ChunkAlloc(size, nobjs);
		}
		return result;
	}
};

//對類內(nèi)部的靜態(tài)成員進(jìn)行初始化
char *__DefaultAllocTemplate<false, 0>::_StartFree = NULL;
char *__DefaultAllocTemplate<false, 0>::_EndFree = NULL;
size_t __DefaultAllocTemplate<false, 0>::_HeapSize = 0;

typedef typename __DefaultAllocTemplate<false, 0>::Obj Obj;

Obj * volatile __DefaultAllocTemplate<false, 0> ::_FreeList[] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, };