ptrdiff_t含義?

減去兩個指針的結果的帶符號整數類型
ptrdiff_t (Type support) - C 中文開發手冊 - 開發者手冊 - 云+社區 - 騰訊云

std::set_new_handler（）函數的理解

關于set_new_handler的理解_wck0617-CSDN博客
new分配內存的時候? 如果分配的空間不足采取什么樣的措施

自己實現空間配置器

#include <new>        //for placement new
#include <cstddef>    //for ptrdiff_t size_t
#include <cstdlib>    //for exit
#include <climits>    //for UINT_MAX
#include <iostream>   //for cerr
#include <vector>namespace Chy{template <class T>inline T* _allocate(ptrdiff_t size,T*){std::set_new_handler(0);T* tmp = (T*)(::operator new((std::size_t)(size * sizeof (T))));if (tmp == 0){std::cerr << "out of memory" << std::endl;exit(1);}return tmp;}template<class T>inline void _deallocate(T* buffer){::operator delete (buffer);}template<class T1,class T2>inline void _construct(T1 *p,const T2& value){new(p) T1 (value);  //沒看懂}template <class T>inline void _destroy(T* ptr){ptr->~T();}template <class T>class allocator{public:typedef T           value_type;typedef T*          pointer;typedef const T*    const_pointer;typedef T&          reference;typedef const T&    const_reference;typedef std::size_t size_type;typedef ptrdiff_t   difference_type;template<class U>struct rebind{typedef allocator<U>other;};pointer allocate(size_type n,const void * hint = 0){return _allocate((difference_type)n,(pointer)0);}void deallocate(pointer p,size_type n){_deallocate(p);}void construct(pointer p,const T& value){_construct(p,value);}void destroy(pointer p){_destroy(p);}pointer address(reference x){return (pointer)&x;}const_pointer const_address(const_reference x){return (const_pointer)&x;}size_type max_size()const{return size_type(UINT_MAX/sizeof (T));}};
}
int main(){int ia[5] = {0,1,2,3,4};unsigned int i;std::vector<int,Chy::allocator<int>>iv(ia,ia+5);for (int j = 0; j < iv.size(); ++j) {std::cout << iv[j] << " ";}std::cout << std::endl;
}

SGI STL 使用了專屬的擁有層級配置的特殊的空間配置器
SGI STL 提供了一個標準的空間配置器的接口叫做 simple_alloc

SGI STL 封裝的特殊的空間配置器 alloc

使用的時候 std::vector<int,std::alloc>iv；std::alloc 采用默認的形式
為了精密分工，STL a llo c a to r決定將這兩階段操作區分開來。內存配置操作由 alloc： al locate ()負責，內存釋放操作由alloc : : deallocate ()負責；對象構造操作由：：construct:()負責，對象析構操作由：；destroy負責

new算式內含兩階段操作： (1 )調用 ::operator new配置內存; ⑵ 調用Foo：：Foo()構造對象內容。
delete算式也內含兩階段操作：(1)調用Foo:~Foo ()將對象析構；(2 ) 調用 ::operator delete釋放內存。

?type_traits

c++11——type_traits 類型萃取 - 農民伯伯-Coding - 博客園
C++ STL __type_traits解析 - 知乎

構造和析構的基本工具 construct()和destroy()

