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