libstdc++
bitmap_allocator.h
Go to the documentation of this file.
1 // Bitmap Allocator. -*- C++ -*-
2 
3 // Copyright (C) 2004-2019 Free Software Foundation, Inc.
4 //
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 3, or (at your option)
9 // any later version.
10 
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
15 
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
19 
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
24 
25 /** @file ext/bitmap_allocator.h
26  * This file is a GNU extension to the Standard C++ Library.
27  */
28 
29 #ifndef _BITMAP_ALLOCATOR_H
30 #define _BITMAP_ALLOCATOR_H 1
31 
32 #include <utility> // For std::pair.
33 #include <bits/functexcept.h> // For __throw_bad_alloc().
34 #include <functional> // For greater_equal, and less_equal.
35 #include <new> // For operator new.
36 #include <debug/debug.h> // _GLIBCXX_DEBUG_ASSERT
37 #include <ext/concurrence.h>
38 #include <bits/move.h>
39 
40 /** @brief The constant in the expression below is the alignment
41  * required in bytes.
42  */
43 #define _BALLOC_ALIGN_BYTES 8
44 
45 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
46 {
47 _GLIBCXX_BEGIN_NAMESPACE_VERSION
48 
49  using std::size_t;
50  using std::ptrdiff_t;
51 
52  namespace __detail
53  {
54  /** @class __mini_vector bitmap_allocator.h bitmap_allocator.h
55  *
56  * @brief __mini_vector<> is a stripped down version of the
57  * full-fledged std::vector<>.
58  *
59  * It is to be used only for built-in types or PODs. Notable
60  * differences are:
61  *
62  * 1. Not all accessor functions are present.
63  * 2. Used ONLY for PODs.
64  * 3. No Allocator template argument. Uses ::operator new() to get
65  * memory, and ::operator delete() to free it.
66  * Caveat: The dtor does NOT free the memory allocated, so this a
67  * memory-leaking vector!
68  */
69  template<typename _Tp>
71  {
73  __mini_vector& operator=(const __mini_vector&);
74 
75  public:
76  typedef _Tp value_type;
77  typedef _Tp* pointer;
78  typedef _Tp& reference;
79  typedef const _Tp& const_reference;
80  typedef size_t size_type;
81  typedef ptrdiff_t difference_type;
82  typedef pointer iterator;
83 
84  private:
85  pointer _M_start;
86  pointer _M_finish;
87  pointer _M_end_of_storage;
88 
89  size_type
90  _M_space_left() const throw()
91  { return _M_end_of_storage - _M_finish; }
92 
93  _GLIBCXX_NODISCARD pointer
94  allocate(size_type __n)
95  { return static_cast<pointer>(::operator new(__n * sizeof(_Tp))); }
96 
97  void
98  deallocate(pointer __p, size_type)
99  { ::operator delete(__p); }
100 
101  public:
102  // Members used: size(), push_back(), pop_back(),
103  // insert(iterator, const_reference), erase(iterator),
104  // begin(), end(), back(), operator[].
105 
106  __mini_vector()
107  : _M_start(0), _M_finish(0), _M_end_of_storage(0) { }
108 
109  size_type
110  size() const throw()
111  { return _M_finish - _M_start; }
112 
113  iterator
114  begin() const throw()
115  { return this->_M_start; }
116 
117  iterator
118  end() const throw()
119  { return this->_M_finish; }
120 
121  reference
122  back() const throw()
123  { return *(this->end() - 1); }
124 
125  reference
126  operator[](const size_type __pos) const throw()
127  { return this->_M_start[__pos]; }
128 
129  void
130  insert(iterator __pos, const_reference __x);
131 
132  void
133  push_back(const_reference __x)
134  {
135  if (this->_M_space_left())
136  {
137  *this->end() = __x;
138  ++this->_M_finish;
139  }
140  else
141  this->insert(this->end(), __x);
142  }
143 
144  void
145  pop_back() throw()
146  { --this->_M_finish; }
147 
148  void
149  erase(iterator __pos) throw();
150 
151  void
152  clear() throw()
153  { this->_M_finish = this->_M_start; }
154  };
155 
156  // Out of line function definitions.
157  template<typename _Tp>
159  insert(iterator __pos, const_reference __x)
160  {
161  if (this->_M_space_left())
162  {
163  size_type __to_move = this->_M_finish - __pos;
164  iterator __dest = this->end();
165  iterator __src = this->end() - 1;
166 
167  ++this->_M_finish;
168  while (__to_move)
169  {
170  *__dest = *__src;
171  --__dest; --__src; --__to_move;
172  }
173  *__pos = __x;
174  }
175  else
176  {
177  size_type __new_size = this->size() ? this->size() * 2 : 1;
178  iterator __new_start = this->allocate(__new_size);
179  iterator __first = this->begin();
180  iterator __start = __new_start;
181  while (__first != __pos)
182  {
183  *__start = *__first;
184  ++__start; ++__first;
185  }
186  *__start = __x;
187  ++__start;
188  while (__first != this->end())
189  {
190  *__start = *__first;
191  ++__start; ++__first;
192  }
193  if (this->_M_start)
194  this->deallocate(this->_M_start, this->size());
195 
196  this->_M_start = __new_start;
197  this->_M_finish = __start;
198  this->_M_end_of_storage = this->_M_start + __new_size;
199  }
200  }
201 
202  template<typename _Tp>
203  void __mini_vector<_Tp>::
204  erase(iterator __pos) throw()
205  {
206  while (__pos + 1 != this->end())
207  {
208  *__pos = __pos[1];
209  ++__pos;
210  }
211  --this->_M_finish;
212  }
213 
214 
215  template<typename _Tp>
216  struct __mv_iter_traits
217  {
218  typedef typename _Tp::value_type value_type;
219  typedef typename _Tp::difference_type difference_type;
220  };
221 
222  template<typename _Tp>
223  struct __mv_iter_traits<_Tp*>
224  {
225  typedef _Tp value_type;
226  typedef ptrdiff_t difference_type;
227  };
228 
229  enum
230  {
231  bits_per_byte = 8,
232  bits_per_block = sizeof(size_t) * size_t(bits_per_byte)
233  };
234 
235  template<typename _ForwardIterator, typename _Tp, typename _Compare>
236  _ForwardIterator
237  __lower_bound(_ForwardIterator __first, _ForwardIterator __last,
238  const _Tp& __val, _Compare __comp)
239  {
240  typedef typename __mv_iter_traits<_ForwardIterator>::difference_type
241  _DistanceType;
242 
243  _DistanceType __len = __last - __first;
244  _DistanceType __half;
245  _ForwardIterator __middle;
246 
247  while (__len > 0)
248  {
249  __half = __len >> 1;
250  __middle = __first;
251  __middle += __half;
252  if (__comp(*__middle, __val))
253  {
254  __first = __middle;
255  ++__first;
256  __len = __len - __half - 1;
257  }
258  else
259  __len = __half;
260  }
261  return __first;
262  }
263 
264  /** @brief The number of Blocks pointed to by the address pair
265  * passed to the function.
266  */
267  template<typename _AddrPair>
268  inline size_t
269  __num_blocks(_AddrPair __ap)
270  { return (__ap.second - __ap.first) + 1; }
271 
272  /** @brief The number of Bit-maps pointed to by the address pair
273  * passed to the function.
274  */
275  template<typename _AddrPair>
276  inline size_t
277  __num_bitmaps(_AddrPair __ap)
278  { return __num_blocks(__ap) / size_t(bits_per_block); }
279 
280  // _Tp should be a pointer type.
281  template<typename _Tp>
282  class _Inclusive_between
283  : public std::unary_function<typename std::pair<_Tp, _Tp>, bool>
284  {
285  typedef _Tp pointer;
286  pointer _M_ptr_value;
287  typedef typename std::pair<_Tp, _Tp> _Block_pair;
288 
289  public:
290  _Inclusive_between(pointer __ptr) : _M_ptr_value(__ptr)
291  { }
292 
293  bool
294  operator()(_Block_pair __bp) const throw()
295  {
296  if (std::less_equal<pointer>()(_M_ptr_value, __bp.second)
297  && std::greater_equal<pointer>()(_M_ptr_value, __bp.first))
298  return true;
299  else
300  return false;
301  }
302  };
303 
304  // Used to pass a Functor to functions by reference.
305  template<typename _Functor>
306  class _Functor_Ref
307  : public std::unary_function<typename _Functor::argument_type,
308  typename _Functor::result_type>
309  {
310  _Functor& _M_fref;
311 
312  public:
313  typedef typename _Functor::argument_type argument_type;
314  typedef typename _Functor::result_type result_type;
315 
316  _Functor_Ref(_Functor& __fref) : _M_fref(__fref)
317  { }
318 
319  result_type
320  operator()(argument_type __arg)
321  { return _M_fref(__arg); }
322  };
323 
324  /** @class _Ffit_finder bitmap_allocator.h bitmap_allocator.h
325  *
326  * @brief The class which acts as a predicate for applying the
327  * first-fit memory allocation policy for the bitmap allocator.
328  */
329  // _Tp should be a pointer type, and _Alloc is the Allocator for
330  // the vector.
331  template<typename _Tp>
333  : public std::unary_function<typename std::pair<_Tp, _Tp>, bool>
334  {
335  typedef typename std::pair<_Tp, _Tp> _Block_pair;
337  typedef typename _BPVector::difference_type _Counter_type;
338 
339  size_t* _M_pbitmap;
340  _Counter_type _M_data_offset;
341 
342  public:
343  _Ffit_finder() : _M_pbitmap(0), _M_data_offset(0)
344  { }
345 
346  bool
347  operator()(_Block_pair __bp) throw()
348  {
349  // Set the _rover to the last physical location bitmap,
350  // which is the bitmap which belongs to the first free
351  // block. Thus, the bitmaps are in exact reverse order of
352  // the actual memory layout. So, we count down the bitmaps,
353  // which is the same as moving up the memory.
354 
355  // If the used count stored at the start of the Bit Map headers
356  // is equal to the number of Objects that the current Block can
357  // store, then there is definitely no space for another single
358  // object, so just return false.
359  _Counter_type __diff = __detail::__num_bitmaps(__bp);
360 
361  if (*(reinterpret_cast<size_t*>
362  (__bp.first) - (__diff + 1)) == __detail::__num_blocks(__bp))
363  return false;
364 
365  size_t* __rover = reinterpret_cast<size_t*>(__bp.first) - 1;
366 
367  for (_Counter_type __i = 0; __i < __diff; ++__i)
368  {
369  _M_data_offset = __i;
370  if (*__rover)
371  {
372  _M_pbitmap = __rover;
373  return true;
374  }
375  --__rover;
376  }
377  return false;
378  }
379 
380  size_t*
381  _M_get() const throw()
382  { return _M_pbitmap; }
383 
384  _Counter_type
385  _M_offset() const throw()
386  { return _M_data_offset * size_t(bits_per_block); }
387  };
388 
389  /** @class _Bitmap_counter bitmap_allocator.h bitmap_allocator.h
390  *
391  * @brief The bitmap counter which acts as the bitmap
392  * manipulator, and manages the bit-manipulation functions and
393  * the searching and identification functions on the bit-map.
394  */
395  // _Tp should be a pointer type.
396  template<typename _Tp>
398  {
399  typedef typename
401  typedef typename _BPVector::size_type _Index_type;
402  typedef _Tp pointer;
403 
404  _BPVector& _M_vbp;
405  size_t* _M_curr_bmap;
406  size_t* _M_last_bmap_in_block;
407  _Index_type _M_curr_index;
408 
409  public:
410  // Use the 2nd parameter with care. Make sure that such an
411  // entry exists in the vector before passing that particular
412  // index to this ctor.
413  _Bitmap_counter(_BPVector& Rvbp, long __index = -1) : _M_vbp(Rvbp)
414  { this->_M_reset(__index); }
415 
416  void
417  _M_reset(long __index = -1) throw()
418  {
419  if (__index == -1)
420  {
421  _M_curr_bmap = 0;
422  _M_curr_index = static_cast<_Index_type>(-1);
423  return;
424  }
425 
426  _M_curr_index = __index;
427  _M_curr_bmap = reinterpret_cast<size_t*>
428  (_M_vbp[_M_curr_index].first) - 1;
429 
430  _GLIBCXX_DEBUG_ASSERT(__index <= (long)_M_vbp.size() - 1);
431 
432  _M_last_bmap_in_block = _M_curr_bmap
433  - ((_M_vbp[_M_curr_index].second
434  - _M_vbp[_M_curr_index].first + 1)
435  / size_t(bits_per_block) - 1);
436  }
437 
438  // Dangerous Function! Use with extreme care. Pass to this
439  // function ONLY those values that are known to be correct,
440  // otherwise this will mess up big time.
441  void
442  _M_set_internal_bitmap(size_t* __new_internal_marker) throw()
443  { _M_curr_bmap = __new_internal_marker; }
444 
445  bool
446  _M_finished() const throw()
447  { return(_M_curr_bmap == 0); }
448 
450  operator++() throw()
451  {
452  if (_M_curr_bmap == _M_last_bmap_in_block)
453  {
454  if (++_M_curr_index == _M_vbp.size())
455  _M_curr_bmap = 0;
456  else
457  this->_M_reset(_M_curr_index);
458  }
459  else
460  --_M_curr_bmap;
461  return *this;
462  }
463 
464  size_t*
465  _M_get() const throw()
466  { return _M_curr_bmap; }
467 
468  pointer
469  _M_base() const throw()
470  { return _M_vbp[_M_curr_index].first; }
471 
472  _Index_type
473  _M_offset() const throw()
474  {
475  return size_t(bits_per_block)
476  * ((reinterpret_cast<size_t*>(this->_M_base())
477  - _M_curr_bmap) - 1);
478  }
479 
480  _Index_type
481  _M_where() const throw()
482  { return _M_curr_index; }
483  };
484 
485  /** @brief Mark a memory address as allocated by re-setting the
486  * corresponding bit in the bit-map.
487  */
488  inline void
489  __bit_allocate(size_t* __pbmap, size_t __pos) throw()
490  {
491  size_t __mask = 1 << __pos;
492  __mask = ~__mask;
493  *__pbmap &= __mask;
494  }
495 
496  /** @brief Mark a memory address as free by setting the
497  * corresponding bit in the bit-map.
498  */
499  inline void
500  __bit_free(size_t* __pbmap, size_t __pos) throw()
501  {
502  size_t __mask = 1 << __pos;
503  *__pbmap |= __mask;
504  }
505  } // namespace __detail
506 
507  /** @brief Generic Version of the bsf instruction.
508  */
509  inline size_t
510  _Bit_scan_forward(size_t __num)
511  { return static_cast<size_t>(__builtin_ctzl(__num)); }
512 
513  /** @class free_list bitmap_allocator.h bitmap_allocator.h
514  *
515  * @brief The free list class for managing chunks of memory to be
516  * given to and returned by the bitmap_allocator.
517  */
518  class free_list
519  {
520  public:
521  typedef size_t* value_type;
523  typedef vector_type::iterator iterator;
524  typedef __mutex __mutex_type;
525 
526  private:
527  struct _LT_pointer_compare
528  {
529  bool
530  operator()(const size_t* __pui,
531  const size_t __cui) const throw()
532  { return *__pui < __cui; }
533  };
534 
535 #if defined __GTHREADS
536  __mutex_type&
537  _M_get_mutex()
538  {
539  static __mutex_type _S_mutex;
540  return _S_mutex;
541  }
542 #endif
543 
544  vector_type&
545  _M_get_free_list()
546  {
547  static vector_type _S_free_list;
548  return _S_free_list;
549  }
550 
551  /** @brief Performs validation of memory based on their size.
552  *
553  * @param __addr The pointer to the memory block to be
554  * validated.
555  *
556  * Validates the memory block passed to this function and
557  * appropriately performs the action of managing the free list of
558  * blocks by adding this block to the free list or deleting this
559  * or larger blocks from the free list.
560  */
561  void
562  _M_validate(size_t* __addr) throw()
563  {
564  vector_type& __free_list = _M_get_free_list();
565  const vector_type::size_type __max_size = 64;
566  if (__free_list.size() >= __max_size)
567  {
568  // Ok, the threshold value has been reached. We determine
569  // which block to remove from the list of free blocks.
570  if (*__addr >= *__free_list.back())
571  {
572  // Ok, the new block is greater than or equal to the
573  // last block in the list of free blocks. We just free
574  // the new block.
575  ::operator delete(static_cast<void*>(__addr));
576  return;
577  }
578  else
579  {
580  // Deallocate the last block in the list of free lists,
581  // and insert the new one in its correct position.
582  ::operator delete(static_cast<void*>(__free_list.back()));
583  __free_list.pop_back();
584  }
585  }
586 
587  // Just add the block to the list of free lists unconditionally.
588  iterator __temp = __detail::__lower_bound
589  (__free_list.begin(), __free_list.end(),
590  *__addr, _LT_pointer_compare());
591 
592  // We may insert the new free list before _temp;
593  __free_list.insert(__temp, __addr);
594  }
595 
596  /** @brief Decides whether the wastage of memory is acceptable for
597  * the current memory request and returns accordingly.
598  *
599  * @param __block_size The size of the block available in the free
600  * list.
601  *
602  * @param __required_size The required size of the memory block.
603  *
604  * @return true if the wastage incurred is acceptable, else returns
605  * false.
606  */
607  bool
608  _M_should_i_give(size_t __block_size,
609  size_t __required_size) throw()
610  {
611  const size_t __max_wastage_percentage = 36;
612  if (__block_size >= __required_size &&
613  (((__block_size - __required_size) * 100 / __block_size)
614  < __max_wastage_percentage))
615  return true;
616  else
617  return false;
618  }
619 
620  public:
621  /** @brief This function returns the block of memory to the
622  * internal free list.
623  *
624  * @param __addr The pointer to the memory block that was given
625  * by a call to the _M_get function.
626  */
627  inline void
628  _M_insert(size_t* __addr) throw()
629  {
630 #if defined __GTHREADS
631  __scoped_lock __bfl_lock(_M_get_mutex());
632 #endif
633  // Call _M_validate to decide what should be done with
634  // this particular free list.
635  this->_M_validate(reinterpret_cast<size_t*>(__addr) - 1);
636  // See discussion as to why this is 1!
637  }
638 
639  /** @brief This function gets a block of memory of the specified
640  * size from the free list.
641  *
642  * @param __sz The size in bytes of the memory required.
643  *
644  * @return A pointer to the new memory block of size at least
645  * equal to that requested.
646  */
647  size_t*
648  _M_get(size_t __sz) _GLIBCXX_THROW(std::bad_alloc);
649 
650  /** @brief This function just clears the internal Free List, and
651  * gives back all the memory to the OS.
652  */
653  void
654  _M_clear();
655  };
656 
657 
658  // Forward declare the class.
659  template<typename _Tp>
661 
662  // Specialize for void:
663  template<>
664  class bitmap_allocator<void>
665  {
666  public:
667  typedef void* pointer;
668  typedef const void* const_pointer;
669 
670  // Reference-to-void members are impossible.
671  typedef void value_type;
672  template<typename _Tp1>
673  struct rebind
674  {
675  typedef bitmap_allocator<_Tp1> other;
676  };
677  };
678 
679  /**
680  * @brief Bitmap Allocator, primary template.
681  * @ingroup allocators
682  */
683  template<typename _Tp>
684  class bitmap_allocator : private free_list
685  {
686  public:
687  typedef size_t size_type;
688  typedef ptrdiff_t difference_type;
689  typedef _Tp* pointer;
690  typedef const _Tp* const_pointer;
691  typedef _Tp& reference;
692  typedef const _Tp& const_reference;
693  typedef _Tp value_type;
694  typedef free_list::__mutex_type __mutex_type;
695 
696  template<typename _Tp1>
697  struct rebind
698  {
699  typedef bitmap_allocator<_Tp1> other;
700  };
701 
702 #if __cplusplus >= 201103L
703  // _GLIBCXX_RESOLVE_LIB_DEFECTS
704  // 2103. propagate_on_container_move_assignment
705  typedef std::true_type propagate_on_container_move_assignment;
706 #endif
707 
708  private:
709  template<size_t _BSize, size_t _AlignSize>
710  struct aligned_size
711  {
712  enum
713  {
714  modulus = _BSize % _AlignSize,
715  value = _BSize + (modulus ? _AlignSize - (modulus) : 0)
716  };
717  };
718 
719  struct _Alloc_block
720  {
721  char __M_unused[aligned_size<sizeof(value_type),
722  _BALLOC_ALIGN_BYTES>::value];
723  };
724 
725 
726  typedef typename std::pair<_Alloc_block*, _Alloc_block*> _Block_pair;
727 
728  typedef typename __detail::__mini_vector<_Block_pair> _BPVector;
729  typedef typename _BPVector::iterator _BPiter;
730 
731  template<typename _Predicate>
732  static _BPiter
733  _S_find(_Predicate __p)
734  {
735  _BPiter __first = _S_mem_blocks.begin();
736  while (__first != _S_mem_blocks.end() && !__p(*__first))
737  ++__first;
738  return __first;
739  }
740 
741 #if defined _GLIBCXX_DEBUG
742  // Complexity: O(lg(N)). Where, N is the number of block of size
743  // sizeof(value_type).
744  void
745  _S_check_for_free_blocks() throw()
746  {
747  typedef typename __detail::_Ffit_finder<_Alloc_block*> _FFF;
748  _BPiter __bpi = _S_find(_FFF());
749 
750  _GLIBCXX_DEBUG_ASSERT(__bpi == _S_mem_blocks.end());
751  }
752 #endif
753 
754  /** @brief Responsible for exponentially growing the internal
755  * memory pool.
756  *
757  * @throw std::bad_alloc. If memory cannot be allocated.
758  *
759  * Complexity: O(1), but internally depends upon the
760  * complexity of the function free_list::_M_get. The part where
761  * the bitmap headers are written has complexity: O(X),where X
762  * is the number of blocks of size sizeof(value_type) within
763  * the newly acquired block. Having a tight bound.
764  */
765  void
766  _S_refill_pool() _GLIBCXX_THROW(std::bad_alloc)
767  {
768 #if defined _GLIBCXX_DEBUG
769  _S_check_for_free_blocks();
770 #endif
771 
772  const size_t __num_bitmaps = (_S_block_size
773  / size_t(__detail::bits_per_block));
774  const size_t __size_to_allocate = sizeof(size_t)
775  + _S_block_size * sizeof(_Alloc_block)
776  + __num_bitmaps * sizeof(size_t);
777 
778  size_t* __temp =
779  reinterpret_cast<size_t*>(this->_M_get(__size_to_allocate));
780  *__temp = 0;
781  ++__temp;
782 
783  // The Header information goes at the Beginning of the Block.
784  _Block_pair __bp =
785  std::make_pair(reinterpret_cast<_Alloc_block*>
786  (__temp + __num_bitmaps),
787  reinterpret_cast<_Alloc_block*>
788  (__temp + __num_bitmaps)
789  + _S_block_size - 1);
790 
791  // Fill the Vector with this information.
792  _S_mem_blocks.push_back(__bp);
793 
794  for (size_t __i = 0; __i < __num_bitmaps; ++__i)
795  __temp[__i] = ~static_cast<size_t>(0); // 1 Indicates all Free.
796 
797  _S_block_size *= 2;
798  }
799 
800  static _BPVector _S_mem_blocks;
801  static size_t _S_block_size;
802  static __detail::_Bitmap_counter<_Alloc_block*> _S_last_request;
803  static typename _BPVector::size_type _S_last_dealloc_index;
804 #if defined __GTHREADS
805  static __mutex_type _S_mut;
806 #endif
807 
808  public:
809 
810  /** @brief Allocates memory for a single object of size
811  * sizeof(_Tp).
812  *
813  * @throw std::bad_alloc. If memory cannot be allocated.
814  *
815  * Complexity: Worst case complexity is O(N), but that
816  * is hardly ever hit. If and when this particular case is
817  * encountered, the next few cases are guaranteed to have a
818  * worst case complexity of O(1)! That's why this function
819  * performs very well on average. You can consider this
820  * function to have a complexity referred to commonly as:
821  * Amortized Constant time.
822  */
823  pointer
824  _M_allocate_single_object() _GLIBCXX_THROW(std::bad_alloc)
825  {
826 #if defined __GTHREADS
827  __scoped_lock __bit_lock(_S_mut);
828 #endif
829 
830  // The algorithm is something like this: The last_request
831  // variable points to the last accessed Bit Map. When such a
832  // condition occurs, we try to find a free block in the
833  // current bitmap, or succeeding bitmaps until the last bitmap
834  // is reached. If no free block turns up, we resort to First
835  // Fit method.
836 
837  // WARNING: Do not re-order the condition in the while
838  // statement below, because it relies on C++'s short-circuit
839  // evaluation. The return from _S_last_request->_M_get() will
840  // NOT be dereference able if _S_last_request->_M_finished()
841  // returns true. This would inevitably lead to a NULL pointer
842  // dereference if tinkered with.
843  while (_S_last_request._M_finished() == false
844  && (*(_S_last_request._M_get()) == 0))
845  _S_last_request.operator++();
846 
847  if (__builtin_expect(_S_last_request._M_finished() == true, false))
848  {
849  // Fall Back to First Fit algorithm.
850  typedef typename __detail::_Ffit_finder<_Alloc_block*> _FFF;
851  _FFF __fff;
852  _BPiter __bpi = _S_find(__detail::_Functor_Ref<_FFF>(__fff));
853 
854  if (__bpi != _S_mem_blocks.end())
855  {
856  // Search was successful. Ok, now mark the first bit from
857  // the right as 0, meaning Allocated. This bit is obtained
858  // by calling _M_get() on __fff.
859  size_t __nz_bit = _Bit_scan_forward(*__fff._M_get());
860  __detail::__bit_allocate(__fff._M_get(), __nz_bit);
861 
862  _S_last_request._M_reset(__bpi - _S_mem_blocks.begin());
863 
864  // Now, get the address of the bit we marked as allocated.
865  pointer __ret = reinterpret_cast<pointer>
866  (__bpi->first + __fff._M_offset() + __nz_bit);
867  size_t* __puse_count =
868  reinterpret_cast<size_t*>
869  (__bpi->first) - (__detail::__num_bitmaps(*__bpi) + 1);
870 
871  ++(*__puse_count);
872  return __ret;
873  }
874  else
875  {
876  // Search was unsuccessful. We Add more memory to the
877  // pool by calling _S_refill_pool().
878  _S_refill_pool();
879 
880  // _M_Reset the _S_last_request structure to the first
881  // free block's bit map.
882  _S_last_request._M_reset(_S_mem_blocks.size() - 1);
883 
884  // Now, mark that bit as allocated.
885  }
886  }
887 
888  // _S_last_request holds a pointer to a valid bit map, that
889  // points to a free block in memory.
890  size_t __nz_bit = _Bit_scan_forward(*_S_last_request._M_get());
891  __detail::__bit_allocate(_S_last_request._M_get(), __nz_bit);
892 
893  pointer __ret = reinterpret_cast<pointer>
894  (_S_last_request._M_base() + _S_last_request._M_offset() + __nz_bit);
895 
896  size_t* __puse_count = reinterpret_cast<size_t*>
897  (_S_mem_blocks[_S_last_request._M_where()].first)
898  - (__detail::
899  __num_bitmaps(_S_mem_blocks[_S_last_request._M_where()]) + 1);
900 
901  ++(*__puse_count);
902  return __ret;
903  }
904 
905  /** @brief Deallocates memory that belongs to a single object of
906  * size sizeof(_Tp).
907  *
908  * Complexity: O(lg(N)), but the worst case is not hit
909  * often! This is because containers usually deallocate memory
910  * close to each other and this case is handled in O(1) time by
911  * the deallocate function.
912  */
913  void
914  _M_deallocate_single_object(pointer __p) throw()
915  {
916 #if defined __GTHREADS
917  __scoped_lock __bit_lock(_S_mut);
918 #endif
919  _Alloc_block* __real_p = reinterpret_cast<_Alloc_block*>(__p);
920 
921  typedef typename _BPVector::iterator _Iterator;
922  typedef typename _BPVector::difference_type _Difference_type;
923 
924  _Difference_type __diff;
925  long __displacement;
926 
927  _GLIBCXX_DEBUG_ASSERT(_S_last_dealloc_index >= 0);
928 
929  __detail::_Inclusive_between<_Alloc_block*> __ibt(__real_p);
930  if (__ibt(_S_mem_blocks[_S_last_dealloc_index]))
931  {
932  _GLIBCXX_DEBUG_ASSERT(_S_last_dealloc_index
933  <= _S_mem_blocks.size() - 1);
934 
935  // Initial Assumption was correct!
936  __diff = _S_last_dealloc_index;
937  __displacement = __real_p - _S_mem_blocks[__diff].first;
938  }
939  else
940  {
941  _Iterator _iter = _S_find(__ibt);
942 
943  _GLIBCXX_DEBUG_ASSERT(_iter != _S_mem_blocks.end());
944 
945  __diff = _iter - _S_mem_blocks.begin();
946  __displacement = __real_p - _S_mem_blocks[__diff].first;
947  _S_last_dealloc_index = __diff;
948  }
949 
950  // Get the position of the iterator that has been found.
951  const size_t __rotate = (__displacement
952  % size_t(__detail::bits_per_block));
953  size_t* __bitmapC =
954  reinterpret_cast<size_t*>
955  (_S_mem_blocks[__diff].first) - 1;
956  __bitmapC -= (__displacement / size_t(__detail::bits_per_block));
957 
958  __detail::__bit_free(__bitmapC, __rotate);
959  size_t* __puse_count = reinterpret_cast<size_t*>
960  (_S_mem_blocks[__diff].first)
961  - (__detail::__num_bitmaps(_S_mem_blocks[__diff]) + 1);
962 
963  _GLIBCXX_DEBUG_ASSERT(*__puse_count != 0);
964 
965  --(*__puse_count);
966 
967  if (__builtin_expect(*__puse_count == 0, false))
968  {
969  _S_block_size /= 2;
970 
971  // We can safely remove this block.
972  // _Block_pair __bp = _S_mem_blocks[__diff];
973  this->_M_insert(__puse_count);
974  _S_mem_blocks.erase(_S_mem_blocks.begin() + __diff);
975 
976  // Reset the _S_last_request variable to reflect the
977  // erased block. We do this to protect future requests
978  // after the last block has been removed from a particular
979  // memory Chunk, which in turn has been returned to the
980  // free list, and hence had been erased from the vector,
981  // so the size of the vector gets reduced by 1.
982  if ((_Difference_type)_S_last_request._M_where() >= __diff--)
983  _S_last_request._M_reset(__diff);
984 
985  // If the Index into the vector of the region of memory
986  // that might hold the next address that will be passed to
987  // deallocated may have been invalidated due to the above
988  // erase procedure being called on the vector, hence we
989  // try to restore this invariant too.
990  if (_S_last_dealloc_index >= _S_mem_blocks.size())
991  {
992  _S_last_dealloc_index =(__diff != -1 ? __diff : 0);
993  _GLIBCXX_DEBUG_ASSERT(_S_last_dealloc_index >= 0);
994  }
995  }
996  }
997 
998  public:
999  bitmap_allocator() _GLIBCXX_USE_NOEXCEPT
1000  { }
1001 
1002  bitmap_allocator(const bitmap_allocator&) _GLIBCXX_USE_NOEXCEPT
1003  { }
1004 
1005  template<typename _Tp1>
1006  bitmap_allocator(const bitmap_allocator<_Tp1>&) _GLIBCXX_USE_NOEXCEPT
1007  { }
1008 
1009  ~bitmap_allocator() _GLIBCXX_USE_NOEXCEPT
1010  { }
1011 
1012  _GLIBCXX_NODISCARD pointer
1013  allocate(size_type __n)
1014  {
1015  if (__n > this->max_size())
1016  std::__throw_bad_alloc();
1017 
1018 #if __cpp_aligned_new
1019  if (alignof(value_type) > __STDCPP_DEFAULT_NEW_ALIGNMENT__)
1020  {
1021  const size_type __b = __n * sizeof(value_type);
1022  std::align_val_t __al = std::align_val_t(alignof(value_type));
1023  return static_cast<pointer>(::operator new(__b, __al));
1024  }
1025 #endif
1026 
1027  if (__builtin_expect(__n == 1, true))
1028  return this->_M_allocate_single_object();
1029  else
1030  {
1031  const size_type __b = __n * sizeof(value_type);
1032  return reinterpret_cast<pointer>(::operator new(__b));
1033  }
1034  }
1035 
1036  _GLIBCXX_NODISCARD pointer
1037  allocate(size_type __n, typename bitmap_allocator<void>::const_pointer)
1038  { return allocate(__n); }
1039 
1040  void
1041  deallocate(pointer __p, size_type __n) throw()
1042  {
1043  if (__builtin_expect(__p != 0, true))
1044  {
1045 #if __cpp_aligned_new
1046  // Types with extended alignment are handled by operator delete.
1047  if (alignof(value_type) > __STDCPP_DEFAULT_NEW_ALIGNMENT__)
1048  {
1049  ::operator delete(__p, std::align_val_t(alignof(value_type)));
1050  return;
1051  }
1052 #endif
1053 
1054  if (__builtin_expect(__n == 1, true))
1055  this->_M_deallocate_single_object(__p);
1056  else
1057  ::operator delete(__p);
1058  }
1059  }
1060 
1061  pointer
1062  address(reference __r) const _GLIBCXX_NOEXCEPT
1063  { return std::__addressof(__r); }
1064 
1065  const_pointer
1066  address(const_reference __r) const _GLIBCXX_NOEXCEPT
1067  { return std::__addressof(__r); }
1068 
1069  size_type
1070  max_size() const _GLIBCXX_USE_NOEXCEPT
1071  { return size_type(-1) / sizeof(value_type); }
1072 
1073 #if __cplusplus >= 201103L
1074  template<typename _Up, typename... _Args>
1075  void
1076  construct(_Up* __p, _Args&&... __args)
1077  { ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }
1078 
1079  template<typename _Up>
1080  void
1081  destroy(_Up* __p)
1082  { __p->~_Up(); }
1083 #else
1084  void
1085  construct(pointer __p, const_reference __data)
1086  { ::new((void *)__p) value_type(__data); }
1087 
1088  void
1089  destroy(pointer __p)
1090  { __p->~value_type(); }
1091 #endif
1092  };
1093 
1094  template<typename _Tp1, typename _Tp2>
1095  bool
1096  operator==(const bitmap_allocator<_Tp1>&,
1097  const bitmap_allocator<_Tp2>&) throw()
1098  { return true; }
1099 
1100  template<typename _Tp1, typename _Tp2>
1101  bool
1102  operator!=(const bitmap_allocator<_Tp1>&,
1103  const bitmap_allocator<_Tp2>&) throw()
1104  { return false; }
1105 
1106  // Static member definitions.
1107  template<typename _Tp>
1108  typename bitmap_allocator<_Tp>::_BPVector
1109  bitmap_allocator<_Tp>::_S_mem_blocks;
1110 
1111  template<typename _Tp>
1112  size_t bitmap_allocator<_Tp>::_S_block_size =
1113  2 * size_t(__detail::bits_per_block);
1114 
1115  template<typename _Tp>
1116  typename bitmap_allocator<_Tp>::_BPVector::size_type
1117  bitmap_allocator<_Tp>::_S_last_dealloc_index = 0;
1118 
1119  template<typename _Tp>
1120  __detail::_Bitmap_counter
1121  <typename bitmap_allocator<_Tp>::_Alloc_block*>
1122  bitmap_allocator<_Tp>::_S_last_request(_S_mem_blocks);
1123 
1124 #if defined __GTHREADS
1125  template<typename _Tp>
1126  typename bitmap_allocator<_Tp>::__mutex_type
1127  bitmap_allocator<_Tp>::_S_mut;
1128 #endif
1129 
1130 _GLIBCXX_END_NAMESPACE_VERSION
1131 } // namespace __gnu_cxx
1132 
1133 #endif
GNU extensions for public use.
size_t * _M_get(size_t __sz)
This function gets a block of memory of the specified size from the free list.
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:208
void __bit_allocate(size_t *__pbmap, size_t __pos)
Mark a memory address as allocated by re-setting the corresponding bit in the bit-map.
void __bit_free(size_t *__pbmap, size_t __pos)
Mark a memory address as free by setting the corresponding bit in the bit-map.
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
Definition: move.h:47
void _M_deallocate_single_object(pointer __p)
Deallocates memory that belongs to a single object of size sizeof(_Tp).
One of the comparison functors.
Definition: stl_function.h:343
__mini_vector<> is a stripped down version of the full-fledged std::vector<>.
#define _BALLOC_ALIGN_BYTES
The constant in the expression below is the alignment required in bytes.
void _M_insert(size_t *__addr)
This function returns the block of memory to the internal free list.
Exception possibly thrown by new.bad_alloc (or classes derived from it) is used to report allocation ...
Definition: new:54
pointer _M_allocate_single_object()
Allocates memory for a single object of size sizeof(_Tp).
The class which acts as a predicate for applying the first-fit memory allocation policy for the bitma...
constexpr pair< typename __decay_and_strip< _T1 >::__type, typename __decay_and_strip< _T2 >::__type > make_pair(_T1 &&__x, _T2 &&__y)
A convenience wrapper for creating a pair from two objects.
Definition: stl_pair.h:524
void _M_clear()
This function just clears the internal Free List, and gives back all the memory to the OS.
The free list class for managing chunks of memory to be given to and returned by the bitmap_allocator...
_T1 first
second_type is the second bound type
Definition: stl_pair.h:214
constexpr const _Tp * end(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to one past the last element of the initializer_list.
One of the comparison functors.
Definition: stl_function.h:346
size_t __num_bitmaps(_AddrPair __ap)
The number of Bit-maps pointed to by the address pair passed to the function.
Scoped lock idiom.
Definition: concurrence.h:228
Common iterator class.
size_t _Bit_scan_forward(size_t __num)
Generic Version of the bsf instruction.
size_t __num_blocks(_AddrPair __ap)
The number of Blocks pointed to by the address pair passed to the function.
integral_constant
Definition: type_traits:57
Bitmap Allocator, primary template.
The bitmap counter which acts as the bitmap manipulator, and manages the bit-manipulation functions a...
ISO C++ entities toplevel namespace is std.
constexpr const _Tp * begin(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to the first element of the initializer_list.