本文不考虑异常处理情况。
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<bool threads, int inst>
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<bool threads, int inst>
95 char* __defalut_alloc_template<threads, inst>::start_free = 0;
96
97 template<bool threads, int inst>
98 char* __defalut_alloc_template<threads, inst>::end_free = 0;
99
100 template<bool threads, int inst>
101 size_t __defalut_alloc_template<threads, inst>::heap_size = 0;
102
103 template<bool threads, int inst>
104 typename __defalut_alloc_template<threads, inst>::obj * volatile
105 __defalut_alloc_template<threads, inst>::free_list[__NFREELISTS] = {0};
106
107
108 template<bool threads, int inst>
109 void* __defalut_alloc_template<threads, inst>::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 list
125 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 } else
138 {
139 current_obj->free_list_link = next_obj;
140 }
141 }
142 return result;
143 }
144
145 template<bool thread, int inst>
146 char* __defalut_alloc_template<thread, inst>::
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 list
175 // 首先寻找适当的free list
176 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 list
192 // 所谓适当是指"尚有未用，且区块足够大"的free list
193 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 // 递归调用自己，修正nobjs
204 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 // 递归调用自己，修正nobjs
214 return chunk_alloc(size, nobjs);
215 }
216 }
217
218 typedef __defalut_alloc_template<0,0> alloc;
219
220
221 #endif
