// c語言中的malloc/free
void *p1 = malloc(512);
*(int*) p1 = 100;
free(p1);

// c++表達式new/delete 
int *p2 = new int(100);// 這里應(yīng)該是初始化為100，若要聲明數(shù)組，用new int[n];
delete p2;

// c++函數(shù)，等價于malloc和free
void *p3 = ::operator new(512);
*(int *)p3 = 100;
::operator delete(p3);

// c++標(biāo)準庫，通過object調(diào)用，以GNU為例
int *p4 = alloctor<int>().allocate(7);// 這里是分配7個int單元而不是7bytes
*p4 = 9;
allocator<int>().deallocate((int *)p4,7);// 7應(yīng)該與上文匹配

Complex *pc;
try {
   void* mem = operator new(sizeof(Complex)); // 分配內(nèi)存
   pc = static_cast<Complex*>(mem);    // cast 轉(zhuǎn)型 以符合對應(yīng)的類型，這里對應(yīng)為Complex*
   pc->Complex::Complex(1,2); // construct
   // 注意：只有編譯器才可以像上面那樣直接呼叫constructor 欲直接調(diào)用constructor可通用placement new: new(p) Complex(1,2);
}
catch(std::bad_alloc) {
   // 若allocation失敗就不執(zhí)行constructor
}

// delete pc;
pc->~Complex();  //先析構(gòu)
operator delete(pc);   //然后釋放內(nèi)存

class A{
public:
 int id;
 
    A(): id(0){}
    A(int i): id(i){}
    ~A(){}
};

A* buf = new A[size]; // 調(diào)用三次默認構(gòu)造函數(shù)A():id(0)
A* tmp = buf;
// placement new指定位置new
for(int i = 0; i<size; i++)
    new(tmp++) A(i);  //調(diào)用A(int i): id(i)自定義初始化
delete []buf; // 調(diào)用三次~A()

int* pi = new int[10];
delete pi;

#include <iostream>
#include <complex>
using namespace std;

class my_allocator{
    private:
     struct obj{
            struct obj* next;  // embedded pointer
        };
     obj* freestore = nullptr;
     const int CHUNK = 5;
    public:
     my_allocator(){};
     ~my_allocator(){};
     void* allocate(size_t);
     void deallocate(void*, size_t);
};

void* my_allocator::allocate(size_t size){
    // 從內(nèi)存池分配一個obj對象大小的內(nèi)存
    assert(size>0);
    obj* p;
    if(!freestore){
        freestore = p = static_cast<obj*>(malloc(CHUNK*size));
        for(int i = 0;i<CHUNK-1;i++){
            p->next = (obj*)((char*)(p+size));
            p = p->next;
        }
        p->next = nullptr;
    }
    p = freestore;
    freestore = freestore->next;
    return p;
}

void deallocate(void* p, size_t size){
    // 插入到內(nèi)存池
    (static_cast<obj*>(p))->next = freestore;
    freestore = static_cast<obj*>(p);
}

// example
class Foo{
    public:
     long L;
     string str;
     static my_allocator myAlloc;
     Foo(long l): L(l){}
     static void* operator new(size_t size){
            return myAlloc.allocate(size);
        }
     static void operator delete(void* dead, size_t size){
            return myAlloc.deallocate(dead, size);
        }
};
my_allocator Foo::myAlloc; // 靜態(tài)成員變量一定要在類聲明之外定義

static const int __ALLGN = 8; // 上調(diào)邊界
static const int __MAX_BYTES = 8; // 分配Chunk的上限
static const int __NFREELISTS = __MAX_BYTES/__ALLGN; // 鏈表的條數(shù)

template<bool threads, int inst>
class __default_alloc_template{
 private:
  static size_t ROUND_UP(size_t bytes){ // 向上取整8 
   return (bytes+__ALLGN-1) & ~(__ALLGN-1);
  }
  union obj{ // 亦可用struct
   union obj* free_list_link; // 鏈表的next指針，老規(guī)矩用了ebedded pointer
  }
  static obj* volatile free_list[__NFREELISTS]; // 多級大小內(nèi)存池
  static size_t FREELIST_INDEX(size_t bytes){ // 根據(jù)大小確定鏈表index
   return ((bytes+ALLGN-1)/__ALLGN-1);
  }
  static void *refill(size_t size);
  static char* chunk_alloc(size_t size, int &nobjs);
  
