/*
eg : 我自己写了一个vector<int>. 
现在我需要先申请一个n = 10的容器. 
我本意只是需要这块空间, 但是你却直接给我构造了对象
咋地, 调构造不要钱（调用函数的消耗）是吧
同样, 我析构的时候.它是整个容器都调用了~T()，
但是可能我的有效对象根本没有装满容器
*/
namespace myvector
{   
  template<class InputIteractor>
  void for_each(InputIteractor first, InputIteractor last) {
    while (first != last) {
      cout << *first++ << " ";
    }
    cout << endl;
  }
  template<class T>
  class vector {
    typedef T* iterator;
    typedef const T* const_iterator;
  public:
    //null obj constructor
    vector() : _first(0), _last(0), _end_of_storage(0) {}
    vector(int n)
      : _first(new T[n]), _last(_first + n), _end_of_storage(_last) {
    }
    template<class InputIteractor>
    vector(InputIteractor first, InputIteractor last)
      :_first(0), _last(0), _end_of_storage(0) {
      size_t _cap = size_t(last - first);
      _first = new T[_cap];
      _last = _first + _cap;
      _end_of_storage = _last;
      iterator iter = _first;
      while (first != last) {
        (*iter) = *first++;
        ++iter;
      }
    }
    iterator begin() {
      return _first;
    }
    const_iterator begin() const {
      return _first;
    }
    iterator end() {
      return _last;
    }
    const_iterator end() const {
      return _last;
    }
    size_t size() {
      return size_t(_last - _first);
    }
    size_t capacity() {
      return size_t(_end_of_storage - _first);
    }
    T& operator[](size_t ind) { 
      return *(_first + ind); 
    }
    const T& operator[](size_t ind) const {
      return *(_first + ind);
    }
    ~vector() {
      if (_first) {
        delete[] _first;
      }
      _first = nullptr;
      _last = nullptr;
      _end_of_storage = nullptr;
    }
  private:
    /*
    数据结构写法
    size_t _size;
    size_t _cap;
    T* _data;
    */
    //stl 迭代器设计
    iterator _first;
    iterator _last;
    iterator _end_of_storage;
    //Alloc _allocator;
  };
}
int main() {
    myvector::vector<Test> ve(5);    
  return 0;
}

//其他几乎是一摸一样的和数据结构的正常写法, 核心所在就是那点iterator的设计.
namespace myvector
{
  template<class T>
  struct Allocator {
    T* allocate(size_t size) {//仅malloc
      cout << "allocate: " << size << endl;
      return (T*)malloc(sizeof(T) * size);
    }
    void deallocate(void* p) {//仅free
      cout << "deallocate" << endl;
      free(p);
    }
    void constructor(T* p, const T& val) {//定位new
      cout << "place new" << endl;
      new (p) T(val); //定位 new 
    }
    void destroy(T* p) {//仅销毁对象资源
      cout << "destroy" << endl;
      p->~T();//调用析构
    }
  };
  template<class InputIteractor>
  void for_each(InputIteractor first, InputIteractor last) {
    while (first != last) {
      cout << *first++ << " ";
    }
    cout << endl;
  }
  template<class T, class Alloc = Allocator<T>>
  class vector {
    typedef T* iterator;
    typedef const T* const_iterator;
  public:
    //null obj constructor
    vector() : _first(0), _last(0), _end_of_storage(0) {}        
    vector(int n) {
      _first = _allocator.allocate(n);
      _last = _first;//起始没有元素
      _end_of_storage = _first + n;
    }
    template<class InputIteractor>
    vector(InputIteractor first, InputIteractor last)
      :_first(0), _last(0), _end_of_storage(0) {
      size_t _cap = size_t(last - first);
      _first = new T[_cap];
      _last = _first + _cap;
      _end_of_storage = _last;
      iterator iter = _first;
      while (first != last) {
        (*iter) = *first++;
        ++iter;
      }
    }
    iterator begin() {
      return _first;
    }
    const_iterator begin() const {
      return _first;
    }
    iterator end() {
      return _last;
    }
    const_iterator end() const {
      return _last;
    }
    size_t size() {
      return size_t(_last - _first);
    }
    size_t capacity() {
      return size_t(_end_of_storage - _first);
    }
    T& operator[](size_t ind) { 
      return *(_first + ind); 
    }
    const T& operator[](size_t ind) const {
      return *(_first + ind);
    }
    ~vector() {//消除内存 + 析构有效空间对象
      //先析构有效对象
      for (int i = 0; i < size(); ++i) {
        _allocator.destroy(_first + i);
      }
      _allocator.deallocate(_first);//free内存
      _first = nullptr;
      _last = nullptr;
      _end_of_storage = nullptr;
    }
  private:
    /*
    数据结构写法
    size_t _size;
    size_t _cap;
    T* _data;
    */
    //stl 迭代器设计
    iterator _first;
    iterator _last;
    iterator _end_of_storage;
    Alloc _allocator;
  };
}

//SGI Allocator相较于operator new的优势所在一. 
static void* _S_oom_malloc(size_t);
static void* _S_oom_realloc(void*, size_t);
​
#ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG
  static void (* __malloc_alloc_oom_handler)();
//oom: out of memory 内存溢出, 内存不足的意思.

template <int __inst>
void*
__malloc_alloc_template<__inst>::_S_oom_malloc(size_t __n)
{
    void (* __my_malloc_handler)();//malloc_handler: 回调处理函数
    void* __result;
    /*
        while (set alloc_oom_handler)
            循环不断的执行handler
            直至 malloc sucess.
        if (not set alloc_oom_handler)
            throw bad_alloc();
    */
    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);
    }
}

