STL中空間配置器(allocator)的簡單實現

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

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


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


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

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

	static void* OomMalloc(size_t n)
	{
		ALLOC_OOM_FUN MyMallocHandler;
		void *result;
		/*
			1:分配內存成功，直接返回
			2:分配失敗，則檢查是否有設置處理的MyMallocHandler，
			   如果有，則調用它以后再嘗試分配，并不斷重復，直到分配成功
			   如果沒有，則直接結束程序
		*/
		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;
	}

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

};

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



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



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

	static Obj* volatile _FreeList[__NFREELISTS];   //自由鏈表
	static char* _StartFree;										//內存池起始位置
	static char* _EndFree;									//內存池結束位置
	static size_t _HeapSize;									//從系統堆分配的內存的總大小

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

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

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

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

		//1、如果自由鏈表中沒有內存，通過Refill填充
		//2、如果自由鏈表中有，則返回一個結點塊的內存
		//ps: 多線程環境需要考慮加鎖

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

	//空間釋放函數
	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;

		//內存塊較大，改用一級空間配置器
		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;
		}

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

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

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

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

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

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

		Obj *result;
		Obj *cur;
		size_t index = FREELIST_INDEX(n);		//根據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;   //內存池的剩余空間

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

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

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


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

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

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

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

			//從系統堆分配的總字節數(可用于下次分配時進行調節)
			_HeapSize += BytesToGet;
			_EndFree = _StartFree + BytesToGet;

			//遞歸調用獲取內存
			return ChunkAlloc(size, nobjs);
		}
		return result;
	}
};

//對類內部的靜態成員進行初始化
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, };