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 
79  if (!ptr)
80  {
81  throw std::bad_alloc();
82  }
83  return ptr;
84  }
85 
86  /**
87  The member function frees storage for an array of n bm::word_t
88  elements, by calling free.
89  */
90  static void deallocate(bm::word_t* p, size_t)
91  {
92 #ifdef BM_ALLOC_ALIGN
93  # ifdef _MSC_VER
94  ::_aligned_free(p);
95  #else
96  ::_mm_free(p);
97  # endif
98 #else
99  ::free(p);
100 #endif
101  }
102 
103 };
104 
105 
106 
107 /*! @brief Default malloc based bitblock allocator class.
108 
109  Functions allocate and deallocate conform to STL allocator specs.
110 */
112 {
113 public:
114  /**
115  The member function allocates storage for an array of n void*
116  elements, by calling malloc.
117  @return pointer to the allocated memory.
118  */
119  static void* allocate(size_t n, const void *)
120  {
121  void* ptr = ::malloc(n * sizeof(void*));
122  if (!ptr)
123  {
124  throw std::bad_alloc();
125  }
126  return ptr;
127  }
128 
129  /**
130  The member function frees storage for an array of n bm::word_t
131  elements, by calling free.
132  */
133  static void deallocate(void* p, size_t)
134  {
135  ::free(p);
136  }
137 };
138 
139 /*!
140  @brief Pool of pointers to buffer cyclic allocations
141 */
143 {
144 public:
145  enum params
146  {
147  n_pool_max_size = BM_DEFAULT_POOL_SIZE
148  };
149 
150  pointer_pool_array() : size_(0)
151  {
152  allocate_pool(n_pool_max_size);
153  }
154 
155  pointer_pool_array(const pointer_pool_array&) = delete;
156  pointer_pool_array& operator=(const pointer_pool_array&) = delete;
157 
159  {
160  BM_ASSERT(size_ == 0); // at destruction point should be empty (otherwise it is a leak)
161  free_pool();
162  }
163 
164  /// Push pointer to the pool (if it is not full)
165  ///
166  /// @return 0 if pointer is not accepted (pool is full)
167  unsigned push(void* ptr)
168  {
169  if (size_ == n_pool_max_size - 1)
170  return 0;
171  pool_ptr_[size_++] = ptr;
172  return size_;
173  }
174 
175  /// Get a pointer if there are any vacant
176  ///
177  void* pop()
178  {
179  if (size_ == 0)
180  return 0;
181  return pool_ptr_[--size_];
182  }
183 private:
184  void allocate_pool(size_t pool_size)
185  {
186  pool_ptr_ = (void**)::malloc(sizeof(void*) * pool_size);
187  if (!pool_ptr_)
188  throw std::bad_alloc();
189  }
190 
191  void free_pool()
192  {
193  ::free(pool_ptr_);
194  }
195 private:
196  void** pool_ptr_; ///< array of pointers in the pool
197  unsigned size_; ///< current size
198 };
199 
200 /**
201  Allocation pool object
202 */
203 template<class BA, class PA>
205 {
206 public:
208  typedef PA ptr_allocator_type;
209 
210 public:
211 
214  {
215  free_pools();
216  }
217 
219  {
220  bm::word_t* ptr = (bm::word_t*)block_pool_.pop();
221  if (ptr == 0)
222  ptr = block_alloc_.allocate(bm::set_block_size, 0);
223  return ptr;
224  }
225 
227  {
228  BM_ASSERT(IS_VALID_ADDR(block));
229  if (!block_pool_.push(block))
230  {
231  block_alloc_.deallocate(block, bm::set_block_size);
232  }
233  }
234 
235  void free_pools()
236  {
237  bm::word_t* block;
238  do
239  {
240  block = (bm::word_t*)block_pool_.pop();
241  if (block)
242  block_alloc_.deallocate(block, bm::set_block_size);
243  } while (block);
244  }
245 
246 protected:
249 };
250 
251 
252 /*! @brief BM style allocator adapter.
253 
254  Template takes parameters:
255  BA - allocator object for bit blocks
256  PA - allocator object for pointer blocks
257  APool - Allocation pool
258 */
259 template<class BA, class PA, class APool>
261 {
262 public:
263 
265  typedef PA ptr_allocator_type;
266  typedef APool allocator_pool_type;
267 
268 public:
269 
270  mem_alloc(const BA& block_alloc = BA(), const PA& ptr_alloc = PA())
271  : block_alloc_(block_alloc),
272  ptr_alloc_(ptr_alloc),
273  alloc_pool_p_(0)
274  {}
275 
276  mem_alloc(const mem_alloc& ma)
277  : block_alloc_(ma.block_alloc_),
278  ptr_alloc_(ma.ptr_alloc_),
279  alloc_pool_p_(0) // do not inherit pool (has to be explicitly defined)
280  {}
281 
283  {
284  block_alloc_ = ma.block_alloc_;
285  ptr_alloc_ = ma.ptr_alloc_;
286  // alloc_pool_p_ - do not inherit pool (has to be explicitly defined)
287  return *this;
288  }
289 
290  /*! @brief Returns copy of the block allocator object
291  */
292  block_allocator_type get_block_allocator() const
293  {
294  return BA(block_alloc_);
295  }
296 
297  /*! @brief Returns copy of the ptr allocator object
298  */
299  ptr_allocator_type get_ptr_allocator() const
300  {
301  return PA(block_alloc_);
302  }
303 
304  /*! @brief set pointer to external pool */
305  void set_pool(allocator_pool_type* pool)
306  {
307  alloc_pool_p_ = pool;
308  }
309 
310  /*! @brief get pointer to allocation pool (if set) */
311  allocator_pool_type* get_pool()
312  {
313  return alloc_pool_p_;
314  }
315 
316  /*! @brief Allocates and returns bit block.
317  @param alloc_factor
318  indicated how many blocks we want to allocate in chunk
319  total allocation is going to be bm::set_block_size * alloc_factor
320  Default allocation factor is 1
321  */
322  bm::word_t* alloc_bit_block(unsigned alloc_factor = 1)
323  {
324  if (alloc_pool_p_ && alloc_factor == 1)
325  return alloc_pool_p_->alloc_bit_block();
326  return block_alloc_.allocate(bm::set_block_size * alloc_factor, 0);
327  }
328 
329  /*! @brief Frees bit block allocated by alloc_bit_block.
330  */
331  void free_bit_block(bm::word_t* block, unsigned alloc_factor = 1)
332  {
333  BM_ASSERT(IS_VALID_ADDR(block));
334  if (alloc_pool_p_ && alloc_factor == 1)
335  alloc_pool_p_->free_bit_block(block);
336  else
337  block_alloc_.deallocate(block, bm::set_block_size * alloc_factor);
338  }
339 
340  /*! @brief Allocates GAP block using bit block allocator (BA).
341 
342  GAP blocks in BM library belong to levels. Each level has a
343  correspondent length described in bm::gap_len_table<>
344 
345  @param level GAP block level.
346  @param glevel_len table of level lengths
347  */
348  bm::gap_word_t* alloc_gap_block(unsigned level,
349  const bm::gap_word_t* glevel_len)
350  {
351  BM_ASSERT(level < bm::gap_levels);
352  unsigned len =
353  (unsigned)(glevel_len[level] / (sizeof(bm::word_t) / sizeof(bm::gap_word_t)));
354 
355  return (bm::gap_word_t*)block_alloc_.allocate(len, 0);
356  }
357 
358  /*! @brief Frees GAP block using bot block allocator (BA)
359  */
361  const bm::gap_word_t* glevel_len)
362  {
364 
365  unsigned len = bm::gap_capacity(block, glevel_len);
366  len /= (unsigned)(sizeof(bm::word_t) / sizeof(bm::gap_word_t));
367  block_alloc_.deallocate((bm::word_t*)block, len);
368  }
369 
370  /*! @brief Allocates block of pointers.
371  */
372  void* alloc_ptr(size_t size)
373  {
374  return ptr_alloc_.allocate(size, 0);
375  }
376 
377  /*! @brief Frees block of pointers.
378  */
379  void free_ptr(void* p, size_t size)
380  {
381  if (p)
382  ptr_alloc_.deallocate(p, size);
383  }
384 private:
385  BA block_alloc_;
386  PA ptr_alloc_;
387  allocator_pool_type* alloc_pool_p_;
388 };
389 
392 
393 /** @} */
394 
395 
396 /// Aligned malloc (unlike classic malloc it throws bad_alloc exception)
397 ///
398 /// To allocate temp bit-block use: bm::aligned_new_malloc(bm::set_block_alloc_size);
399 /// @internal
400 inline
401 void* aligned_new_malloc(size_t size)
402 {
403  void* ptr;
404 
405 #ifdef BM_ALLOC_ALIGN
406 #ifdef _MSC_VER
407  ptr = ::_aligned_malloc(size, BM_ALLOC_ALIGN);
408 #else
409  ptr = ::_mm_malloc(size, BM_ALLOC_ALIGN);
410 #endif
411 #else
412  ptr = ::malloc(size);
413 #endif
414  if (!ptr)
415  {
416 #ifndef BM_NO_STL
417  throw std::bad_alloc();
418 #else
419  BM_THROW(BM_ERR_BADALLOC);
420 #endif
421  }
422  return ptr;
423 }
424 
425 /// Aligned free
426 ///
427 /// @internal
428 inline
429 void aligned_free(void* ptr)
430 {
431  if (!ptr)
432  return;
433 #ifdef BM_ALLOC_ALIGN
434 # ifdef _MSC_VER
435  ::_aligned_free(ptr);
436 #else
437  ::_mm_free(ptr);
438 # endif
439 #else
440  ::free(ptr);
441 #endif
442 }
443 
444 
445 
446 #undef BM_ALLOC_ALIGN
447 
448 } // namespace bm
449 
450 
451 #endif
unsigned gap_capacity(const T *buf, const T *glevel_len)
Returs GAP block capacity.
Definition: bmfunc.h:1082
bm::word_t * alloc_bit_block()
Definition: bmalloc.h:218
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:348
const unsigned set_block_size
Definition: bmconst.h:54
block_allocator_type get_block_allocator() const
Returns copy of the block allocator object.
Definition: bmalloc.h:292
APool allocator_pool_type
Definition: bmalloc.h:266
pointer_pool_array block_pool_
Definition: bmalloc.h:247
void free_bit_block(bm::word_t *block, unsigned alloc_factor=1)
Frees bit block allocated by alloc_bit_block.
Definition: bmalloc.h:331
mem_alloc(const mem_alloc &ma)
Definition: bmalloc.h:276
#define IS_VALID_ADDR(addr)
Definition: bmdef.h:139
void * pop()
Get a pointer if there are any vacant.
Definition: bmalloc.h:177
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:119
void * aligned_new_malloc(size_t size)
Aligned malloc (unlike classic malloc it throws bad_alloc exception)
Definition: bmalloc.h:401
unsigned push(void *ptr)
Push pointer to the pool (if it is not full)
Definition: bmalloc.h:167
BM style allocator adapter.
Definition: bmalloc.h:260
Definition: bm.h:76
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:360
bm::alloc_pool< block_allocator, ptr_allocator > standard_alloc_pool
Definition: bmalloc.h:390
#define BM_ALLOC_ALIGN
Definition: bmalloc.h:32
void free_pools()
Definition: bmalloc.h:235
static void deallocate(void *p, size_t)
The member function frees storage for an array of n bm::word_t elements, by calling free...
Definition: bmalloc.h:133
mem_alloc & operator=(const mem_alloc &ma)
Definition: bmalloc.h:282
void * alloc_ptr(size_t size)
Allocates block of pointers.
Definition: bmalloc.h:372
void aligned_free(void *ptr)
Aligned free.
Definition: bmalloc.h:429
BA block_allocator_type
Definition: bmalloc.h:207
mem_alloc(const BA &block_alloc=BA(), const PA &ptr_alloc=PA())
Definition: bmalloc.h:270
unsigned int word_t
Definition: bmconst.h:38
PA ptr_allocator_type
Definition: bmalloc.h:265
BA block_allocator_type
Definition: bmalloc.h:264
Default malloc based bitblock allocator class.
Definition: bmalloc.h:111
PA ptr_allocator_type
Definition: bmalloc.h:208
Allocation pool object.
Definition: bmalloc.h:204
const unsigned gap_levels
Definition: bmconst.h:83
unsigned short gap_word_t
Definition: bmconst.h:76
ptr_allocator_type get_ptr_allocator() const
Returns copy of the ptr allocator object.
Definition: bmalloc.h:299
void set_pool(allocator_pool_type *pool)
set pointer to external pool
Definition: bmalloc.h:305
Pool of pointers to buffer cyclic allocations.
Definition: bmalloc.h:142
allocator_pool_type * get_pool()
get pointer to allocation pool (if set)
Definition: bmalloc.h:311
#define BM_DEFAULT_POOL_SIZE
Definition: bmconst.h:42
void free_ptr(void *p, size_t size)
Frees block of pointers.
Definition: bmalloc.h:379
bm::mem_alloc< block_allocator, ptr_allocator, standard_alloc_pool > standard_allocator
Definition: bmalloc.h:391
void free_bit_block(bm::word_t *block)
Definition: bmalloc.h:226
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
#define BM_ASSERT
Definition: bmdef.h:117
static void deallocate(bm::word_t *p, size_t)
The member function frees storage for an array of n bm::word_t elements, by calling free...
Definition: bmalloc.h:90
bm::word_t * alloc_bit_block(unsigned alloc_factor=1)
Allocates and returns bit block.
Definition: bmalloc.h:322
Default malloc based bitblock allocator class.
Definition: bmalloc.h:57