本文不考虑异常处理情况。
STL的第二级配置器是默认使用的配置器，第一级配置器只是简单的调用malloc(),free(),realloc()等函数，并没有真正意义上对内存进行管理
STL的第二级配置器相对较为复杂，利用了链表的形式管理16种内存大小不同的区块。由于链表的存在，当使用内存不再需要时，不是简单的释放(free())，而是将其回收到链表中，省去了反复释放和申请内存的开销。
代码如下：
1 #ifndef __H_DEFAULT 2 #define __H_DEFAULT 3 #include "__malloc_alloc_template.h" 4 5 enum {__ALIGN = 8}; // 小型区块的上调边界 6 enum {__MAX_BYTES = 128}; // 小型区块的上限 7 enum {__NFREELISTS = __MAX_BYTES / __ALIGN}; // free-lists 个数 8 9 10 template 11 class __defalut_alloc_template 12 { 13 private: 14 // ROUND_UP() 将bytes上调至8的倍数 15 static size_t ROUND_UP(size_t bytes) 16 { 17 return ((bytes) + __ALIGN - 1) & ~(__ALIGN - 1); 18 } 19 20 private: 21 union obj // free-lists 的节点构造 22 { 23 union obj* free_list_link; 24 char client_data[1]; 25 }; 26 27 private: 28 // 16个free-lists 29 static obj * volatile free_list[__NFREELISTS]; 30 // 以下函数根据区块大小，决定使用第n号free-list，n从0算起 31 static size_t FREELIST_INDEX(size_t bytes) 32 { 33 return (((bytes) + __ALIGN - 1)/__ALIGN -1); 34 } 35 36 // 返回一个大小为n的对象，并可能加入大小为n的其他区块到free list 37 static void* refill(size_t n); 38 static char* chunk_alloc(size_t size, int& nobjs); 39 40 // Chunk allocation state 41 static char* start_free; // 内存池的起始位置，只在chunk_alloc()中变化 42 static char* end_free; // 内存池的结束位置，只在chunk_alloc()中变化 43 static size_t heap_size; 44 45 public: 46 static void* allocate(size_t n) 47 { 48 // a pointer to a valatile pointer to obj 49 obj * volatile * my_free_list; 50 obj * result; 51 // 大于128就使用第一级配置器 52 if(n > (size_t) __MAX_BYTES) 53 { 54 return malloc_alloc::allocate(n); 55 } 56 57 // 寻找16个free list中适当的一个 58 my_free_list = free_list + FREELIST_INDEX(n); 59 result = *my_free_list; 60 if(result == 0) 61 { 62 // 没有找到可用的free list，准备重新填充free list 63 void* r = refill(ROUND_UP(n)); 64 return r; 65 } 66 *my_free_list = result->free_list_link; 67 return result; 68 } 69 70 public: 71 static void deallocate(void* p, size_t n) 72 { 73 obj* q = (obj *)p; 74 obj * volatile * my_free_list; 75 76 // 大于128就调用第一级配置器 77 if(n > (size_t)__MAX_BYTES) 78 { 79 malloc_alloc::deallocate(p, n); 80 return; 81 } 82 83 // 寻找对应的free list 84 my_free_list = free_list + FREELIST_INDEX(n); 85 // 调整free list，回收区块 86 q->free_list_link = *my_free_list; 87 *my_free_list = q; 88 } 89 90 static void* reallocate(void* p, size_t old_sz, size_t new_sz); 91 }; 92 93 // 以下是static data member 的定义与初值设定 94 template 95 char* __defalut_alloc_template ::start_free = 0; 96 97 template 98 char* __defalut_alloc_template ::end_free = 0; 99 100 template 101 size_t __defalut_alloc_template ::heap_size = 0;102 103 template 104 typename __defalut_alloc_template ::obj * volatile 105 __defalut_alloc_template ::free_list[__NFREELISTS] = { 0};106 107 108 template 109 void* __defalut_alloc_template ::refill(size_t n)110 {111 int nobjs = 20;112 char* chunk = chunk_alloc(n, nobjs);113 obj * volatile * my_free_list;114 obj * result;115 obj * current_obj, * next_obj;116 int i;117 118 // 如果只获得一个区块，这个区块就分配给调用者用，free list 无新节点119 if(nobjs == 1)120 return chunk;121 // 否则准备调整free list，纳入新节点122 my_free_list = free_list + FREELIST_INDEX(n);123 124 // 以下在chunk空间内建立free list125 result = (obj *)chunk; // 这一块返回给客端126 // 以下引导free list 指向新配置的空间（取自内存池）127 *my_free_list = next_obj = (obj *)(chunk + n);128 // 以下将free list 串接起来129 for(i = 1; ; i++) // 从1开始，因为第0个将返回给客端130 {131 current_obj = next_obj;132 next_obj = (obj *)((char *)next_obj + n);133 if(nobjs - 1 == i)134 {135 current_obj->free_list_link = 0;136 break;137 } else138 {139 current_obj->free_list_link = next_obj;140 }141 }142 return result;143 }144 145 template 146 char* __defalut_alloc_template ::147 chunk_alloc(size_t size, int& nobjs)148 {149 char* result;150 size_t total_bytes = size * nobjs;151 size_t bytes_left = end_free - start_free; // 内存池剩余空间152 153 if(bytes_left >= total_bytes)154 {155 // 内存池剩余空间完全满足需求156 result = start_free;157 start_free += total_bytes;158 return result;159 } else if(bytes_left >= size)160 {161 // 内存池剩余空间不能完全满足需求量，但足够提供一个(含)以上的区块162 nobjs = bytes_left / size;163 total_bytes = size * nobjs;164 result = start_free;165 start_free += total_bytes;166 return result;167 } else 168 {169 // 内存池剩余空间连一个区块大小都无法提供170 size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);171 // 以下试着让内存池中的残余零头还有利用价值172 if(bytes_left > 0)173 {174 // 内存池内还有一些零头，先配给适当的free list175 // 首先寻找适当的free list176 obj * volatile * my_free_list =177 free_list + FREELIST_INDEX(bytes_left);178 // 调整free list，将内存池中的残余空间编入179 ((obj *)start_free)->free_list_link = *my_free_list;180 *my_free_list = (obj *)start_free;181 }182 183 // 配置heap空间，用来补充内存池184 start_free = (char *)malloc(bytes_to_get);185 if(0 == start_free)186 {187 // heap 空间不足，malloc()失败188 int i;189 obj * volatile * my_free_list, *p;190 // 试着检视我们手上拥有的东西191 // 以下搜寻适当的free list192 // 所谓适当是指"尚有未用，且区块足够大"的free list193 for(i = size; i < __MAX_BYTES; i += __ALIGN)194 {195 my_free_list = free_list + FREELIST_INDEX(size);196 p = *my_free_list;197 if(p != 0)198 {199 // 调整free list以释放未用区块200 *my_free_list = p->free_list_link;201 start_free = (char *)p;202 end_free = start_free + i;203 // 递归调用自己，修正nobjs204 return chunk_alloc(size, nobjs);205 }206 }207 end_free = 0; // 如果出现意外(山穷水尽，到处都没有内存用了)208 // 调用第一配置器，看看out-of-memory机制能否尽力209 start_free = (char *)malloc_alloc::allocate(bytes_to_get);210 }211 heap_size += bytes_to_get;212 end_free = start_free + bytes_to_get;213 // 递归调用自己，修正nobjs214 return chunk_alloc(size, nobjs);215 }216 }217 218 typedef __defalut_alloc_template<0,0> alloc;219 220 221 #endif