Debian Codegraph @

lang-maps/libbm/src/bmcalloc.h

raw
1 #ifndef BMCALLOC__H__INCLUDED__
2 #define BMCALLOC__H__INCLUDED__
3 /*
4 Copyright(c) 2002-2017 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)
5
6 Licensed under the Apache License, Version 2.0 (the "License");
7 you may not use this file except in compliance with the License.
8 You may obtain a copy of the License at
9
10 http://www.apache.org/licenses/LICENSE-2.0
11
12 Unless required by applicable law or agreed to in writing, software
13 distributed under the License is distributed on an "AS IS" BASIS,
14 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 See the License for the specific language governing permissions and
16 limitations under the License.
17
18 For more information please visit: http://bitmagic.io
19 */
20
21 #include <stdlib.h>
22 #include "try_throw_catch.h"
23
24 #include "bmfunc.h"
25
26 namespace libbm
27 {
28
29 #if defined(BMSSE2OPT) || defined(BMSSE42OPT)
30 #define BM_ALLOC_ALIGN 16
31 #endif
32 #if defined(BMAVX2OPT)
33 #define BM_ALLOC_ALIGN 32
34 #endif
35
36
37
38 class block_allocator
39 {
40 public:
41 static bm::word_t* allocate(size_t n, const void *)
42 {
43 bm::word_t* ptr;
44 #if defined(BM_ALLOC_ALIGN)
45 #ifdef _MSC_VER
46 ptr = (bm::word_t*) ::_aligned_malloc(n * sizeof(bm::word_t), BM_ALLOC_ALIGN);
47 #else
48 ptr = (bm::word_t*) ::_mm_malloc(n * sizeof(bm::word_t), BM_ALLOC_ALIGN);
49 #endif
50 #else
51 ptr = (bm::word_t*) ::malloc(n * sizeof(bm::word_t));
52 #endif
53 if (!ptr)
54 {
55 BM_THROW( BM_ERR_BADALLOC );
56 }
57 return ptr;
58 }
59
60 static void deallocate(bm::word_t* p, size_t)
61 {
62 #ifdef BM_ALLOC_ALIGN
63 # ifdef _MSC_VER
64 ::_aligned_free(p);
65 #else
66 ::_mm_free(p);
67 # endif
68 #else
69 ::free(p);
70 #endif
71 }
72
73 };
74
75 class ptr_allocator
76 {
77 public:
78 /**
79 The member function allocates storage for an array of n void*
80 elements, by calling malloc.
81 @return pointer to the allocated memory.
82 */
83 static void* allocate(size_t n, const void *)
84 {
85 void* ptr;
86 #if defined(BM_ALLOC_ALIGN)
87 #ifdef _MSC_VER
88 ptr = (bm::word_t*) ::_aligned_malloc(n * sizeof(void*), BM_ALLOC_ALIGN);
89 #else
90 ptr = (bm::word_t*) ::_mm_malloc(n * sizeof(void*), BM_ALLOC_ALIGN);
91 #endif
92 #else
93 ptr = (bm::word_t*) ::malloc(n * sizeof(void*));
94 #endif
95 // void* ptr = ::malloc(n * sizeof(void*));
96 if (!ptr)
97 {
98 BM_THROW( BM_ERR_BADALLOC );
99 }
100 return ptr;
101 }
102
103 /**
104 The member function frees storage for an array of n bm::word_t
105 elements, by calling free.
106 */
107 static void deallocate(void* p, size_t) BMNOEXCEPT
108 {
109 #ifdef BM_ALLOC_ALIGN
110 # ifdef _MSC_VER
111 ::_aligned_free(p);
112 #else
113 ::_mm_free(p);
114 # endif
115 #else
116 ::free(p);
117 #endif
118 }
119 };
120
121 /*!
122 @brief Pool of pointers to buffer cyclic allocations
123 */
124 class pointer_pool_array
125 {
126 public:
127 enum params
128 {
129 n_pool_max_size = BM_DEFAULT_POOL_SIZE
130 };
131
132 pointer_pool_array() : size_(0)
133 {
134 allocate_pool(n_pool_max_size);
135 }
136
137 pointer_pool_array(const pointer_pool_array&) = delete;
138 pointer_pool_array& operator=(const pointer_pool_array&) = delete;
139
140 ~pointer_pool_array()
141 {
142 BM_ASSERT(size_ == 0); // at destruction point should be empty (otherwise it is a leak)
143 free_pool();
144 }
145
146 /// Push pointer to the pool (if it is not full)
147 ///
148 /// @return 0 if pointer is not accepted (pool is full)
149 unsigned push(void* ptr)
150 {
151 if (size_ == n_pool_max_size - 1)
152 return 0;
153 pool_ptr_[size_++] = ptr;
154 return size_;
155 }
156
157 /// Get a pointer if there are any vacant
158 ///
159 void* pop()
160 {
161 if (size_ == 0)
162 return 0;
163 return pool_ptr_[--size_];
164 }
165 private:
166 void allocate_pool(size_t pool_size)
167 {
168 pool_ptr_ = (void**)::malloc(sizeof(void*) * pool_size);
169 if (!pool_ptr_)
170 BM_THROW(BM_ERR_BADALLOC);
171 }
172
173 void free_pool()
174 {
175 ::free(pool_ptr_);
176 }
177 private:
178 void** pool_ptr_; ///< array of pointers in the pool
179 unsigned size_; ///< current size
180 };
181
182 /**
183 Allocation pool object
184 */
185 template<class BA, class PA>
186 class alloc_pool
187 {
188 public:
189 typedef BA block_allocator_type;
190 typedef PA ptr_allocator_type;
191
192 public:
193
194 alloc_pool() {}
195 ~alloc_pool()
196 {
197 free_pools();
198 }
199
200 bm::word_t* alloc_bit_block()
201 {
202 bm::word_t* ptr = (bm::word_t*)block_pool_.pop();
203 if (ptr == 0)
204 ptr = block_alloc_.allocate(bm::set_block_size, 0);
205 return ptr;
206 }
207
208 void free_bit_block(bm::word_t* block)
209 {
210 BM_ASSERT(IS_VALID_ADDR(block));
211 if (!block_pool_.push(block))
212 {
213 block_alloc_.deallocate(block, bm::set_block_size);
214 }
215 }
216
217 void free_pools()
218 {
219 bm::word_t* block;
220 do
221 {
222 block = (bm::word_t*)block_pool_.pop();
223 if (block)
224 block_alloc_.deallocate(block, bm::set_block_size);
225 } while (block);
226 }
227
228 protected:
229 pointer_pool_array block_pool_;
230 BA block_alloc_;
231 };
232
233
234
235 /*! @brief BM style allocator adapter.
236
237 Template takes parameters:
238 BA - allocator object for bit blocks
239 PA - allocator object for pointer blocks
240 APool - Allocation pool
241 */
242 template<class BA, class PA, class APool>
243 class mem_alloc
244 {
245 public:
246
247 typedef BA block_allocator_type;
248 typedef PA ptr_allocator_type;
249 typedef APool allocator_pool_type;
250
251 public:
252
253 mem_alloc(const BA& block_alloc = BA(), const PA& ptr_alloc = PA())
254 : block_alloc_(block_alloc),
255 ptr_alloc_(ptr_alloc),
256 alloc_pool_p_(0)
257 {}
258
259 mem_alloc(const mem_alloc& ma)
260 : block_alloc_(ma.block_alloc_),
261 ptr_alloc_(ma.ptr_alloc_),
262 alloc_pool_p_(0) // do not inherit pool (has to be explicitly defined)
263 {}
264
265 mem_alloc& operator=(const mem_alloc& ma)
266 {
267 block_alloc_ = ma.block_alloc_;
268 ptr_alloc_ = ma.ptr_alloc_;
269 // alloc_pool_p_ - do not inherit pool (has to be explicitly defined)
270 return *this;
271 }
272
273 /*! @brief Returns copy of the block allocator object
274 */
275 block_allocator_type get_block_allocator() const
276 {
277 return BA(block_alloc_);
278 }
279
280 /*! @brief Returns copy of the ptr allocator object
281 */
282 ptr_allocator_type get_ptr_allocator() const
283 {
284 return PA(block_alloc_);
285 }
286
287 /*! @brief set pointer to external pool */
288 void set_pool(allocator_pool_type* pool) BMNOEXCEPT
289 {
290 alloc_pool_p_ = pool;
291 }
292
293 /*! @brief get pointer to allocation pool (if set) */
294 allocator_pool_type* get_pool() BMNOEXCEPT
295 {
296 return alloc_pool_p_;
297 }
298
299 /*! @brief Allocates and returns bit block.
300 @param alloc_factor
301 indicated how many blocks we want to allocate in chunk
302 total allocation is going to be bm::set_block_size * alloc_factor
303 Default allocation factor is 1
304 */
305 bm::word_t* alloc_bit_block(unsigned alloc_factor = 1)
306 {
307 if (alloc_pool_p_ && alloc_factor == 1)
308 return alloc_pool_p_->alloc_bit_block();
309 return block_alloc_.allocate(bm::set_block_size * alloc_factor, 0);
310 }
311
312 /*! @brief Frees bit block allocated by alloc_bit_block.
313 */
314 void free_bit_block(bm::word_t* block, unsigned alloc_factor = 1) BMNOEXCEPT
315 {
316 BM_ASSERT(IS_VALID_ADDR(block));
317 if (alloc_pool_p_ && alloc_factor == 1)
318 alloc_pool_p_->free_bit_block(block);
319 else
320 block_alloc_.deallocate(block, bm::set_block_size * alloc_factor);
321 }
322
323 /*! @brief Allocates GAP block using bit block allocator (BA).
324
325 GAP blocks in BM library belong to levels. Each level has a
326 correspondent length described in bm::gap_len_table<>
327
328 @param level GAP block level.
329 @param glevel_len table of level lengths
330 */
331 bm::gap_word_t* alloc_gap_block(unsigned level,
332 const bm::gap_word_t* glevel_len)
333 {
334 BM_ASSERT(level < bm::gap_levels);
335 unsigned len =
336 (unsigned)(glevel_len[level] / (sizeof(bm::word_t) / sizeof(bm::gap_word_t)));
337
338 return (bm::gap_word_t*)block_alloc_.allocate(len, 0);
339 }
340
341 /*! @brief Frees GAP block using bot block allocator (BA)
342 */
343 void free_gap_block(bm::gap_word_t* block,
344 const bm::gap_word_t* glevel_len)
345 {
346 BM_ASSERT(IS_VALID_ADDR((bm::word_t*)block));
347
348 unsigned len = bm::gap_capacity(block, glevel_len);
349 len /= (unsigned)(sizeof(bm::word_t) / sizeof(bm::gap_word_t));
350 block_alloc_.deallocate((bm::word_t*)block, len);
351 }
352
353 /*! @brief Allocates block of pointers.
354 */
355 void* alloc_ptr(unsigned size)
356 {
357 return ptr_alloc_.allocate(size, 0);
358 }
359
360 /*! @brief Frees block of pointers.
361 */
362 void free_ptr(void* p, unsigned size) BMNOEXCEPT
363 {
364 if (p)
365 ptr_alloc_.deallocate(p, size);
366 }
367
368 /**
369 Get access to block allocator
370 */
371 BA& get_block_alloc() BMNOEXCEPT { return block_alloc_; }
372
373 public:
374 BA block_alloc_;
375 PA ptr_alloc_;
376 allocator_pool_type* alloc_pool_p_;
377 };
378
379
380 //typedef mem_alloc<block_allocator, ptr_allocator> standard_allocator;
381
382 typedef libbm::alloc_pool<block_allocator, ptr_allocator> standard_alloc_pool;
383 typedef libbm::mem_alloc<block_allocator, ptr_allocator, standard_alloc_pool> standard_allocator;
384
385
386 /// Aligned malloc (unlike classic malloc it throws bad_alloc exception)
387 ///
388 /// @internal
389 inline
390 void* aligned_new_malloc(size_t size)
391 {
392 void* ptr;
393
394 #ifdef BM_ALLOC_ALIGN
395 #ifdef _MSC_VER
396 ptr = ::_aligned_malloc(size, BM_ALLOC_ALIGN);
397 #else
398 ptr = ::_mm_malloc(size, BM_ALLOC_ALIGN);
399 #endif
400 #else
401 ptr = ::malloc(size);
402 #endif
403 if (!ptr)
404 {
405 #ifndef BM_NO_STL
406 throw std::bad_alloc();
407 #else
408 BM_THROW(BM_ERR_BADALLOC);
409 #endif
410 }
411 return ptr;
412 }
413
414 /// Aligned free (safe to pass NULL ptr)
415 ///
416 /// @internal
417 inline
418 void aligned_free(void* ptr)
419 {
420 if (!ptr)
421 return;
422 #ifdef BM_ALLOC_ALIGN
423 # ifdef _MSC_VER
424 ::_aligned_free(ptr);
425 #else
426 ::_mm_free(ptr);
427 # endif
428 #else
429 ::free(ptr);
430 #endif
431 }
432
433
434 } // namespace libbm
435
436
437 #endif