#include <new>        //for placement new
#include <cstddef>    //for ptrdiff_t size_t
#include <cstdlib>    //for exit
#include <climits>    //for UINT_MAX
#include <iostream>   //for cerr
#include <vector>using namespace std;
template<class T>
struct __type_traits {typedef __true_type this_dummy_member_must_be_first;typedef __false_type has_trivial_default_constructor;typedef __false_type has_trivial_copy_constructor;typedef __false_type has_trivial_assignment_constructor;typedef __false_type has_trivial_destructor;typedef __false_type is_POD_type;
};template<class T1,class T2>
inline void _construct(T1 *p,const T2& value){new(p) T1 (value);  //placement new; 調用T1::T1(value)
}/** destroy() 的兩個版本*/
//以下是 destroy() 第一版本 接收一個指針
template <class T>
inline void _destroy(T* ptr){ptr->~T(); //調用 ~T()
}/********************************************************************/
//如果元素的型別(value_type)有non_trivial destructor
template <class ForwardIterator>
inline void __destroy_aux(ForwardIterator first,ForwardIterator last,std::__false_type){for( ; first < last;++first){destroy(&*first); //調用destroy的第一個版本}
}
//如果元素的型別(value_type)有trivial destructor
template <class ForwardIterator>
inline void __destroy_aux(ForwardIterator,ForwardIterator,std::true_type){}//判斷元素的型別(value type) 是否有 trivial 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());
}//destroy()第二版本 接收兩個迭代器 這個函數設法找出元素的型別
//進而使用 __Type_traits<> 求取適當的措施
template <class ForwardIterator>
inline void destroy(ForwardIterator first,ForwardIterator last){
//    __destroy()
}
/********************************************************************//** 以下是destroy() 第二版本針對迭代器為 char* 和 wchar_t 的特化版本*/
inline void destroy(char*,char*){}
inline void destroy(wchar_t *,wchar_t *){}

?第二版本的接受first和last兩個迭代器準備將[first，last)范圍內的元素都析構掉，但是如果這段范圍很大，對于每一個元素的析構都無關痛癢(即 trivial destructor類型的)，對于效率是一種損失。
因此需要進行偏特化的操作，在執行析構函數之前進行類型的判斷。如果是 true_type 什么都不做直接結束，如果是false_type的類型，使用循環的方式，針對每個元素使用第一個版本的destroy()函數進行析構釋放
問題：如何實現上述的 value_type() 和 __type_traits<> ？？

空間的配置和釋放

對象構造之前的空間配置和對象析構之后的空間的釋放由 <stl_alloc.h>負責

設計思路

向系統的heap 申請內存空間
考慮多線程狀態
考慮內存不足的應對措施
考慮小型區塊可能造成的內存碎片問題
代碼舉例排除了多線程的處理

設計思想

考慮到小型區塊造成的內存破碎問題，SGI設計了雙層級配置器，第一層級使用malloc()和free(),第二層級視情況采用不同的策略。
當配置的區塊超過128bytes時視為足夠大使用第一層級配置器
當配置的區塊小于128bytes時為了降低額外的負擔，使用memory pool的方式
alloc并不接受任何 template型別的參數
無論alloc使用的是第一級或者第二級配置器都需要外包一層接口

#ifdef __USE_MALLOC
typedef __malloc_alloc_template<0>malloc_alloc;
typedef malloc_alloc alloc;  //令alloc為第一級配置器//令alloc為第二級配置器
typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS,0>alloc;#endiftemplate<class T,class Alloc>
class simple_alloc{
public:static T* allocate(std::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 (n!=0){Alloc::deallocate(p,n * sizeof(T));}}static void deallocate(T* p){Alloc::deallocate(p,sizeof(T));}
};

內部的四個函數本質上是單純的轉接調用的關系調用傳遞給配置器的(可能是第一級別也可能是第二級別)
SGI STL容器都使用這個simple_alloc的接口

template <class T,class Alloc = alloc>
class vector{
protected://專屬空間配置器 每次分配一個元素的大小typedef simple_alloc<value_type,Alloc> data_allocator;void deallocate(){if(){data_allocator::deallocate(start,end_of_storage - start);}}
};

第一級配置器 __malloc_alloc_template剖析

