// 这里的construct调用的是placement new, 在一个已经获得的内存里建立一个对象
template <class T1, class T2>
inline void construct(T1* p, const T2& value)
{
  new (p) T1(value);
}

template<class T>
inline T* allocate(ptrdiff_t size, T*)
{
    set_new_handler(0);
    T* tmp = (T*)(::operator new(size)(size * sizeof(T)));
    if(!tmp)
    {
        cerr << "out of memort" << endl;
        exit(1);
    }
    return tmp;
}

const int N = 4;
int main()
{
	allocator<string>  alloc;
	auto str_ve = alloc.allocate(N);
	auto p = str_ve;	// vector<string> *p = str_ve;
	alloc.construct(p++);
	alloc.construct(p++, 10, 'a');
	alloc.construct(p++, "construct");
    cout << str_ve[0] << endl;
	cout << str_ve[1] << endl;
	cout << str_ve[2] << endl;

	while(p != str_ve)
	{
		alloc.destroy(--p);
	}
	alloc.deallocate(str_ve, N);

	exit(0);
}

rpz@0505:stl3.0$ ./a.out

aaaaaaaaaa
construct

// 第一版本, 接收指针
template <class T> inline void destroy(T* pointer)
{
    pointer->~T();
}

// 第二个版本的, 接受两个迭代器, 并设法找出元素的类型. 通过__type_trais<> 找出最佳措施
template <class ForwardIterator>
inline void destroy(ForwardIterator first, ForwardIterator last)
{
  __destroy(first, last, value_type(first));
}

// 接受两个迭代器, 以__type_trais<> 判断是否有traival destructor
template <class ForwardIterator, class T>
inline void __destroy(ForwardIterator first, ForwardIterator last, T*)
{
  typedef typename __type_traits<T>::has_trivial_destructor trivial_destructor;
  __destroy_aux(first, last, trivial_destructor());
}

// 没有non-travial destructor
template <class ForwardIterator>
inline void __destroy_aux(ForwardIterator first, ForwardIterator last, __false_type)
{
  for ( ; first < last; ++first)
    destroy(&*first);
}

// 有travial destructor
template <class ForwardIterator>
inline void __destroy_aux(ForwardIterator, ForwardIterator, __true_type) {}

inline void destroy(char*, char*) {}
inline void destroy(wchar_t*, wchar_t*) {}

// 一级配置器
template <int inst>
class __malloc_alloc_template
{
  // 这里private里面的函数都是在内存不足的时候进行调用的
  private:
    static void *oom_malloc(size_t);        // 分配不足
    static void *oom_realloc(void *, size_t);   // 重新分配不足
#ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG
    static void (* __malloc_alloc_oom_handler)();   // 内存不足设置的处理例程, 默认设置的是0, 表示没有设置处理例程, 这个处理例程是由用户手动设置的
#endif
  public:
};

// 这里是模仿c++的set_new_handler. 是由用户自己定义的处理函数, 没有设置默认为0
static void (* set_malloc_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;

// 在分配和再次分配中, 都会检查内存不足, 在不足的时候直接调用private中相应的函数
static void * allocate(size_t n)
{
      void *result = malloc(n);
      if (0 == result) result = oom_malloc(n);
      return result;
}

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)();
    result = malloc(n);
    if (result) return(result);
  }
}

static void deallocate(void *p, size_t /* n */)
{
      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;
}

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);
  }
}

// 默认将malloc_alloc设为0;
typedef __malloc_alloc_template<0> malloc_alloc;

// 定义符合STL规格的配置器接口, 不管是一级配置器还是二级配置器都是使用这个接口进行分配的
template<class T, class Alloc>
class simple_alloc {
  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)); }
};

