学步园

#ifndef __OOM_ALLOCATER__H__
#define __OOM_ALLOCATER__H__

#ifdef _MSC_VER
#if _MSC_VER > 1000
#pragma once
#endif
#endif

#ifndef __STC_NAMESPACE_BEGIN 
#define __STC_NAMESPACE_BEGIN namespace stc{
#endif

#ifndef __STC_NAMESPACE_END
#define __STC_NAMESPACE_END }
#endif


#include <cstddef>
#include <cassert>
#include <cstdlib>
#include <new>
#include <stdexcept>

__STC_NAMESPACE_BEGIN

template <int _Ty>
class oom_allocater{
	typedef void(*new_handler)();
private:
	static new_handler	__oom_handler;
	static void* oom_malloc(const std::size_t);
	static void* oom_realloc(void*, const std::size_t);
public:

	static void* allocate(const std::size_t __Sz){
		const std::size_t __tSz = __Sz ? __Sz : 1u;
		void* __Res = ::malloc(__tSz);
		if (__Res == NULL)
			__Res = oom_malloc(__tSz);
		return __Res;
	}

	static void* realloc(void* __Src, const std::size_t, const std::size_t __nSz){
		void* __Res = ::realloc(__Src, __nSz);
		if (__Res == NULL)
			oom_realloc(__Src, __nSz);
		return __Res;
	}

	static void deallocate(void* __Src, const std::size_t __Sz){
		::free(__Src);
	}

	static void(*set_new_handler(void(*__nHd)())) (){
		new_handler __oHd = __oom_handler;
		__oom_handler	  = __nHd;
		return __oHd;
	}


};

template <int _Ty>
void(*(oom_allocater<_Ty>::__oom_handler))() = NULL;

template <int _Ty>
void* oom_allocater<_Ty>::oom_malloc(const std::size_t __Sz){
	const std::size_t __tSz = __Sz ? __Sz : 1u;
	new_handler __tmp_new_handler = NULL;
	void* __Res = NULL;
	while (true){
		__tmp_new_handler = __oom_handler;
		if (__tmp_new_handler == NULL)
			throw std::bad_alloc();
		(*__tmp_new_handler)();
		__Res = ::malloc(__tSz);
		if (__Res) return __Res;
	}
}

template <int _Ty>
void* oom_allocater<_Ty>::oom_realloc(void* __Src, const std::size_t __nSz){
	try{
		void* __nSrc = oom_allocater<_Ty>::malloc(__nSz);
		::free(__Src);
		__Src = __nSrc;
		return __nSrc;
	}
	catch (const std::bad_alloc&){
		throw std::bad_alloc("");
		return __Src;
	}
	catch (...){ throw std::bad_alloc(""); }
}

typedef oom_allocater<0> malloc_alloc;


__STC_NAMESPACE_END

#endif

#ifndef __ALLOCATER__H__
#define __ALLOCATER__H__

#ifdef _MSC_VER
#if _MSC_VER > 1000
#pragma once
#endif
#endif

#include <cassert>
#include <string>
#include "oom_allocater.h"

__STC_NAMESPACE_BEGIN

#pragma pack(push)
#pragma pack(4)

class list_node{
public:
	list_node():__Src(NULL), __Next(NULL){}
	void* 			__Src;
	list_node*		__Next;
};

#pragma pack(pop)


inline list_node* __creat_node(const std::size_t __Sz = 1u){
	if (__Sz == 1u)
		return new list_node;
	return new list_node[__Sz];
}

inline void __destroy_node(list_node*& __p, const std::size_t __Sz = 1u){
	if (__Sz == 1u)
		delete __p;
	else delete[] __p;
	__p = NULL;
}


const std::size_t __ALIGN	  = 4u;
const std::size_t __MAX_BYTES = 128u;
const std::size_t __NFREELIST = __MAX_BYTES / __ALIGN;

const std::size_t __round_up(const std::size_t __Sz){
	return static_cast<std::size_t>(((__Sz)+__ALIGN - 1) & ~(__ALIGN - 1));
}

const std::size_t __index(const std::size_t __Sz){
	return static_cast<std::size_t>(((__Sz + __ALIGN - 1) / __ALIGN - 1));
}


template <typename _Ty>

class allocater{
public:
	template <typename _Ty2>
	struct bind{
		typedef allocater<_Ty2> other;
	};
	static _Ty* allocate(const std::size_t);
	static _Ty* realloc(void*, const std::size_t, const std::size_t);
	static void deallocate(void*, const std::size_t);
	template <typename _Ty2>
	static void construct(_Ty* const __Src, const _Ty2& __Val){
		new (__Src)_Ty(__Val);
	}
	static void construct(_Ty* const __Src){
		new (__Src)_Ty();
	}
	static void destroy(_Ty* const __Src){
		__Src->~_Ty();
	}
	static _Ty* address(const _Ty& __Val){
		return &__Val;
	}
	allocater& operator =(const allocater&) = default;
private:
	static void __refill(const std::size_t);
	static char* __chunk_alloc(const std::size_t, std::size_t&);
	static const std::size_t __bit_size(const std::size_t);
private:
	static list_node* 	__free_list[__NFREELIST];
	static char* 		__start_free;
	static char*        __end_free;
	static std::size_t  __heap_size;
};

