enum { __ALIGN = 8};
enum { __MAX_BYTES = 128};
enum { __NFREELISTS = __MAX_BYTES / __ALIGN};	// 128 / 8 = 16

template<bool threads, int inst>	//参数1：是否考虑多线程，参数2：标识
class __default_alloc_template
{
private:
    union obj	/* 只是类型定义 */
    {
        union obj * free_list_link;	//next
        char client_data[1];
    };
private:
    static obj * volatile free_list[__NFREELISTS];//volatile修饰obj*，即free_list数组中对于的数据内容。
    static char* start_free;//每次配置的一大块'内存' 的内存来源的剩余部分的起始
    static char* end_free;	//每次配置的一大块'内存' 的内存来源的剩余部分的末尾
    static size_t heap_size;//上面提到的都是内存来源，而这个内存来源都是从堆区申请的，堆区申请的总空间数要记录在案
    static size_t ROUNT_UP(size_t bytes);
    static size_t FREELIST_INDEX(size_t bytes);	//hash
    static char* chunk_alloc(size_t size, int & nobjs);//size - 对象的大小，nobjs对象的个数
    static void* refill(size_t size);	//重新填充
public:	/* 用户调用 */
    static void* allocate(size_t size);
    static void deallocate(void* p, size_t n);
    static void* reallocate(void* p, size_t old_sz, size_t new_sz);
};

// 对free_list[__NFREELISTS]进行初始化。
template<bool threads, int inst> //	1: __default_alloc_template是模板类，需要声明
typename __default_alloc_template<threads, inst>::obj * volatile // 2: obj是__default_alloc_template<threads, inst>类内的类，需要加上“哪个类”，并且要加上"typename"以示"obj"是个类名，而非成员。
    __default_alloc_template<threads, inst>::free_list[__NFREELISTS] = {};	// 3: free_list[__NFREELISTS]是__default_alloc_template<threads, inst>类内的成员，需要加上“哪个类”，但无需加"typename"。
// 对start_free进行初始化
template<bool threads, int inst>
char* __default_alloc_template<threads, inst>::start_free = nullptr;
// 对end_free进行初始化
template<bool threads, int inst>
char* __default_alloc_template<threads, inst>::end_free = nullptr;
// 对heap_size进行初始化
template<bool threads, int inst>
size_t __default_alloc_template<threads, inst>::heap_size = 0;

using malloc_alloc = __malloc_alloc_template<0>;

static void * allocate(size_t size)
{
    if(size > (size_t)__MAX_BYTES)
    {
        return malloc_alloc::allocate(size);	//转给一级配置器。
    }
    obj * result = nullptr;
    obj * volatile * my_free_list = nullptr;	//是二级指针，要指向obj*
    my_free_list = free_list + FREELIST_INDEX(size);
    result = *my_free_list;
    if(nullptr == result)	//说明此下标处无内存块了，需要申请。
    {
        void * r = refill(ROUND_UP(size));
        return r;
    }
    *my_free_list = result->free_list_link;	//把free_list此下标的指针更新到下一个节点。相当于链表的头删法。
    return result;
}

static void * refill(size_t size)
{
    int nobjs = 20;
    char * chunk = chunk_alloc(size, nobjs);
    //chunk_alloc运行之后，nobjs值可能发生改变。
    if(1 == nobjs)
    {
        //如果nobjs是1，则说明内存块正好用完，不用再处理后续内存区域的链接、移动
        return chunk;
    }
    
    //接下来，把内存块分崩离析，依次串联。
    obj * volatile * my_free_list = NULL;
    obj * result = (obj*)chunk;
    obj * current_obj = NULL, * next_obj = NULL;
    my_free_list = free_list + FREELIST_INDEX(size);
    *my_free_list = next_obj = (obj*)(chunk+size);
    for(int i = 1; ; ++i)
    {
        current_obj = next_obj;
        next_obj = (obj*)((char*)next_obj + size);
        if(i == nobjs-1)//最后一块
        {
            current_obj->free_list_link = NULL;
            break;
        }
        current_obj->free_list_link = next_obj;
    }
    return result;
}

static char* chunk_alloc(size_t size, int & nobjs)
{
    char * result = NULL;
    size_t total_bytes = size * nobjs;
    size_t bytes_left = end_free - start_free;
    if(bytes_left >= total_bytes)
    {
        result = start_free;
        start_free = start_free + total_bytes;
        return result;
    }
    else if(bytes_left >= size)
    {
        nobjs = bytes_left / size;
        total = size * nobjs;
        
        result = start_free;
        start_free = start_free + total_bytes;
        return result;
    }
    else //内存不足以分配1个对象，把剩余的插入到其他下标(剩8字节插到0, 16字节插到1, ...)，然后再另外申请一个大的
    {
        size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);
        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(NULL == start_free)	//堆区居然没有资源了！无奈之计，只能向比他之后的链表找有无剩余块。
        {
            obj * volatile * my_free_list = NULL;
            for(int i = size; i <= __MAX_BYTES; i += __ALIGN)	//注意，i从size开始，而不一定从最小的块大小8开始，因为找比你小的没有用处。得找大的。
            {
                my_free_list = free_list + FREELIST_INDEX(i);
                obj * p = NULL;
                if(NULL != p)	//找到了比他大的的剩余的了！
                {
                    *my_free_list = (*my_free_list)->free_list_link;
                    start_free = (char*)p;
                    end_free = start_free + i;
                    return chunk_alloc(size, nobjs);
                }
            }
            //如果上面的for循环没能使得其找到合适的内存块，则说明真的是“山穷水尽疑无路”了，只能转1级配置器，抛出异常或者通过handler处理。
            start_free = malloc_alloc::allocate(bytes_to_get);
        }
        end_free = start_free + bytes_to_get;
        heap_size += bytes_to_get;
        return chunk_alloc(size, nobjs);	//递归此函数，相当于重新来一遍流程
    }
}