#if 0
#   include<new>
#   define __THROW_BAD_ALLOC throw bad_alloc
#elif !defined(__THROW_BAD_ALLOC)
#   include<iostream>
#   define __THROW_BAD_ALLOC std::cerr << "out of memory" << std::endl; exit(1);
#endif//malloc-based allocator 通常比稍后介紹的default alloc要慢
//但是它是線程安全的 thread-safe，并對于空間的運用比較高效
//以下是第一級別配置器
//無“template 型別參數” 至于非型別參數 inst 完全沒有用到
template <int inst>
class __malloc_alloc_template{
private://以下內容都是函數指針，所代表的函數用于處理內存不足的情況//oom : out of memorystatic void *oom_malloc(std::size_t);static void *oom_realloc(void*,std::size_t);static void (* __malloc_alloc_oom_handler)();
public:static void* allocate(std::size_t n){void * result = malloc(n);//第一級配置器 直接使用malloc進行內存的分配//當無法滿足內存分配的需求的時候，使用oom_malloc()if(result == 0){result = oom_malloc(n);}return result;}static void deallocate(void* p,size_t /* n */){free(p); //第一級配置器 直接使用 free()進行釋放}static void* reallocate(void* p,size_t /*old_size*/,size_t new_size){void *result = realloc(p,new_size); //第一級別配置器直接使用realloc()//以下無法滿足需求的時候 改用oom_realloc()if (0==result){result = oom_realloc(p,new_size);}return result;}//以下是仿真C++的set_new_handler(),換句話說 你可以通過他指定自己的out_of_handlerstatic void(*set_malloc_handler(void (*f)()))(){void (* old)() = __malloc_alloc_oom_handler;__malloc_alloc_oom_handler = f;return (old);}};
//malloc_alloc out_of_memory handling
//初始化為0
template <int inst>
void (* __malloc_alloc_template<inst>::__malloc_alloc_oom_handler)() = 0;template <int inst>
void* __malloc_alloc_template<inst>::oom_malloc(std::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;}}
}template <int inst>
void *__malloc_alloc_template<inst>::oom_realloc(void *p, std::size_t n) {void (* my_malloc_handler)() = __malloc_alloc_oom_handler;void * result;if(0 == my_malloc_handler){__THROW_BAD_ALLOC;}(*my_malloc_handler)();//調用處理例程，企圖釋放內存result = realloc(p,n);//再次嘗試配置內存if (result){return result;}
}//以下直接將參數 inst 指定為0
typedef __malloc_alloc_template<0>malloc_alloc;

?第一級配置器使用malloc、free、realloc等C函數執行內存的配置、釋放、重新配置，并實現了類似C++ newhandler的機制，但是不能直接使用C++的new handler的機制因為他并沒有使用 ::operator new的方式來配置內存
C++ 的new handler的機制是要求系統在內存配置需求無法被滿足的時候調用一個用戶自定義的函數即 ::operator new無法完成任務拋出std::bad_alloc異常狀態之前先調用客戶指定的處理例程。這個處理的例程被稱作new handler
第一級配置器? allocate（）和 reallocate（）都會在調用malloc 和 realloc不成功之后改用 oom_malloc 和 oom_realloc 后者函數內設定一個循環，不斷調用內存不足處理的程序? ，期望某一次可以得到足夠的內存。如果未指定例程便會調用 __THROW_BAD_ALLOC 拋出bad_alloc異常信息，或者使用 exit(1) 終止程序

第二級配置器__default_alloc_template 剖析

第二級配置器使用機制避免造成內存的碎片?
額外負擔無法避免涉及到操作系統的內存管理；但是區塊越小，顯現的額外的負擔的比例就會越來越大，就會顯得浪費

?大于128轉交第一級配置器，小于128使用內存池管理。
次層配置：每次配置大內存，維護對應的自由鏈表，下次若有相同大小的內存需求，直接從自由鏈表中撥出
配置器負責內存的釋放和回收?
第二級配置器的小額區塊的內存空間是以8的倍數進行劃分，劃分的時候會自動將需求量上調至8的倍數
維護16個free_lists 各自管理 8 16 24 32 40 48 56 64 72 80 88 96 104 112 120 128

union obj{union obj * free_list_link;char client_data[1];// The client sees this
};

維護鏈表是需要額外的指針造成額外的負擔
考慮到 obj 使用的是union，可以視為一個指針指向相同類型的另外一個obj ； obj也可以視為一個指針指向實際的區塊? 一物二用