template <typename _Ty>
list_node* allocater<_Ty>::__free_list[__NFREELIST] = {
	NULL, NULL, NULL, NULL, NULL,
	NULL, NULL, NULL, NULL, NULL,
	NULL, NULL, NULL, NULL, NULL,
	NULL, NULL, NULL, NULL, NULL,
	NULL, NULL, NULL, NULL, NULL,
	NULL, NULL, NULL, NULL, NULL,
	NULL, NULL
};

template <typename _Ty>
char* allocater<_Ty>::__start_free = NULL;
template <typename _Ty>
char* allocater<_Ty>::__end_free = NULL;
template <typename _Ty>
std::size_t allocater<_Ty>::__heap_size = 0u;


template <typename _Ty>
const std::size_t allocater<_Ty>::__bit_size(const std::size_t __Sz){
	const std::size_t __tSz = __Sz ? __Sz : 1u;//如果不为0那么还是返回它的大小，如果是零那么大小要求为1
	return static_cast<size_t>(__tSz * sizeof(_Ty));
}

template <typename _Ty>
_Ty* allocater<_Ty>::allocate(const std::size_t __Sz){
	const std::size_t __bSz = __bit_size(__Sz);
	if (__bSz > __MAX_BYTES){
		return static_cast<_Ty*>(malloc_alloc::allocate(__bSz));
	}
	const std::size_t __Solt = __index(__bSz);
	list_node* __Res = __free_list[__Solt];
	if (__Res == NULL){
		__refill(__round_up(__bSz));
		__Res = __free_list[__Solt];
	}
	__free_list[__Solt] = __Res->__Next;
	_Ty* __Src	= static_cast<_Ty*>(__Res->__Src);
	__destroy_node(__Res);
	return __Src;
}

template <typename _Ty>
_Ty* allocater<_Ty>::realloc(void* __Src, const std::size_t __oSz, const std::size_t __nSz){
	const std::size_t __bnSz = __bit_size(__nSz);
	const std::size_t __boSz = __bit_size(__oSz);
	_Ty* __Res = static_cast<_Ty*>(allocater<_Ty>::allocate(__bnSz));
	allocater<_Ty>::deallocate(__Src, __boSz);
	return __Res;
}

template <typename _Ty>
void allocater<_Ty>::deallocate(void* __Src, const std::size_t __Sz){
	const std::size_t __bSz = __bit_size(__Sz);
	if (__bSz > __MAX_BYTES){
		malloc_alloc::deallocate(__Src, __bSz);
		return;
	}
	list_node* __node = __creat_node();
	__node->__Src	  = __Src;
	const std::size_t __Solt = __index(__bSz);
	__node->__Next	  = __free_list[__Solt];
	__free_list[__Solt] = __node;
}

template <typename _Ty>//重新填大小为Sz块大小的项
void allocater<_Ty>::__refill(const std::size_t __Sz){
	assert(__Sz);
	std::size_t __Node_Sz = 20u;//defalut node size;
	char* __chunk = __chunk_alloc(__Sz, __Node_Sz);
	const std::size_t __Solt = __index(__Sz);
	list_node* __Curr = NULL;
	list_node* __Prev = __creat_node();
	__Prev->__Src = __chunk;
	__free_list[__Solt] = __Prev;
	for (std::size_t i = 1u; i < __Node_Sz; ++i){
		__chunk			+= __Sz;
		__Curr			= __creat_node();
		__Curr->__Next	= __Prev;
		__Curr->__Src	= __chunk;
		__Prev			= __Curr;
	}
}

template <typename _Ty>
char* allocater<_Ty>::__chunk_alloc(const std::size_t __Sz, std::size_t& __Node_Sz){
	assert(__Sz);
	const std::size_t __lSz = __end_free - __start_free;
	const std::size_t __tSz = __Sz * __Node_Sz;
	char* __Res = NULL;
	if (__lSz >= __tSz){
		__Res		 = __start_free;
		__start_free += __tSz;
		return (__Res);
	}
	if (__lSz >= __Sz){//如果能给出内存，但是不够所有的
		__Node_Sz = __lSz / __Sz;
		__Res	  = __start_free;
		__start_free += static_cast<std::size_t>(__Node_Sz * __Sz);
		return (__Res);
	}
	//剩下的完全不够了
	const std::size_t __bit_get = __tSz * 2 + __round_up(__heap_size >> 4);
	const std::size_t __Solt	= __index(__lSz ? __lSz : 1u);//如果left size 为0会出现BUG
	if (__lSz){//如果剩下还有内存，那么就放入到现在的表中	
		list_node* __node	= __creat_node();
		__node->__Src		= __start_free;
		__node->__Next		= __free_list[__Solt];
		__free_list[__Solt] = __node;
	}
	__start_free = (char*)::malloc(__bit_get);
	if (__start_free == NULL){//如果内存足了，就从现在的表项中找合适的
		for (std::size_t i = __Solt; i < __NFREELIST; ++i){
			if (__free_list[i]){
				list_node* __node = __free_list[i];
				__start_free	= static_cast<char*>(__node->__Src);
				__free_list[i]  = __node->__Next;
				__destroy_node(__node);
				__end_free		= __start_free + (i + 1) * __ALIGN;
				return __chunk_alloc(__Sz, __Node_Sz);
			}
		}
		__start_free = static_cast<char*>(malloc_alloc::allocate(__bit_get));//尝试使用用户自己定义的机制找
	}
	__heap_size = __bit_get;
	__end_free	= __start_free + __bit_get;
	return __chunk_alloc(__Sz, __Node_Sz);
}


__STC_NAMESPACE_END

#endif