#if ! (defined(__SUNPRO_CC) || defined(__GNUC__))
    enum {_ALIGN = 8};
    enum {_MAX_BYTES = 128};
    enum {_NFREELISTS = 16}; // _MAX_BYTES/_ALIGN  

  static char* _S_start_free;           //当前空闲内存起点
  static char* _S_end_free;             //空闲内存末尾
  static size_t _S_heap_size;           //已利用内存, 用于make free_list的内存
//上述静态成员数据的初始化
template <bool __threads, int __inst>
char* __default_alloc_template<__threads, __inst>::_S_start_free = 0;
​
template <bool __threads, int __inst>
char* __default_alloc_template<__threads, __inst>::_S_end_free = 0;
​
template <bool __threads, int __inst>
size_t __default_alloc_template<__threads, __inst>::_S_heap_size = 0;

  /* __n must be > 0      */
  static void* allocate(size_t __n)
  {
    void* __ret = 0;
​
    if (__n > (size_t) _MAX_BYTES) { //超过内存池最大限制
      __ret = malloc_alloc::allocate(__n);//采取malloc
    }
    else {//从内存池中获取内存
      _Obj* volatile* __my_free_list
          = _S_free_list + _S_freelist_index(__n);  //指向对应chunk块所在自由链表表头
#     ifndef _NOTHREADS
      _Lock __lock_instance;    //智能锁. 线程安全, 操作内存池（全局资源, 多线程共享）
#     endif
     //尝试获取头部chunk块
      _Obj* __RESTRICT __result = *__my_free_list;//拿取头部
      if (__result == 0)
        __ret = _S_refill(_S_round_up(__n));//填充chunk块free_list并return head chunk块 
      else {//chunk块free_list not null 拿走头部chunk块, 并且进行pop_front
        *__my_free_list = __result -> _M_free_list_link;
        __ret = __result;
      }
    }
    return __ret;
  };

template <bool __threads, int __inst>
void*
__default_alloc_template<__threads, __inst>::_S_refill(size_t __n)
{
    int __nobjs = 20;      //数目. chunk块数目
    char* __chunk = _S_chunk_alloc(__n, __nobjs);//alloc 先分配内存. 貌似就是一维数组
    _Obj* volatile* __my_free_list;
    _Obj* __result;
    _Obj* __current_obj;  //当前对象, 也就是记录当前chunk块
    _Obj* __next_obj;     //下一个chunk块
    int __i;            
​
    if (1 == __nobjs) return(__chunk);//只有一个chunk块, 直接return
/*
    往下必然是超过一个chunk块了, 干啥??? 不可以直接return ???
    上述仅仅create memory了. 我们需要的是链表, _free_list. so: 必然是分割memory为chunk块并且link起来
*/
    __my_free_list = _S_free_list + _S_freelist_index(__n);//拿到对应chunk块head node
​
    /* Build free list in chunk */
      __result = (_Obj*)__chunk;// get ans chunk
      *__my_free_list = __next_obj = (_Obj*)(__chunk + __n);//pop_front
      for (__i = 1; ; __i++) {//link 操作n 个node link n-1次 + pop_front, so link objs-2次
        __current_obj = __next_obj;
        __next_obj = (_Obj*)((char*)__next_obj + __n);
        if (__nobjs - 1 == __i) {
            __current_obj -> _M_free_list_link = 0;
            break;
        } else {
            __current_obj -> _M_free_list_link = __next_obj;
        }
      }
    return(__result);
}

 size_t __bytes_to_get =  //need malloc(__bytes_to_get) 用于 make _memory_free_list    
    2 * __total_bytes + _S_round_up(_S_heap_size >> 4);
//之前剩余的空闲内存__bytes_left > 0. 我们扔掉？ NO 想办法利用起来       
        if (__bytes_left > 0) {
            _Obj* volatile* __my_free_list =
                        _S_free_list + _S_freelist_index(__bytes_left);
      //头部插入到可以插入的小chunk块. 将剩余的small memory利用起来 
            ((_Obj*)_S_start_free) -> _M_free_list_link = *__my_free_list;
            *__my_free_list = (_Obj*)_S_start_free;
        }
//为内存池扩充内存. 产生 _chunk_free_list to provide chunk for user
        _S_start_free = (char*)malloc(__bytes_to_get);
        _S_heap_size += __bytes_to_get;//已利用的内存增加，制作成chunk_free_list的内存部分
        _S_end_free = _S_start_free + __bytes_to_get;//跳过已用于制作chunk_free_list内存
        return(_S_chunk_alloc(__size, __nobjs));//递归调用, 精髓在于前面的两个if

   //内存够了, 咋可能突然足够make chunk_free_list, 
    //必然是之前走了malloc. 对内存池扩充了可用内存
    if (__bytes_left >= __total_bytes) {
        __result = _S_start_free;
        _S_start_free += __total_bytes;
        return(__result);//真正的return memory逻辑. 将搞内存和return 内存分开
    }
//下面这个是个狠人逻辑. 虽然不足以整个__total_bytes 的分配, 但是我暂时还不想去malloc. 内存物尽其用. 能分配几个chunk块, 就利用起来产生几个chunk块咯. 总不能丢掉这点直接去从新malloc内存池吧. 
//牛逼之处, 真的做到了一丁点不浪费, 边角料大不了少做几个
    else if (__bytes_left >= __size) {
        __nobjs = (int)(__bytes_left/__size);
        __total_bytes = __size * __nobjs;
        __result = _S_start_free;
        _S_start_free += __total_bytes;
        return(__result);
    }