STL的第二级配置器

2018/06/11 14:41
阅读数 13

本文不考虑异常处理情况。

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

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部