sgistl2.91.57 之内存池

　　代码还是比较简单的，加个main函数多调试几次，自然就知道是什么意思了。

　　重点在于chunk_alloc这个函数里面的递归调用。

C++语言: Codee#25985

001 /*
002 简言之，一个链表数组加一个内存池
003 先在数组中找，找不到就向内存池要，如果池子空了，再向系统申请
004 */
005
006 #include <cstdlib>
007 #include <iostream>
008 using namespace std;
009
010 enum
011 {
012     __ALIGN = 8
013 };
014
015 enum
016 {
017     __MAX_BYTES = 128
018 };
019
020 enum
021 {
022     __NFREELISTS = __MAX_BYTES / __ALIGN
023 };
024
025 template <bool threads, int inst>
026 class __default_alloc_template
027 {
028 private:
029     static size_t ROUND_UP(size_t bytes)
030     {
031         return (((bytes) + __ALIGN - 1) & ~(__ALIGN - 1));
032     }
033
034     union obj
035     {
036         union obj* free_list_link;
037         char client_data[1];
038     };
039
040     /*
041        链表数组
042        */
043     static obj* volatile free_list[__NFREELISTS];
044
045     static size_t FREELIST_INDEX(size_t bytes)
046     {
047         return (((bytes) + __ALIGN - 1) / __ALIGN - 1);
048     }
049
050     static void* refill(size_t n);
051     static char* chunk_alloc(size_t size, int& nobjs);
052
053
054     static char* start_free;    //内存池起始地址
055     static char* end_free;        //内存池结束地址
056     static size_t heap_size;    //堆大小（到目前为止总共向系统申请的内存）
057
058 public:
059     void special_access(size_t sz, int n)
060     {
061         chunk_alloc(sz, n);
062     }
063
064     static void* allocate(size_t n)
065     {
066         obj* volatile* my_free_list;
067         obj* result;
068
069         if (n > (size_t) __MAX_BYTES)
070     /*
071             return malloc_alloc::allocate(n);
072     */
073             return malloc((size_t)n);
074
075         my_free_list = free_list + FREELIST_INDEX(n);
076         result = *my_free_list;
077         /*
078            数组中对应项为空表
079            */
080         if (0 == result)
081         {
082             /*
083                申请内存，并填充对应表项
084                */
085             void* r = refill(ROUND_UP(n));
086             return r;
087         }
088
089         /*
090            修改表项值
091            */
092         *my_free_list = result->free_list_link;
093         return result;
094     }
095
096     static void deallocate(void* p, size_t n)
097     {
098         obj* q = (obj*)p;
099         obj* volatile* my_free_list;
100
101         if (n > (size_t) __MAX_BYTES)
102         {
103     /*
104             malloc_alloc::deallocate(p, n);
105     */
106             free(p);
107             return ;
108         }
109
110         /*
111            归还内存，插入对应链表表头处
112            */
113
114         my_free_list = free_list + FREELIST_INDEX(n);
115         q->free_list_link = *my_free_list;
116         *my_free_list = q;
117     }
118
119     static void* reallocate(void* p, size_t old_sz, size_t new_sz);
120 };
121
122 template <bool threads, int inst>
123 char* __default_alloc_template<threads, inst>::start_free = 0;
124
125 template <bool threads, int inst>
126 char* __default_alloc_template<threads, inst>::end_free = 0;
127
128 template <bool threads, int inst>
129 size_t __default_alloc_template<threads, inst>::heap_size = 0;
130
131 /*
132    sgi-stl-2.91.57中原来的代码，现无法通过编译
133    注意此处的typename 具体解释见此处：
134    http://stackoverflow.com/questions/610245/
135    where-and-why-do-i-have-to-put-the-template-and-typename-keywords
136    */
137 template <bool threads, int inst>
138 typename __default_alloc_template<threads,inst>::obj* volatile
139 __default_alloc_template<threads, inst>::free_list[__NFREELISTS] =
140 {
141     0, 0, 0, 0,
142     0, 0, 0, 0,
143     0, 0, 0, 0,
144     0, 0, 0, 0
145 };
146
147 template <bool threads, int inst>
148 void* __default_alloc_template<threads, inst>::refill(size_t n)
149 {
150     int nobjs = 20;
151     /*
152        申请内存块
153        */
154     char* chunk = chunk_alloc(n, nobjs);
155     obj* volatile* my_free_list;
156     obj* result;
157     obj* current_obj, *next_obj;
158     int i;
159
160     if (1 == nobjs)
161         return chunk;
162     my_free_list = free_list + FREELIST_INDEX(n);
163     result = (obj*)chunk;                            //第一块拿来用
164     *my_free_list = next_obj = (obj*)(chunk + n);    //剩下的插入到对应大小的链表中
165
166     /*
167        建立链表，还是头插法
168        */
169     for (i = 1;; ++i)
170     {
171         current_obj = next_obj;
172         next_obj = (obj*)((char*)next_obj + n);
173         if (i == nobjs - 1)
174         {
175             current_obj->free_list_link = 0;
176             break;
177         }
178         else
179             current_obj->free_list_link = next_obj;
180     }
181     return result;
182 }
183
184 /*
185 */
186 template<bool threads, int inst>
187 char* __default_alloc_template<threads, inst>
188 ::chunk_alloc(size_t size, int& nobjs)
189 {
190     /*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
191     char*    result;
192     size_t total_bytes = size * nobjs;
193     size_t bytes_left = end_free - start_free;
194     /*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
195
196     if (bytes_left >= total_bytes)
197     {
198         result = start_free;
199         start_free += total_bytes;
200         return(result);
201     }
202     else if (bytes_left >= size)
203     {
204         /*
205            nobjs引用传参
206            为的就是内存只够1块以上又不够20块分配，
207            在此处修改为实际上分配到的块数
208            */
209
210         nobjs = bytes_left / size;
211         total_bytes = size * nobjs;
212         result = start_free;
213         start_free += total_bytes;
214         return(result);
215     }
216     else
217     {
218         /*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
219         size_t bytes_to_get = 2 * total_bytes + ROUND_UP (heap_size >> 4);
220         /*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
221
222         /*
223          * Try to make use of the
224          * left-over piece.
225          */
226         if (bytes_left > 0)
227         {
228             obj* volatile* my_free_list = free_list + FREELIST_INDEX (bytes_left);
229             ((obj*) start_free)->free_list_link = *my_free_list;
230             *my_free_list = (obj*) start_free;
231         }
232
233         start_free = (char*) malloc (bytes_to_get);
234         if (0 == start_free)
235         {
236             /*~~*/
237             int i;
238             /*~~*/
239
240             obj* volatile* my_free_list, *p;
241
242             /*
243              * Try to make do with
244              * what we have. That
245              * can't ;
246              * hurt. We do not try
247              * smaller requests,
248              * since that tends ;
249              * to result in disaster
250              * on multi-process
251              * machines.
252              */
253             /*
254                申请不到内存，只好在原来的链表中找找看
255                有一点就用一点
256                */
257             for (i = size; i <= __MAX_BYTES; i += __ALIGN)
258             {
259                 my_free_list = free_list + FREELIST_INDEX (i);
260                 p = *my_free_list;
261                 if (0 != p)
262                 {
263                     *my_free_list = p->free_list_link;
264                     start_free = (char*) p;
265                     end_free = start_free + i;
266                     return(chunk_alloc (size, nobjs));
267
268                     /*
269                      * Any leftover
270                      * piece will
271                      * eventually
272                      * make it to the ;
273                      * right free
274                      * list.
275                      */
276                 }
277             }
278
279             end_free = 0;    /* In case of exception. */
280             start_free = (char*) malloc(bytes_to_get);
281
282             /*
283              * This should either
284              * throw an ;
285              * exception or remedy
286              * the situation. Thus we
287              * assume it ;
288              * succeeded.
289              */
290         }
291
292         heap_size += bytes_to_get;
293         end_free = start_free + bytes_to_get;
294         return(chunk_alloc (size, nobjs));
295     }
296 }
297
298 int main()
299 {
300     /*
301     *    just test,debug to see how it works
302     */
303     __default_alloc_template<false, 1> my_alloc;
304
305     for (int i = 0; i < 1024; ++i)
306     {
307         int x = rand() % 128+1;
308         my_alloc.allocate(x);
309     }
310
311     return 0;
312 }