enum {__ALIGN = 8}; //小型區塊的上調邊界
enum {__MAX_BYTES = 128};//小型區塊的上限
enum {__NFREELISTS = __MAX_BYTES/__ALIGN};//free-lists的個數using namespace std;
//以下是第二級配置器
//注意：無 template型別參數 且第二參數哇怒氣按沒有被派上用場
//第一參數用于多線程的環境 本示例 暫未涉及
template <bool threads,int inst>
class __default_alloc_template{
private://ROUND_UP() 將bytes上調至8的倍數static size_t ROUND_UP(size_t bytes){return (((bytes) + __ALIGN - 1) & ~(__ALIGN-1));}private:union obj{    //free-lists 節點構造union obj * free_list_link;char client_data[1];// The client sees this};
private://16個free-listsstatic obj * volatile free_list[__NFREELISTS];//以下函數根據區塊的大小 決定使用第 n 號free-list，n從1開始算起static size_t FREELIST_INDEX(size_t bytes){return (((bytes) + __ALIGN-1)/__ALIGN-1);}//返回一個大小為n的對象 并可能加入大小為n 的其他區塊到free liststatic void* refill(size_t n);//配置一大塊區間 可以容納nobjs個“size”大小的區塊//如果配置nobjs個大小的區塊有所不方便 ，可以降低nobjsstatic char * chunk_alloc(size_t size,int &objs);//Chunk allocation statestatic char *start_free;//內存池起始的位置 只在chunk_alloc()中變化static char *end_free;//內存池結束的位置  只在chunk_alloc()中變化static size_t heap_size;public:static void* allocate(size_t n){}static void deallocate(void* p,size_t n){}static void *reallocate(void* p,size_t old_sz,size_t new_sz){}
};//以下是static data member 的定義與初值的設定
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>
typename __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};

空間配置函數 allocate()

這個函數首先判斷區塊的大小，大于128 使用第一級配置器，小于128 檢查對應的 free list。如果free list之內有可用的區塊就直接拿來使用
如果沒有可用的區塊，就將區塊大小上調至8的倍數邊界使用refill（）準備為free list填充空間?

template <bool threads,int inst>
void* __default_alloc_template<threads,inst>::allocate(size_t n) {obj* volatile *my_free_list;obj* result;//大于128就調用第一級配置器if(n>(size_t)__MAX_BYTES){return (malloc_alloc::allocate(n));}//尋找16個free lists中適當的一個my_free_list = free_list + FREELIST_INDEX(n);result = *my_free_list;if (result==0){//沒有找到free list，需要重新補充 free listvoid *r = refill(ROUND_UP(n));return r;}//調整free list*my_free_list = result->free_list_link;return result;
}

注意事項

注意事項：類里面聲明的靜態函數不能帶有{} ，否則后期實現函數邏輯的時候編譯不通過
只有用戶自定義的類型作為函數的返回值的時候需要使用typename關鍵字

template <bool threads,int inst>
void __default_alloc_template<threads,inst>::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;}//尋找對應的free listmy_free_list = free_list + FREELIST_INDEX(n);//調整free list 回收區塊q->free_list_link = *my_free_list;*my_free_list = q;}

?重新填充 free lists

當 free list中沒有可用的區塊的時候需要調用 refill() 函數為free list重新填充空間，新的空間將取自內存池(通過chunk_alloc完成 )
缺省獲得 20個新節點，萬一內存池空間不足獲得的節點數可能小于20

//返回一個大小為n的對象，并且有的時候會適當的位free list增加節點
//假設n已經上調為8的倍數
template <bool threads,int inst>
void* __default_alloc_template<threads,inst>::refill(size_t n) {int nobjs = 20;//調用chunk_alloc() 嘗試獲取nobjs個區塊作為free list的新的節點//注意參數nobjs是pass by reference的方式char* chunk = chunk_alloc(n,nobjs);obj* volatile * my_free_list;obj* result;obj* current_obj,*next_obj;int i;//如果只獲得一個區塊 這個區塊就會被分配給調用者使用 free list無新的節點if (1 == nobjs){return chunk;}//否則準備調整free list 納入新的節點my_free_list = free_list + FREELIST_INDEX(n);//在chunk空間內 建立free listresult = (obj*) chunk;   //這一塊準備返回給客戶端//以下導引free list指向新的配置的空間（取自內存池）*my_free_list = next_obj = (obj*)(chunk +n);//以下將free list的各個節點串接起來for(i=1;;i++){ //從1開始 因為第0個將會返回給客戶端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);
}