static size_t ROUNT_UP(size_t bytes)
{
    // 0 -> 0, 1~8 -> 8, 9~16 - > 16, 17~24 -> 24, ...
    return (bytes+ __ALIGN-1) & ~(__ALIGN - 1);
}
static size_t FREELIST_INDEX(size_t bytes)
{
    // 1~8 -> 0, 9~16 -> 1, 17~24 -> 2, ...
    return ((bytes+ __ALIGN-1) / __ALIGN) - 1;
}

#ifdef __USE_MALLOC
typedef __malloc_alloc_template<0> malloc_alloc;
typedef malloc_alloc alloc;
#else
typedef __default_alloc_template<0, 0> alloc;
#endif

template<class T, class Alloc>
class simple_alloc
{
public:
    static T* allocate(size_t n)	//申请n个T对象
    {
        return Alloc::allocate(sizeof(T)*n);
    }
    static T* allocate()
    {
        return Alloc::allocate(sizeof(T));
    }
    void deallocate(T *p, size_t n)
    {
        if(NULL == p)return;
        Alloc::deallocate(p, sizeof(T)*n);
    }
    void deallocate(T* p)
    {
        if(NULL == p)return;
        Alloc::deallocate(p, sizeof(T));
    }
};

#include"my_list.h"
using namespace std;
int main()
{
    xcg::my_list<char> mylist;
    
    for(int i = 0; i < 23; ++i)
    {
        mylist.push_back(i + 'a');
    }
    return 0;
}

template<class _Ty, class _A = xcg::alloc>
class my_list
{
public:
    typedef _Ty							 value_type;
    typedef _Ty&						 reference;
    typedef _Ty*						 pointer;
    typedef const _Ty&					 const_reference;
    typedef const _Ty*					 const_pointer;
    
    typedef _A							 allocator_type;
    typedef xcg::simple_alloc<_Node, _A> data_allocate;		//simple_alloc中使用的是第二个参数的allocate。在这里即使用_A::allocate，默认参数是xcg::alloc，而根据开关语句，若是使用malloc_alloc则为一级配置器，若为default_alloc则用二级配置器。我们默认使用的是__default_alloc_template<0, 0>。
    
public:
    my_list() : _Head(_Buynode()), _Size(0) {}
protected:
    _Nodeptr _Buynode(_Nodeptr _parg = NULL, _Nodeptr _narg = NULL)
    {
        _Nodeptr _S = data_allocate::allocate();
        _Acc::_Prev(_S) = _parg == NULL ? _S : _parg;
        _Acc::_Next(_S) = _narg == NULL ? _S : _narg;
        return _S;
    }
private:
    _Nodeptr _Head;
    size_t _Size;
};

static void deallocate(void * p, size_t size)	// n 表示空间大小
{
    if(size > (size_t)__MAX_BYTES)
    {
        malloc_alloc::deallocate(p, size);
        return;
    }
    //归还给配置器
    obj * q = (obj*)p;
    obj * volatile * my_free_list = free_list + FREELIST_INDEX(size);
    //头插
    q->free_list_link = *my_free_list;
    *my_free_list = q;
    return;
}

iterator erase(iterator _P)
{
    _Nodeptr _S = _P++._Mynode();
    _Acc::_Next(_Acc::_Prev(_S)) = _Acc::_Next(_S);
    _Acc::_Prev(_Acc::_Next(_S)) = _Acc::_Prev(_S);
    destroy(&_Acc::_Value(_S));	//不删除节点，而是释放value域。
    _Freenode(_);
    
    return _P;
}
void _Freenode(_Nodeptr _P)
{
    data_allocate::deallocate(_P);
}
void pop_back()
{
    erase(--end());
}
void pop_front()
{
    erase(begin());
}

class Object
{
private:
    int value;
public:
    Object(int x = 0) : value(x)
    {
        cout << "create object" << this << endl;
    }
    ~Object()
    {
        cout << "destroy object" << this << endl;
    }
};
int main()
{
    xcg::my_list<Object> objlist;
    for(int i = 0; i < 10; ++i)
    {
        objlist.push_back(Object(i));
    }
    objlist.pop_back();
    return 0;
}

static void* reallocate(void * p, size_t old_sz, size_t new_sz)
{
    if(old_sz > (size_t)__MAX_BYTES && new_sz > (size_t)__MAX_BYTES)
    {
        return malloc_alloc::reallocate(p, old_sz, new_sz);
    }
    // old_sz == 20, new_sz == 22	-->24, 24
    if(ROUND_UP(old_sz) == ROUND_UP(new_sz))
    {
        return p;
    }
    // old_sz > 128, new_sz < 128
    // old_sz < 128, new_sz < 128
    // old_sz < 128, new_sz > 128
    size_t sz = old_sz < new_sz ? old_sz : new_sz;
    void * s = allocate(new_sz);
    memmove(s, p ,sz);
    deallocate(p, old, sz);
    return s;
}