BitMagic-C++
bmalloc.h
Go to the documentation of this file.
1 #ifndef BMALLOC__H__INCLUDED__
2 #define BMALLOC__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 /*! \file bmalloc.h
22  \brief Default SIMD friendly allocator
23 */
24 
25 #include <stdlib.h>
26 #include <new>
27 
28 namespace 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 {
59 public:
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 {
110 public:
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 {
139 public:
140  enum params
141  {
143  };
144 
145  pointer_pool_array() : pool_ptr_(0), size_(0)
146  {
147  allocate_pool(n_pool_max_size);
148  }
149 
150  pointer_pool_array(const pointer_pool_array&) = delete;
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  ///
172  void* pop() BMNOEXCEPT
173  {
174  if (!size_)
175  return 0;
176  return pool_ptr_[--size_];
177  }
178 private:
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  }
191 private:
192  void** pool_ptr_; ///< array of pointers in the pool
193  unsigned size_; ///< current size
194 };
195 
196 /**
197  Allocation pool object
198 */
199 template<class BA, class PA>
201 {
202 public:
204  typedef PA ptr_allocator_type;
205 
206 public:
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 
240 protected:
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 */
253 template<class BA, class PA, class APool>
255 {
256 public:
257 
259  typedef PA ptr_allocator_type;
260  typedef APool allocator_pool_type;
261 
262 public:
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  */
342  bm::gap_word_t* alloc_gap_block(unsigned level,
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  }
379 private:
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
395 inline
396 void* 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
423 inline
424 void aligned_free(void* ptr) BMNOEXCEPT
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
bm::ptr_allocator::deallocate
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::pointer_pool_array::pop
void * pop() BMNOEXCEPT
Get a pointer if there are any vacant.
Definition: bmalloc.h:172
bm::block_allocator::allocate
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
bm::mem_alloc::free_ptr
void free_ptr(void *p, size_t size) BMNOEXCEPT
Frees block of pointers.
Definition: bmalloc.h:374
bm::mem_alloc::allocator_pool_type
APool allocator_pool_type
Definition: bmalloc.h:260
bm::pointer_pool_array
Pool of pointers to buffer cyclic allocations.
Definition: bmalloc.h:137
bm::pointer_pool_array::operator=
pointer_pool_array & operator=(const pointer_pool_array &)=delete
bm::mem_alloc::set_pool
void set_pool(allocator_pool_type *pool) BMNOEXCEPT
set pointer to external pool
Definition: bmalloc.h:299
bm::ptr_allocator::allocate
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
bm::set_block_size
const unsigned set_block_size
Definition: bmconst.h:54
bm::pointer_pool_array::n_pool_max_size
Definition: bmalloc.h:142
bm::standard_alloc_pool
bm::alloc_pool< block_allocator, ptr_allocator > standard_alloc_pool
Definition: bmalloc.h:385
bm::alloc_pool::alloc_pool
alloc_pool()
Definition: bmalloc.h:208
bm::aligned_new_malloc
void * aligned_new_malloc(size_t size)
Aligned malloc (unlike classic malloc it throws bad_alloc exception)
Definition: bmalloc.h:396
bm::alloc_pool
Allocation pool object.
Definition: bmalloc.h:200
bm::gap_capacity
unsigned gap_capacity(const T *BMRESTRICT buf, const T *BMRESTRICT glevel_len) BMNOEXCEPT
Returs GAP block capacity.
Definition: bmfunc.h:1114
bm::mem_alloc::mem_alloc
mem_alloc(const mem_alloc &ma) BMNOEXCEPT
Definition: bmalloc.h:270
bm::alloc_pool::~alloc_pool
~alloc_pool()
Definition: bmalloc.h:209
bm::pointer_pool_array::~pointer_pool_array
~pointer_pool_array()
Definition: bmalloc.h:153
bm::pointer_pool_array::push
unsigned push(void *ptr) BMNOEXCEPT
Push pointer to the pool (if it is not full)
Definition: bmalloc.h:162
bm::mem_alloc::free_gap_block
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
bm::alloc_pool::alloc_bit_block
bm::word_t * alloc_bit_block()
Definition: bmalloc.h:214
bm::alloc_pool::ptr_allocator_type
PA ptr_allocator_type
Definition: bmalloc.h:204
bm::ptr_allocator
Default malloc based bitblock allocator class.
Definition: bmalloc.h:108
BM_ALLOC_ALIGN
#define BM_ALLOC_ALIGN
Definition: bmalloc.h:32
BMNOEXCEPT
#define BMNOEXCEPT
Definition: bmdef.h:79
bm::mem_alloc::ptr_allocator_type
PA ptr_allocator_type
Definition: bmalloc.h:259
bm::mem_alloc::get_block_allocator
block_allocator_type get_block_allocator() const BMNOEXCEPT
Returns copy of the block allocator object.
Definition: bmalloc.h:286
bm::gap_word_t
unsigned short gap_word_t
Definition: bmconst.h:77
BM_DEFAULT_POOL_SIZE
#define BM_DEFAULT_POOL_SIZE
Definition: bmconst.h:42
BM_ASSERT
#define BM_ASSERT
Definition: bmdef.h:130
bm::alloc_pool::block_alloc_
BA block_alloc_
Definition: bmalloc.h:242
bm::mem_alloc::get_ptr_allocator
ptr_allocator_type get_ptr_allocator() const BMNOEXCEPT
Returns copy of the ptr allocator object.
Definition: bmalloc.h:293
bm::alloc_pool::free_bit_block
void free_bit_block(bm::word_t *block) BMNOEXCEPT
Definition: bmalloc.h:222
bm::aligned_free
void aligned_free(void *ptr) BMNOEXCEPT
Aligned free.
Definition: bmalloc.h:424
bm::mem_alloc::alloc_bit_block
bm::word_t * alloc_bit_block(unsigned alloc_factor=1)
Allocates and returns bit block.
Definition: bmalloc.h:316
bm::mem_alloc::block_allocator_type
BA block_allocator_type
Definition: bmalloc.h:258
IS_VALID_ADDR
#define IS_VALID_ADDR(addr)
Definition: bmdef.h:152
bm::standard_allocator
bm::mem_alloc< block_allocator, ptr_allocator, standard_alloc_pool > standard_allocator
Definition: bmalloc.h:386
bm::alloc_pool::block_allocator_type
BA block_allocator_type
Definition: bmalloc.h:203
bm::pointer_pool_array::params
params
Definition: bmalloc.h:140
bm::alloc_pool::block_pool_
pointer_pool_array block_pool_
Definition: bmalloc.h:241
bm::mem_alloc::mem_alloc
mem_alloc(const BA &block_alloc=BA(), const PA &ptr_alloc=PA()) BMNOEXCEPT
Definition: bmalloc.h:264
bm::alloc_pool::free_pools
void free_pools() BMNOEXCEPT
Definition: bmalloc.h:229
bm::mem_alloc::operator=
mem_alloc & operator=(const mem_alloc &ma) BMNOEXCEPT
Definition: bmalloc.h:276
bm
Definition: bm.h:76
bm::mem_alloc::alloc_ptr
void * alloc_ptr(size_t size)
Allocates block of pointers.
Definition: bmalloc.h:366
bm::mem_alloc::alloc_gap_block
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
bm::word_t
unsigned int word_t
Definition: bmconst.h:38
bm::mem_alloc::free_bit_block
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
bm::mem_alloc::get_pool
allocator_pool_type * get_pool() BMNOEXCEPT
get pointer to allocation pool (if set)
Definition: bmalloc.h:305
bm::block_allocator::deallocate
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::block_allocator
Default malloc based bitblock allocator class.
Definition: bmalloc.h:57
bm::gap_levels
const unsigned gap_levels
Definition: bmconst.h:84
bm::mem_alloc
BM style allocator adapter.
Definition: bmalloc.h:254
bm::pointer_pool_array::pointer_pool_array
pointer_pool_array()
Definition: bmalloc.h:145