內存池

從內存池取空間給free list使用? 是chunk alloc函數的作用

//假設n已經上調為8的倍數
//注意參數nobjs是pass by reference
/** size：每一個objs的大小+* nobjs：創建objs的數量*/
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 byte_left = end_free - start_free;//內存池剩余空間if (byte_left >= total_bytes){//內存池的空間滿足需求量result = start_free;start_free += total_bytes;return result;} else if(byte_left >= size){//內存池存儲的空間不能完全滿足需求，但是足夠供應一個 （含）以上的區塊nobjs = byte_left/size; //可以滿足的數量total_bytes = nobjs * size;result = start_free;start_free += total_bytes;return (result);} else{//內存池剩余的空間連一個區塊的大小都無法滿足size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);//以下內容試著從內存池 殘余中 尋找if (byte_left > 0){//內存中還存在部分的內存空間 但是這個內存空間小于一個size 但是大于0//首先找到適當的free listobj* volatile* my_free_list = free_list + FREELIST_INDEX(byte_left);//調整free list 將內存池中的殘余空間全部編入到 free list里面((obj *)start_free)->free_list_link = *my_free_list;*my_free_list = (obj*) start_free;}//配置heap空間 用于填充內存池start_free = (char*)malloc(bytes_to_get);if (0 == start_free){//heap空間不足 malloc失敗int i;obj* volatile * my_free_list,*p;//嘗試檢視手上具備的東西 這不會造成傷害 我們不打算進一步進行配置較小的區塊//因為在多進程的機器上容易導致災難//以下代碼的目的是搜尋適當( 尚有未用的區塊，且區塊夠大 )的free listfor (i = size;i <= __MAX_BYTES;i+- __ALIGN ) {my_free_list = free_list + FREELIST_INDEX(i);p = *my_free_list;if (p!=0){//free list 內尚有未用的區塊//調整free list 釋放未使用的區塊*my_free_list = p->free_list_link;start_free = (char*)p;end_free = start_free + i;//遞歸調用自己 為了修正nobjsreturn (chunk_alloc(size,nobjs));//注意：任何殘余的領頭 終將被編入適當的free list中作為備用}}end_free = 0;//如果出現意外(山窮水盡 到處無內存可以使用)//調用第一級配置器 寄希望于第一級配置器 希望out-of-memory機制可以出一份力start_free = (char*) malloc_alloc::allocate(bytes_to_get);//這會拋出異常(exception) 或內存不足的情況獲得改善}heap_size += bytes_to_get;end_free = start_free + bytes_to_get;//遞歸調用自己 為了修正 nobjsreturn (chunk_alloc(size,nobjs));}
}

使用 end_free - start_free 判斷內存池的容量，如果空間充足直接調出20個區塊返回給free_list
如果不足20個但是大于1個以上的容量先提供可以滿足的區塊，遞歸更新 (pass by reference的nobjs修改為實際可以提供的區塊數)
如果一個都不可以滿足? 使用malloc從heap中配置內存為內存池注入活水，新水量的大小是需求量的2倍，還需要加上隨著配置次數增加愈來愈大的附加量

