STL源码标注_空间适配器
2018-06-17 20:42:47来源：未知 阅读 ()
/* 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 //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
标签：
版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有
IDC资讯： 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营： 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程： Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术： Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧： 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作： FrontPages Dreamweaver Javascript css photoshop fireworks Flash
热门词条
最新资讯
热门关注
热门标签