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