例子：假設程序一開始客戶端就調用?chunk_alloc（32，20），此刻內存池和free_list里面均沒有可用的內存空間，所以使用malloc() 配置40個32byte區塊，使用malloc分配的內存空間是需求的兩倍。其中第一個 32byte交出，19個給free_list [3] 進行維護，其余的20個留給內存池。
客戶端使用?chunk_alloc（64，20），此刻free_list [7]沒有內存，向內存池提出申請；內存池此刻具備的內存 (32 * 20)，所以只可以提供 (32 * 20)/64 = 10個64位區塊，返回10個區塊，第一個交給客戶端，剩余的9個由 free_list [7]。此刻內存池全空
客戶端調用chunk_alloc（96，20）此刻free_list [11]和內存池全為空，需要使用malloc分配內存，分配40+n個96bytes區塊，將第一個交出，另外19個交給free_list [11]維護，其余的20+n 的容量交給內存池
假設system heap空間不足了 (無法為內存池注入活水),malloc()行動失敗，chunk_malloc()就需要四處尋找合適的內存。找到了就挖一塊，這個是從free_list上面去挖內存，找不到就需要第一級配置器。
第一級配置器本質上還是使用malloc() 進行內存的配置，考慮到前提 system heap已經沒有內存了，為啥同樣使用malloc這里就可以了呢？因為第一配置器具備out-free-memory處理機制(類似new-handler機制) 就有機會去釋放其余地方多余的內存，進行內存的分配和使用。如果可以就成功，如果不可以就返回bad_malloc的異常。

注意事項：

template<class T,class Alloc>
class simple_alloc{};
//SGI 通常使用這種方式來使用配置器
template<class T,class Alloc = alloc> //缺省使用alloc為配置器
class vector{
public:typedef T value_type;
protected://專屬空間配置器  每次配置一個元素的大小typedef simple_alloc<value_type,Alloc>data_allocator;
};

其中第二個template參數所接受的缺省參數值alloc 可以是第一級配置器也可以是第二級配置器
不過SGI STL已經將其設定為第二級配置器?

完整代碼