// 二级配置器
enum {__ALIGN = 8}; // 设置对齐要求. 对齐为8字节, 没有8字节自动补齐
enum {__MAX_BYTES = 128};   // 第二级配置器的最大一次性申请大小, 大于128就直接调用第一级配置器
enum {__NFREELISTS = __MAX_BYTES/__ALIGN};  // 链表个数, 分别代表8, 16, 32....字节的链表

static size_t FREELIST_INDEX(size_t bytes) \
{\
    return (((bytes) + ALIGN-1) / __ALIGN - 1);\
}

static void * allocate(size_t n)
{
      obj * __VOLATILE * my_free_list;
      obj * __RESTRICT result;

      if (n > (size_t) __MAX_BYTES)
      {
        return(malloc_alloc::allocate(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>::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);

  	// 申请的大小不只一个对象的大小的时候
  	result = (obj *)chunk;
  	// my_free_list指向内存池返回的地址的下一个对齐后的地址
  	*my_free_list = next_obj = (obj *)(chunk + n);
  	// 这里从第二个开始的原因主要是第一块地址返回给了用户, 现在需要把从内存池里面分配的内存用链表给串起来
  	for (i = 1; ; i++)
  	{
	    current_obj = next_obj;
    	next_obj = (obj *)((char *)next_obj + n);
	    if (nobjs - 1 == i)
        {
			current_obj -> free_list_link = 0;
      		break;
    	}
        else
        {
      		current_obj -> free_list_link = next_obj;
    	}
  		}
  	return(result);
}

static void deallocate(void *p, size_t n)
{
      obj *q = (obj *)p;
      obj * __VOLATILE * my_free_list;

      // 释放的内存大于128字节直接调用一级配置器进行释放
      if (n > (size_t) __MAX_BYTES)
      {
        malloc_alloc::deallocate(p, n);
        return;
      }
      my_free_list = free_list + FREELIST_INDEX(n);
      q -> free_list_link = *my_free_list;
      *my_free_list = q;
}

// 定义符合STL规格的配置器接口, 不管是一级配置器还是二级配置器都是使用这个接口进行分配的
template<class T, class Alloc>
class simple_alloc {
  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)); }
};

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>
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)
  	{
	    result = start_free;
    	start_free += total_bytes;  // 内存池的首地址往后移
	    return(result);
  	}
  	// 内存池的内存不足以马上分配那么多内存, 但是还能满足分配一个即以上的大小, 那就按对齐方式全部分配出去
  	else if (bytes_left >= size)
  	{
	    nobjs = bytes_left/size;
    	total_bytes = size * nobjs;
    	result = start_free;
    	start_free += total_bytes;  // 内存池的首地址往后移
    	return(result);
  	}
  	else
  	{
	    // 如果一个对象的大小都已经提供不了了, 那就准备调用malloc申请两倍+额外大小的内存
	    size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);
    	// Try to make use of the left-over piece.
    	// 内存池还剩下的零头内存分给给其他能利用的链表, 也就是绝不浪费一点.
    	if (bytes_left > 0)
    	{
      		// 链表指向申请内存的地址
      		obj * __VOLATILE * my_free_list = free_list + FREELIST_INDEX(bytes_left);
      		((obj *)start_free) -> free_list_link = *my_free_list;
      		*my_free_list = (obj *)start_free;
    	}
    	start_free = (char *)malloc(bytes_to_get);
    	// 内存不足了
    	if (0 == start_free)
    	{
      		int i;
      		obj * __VOLATILE * my_free_list, *p;
      		// 充分利用剩余链表的内存, 通过递归来申请
      		for (i = size; i <= __MAX_BYTES; i += __ALIGN)
      		{
	        	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;	// In case of exception.
      		start_free = (char *)malloc_alloc::allocate(bytes_to_get);
	    }
	    	// 申请内存成功后重新修改内存起始地址和结束地址, 重新调用chunk_alloc分配内存
	    	heap_size += bytes_to_get;
	    	end_free = start_free + bytes_to_get;
    		return(chunk_alloc(size, nobjs));
  	}
}