STL源码标注_空间适配器
程序员文章站
2022-10-17 15:12:13
STL源码学习---空间适配器 ......
/* stl_alloc.h */
SGI STL空间适配器的主要由alloc.h和stl_alloc.h实现
SGI STL空间适配器的核心：
第一级适配器__malloc_alloc_template:直接调用malloc()和free()函数
第二级适配器__default_alloc_template:当配置区块超过128B时调用一级适配器;否则采用内存池管理空间的分配
第二级配置器工作流程：当配置区块超过128B时调用一级适配器;否则，从*链表维护的内存块中申请内存，若没有对应申请大小的*链表，则从内存池中申请内存构造*链表，内存池中内存不足时，从堆中申请内存填充内存池(*链表：负责维护不同大小的内存块，由于第二级配置器会将任何内存需求量上调为8的倍数,且能够分配的最大内存为128B,则*链表的个数为128/8=16个;每个链表分别维护区块内存大小为8,16,24,32,40,48,56,64,72,80,88,96,104,112,120,128B)
例子:
1、请求168字节内存:由于其大于128字节,则交由一级内存适配器
2、请求16字节内存:由于其小于128字节,二级配置器接管请求，对应第2个*链表,数组下标为1,*链表为空，则调用_S_refill函数申请内存并构造*链表;此时s_refill(16)接收到请求后,调用_S_chunk_alloc(16,20)函数完成从内存池的内存分配，_S_chunk_alloc(16,20)被调用后,若内存池是空的,接着从堆中申请足够大的内存块给内存池，内存池填充完毕后，分配16*20个字节的内存给*链表，该*链表维护单位为16B的内存
3、请求64字节内存由于其小于128字节,二级配置器接管请求，对应第8个*链表,数组下标为7,*链表为空，则调用_S_refill函数申请内存并构造*链表;此时s_refill(64)接收到请求后,调用_S_chunk_alloc(64,20)函数完成从内存池的内存分配，_S_chunk_alloc(64,20)被调用后,若内存池是空的,接着从堆中申请足够大的内存块给内存池，内存池填充完毕后，分配64*20个字节的内存给*链表，该*链表维护单位为64B的内存
4、再次请求16字节内存：由于其小于128字节,二级配置器接管请求，对应第2个*链表,数组下标为1,*链表不为空，从*链表维护的内存中申请内存，同时调整*链表头调整位置
1 ///////////////////////////////////////////////////////////////////////////////////////////
2
3 //++定义一级内存适配器
4 template <int __inst>
5 class __malloc_alloc_template {
6 private:
7
8 static void* _S_oom_malloc(size_t); //allocate函数分配内存失败时执行的函数
9 static void* _S_oom_realloc(void*, size_t); //reallocate函数分配内存失败时执行的函数
10
11 #ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG
12 static void (* __malloc_alloc_oom_handler)(); //定义分配出错时执行的函数指针
13 #endif
14
15 public:
16
17 static void* allocate(size_t __n) //内存分配函数
18 {
19 void* __result = malloc(__n);
20 if (0 == __result) __result = _S_oom_malloc(__n);
21 return __result;
22 }
23
24 static void deallocate(void* __p） //内存释放函数
25 {
26 free(__p);
27 }
28
29 static void* reallocate(void* __p, size_t __new_sz) //内存重新分配函数
30 {
31 void* __result = realloc(__p, __new_sz);
32 if (0 == __result) __result = _S_oom_realloc(__p, __new_sz);
33 return __result;
34 }
35
36 static void (* __set_malloc_handler(void (*__f)()))()//指定自己的异常处理,__set_malloc_handler为一个函数，参数为void (*__f)()，返回值为static void(*)()
37 {
38 void (* __old)() = __malloc_alloc_oom_handler;
39 __malloc_alloc_oom_handler = __f;
40 return(__old);
41 }
42
43 };
44
45 #ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG
46 template <int __inst>
47 void (* __malloc_alloc_template<__inst>::__malloc_alloc_oom_handler)() = 0;
48 #endif
49
50 //++定义_S_oom_malloc(size_t)
51 template <int __inst>
52 void* __malloc_alloc_template<__inst>::_S_oom_malloc(size_t __n)
53 {
54 void (* __my_malloc_handler)();
55 void* __result;
56
57 for (;;) //不断执行循环，每次都尝试申请内存，直至分配成功，内存分配失败时若存在内存分配失败函数则执行，否则抛出异常
58 {
59 __my_malloc_handler = __malloc_alloc_oom_handler;
60 if (0 == __my_malloc_handler) { __THROW_BAD_ALLOC; }
61 (*__my_malloc_handler)();
62 __result = malloc(__n);
63 if (__result) return(__result);
64 }
65 }
66 //++定义_S_oom_realloc(size_t)
67 template <int __inst>
68 void* __malloc_alloc_template<__inst>::_S_oom_realloc(void* __p, size_t __n)
69 {
70 void (* __my_malloc_handler)();
71 void* __result;
72
73 for (;;) //不断执行循环，每次都尝试申请内存，直至分配成功，内存分配失败时若存在内存分配失败函数则执行，否则抛出异常
74 {
75 __my_malloc_handler = __malloc_alloc_oom_handler;
76 if (0 == __my_malloc_handler) { __THROW_BAD_ALLOC; }
77 (*__my_malloc_handler)();
78 __result = realloc(__p, __n);
79 if (__result) return(__result);
80 }
81 }
82
83 //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
1 #ifdef __USE_MALLOC
2 typedef malloc_alloc alloc;
3 typedef malloc_alloc single_client_alloc;
4 #else
5 #if defined(__SUNPRO_CC) || defined(__GNUC__)
6 enum {_ALIGN = 8};
7 enum {_MAX_BYTES = 128};
8 enum {_NFREELISTS = 16};
9 #endif
10
11
12 //////////////////////////////////////////////////////////////////////////////////
13
14 //++定义二级内存适配器
15 template <bool threads, int inst>
16 class __default_alloc_template {
17
18 private:
19
20 #if !(defined(__SUNPRO_CC) || defined(__GNUC__))
21 enum {_ALIGN = 8}; //对齐字节数
22 enum {_MAX_BYTES = 128}; //最大分配字节数
23 enum {_NFREELISTS = 16}; //_MAX_BYTES/_ALIGN
24 #endif
25
26 static size_t _S_round_up(size_t __bytes) { return (((__bytes) + (size_t)_ALIGN-1) & ~((size_t)_ALIGN - 1)); } //计算向上对齐后的字节数
27
28 __PRIVATE:
29 union _Obj //*链表节点
30 {
31 union _Obj* _M_free_list_link;
32 char _M_client_data[1];
33 };
34
35 private:
36 #if defined(__SUNPRO_CC) || defined(__GNUC__) || defined(__HP_aCC) //定义*链表数组
37 static _Obj* __STL_VOLATILE _S_free_list[];
38 #else
39 static _Obj* __STL_VOLATILE _S_free_list[_NFREELISTS];
40 #endif
41
42 static size_t _S_freelist_index(size_t __bytes) {return (((__bytes) + (size_t)_ALIGN-1)/(size_t)_ALIGN - 1);} //计算对应*链表在数组中的位置
43
44 static void* _S_refill(size_t __n); //填充空间,把大小为__n的内存空间加到*链表中
45 static char* _S_chunk_alloc(size_t __size, int& __nobjs); //从内存池中分配空间给*链表,该空间可容纳__nobjs个大小为__size的区块
46 static char* _S_start_free; //内存池起始位置
47 static char* _S_end_free; //内存池结束位置
48 static size_t _S_heap_size; //当前内存池大小
49
50 #ifdef __STL_THREADS
51 static _STL_mutex_lock _S_node_allocator_lock;
52 #endif
53
54 class _Lock;
55 friend class _Lock;
56 class _Lock
57 {
58 public:
59 _Lock() { __NODE_ALLOCATOR_LOCK; }
60 ~_Lock() { __NODE_ALLOCATOR_UNLOCK; }
61 };
62
63 public:
64
65 static void* allocate(size_t __n)
66 {
67 void* __ret = 0;
68 if (__n > (size_t)_MAX_BYTES) //申请内存大于128B时,采用一级内存适配器
69 {
70 __ret = malloc_alloc::allocate(__n);
71 }
72 else //申请内存小于128B时，从*链表中申请内存
73 {
74 _Obj* __STL_VOLATILE* __my_free_list = _S_free_list + _S_freelist_index(__n); //单位为__n大小的*链表头节点
75 #ifndef _NOTHREADS
76 _Lock __lock_instance;
77 #endif
78 _Obj* __RESTRICT __result = *__my_free_list; //从*链表中截取内存赋值给__result
79 if (__result == 0)
80 __ret = _S_refill(_S_round_up(__n)); //若数组中不存在单位为__n大小的*链表，则调用_S_refill函数生成单位为__n大小的*链表
81 else
82 {
83 *__my_free_list = __result -> _M_free_list_link; //若数组中存在单位为__n大小的*链表，则*链表头节点后移一个单位
84 __ret = __result;
85 }
86 }
87 return __ret;
88 };
89
90 static void deallocate(void* __p, size_t __n)
91 {
92 if (__n > (size_t) _MAX_BYTES)
93 malloc_alloc::deallocate(__p, __n); //释放内存大于128B时,采用一级内存适配器
94 else //释放内存小于128B时，从*链表中申请内存
95 {
96 _Obj* __STL_VOLATILE* __my_free_list = _S_free_list + _S_freelist_index(__n); //单位为__n大小的*链表头节点
97 _Obj* __q = (_Obj*)__p;
98 #ifndef _NOTHREADS
99 _Lock __lock_instance;
100 #endif
101 __q -> _M_free_list_link = *__my_free_list;
102 *__my_free_list = __q; //将内存归还至单位为__n的*链表中，并将*链表头节点指向新归还的地址
103 }
104 }
105 };
106
107 static void* reallocate(void* __p, size_t __old_sz, size_t __new_sz);
108
109 typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS, 0> alloc;
110 typedef __default_alloc_template<false, 0> single_client_alloc;
111
112 template <bool __threads, int __inst>
113 inline bool operator==(const __default_alloc_template<__threads, __inst>&,const __default_alloc_template<__threads, __inst>&)
114 {
115 return true;
116 }
117
118 # ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
119 template <bool __threads, int __inst>
120 inline bool operator!=(const __default_alloc_template<__threads, __inst>&,const __default_alloc_template<__threads, __inst>&)
121 {
122 return false;
123 }
124 # endif
125
126
127 //++定义_S_chunk_alloc函数
128 template <bool __threads, int __inst>
129 char* __default_alloc_template<__threads, __inst>::_S_chunk_alloc(size_t __size, int& __nobjs)
130 {
131 char* __result; //预返回的内存块儿首地址
132 size_t __total_bytes = __size * __nobjs; //预分配的内存块总大小,通常情况下nojbs的大小为20,nobjs的大小由s_refill函数传进
133 size_t __bytes_left = _S_end_free - _S_start_free; //memory pool剩余内存块大小
134
135 if (__bytes_left >= __total_bytes) //内存池剩余空间满足20个需求,直接分配
136 {
137 __result = _S_start_free;
138 _S_start_free += __total_bytes;
139 return (__result);
140 }
141 else if (__bytes_left >= __size) //内存池剩余空间不满足20个需求,但满足一个或多个,取出最多个能满足条件区块的个数
142 {
143 __nobjs = (int)(__bytes_left/__size);
144 __total_bytes = __size * __nobjs;
145 __result = _S_start_free;
146 _S_start_free += __total_bytes;
147 return(__result);
148 }
149 else //内存池剩余空间不足一个区块大小，则向堆中重新申请内存至内存池
150 {
151 size_t __bytes_to_get = 2 * __total_bytes + _S_round_up(_S_heap_size >> 4); //扩大需要量, 新需求量是原需求量的二倍与现有内存池大小的十六分之一的和
152 if (__bytes_left > 0) //判断内存池中是否有残余空间,如果有则将其编入*链表
153 {
154 _Obj* __STL_VOLATILE* __my_free_list = _S_free_list + _S_freelist_index(__bytes_left);
155 ((_Obj*)_S_start_free) -> _M_free_list_link = *__my_free_list;
156 *__my_free_list = (_Obj*)_S_start_free;
157 }
158
159 _S_start_free = (char*)malloc(__bytes_to_get); //从堆中申请内存
160
161 if (0 == _S_start_free) //若从堆中申请内存失败，则循环的从所有*链表中寻找未用且足够大的内存块,释放这些内存块并将其编入内存池
162 {
163 size_t __i;
164 _Obj* __STL_VOLATILE* __my_free_list;
165 _Obj* __p;
166 for (__i = __size;__i <= (size_t)_MAX_BYTES;__i += (size_t)_ALIGN) //每次增加8个字节，查找每一个单位大于__size的*链表
167 {
168 __my_free_list = _S_free_list + _S_freelist_index(__i);
169 __p = *__my_free_list;
170 if (0 != __p) {
171 *__my_free_list = __p -> _M_free_list_link;
172 _S_start_free = (char*)__p;
173 _S_end_free = _S_start_free + __i;
174 return(_S_chunk_alloc(__size, __nobjs)); //递归调用_S_chunk_alloc函数填充内存池
175 }
176 }
177 _S_end_free = 0; //从*链表中找不到合适的内存，则调用一级内存适配器再次申请内存
178 _S_start_free = (char*)malloc_alloc::allocate(__bytes_to_get);
179 }
180 _S_heap_size += __bytes_to_get;
181 _S_end_free = _S_start_free + __bytes_to_get;
182 return(_S_chunk_alloc(__size, __nobjs)); //递归调用_S_chunk_alloc函数填充内存池
183 }
184 }
185
186
187 //++定义_S_refill函数
188 template <bool __threads, int __inst>
189 void* __default_alloc_template<__threads, __inst>::_S_refill(size_t __n)
190 {
191 int __nobjs = 20; //默认*链表管理的块数
192 char* __chunk = _S_chunk_alloc(__n, __nobjs); //内存池头指针
193 _Obj* __STL_VOLATILE* __my_free_list; //当前空闲内存块地址
194 _Obj* __result; //返回的地址
195 _Obj* __current_obj; //当前内存块头
196 _Obj* __next_obj; //下一个内存块头
197 int __i; //循环变量
198
199 if (1 == __nobjs) return(__chunk); //如果只有一个块则返回,*链表没有接区块管理
200
201 __my_free_list = _S_free_list + _S_freelist_index(__n);
202 __result = (_Obj*)__chunk; //将第一个内存块返回，其余内存块编入*链表
203 *__my_free_list = __next_obj = (_Obj*)(__chunk + __n);
204 for (__i = 1; ; __i++) //for循环，生成单位大小为__n的*链表
205 {
206 __current_obj = __next_obj;
207 __next_obj = (_Obj*)((char*)__next_obj + __n);
208 if (__nobjs - 1 == __i) {
209 __current_obj -> _M_free_list_link = 0;
210 break;
211 } else {
212 __current_obj -> _M_free_list_link = __next_obj;
213 }
214 }
215 return(__result);
216 }
217
218 //++定义reallocate函数
219 template <bool threads, int inst>
220 void*__default_alloc_template<threads, inst>::reallocate(void* __p,size_t __old_sz,size_t __new_sz)
221 {
222 void* __result;
223 size_t __copy_sz;
224
225 if (__old_sz > (size_t) _MAX_BYTES && __new_sz > (size_t) _MAX_BYTES)
226 {
227 return(realloc(__p, __new_sz));
228 }
229 if (_S_round_up(__old_sz) == _S_round_up(__new_sz)) return(__p);
230 __result = allocate(__new_sz);
231 __copy_sz = __new_sz > __old_sz? __old_sz : __new_sz;
232 memcpy(__result, __p, __copy_sz);
233 deallocate(__p, __old_sz);
234 return(__result);
235 }
236
237 #ifdef __STL_THREADS
238 template <bool __threads, int __inst>
239 _STL_mutex_lock
240 __default_alloc_template<__threads, __inst>::_S_node_allocator_lock
241 __STL_MUTEX_INITIALIZER;
242 #endif
243
244 //++二级内存适配器类变量初始化操作
245 template <bool __threads, int __inst>
246 char* __default_alloc_template<__threads, __inst>::_S_start_free = 0;
247
248 template <bool __threads, int __inst>
249 char* __default_alloc_template<__threads, __inst>::_S_end_free = 0;
250
251 template <bool __threads, int __inst>
252 size_t __default_alloc_template<__threads, __inst>::_S_heap_size = 0;
253
254
255 template <bool __threads, int __inst>
256 typename __default_alloc_template<__threads, __inst>::_Obj* __STL_VOLATILE __default_alloc_template<__threads, __inst> ::_S_free_list[
257 #if defined(__SUNPRO_CC) || defined(__GNUC__) || defined(__HP_aCC)
258 _NFREELISTS
259 #else
260 __default_alloc_template<__threads, __inst>::_NFREELISTS
261 #endif
262 ] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, };
263
264 #endif /* __USE_MALLOC */
265
266 //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
1 /////////////////////////////////////////////////////////////////////////////
2
3 //++标准内存适配器标准接口
4 #ifdef __STL_USE_STD_ALLOCATORS
5
6 template <class _Tp>
7 class allocator
8 {
9 typedef alloc _Alloc; //二级内存适配器
10 public:
11 typedef size_t size_type;
12 typedef ptrdiff_t difference_type;
13 typedef _Tp* pointer;
14 typedef const _Tp* const_pointer;
15 typedef _Tp& reference;
16 typedef const _Tp& const_reference;
17 typedef _Tp value_type;
18
19 template <class _Tp1>
20 structs rebind
21 {
22 typedef allocator<_Tp1> other;
23 };
24
25 allocator() __STL_NOTHROW {} //默认构造函数,__STL_NOTHROW在stl_config.h中定义,要么为空,要么为throw()异常
26 allocator(const allocator&) __STL_NOTHROW {} //复制构造函数
27 template <class _Tp1> allocator(const allocator<_Tp1>&) __STL_NOTHROW {} //泛化的复制构造函数
28 ~allocator() __STL_NOTHROW {} //析构函数
29
30 pointer address(reference __x) const { return &__x; } //返回对象的地址
31 const_pointer address(const_reference __x) const { return &__x; } //返回const对象的地址
32
33 _Tp* allocate(size_type __n, const void* = 0)
34 {
35 return __n != 0 ? static_cast<_Tp*>(_Alloc::allocate(__n * sizeof(_Tp))) : 0; //如果申请的空间块数不为0，那么调用二级内存适配器的allocate函数来分配内存
36 }
37
38 void deallocate(pointer __p, size_type __n) //释放内存
39 {
40 _Alloc::deallocate(__p, __n * sizeof(_Tp));
41 }
42
43 size_type max_size() const __STL_NOTHROW
44 {
45 return size_t(-1) / sizeof(_Tp); //size_t为unsigned类型，将-1强制转换为unsigned类型会得到unsiged类型的最大数,结果就是计算可分配_Tp类型的最大个数
46 }
47
48 /* 调用new与delete完成内存分配与释放*/
49 void construct(pointer __p, const _Tp& __val) { new(__p) _Tp(__val); }
50 void destroy(pointer __p) { __p->~_Tp(); }
51 };
52
53 //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////