1 #ifndef _STL_ALLOC_H_
2 #define _STL_ALLOC_H_
3
4 #include <cstddef>//for size_t, nullptr_t
5 #include <cstdlib>//for exit（）， malloc（）， free（）
6
7 namespace zstd
8 {
9 /*
10 **this is the _malloc_alloc class
11 */
12 class _malloc_alloc
13 {
14 public:
15 //分配size字节的内存空间
16 inline static void* allocate（size_t bytes）；
17 //回收ptr指向的内存空间
18 inline static void deallocate（void *ptr, size_t）；
19 };
20 void* _malloc_alloc::allocate（size_t bytes）
21 {
22 void *result = nullptr;
23
24 result = （void*）malloc（bytes）；
25 if （！result）
26 exit（-1）；
27 else
28 return result;
29 }
30 void _malloc_alloc::deallocate（void *ptr, size_t）
31 {
32 free（ptr）；
33 }
34 /*
35 **this is the _default_alloc class
36 */
37 class _default_alloc
38 {
39 private:
40 //小型区块的上调边界
41 static const int ALIGN = 8;
42 //小型区块的上限
43 static const int MAX_BYTES = 128;
44 //free-lists个数
45 static const int FREELIST_NUMS = MAX_BYTES / ALIGN;
46 //free-lists的节点构造
47 union node
48 {
49 union node *free_list_link;
50 char client_data ;
51 };
52
53 static node *free_list[FREELIST_NUMS];
54 //内存池起始的位置
55 static char *start_of_memorypool;
56 //内存池结束的位置
57 static char *end_of_memorypool;
58 //每次向内存池中注水时的水量修正值
59 static int heap_size;
60 private:
61 //将bytes上调至ALIGN的倍数
62 static size_t ROUND_UP（size_t bytes）
63 {
64 return （bytes + （ALIGN - 1）） & ~（ALIGN - 1）；
65 }
66 //根据bytes大小决定使用第几个free-list,从0开始算起
67 static size_t FREELIST_INDEX（size_t bytes）
68 {
69 //return ROUND_UP（bytes） / ALIGN - 1;
70 return （（bytes）+ALIGN - 1） / ALIGN - 1;
71 }
72 //返回一个大小为bytes的对象，并可能加入大小为n的其他区块到free list
73 static void *refill（size_t bytes）；
74 //配置一大块空间，可容纳nobjs个大小为bytes的区块
75 //如果配置nobjs个区块有所不便，nobjs可能降低
76 static char *chunk_alloc（size_t bytes, int &nobjs）；
77 public:
78 //分配size字节的内存空间
79 static void* allocate（size_t bytes）；
80 //回收ptr指向的内存空间
81 static void deallocate（void *ptr, size_t n）；
82 };
83 _default_alloc::node *_default_alloc::free_list[FREELIST_NUMS] =
84 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, };
85 char *_default_alloc::start_of_memorypool = nullptr;
86 char *_default_alloc::end_of_memorypool = nullptr;
87 int _default_alloc::heap_size = 0;
88
89 void *_default_alloc::allocate（size_t bytes）
90 {
91 node *result = nullptr;
92 node **my_free_list = nullptr;
93
94 if （bytes > （size_t）MAX_BYTES）
95 return _malloc_alloc::allocate（bytes）；
96
97 my_free_list = free_list + FREELIST_INDEX（bytes）；
98 if（！*my_free_list）
99 {
100 void *r = refill（ROUND_UP（bytes））；
101 return r;
102 }
103 else
104 result = *my_free_list;
105 *my_free_list = result->free_list_link;
106 return result;
107 }
108 void _default_alloc::deallocate（void *ptr, size_t n）
109 {
110 node *q = （node*）ptr;
111 node **my_free_list = nullptr;
112
113 if（n > （size_t）MAX_BYTES）
114 return _malloc_alloc::deallocate（ptr, n）；
115
116 my_free_list = free_list + FREELIST_INDEX（n）；
117 q->free_list_link = *my_free_list;
118 *my_free_list = q;
119 }
121 {
122 int nobjs = 20;
123
124 char *chunk = chunk_alloc（bytes, nobjs）；
125 node **my_free_list = nullptr;
126 node *result = nullptr;
127 node *cur, *next;
128
129 if（1 == nobjs）
130 return chunk;
131 result = （node*）chunk;
132 my_free_list = free_list + FREELIST_INDEX（bytes）；
133 next = *my_free_list = （node*）（chunk + bytes）；
134
135 for（int i = 1; ;++i）
136 {
137 cur = next;
138 next = （node*）（（char*）next + bytes）；
139 if（nobjs - 1 == i）
140 {
141 cur->free_list_link = nullptr;
142 break;
143 }
144 else
145 cur->free_list_link = next;
146 }
147 return result;
148 }
149 char *_default_alloc::chunk_alloc（size_t bytes, int &nobjs）
150 {
151 char *result = nullptr;
152 size_t total_bytes = bytes * nobjs;
153 size_t bytes_left = end_of_memorypool - start_of_memorypool;
154
155 if（bytes_left >= total_bytes）
156 {
157 result = start_of_memorypool;
158 start_of_memorypool += total_bytes;
159 return result;
160 }
161 else if （bytes_left >= bytes）
162 {
163 nobjs = bytes_left / bytes;
164 total_bytes = bytes * nobjs;
165 result = start_of_memorypool;
166 start_of_memorypool += total_bytes;
167 return result;
168 }
169 else
170 {
171 size_t bytes_to_get = 2 * total_bytes + ROUND_UP（heap_size 》 4）；
172 if（bytes_left > 0）
173 {
174 node **my_free_list = free_list + FREELIST_INDEX（bytes_left）；
175 （（node*）start_of_memorypool）->free_list_link = *my_free_list;
176 *my_free_list = （node*）start_of_memorypool;
177 }
178 start_of_memorypool = （char*）malloc（bytes_to_get）；
179 if（nullptr == start_of_memorypool）
180 {
181 node **my_free_list, *p;
182 for （int i = bytes; i <= MAX_BYTES; i += ALIGN）
183 {
184 my_free_list = free_list + FREELIST_INDEX（i）；
185 p = *my_free_list;
186 if（nullptr != p）
187 {
188 *my_free_list = p->free_list_link;
189 start_of_memorypool = （char*）p;
190 end_of_memorypool = start_of_memorypool + i;
191 return chunk_alloc（bytes, nobjs）；
192 }
193 }
194 end_of_memorypool = nullptr;
195 start_of_memorypool = （char*）_malloc_alloc::allocate（bytes_to_get）；
196 }
197 heap_size += bytes_to_get;
198 end_of_memorypool = start_of_memorypool + bytes_to_get;
199 return chunk_alloc（bytes, nobjs）；
200 }
201 }
202
203 #ifdef _USE_MALLOC_ALLOC_
204 typedef _malloc_alloc malloc_alloc;
205 typedef malloc_alloc alloc;
206 #else
207 typedef _default_alloc default_alloc;
208 typedef default_alloc alloc;
209 #endif
210
211
212 template<class T, class Alloc>
213 class simple_alloc
214 {
215 public:
216 //分配能容纳n个T对象的内存空间
217 static T *allocate（size_t n）
218 {
219 return 0 == n 0 : （T*）Alloc::allocate（n * sizeof（T））；
220 }
221 //分配能容纳1个T对象的内存空间
222 static T *allocate（）
223 {
224 return （T*）Alloc::allocate（sizeof（T））；
225 }
226 static void deallocate（T *ptr, size_t n）
227 {
228 if （0 != n）
229 Alloc::deallocate（ptr, n * sizeof（T））；
230 }
231 static void deallocate（T *ptr）
232 {
233 Alloc::deallocate（ptr, sizeof（T））；
234 }
235 };
236 }//end of namespace
237
238 #endif