#if 0
#   include<new>
#   define __THROW_BAD_ALLOC throw bad_alloc
#elif !defined(__THROW_BAD_ALLOC)
#   include<iostream>
#   define __THROW_BAD_ALLOC std::cerr << "out of memory" << std::endl; exit(1);
#endif//malloc-based allocator 通常比稍后介紹的default alloc要慢
//但是它是線程安全的 thread-safe，并對于空間的運用比較高效
//以下是第一級別配置器
//無“template 型別參數” 至于非型別參數 inst 完全沒有用到
template <int inst>
class __malloc_alloc_template{
private://以下內容都是函數指針，所代表的函數用于處理內存不足的情況//oom : out of memorystatic void *oom_malloc(std::size_t);static void *oom_realloc(void*,std::size_t);static void (* __malloc_alloc_oom_handler)();
public:static void* allocate(std::size_t n){void * result = malloc(n);//第一級配置器 直接使用malloc進行內存的分配//當無法滿足內存分配的需求的時候，使用oom_malloc()if(result == 0){result = oom_malloc(n);}return result;}static void deallocate(void* p,size_t /* n */){free(p); //第一級配置器 直接使用 free()進行釋放}static void* reallocate(void* p,size_t /*old_size*/,size_t new_size){void *result = realloc(p,new_size); //第一級別配置器直接使用realloc()//以下無法滿足需求的時候 改用oom_realloc()if (0==result){result = oom_realloc(p,new_size);}return result;}//以下是仿真C++的set_new_handler(),換句話說 你可以通過他指定自己的out_of_handlerstatic void(*set_malloc_handler(void (*f)()))(){void (* old)() = __malloc_alloc_oom_handler;__malloc_alloc_oom_handler = f;return (old);}};
//malloc_alloc out_of_memory handling
//初始化為0
template <int inst>
void (* __malloc_alloc_template<inst>::__malloc_alloc_oom_handler)() = 0;template <int inst>
void* __malloc_alloc_template<inst>::oom_malloc(std::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;}}
}template <int inst>
void *__malloc_alloc_template<inst>::oom_realloc(void *p, std::size_t n) {void (* my_malloc_handler)() = __malloc_alloc_oom_handler;void * result;if(0 == my_malloc_handler){__THROW_BAD_ALLOC;}(*my_malloc_handler)();//調用處理例程，企圖釋放內存result = realloc(p,n);//再次嘗試配置內存if (result){return result;}
}//以下直接將參數 inst 指定為0
typedef __malloc_alloc_template<0>malloc_alloc;enum {__ALIGN = 8}; //小型區塊的上調邊界
enum {__MAX_BYTES = 128};//小型區塊的上限
enum {__NFREELISTS = __MAX_BYTES/__ALIGN};//free-lists的個數using namespace std;
//以下是第二級配置器
//注意：無 template型別參數 且第二參數哇怒氣按沒有被派上用場
//第一參數用于多線程的環境 本示例 暫未涉及
template <bool threads,int inst>
class __default_alloc_template{
private://ROUND_UP() 將bytes上調至8的倍數static size_t ROUND_UP(size_t bytes){return (((bytes) + __ALIGN - 1) & ~(__ALIGN-1));}private:union obj{    //free-lists 節點構造union obj * free_list_link;char client_data[1];// The client sees this};
private://16個free-listsstatic obj * volatile free_list[__NFREELISTS];//以下函數根據區塊的大小 決定使用第 n 號free-list，n從1開始算起static size_t FREELIST_INDEX(size_t bytes){return (((bytes) + __ALIGN-1)/__ALIGN-1);}//返回一個大小為n的對象 并可能加入大小為n 的其他區塊到free liststatic void* refill(size_t n);//配置一大塊區間 可以容納nobjs個“size”大小的區塊//如果配置nobjs個大小的區塊有所不方便 ，可以降低nobjsstatic char * chunk_alloc(size_t size,int &nobjs);//Chunk allocation statestatic char *start_free;//內存池起始的位置 只在chunk_alloc()中變化static char *end_free;//內存池結束的位置  只在chunk_alloc()中變化static size_t heap_size;public:static void* allocate(size_t n);static void deallocate(void* p,size_t n);static void *reallocate(void* p,size_t old_sz,size_t new_sz);
};//以下是static data member 的定義與初值的設定
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>
typename __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};template <bool threads,int inst>
void* __default_alloc_template<threads,inst>::allocate(size_t n) {obj* volatile *my_free_list;obj* result;//大于128就調用第一級配置器if(n>(size_t)__MAX_BYTES){return (malloc_alloc::allocate(n));}//尋找16個free lists中適當的一個my_free_list = free_list + FREELIST_INDEX(n);result = *my_free_list;if (result==0){//沒有找到free list，需要重新補充 free listvoid *r = refill(ROUND_UP(n));return r;}//調整free list*my_free_list = result->free_list_link;return result;
}template <bool threads,int inst>
void __default_alloc_template<threads,inst>::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;}//尋找對應的free listmy_free_list = free_list + FREELIST_INDEX(n);//調整free list 回收區塊q->free_list_link = *my_free_list;*my_free_list = q;
}//返回一個大小為n的對象，并且有的時候會適當的位free list增加節點
//假設n已經上調為8的倍數
template <bool threads,int inst>
void* __default_alloc_template<threads,inst>::refill(size_t n) {int nobjs = 20;//調用chunk_alloc() 嘗試獲取nobjs個區塊作為free list的新的節點//注意參數nobjs是pass by reference的方式char* chunk = chunk_alloc(n,nobjs);obj* volatile * my_free_list;obj* result;obj* current_obj,*next_obj;int i;//如果只獲得一個區塊 這個區塊就會被分配給調用者使用 free list無新的節點if (1 == nobjs){return chunk;}//否則準備調整free list 納入新的節點my_free_list = free_list + FREELIST_INDEX(n);//在chunk空間內 建立free listresult = (obj*) chunk;   //這一塊準備返回給客戶端//以下導引free list指向新的配置的空間（取自內存池）*my_free_list = next_obj = (obj*)(chunk +n);//以下將free list的各個節點串接起來for(i=1;;i++){ //從1開始 因為第0個將會返回給客戶端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);
}//假設n已經上調為8的倍數
//注意參數nobjs是pass by reference
/** size：每一個objs的大小+* nobjs：創建objs的數量*/
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 byte_left = end_free - start_free;//內存池剩余空間if (byte_left >= total_bytes){//內存池的空間滿足需求量result = start_free;start_free += total_bytes;return result;} else if(byte_left >= size){}}