  // 戰(zhàn)備池
  static char* start_free; // 指向pool的頭
  static char* end_free; // 指向pool的尾
  static size_t heap_size; // 分配累積量
  
 public:
  static void* allocate(size_t size){
   obj* volatile *my_free_list; // 鏈表的鏈表
   obj* result;
   
   if(size > (size_t)__MAX_BYTES) // 大于128改用第一級分配器
    return (malloc_alloc::allocate(size));
   my_free_list = free_list+FREELIST_INDEX(size);
   result = *my_free_list;
   if(0==result){
    void* t = refill(ROUND_UP(size)); // 對此鏈表充值
    return t;
   }
   *my_free_list = result->free_list_link;
   return result;
  }
  static deallocate(void* p, size_t size){
            obj* q = (obj*)p;
            obj* volatile* my_free_list;
   if(size > static_cast<size_t>(__MAX_BYTES)){
    malloc_alloc::deallocate(p,size); // 大于128改用第一級分配器
    return;
   }
   my_free_list = free_list + FREELIST_INDEX(size);
   q->free_list_link = *my_free_list;
   *my_free_list = q;
  }
  static void* reallocate(void* p, size_t old_size,size_t new_size);
}


/*
    We allocate memory in large chunks inn order to avoid fragmenting the malloc
   heap too much, We assume that size is properly aligned.
    We hold the allocation lock. 
*/
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 bytees_left = end_free - start_free;
    
    if(bytees_left >= total_bytes) {  //pool空間足以滿足需求
 
        result = start_free;
        start_free += total_bytes; // 【Q1：如果pool中的空間不連續(xù)還能直接分配和相加嗎？A：虛擬地址是連續(xù)的】
        return(result); 
    }else if(bytees_left >= size) {  //pool空間只滿足一塊以上
        
        nobjs = bytees_left / size;   //改變需求個數(shù)
        total_bytes  = size * nobjs;  //改變需求總量   pass-by-value會改變參數(shù)
        result = start_free;
        start_free += total_bytes;
        return (result); 
    }else {   //pool空間不足以滿足一塊需求  碎片&&0
 
        //打算從system free-store上去這么多來充值
        size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);
        //處理碎片(將其掛到相應(yīng)的chunk指針端口)
        if(bytes_to_get > 0) {
            obj* volatile *my_free_list =   //重新定位碎片的指針
               free_list + FREELIST_INDEX(bytees_left); 
            ((obj*)start_free)->free_list_link = *my_free_list;
            *my_free_list = (obj*)start_free; 
        }
 
        //從system free-store中取
        start_free = (char*)malloc(bytes_to_get); 
        if(0 == start_free) {  //如果當(dāng)前的chunk分配失敗，則向上繼續(xù)找相鄰的chunk繼續(xù)分配
            obj* volatile *my_free_list, *p;
            for(int i = size; i <= __MAX_BYTES; i += __ALLGN) {
                my_free_list = free_list + FREELIST_INDEX(i); 
                p = *my_free_list;
                if(0 != p) {  //該free-list有可用區(qū)塊
                    *my_free_list = p->free_list_link; 
                    start_free  = (char*)p;
                    end_free = start_free + i; 
                    return (chunk_alloc(size, nobjs));   //結(jié)果再試一次
                }
            }
            end_free = 0;
            start_free = (char*)malloc_alloc::allocate(bytes_to_get); 
        }
 
        //至此，表示已經(jīng)從system free-store成功取得很多memory
        heap_size += bytes_to_get;
        end_free = start_free + bytes_to_get;
        return (chunk_alloc(size, nobjs));   //戰(zhàn)備池有內(nèi)存了，所以遞歸重新處理分配邏輯
    }
}
 
//靜態(tài)定義(分配內(nèi)存)
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>
__default_alloc_template<threads, inst>::obj* volatile
__default_alloc_template<threads, inst>::free_list[__NFREELISTS] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
 
 
//std::alloc為第二級分配器
typedef  __default_alloc_template<false, 0> alloc;

int main(void){
    std::vector<int,MyAllocator<int>> v;
}