libstdc++
bitmap_allocator.h
Go to the documentation of this file.
00001 // Bitmap Allocator. -*- C++ -*-
00002 
00003 // Copyright (C) 2004-2019 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 3, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 /** @file ext/bitmap_allocator.h
00026  *  This file is a GNU extension to the Standard C++ Library.
00027  */
00028 
00029 #ifndef _BITMAP_ALLOCATOR_H
00030 #define _BITMAP_ALLOCATOR_H 1
00031 
00032 #include <utility> // For std::pair.
00033 #include <bits/functexcept.h> // For __throw_bad_alloc().
00034 #include <functional> // For greater_equal, and less_equal.
00035 #include <new> // For operator new.
00036 #include <debug/debug.h> // _GLIBCXX_DEBUG_ASSERT
00037 #include <ext/concurrence.h>
00038 #include <bits/move.h>
00039 
00040 /** @brief The constant in the expression below is the alignment
00041  * required in bytes.
00042  */
00043 #define _BALLOC_ALIGN_BYTES 8
00044 
00045 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
00046 {
00047 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00048 
00049   using std::size_t;
00050   using std::ptrdiff_t;
00051 
00052   namespace __detail
00053   {
00054     /** @class  __mini_vector bitmap_allocator.h bitmap_allocator.h
00055      *
00056      *  @brief  __mini_vector<> is a stripped down version of the
00057      *  full-fledged std::vector<>.
00058      *
00059      *  It is to be used only for built-in types or PODs. Notable
00060      *  differences are:
00061      * 
00062      *  1. Not all accessor functions are present.
00063      *  2. Used ONLY for PODs.
00064      *  3. No Allocator template argument. Uses ::operator new() to get
00065      *  memory, and ::operator delete() to free it.
00066      *  Caveat: The dtor does NOT free the memory allocated, so this a
00067      *  memory-leaking vector!
00068      */
00069     template<typename _Tp>
00070       class __mini_vector
00071       {
00072         __mini_vector(const __mini_vector&);
00073         __mini_vector& operator=(const __mini_vector&);
00074 
00075       public:
00076         typedef _Tp value_type;
00077         typedef _Tp* pointer;
00078         typedef _Tp& reference;
00079         typedef const _Tp& const_reference;
00080         typedef size_t size_type;
00081         typedef ptrdiff_t difference_type;
00082         typedef pointer iterator;
00083 
00084       private:
00085         pointer _M_start;
00086         pointer _M_finish;
00087         pointer _M_end_of_storage;
00088 
00089         size_type
00090         _M_space_left() const throw()
00091         { return _M_end_of_storage - _M_finish; }
00092 
00093         _GLIBCXX_NODISCARD pointer
00094         allocate(size_type __n)
00095         { return static_cast<pointer>(::operator new(__n * sizeof(_Tp))); }
00096 
00097         void
00098         deallocate(pointer __p, size_type)
00099         { ::operator delete(__p); }
00100 
00101       public:
00102         // Members used: size(), push_back(), pop_back(),
00103         // insert(iterator, const_reference), erase(iterator),
00104         // begin(), end(), back(), operator[].
00105 
00106         __mini_vector()
00107         : _M_start(0), _M_finish(0), _M_end_of_storage(0) { }
00108 
00109         size_type
00110         size() const throw()
00111         { return _M_finish - _M_start; }
00112 
00113         iterator
00114         begin() const throw()
00115         { return this->_M_start; }
00116 
00117         iterator
00118         end() const throw()
00119         { return this->_M_finish; }
00120 
00121         reference
00122         back() const throw()
00123         { return *(this->end() - 1); }
00124 
00125         reference
00126         operator[](const size_type __pos) const throw()
00127         { return this->_M_start[__pos]; }
00128 
00129         void
00130         insert(iterator __pos, const_reference __x);
00131 
00132         void
00133         push_back(const_reference __x)
00134         {
00135           if (this->_M_space_left())
00136             {
00137               *this->end() = __x;
00138               ++this->_M_finish;
00139             }
00140           else
00141             this->insert(this->end(), __x);
00142         }
00143 
00144         void
00145         pop_back() throw()
00146         { --this->_M_finish; }
00147 
00148         void
00149         erase(iterator __pos) throw();
00150 
00151         void
00152         clear() throw()
00153         { this->_M_finish = this->_M_start; }
00154       };
00155 
00156     // Out of line function definitions.
00157     template<typename _Tp>
00158       void __mini_vector<_Tp>::
00159       insert(iterator __pos, const_reference __x)
00160       {
00161         if (this->_M_space_left())
00162           {
00163             size_type __to_move = this->_M_finish - __pos;
00164             iterator __dest = this->end();
00165             iterator __src = this->end() - 1;
00166 
00167             ++this->_M_finish;
00168             while (__to_move)
00169               {
00170                 *__dest = *__src;
00171                 --__dest; --__src; --__to_move;
00172               }
00173             *__pos = __x;
00174           }
00175         else
00176           {
00177             size_type __new_size = this->size() ? this->size() * 2 : 1;
00178             iterator __new_start = this->allocate(__new_size);
00179             iterator __first = this->begin();
00180             iterator __start = __new_start;
00181             while (__first != __pos)
00182               {
00183                 *__start = *__first;
00184                 ++__start; ++__first;
00185               }
00186             *__start = __x;
00187             ++__start;
00188             while (__first != this->end())
00189               {
00190                 *__start = *__first;
00191                 ++__start; ++__first;
00192               }
00193             if (this->_M_start)
00194               this->deallocate(this->_M_start, this->size());
00195 
00196             this->_M_start = __new_start;
00197             this->_M_finish = __start;
00198             this->_M_end_of_storage = this->_M_start + __new_size;
00199           }
00200       }
00201 
00202     template<typename _Tp>
00203       void __mini_vector<_Tp>::
00204       erase(iterator __pos) throw()
00205       {
00206         while (__pos + 1 != this->end())
00207           {
00208             *__pos = __pos[1];
00209             ++__pos;
00210           }
00211         --this->_M_finish;
00212       }
00213 
00214 
00215     template<typename _Tp>
00216       struct __mv_iter_traits
00217       {
00218         typedef typename _Tp::value_type value_type;
00219         typedef typename _Tp::difference_type difference_type;
00220       };
00221 
00222     template<typename _Tp>
00223       struct __mv_iter_traits<_Tp*>
00224       {
00225         typedef _Tp value_type;
00226         typedef ptrdiff_t difference_type;
00227       };
00228 
00229     enum 
00230       { 
00231         bits_per_byte = 8,
00232         bits_per_block = sizeof(size_t) * size_t(bits_per_byte) 
00233       };
00234 
00235     template<typename _ForwardIterator, typename _Tp, typename _Compare>
00236       _ForwardIterator
00237       __lower_bound(_ForwardIterator __first, _ForwardIterator __last,
00238                     const _Tp& __val, _Compare __comp)
00239       {
00240         typedef typename __mv_iter_traits<_ForwardIterator>::difference_type
00241           _DistanceType;
00242 
00243         _DistanceType __len = __last - __first;
00244         _DistanceType __half;
00245         _ForwardIterator __middle;
00246 
00247         while (__len > 0)
00248           {
00249             __half = __len >> 1;
00250             __middle = __first;
00251             __middle += __half;
00252             if (__comp(*__middle, __val))
00253               {
00254                 __first = __middle;
00255                 ++__first;
00256                 __len = __len - __half - 1;
00257               }
00258             else
00259               __len = __half;
00260           }
00261         return __first;
00262       }
00263 
00264     /** @brief The number of Blocks pointed to by the address pair
00265      *  passed to the function.
00266      */
00267     template<typename _AddrPair>
00268       inline size_t
00269       __num_blocks(_AddrPair __ap)
00270       { return (__ap.second - __ap.first) + 1; }
00271 
00272     /** @brief The number of Bit-maps pointed to by the address pair
00273      *  passed to the function.
00274      */
00275     template<typename _AddrPair>
00276       inline size_t
00277       __num_bitmaps(_AddrPair __ap)
00278       { return __num_blocks(__ap) / size_t(bits_per_block); }
00279 
00280     // _Tp should be a pointer type.
00281     template<typename _Tp>
00282       class _Inclusive_between 
00283       : public std::unary_function<typename std::pair<_Tp, _Tp>, bool>
00284       {
00285         typedef _Tp pointer;
00286         pointer _M_ptr_value;
00287         typedef typename std::pair<_Tp, _Tp> _Block_pair;
00288         
00289       public:
00290         _Inclusive_between(pointer __ptr) : _M_ptr_value(__ptr) 
00291         { }
00292         
00293         bool 
00294         operator()(_Block_pair __bp) const throw()
00295         {
00296           if (std::less_equal<pointer>()(_M_ptr_value, __bp.second) 
00297               && std::greater_equal<pointer>()(_M_ptr_value, __bp.first))
00298             return true;
00299           else
00300             return false;
00301         }
00302       };
00303   
00304     // Used to pass a Functor to functions by reference.
00305     template<typename _Functor>
00306       class _Functor_Ref 
00307       : public std::unary_function<typename _Functor::argument_type, 
00308                                    typename _Functor::result_type>
00309       {
00310         _Functor& _M_fref;
00311         
00312       public:
00313         typedef typename _Functor::argument_type argument_type;
00314         typedef typename _Functor::result_type result_type;
00315 
00316         _Functor_Ref(_Functor& __fref) : _M_fref(__fref) 
00317         { }
00318 
00319         result_type 
00320         operator()(argument_type __arg) 
00321         { return _M_fref(__arg); }
00322       };
00323 
00324     /** @class  _Ffit_finder bitmap_allocator.h bitmap_allocator.h
00325      *
00326      *  @brief  The class which acts as a predicate for applying the
00327      *  first-fit memory allocation policy for the bitmap allocator.
00328      */
00329     // _Tp should be a pointer type, and _Alloc is the Allocator for
00330     // the vector.
00331     template<typename _Tp>
00332       class _Ffit_finder 
00333       : public std::unary_function<typename std::pair<_Tp, _Tp>, bool>
00334       {
00335         typedef typename std::pair<_Tp, _Tp> _Block_pair;
00336         typedef typename __detail::__mini_vector<_Block_pair> _BPVector;
00337         typedef typename _BPVector::difference_type _Counter_type;
00338 
00339         size_t* _M_pbitmap;
00340         _Counter_type _M_data_offset;
00341 
00342       public:
00343         _Ffit_finder() : _M_pbitmap(0), _M_data_offset(0)
00344         { }
00345 
00346         bool 
00347         operator()(_Block_pair __bp) throw()
00348         {
00349           // Set the _rover to the last physical location bitmap,
00350           // which is the bitmap which belongs to the first free
00351           // block. Thus, the bitmaps are in exact reverse order of
00352           // the actual memory layout. So, we count down the bitmaps,
00353           // which is the same as moving up the memory.
00354 
00355           // If the used count stored at the start of the Bit Map headers
00356           // is equal to the number of Objects that the current Block can
00357           // store, then there is definitely no space for another single
00358           // object, so just return false.
00359           _Counter_type __diff = __detail::__num_bitmaps(__bp);
00360 
00361           if (*(reinterpret_cast<size_t*>
00362                 (__bp.first) - (__diff + 1)) == __detail::__num_blocks(__bp))
00363             return false;
00364 
00365           size_t* __rover = reinterpret_cast<size_t*>(__bp.first) - 1;
00366 
00367           for (_Counter_type __i = 0; __i < __diff; ++__i)
00368             {
00369               _M_data_offset = __i;
00370               if (*__rover)
00371                 {
00372                   _M_pbitmap = __rover;
00373                   return true;
00374                 }
00375               --__rover;
00376             }
00377           return false;
00378         }
00379     
00380         size_t*
00381         _M_get() const throw()
00382         { return _M_pbitmap; }
00383 
00384         _Counter_type
00385         _M_offset() const throw()
00386         { return _M_data_offset * size_t(bits_per_block); }
00387       };
00388 
00389     /** @class  _Bitmap_counter bitmap_allocator.h bitmap_allocator.h
00390      *
00391      *  @brief  The bitmap counter which acts as the bitmap
00392      *  manipulator, and manages the bit-manipulation functions and
00393      *  the searching and identification functions on the bit-map.
00394      */
00395     // _Tp should be a pointer type.
00396     template<typename _Tp>
00397       class _Bitmap_counter
00398       {
00399         typedef typename
00400         __detail::__mini_vector<typename std::pair<_Tp, _Tp> > _BPVector;
00401         typedef typename _BPVector::size_type _Index_type;
00402         typedef _Tp pointer;
00403 
00404         _BPVector& _M_vbp;
00405         size_t* _M_curr_bmap;
00406         size_t* _M_last_bmap_in_block;
00407         _Index_type _M_curr_index;
00408     
00409       public:
00410         // Use the 2nd parameter with care. Make sure that such an
00411         // entry exists in the vector before passing that particular
00412         // index to this ctor.
00413         _Bitmap_counter(_BPVector& Rvbp, long __index = -1) : _M_vbp(Rvbp)
00414         { this->_M_reset(__index); }
00415     
00416         void 
00417         _M_reset(long __index = -1) throw()
00418         {
00419           if (__index == -1)
00420             {
00421               _M_curr_bmap = 0;
00422               _M_curr_index = static_cast<_Index_type>(-1);
00423               return;
00424             }
00425 
00426           _M_curr_index = __index;
00427           _M_curr_bmap = reinterpret_cast<size_t*>
00428             (_M_vbp[_M_curr_index].first) - 1;
00429           
00430           _GLIBCXX_DEBUG_ASSERT(__index <= (long)_M_vbp.size() - 1);
00431         
00432           _M_last_bmap_in_block = _M_curr_bmap
00433             - ((_M_vbp[_M_curr_index].second 
00434                 - _M_vbp[_M_curr_index].first + 1) 
00435                / size_t(bits_per_block) - 1);
00436         }
00437     
00438         // Dangerous Function! Use with extreme care. Pass to this
00439         // function ONLY those values that are known to be correct,
00440         // otherwise this will mess up big time.
00441         void
00442         _M_set_internal_bitmap(size_t* __new_internal_marker) throw()
00443         { _M_curr_bmap = __new_internal_marker; }
00444     
00445         bool
00446         _M_finished() const throw()
00447         { return(_M_curr_bmap == 0); }
00448     
00449         _Bitmap_counter&
00450         operator++() throw()
00451         {
00452           if (_M_curr_bmap == _M_last_bmap_in_block)
00453             {
00454               if (++_M_curr_index == _M_vbp.size())
00455                 _M_curr_bmap = 0;
00456               else
00457                 this->_M_reset(_M_curr_index);
00458             }
00459           else
00460             --_M_curr_bmap;
00461           return *this;
00462         }
00463     
00464         size_t*
00465         _M_get() const throw()
00466         { return _M_curr_bmap; }
00467     
00468         pointer 
00469         _M_base() const throw()
00470         { return _M_vbp[_M_curr_index].first; }
00471 
00472         _Index_type
00473         _M_offset() const throw()
00474         {
00475           return size_t(bits_per_block)
00476             * ((reinterpret_cast<size_t*>(this->_M_base()) 
00477                 - _M_curr_bmap) - 1);
00478         }
00479     
00480         _Index_type
00481         _M_where() const throw()
00482         { return _M_curr_index; }
00483       };
00484 
00485     /** @brief  Mark a memory address as allocated by re-setting the
00486      *  corresponding bit in the bit-map.
00487      */
00488     inline void 
00489     __bit_allocate(size_t* __pbmap, size_t __pos) throw()
00490     {
00491       size_t __mask = 1 << __pos;
00492       __mask = ~__mask;
00493       *__pbmap &= __mask;
00494     }
00495   
00496     /** @brief  Mark a memory address as free by setting the
00497      *  corresponding bit in the bit-map.
00498      */
00499     inline void 
00500     __bit_free(size_t* __pbmap, size_t __pos) throw()
00501     {
00502       size_t __mask = 1 << __pos;
00503       *__pbmap |= __mask;
00504     }
00505   } // namespace __detail
00506 
00507   /** @brief  Generic Version of the bsf instruction.
00508    */
00509   inline size_t 
00510   _Bit_scan_forward(size_t __num)
00511   { return static_cast<size_t>(__builtin_ctzl(__num)); }
00512 
00513   /** @class  free_list bitmap_allocator.h bitmap_allocator.h
00514    *
00515    *  @brief  The free list class for managing chunks of memory to be
00516    *  given to and returned by the bitmap_allocator.
00517    */
00518   class free_list
00519   {
00520   public:
00521     typedef size_t*                             value_type;
00522     typedef __detail::__mini_vector<value_type> vector_type;
00523     typedef vector_type::iterator               iterator;
00524     typedef __mutex                             __mutex_type;
00525 
00526   private:
00527     struct _LT_pointer_compare
00528     {
00529       bool
00530       operator()(const size_t* __pui, 
00531                  const size_t __cui) const throw()
00532       { return *__pui < __cui; }
00533     };
00534 
00535 #if defined __GTHREADS
00536     __mutex_type&
00537     _M_get_mutex()
00538     {
00539       static __mutex_type _S_mutex;
00540       return _S_mutex;
00541     }
00542 #endif
00543 
00544     vector_type&
00545     _M_get_free_list()
00546     {
00547       static vector_type _S_free_list;
00548       return _S_free_list;
00549     }
00550 
00551     /** @brief  Performs validation of memory based on their size.
00552      *
00553      *  @param  __addr The pointer to the memory block to be
00554      *  validated.
00555      *
00556      *  Validates the memory block passed to this function and
00557      *  appropriately performs the action of managing the free list of
00558      *  blocks by adding this block to the free list or deleting this
00559      *  or larger blocks from the free list.
00560      */
00561     void
00562     _M_validate(size_t* __addr) throw()
00563     {
00564       vector_type& __free_list = _M_get_free_list();
00565       const vector_type::size_type __max_size = 64;
00566       if (__free_list.size() >= __max_size)
00567         {
00568           // Ok, the threshold value has been reached.  We determine
00569           // which block to remove from the list of free blocks.
00570           if (*__addr >= *__free_list.back())
00571             {
00572               // Ok, the new block is greater than or equal to the
00573               // last block in the list of free blocks. We just free
00574               // the new block.
00575               ::operator delete(static_cast<void*>(__addr));
00576               return;
00577             }
00578           else
00579             {
00580               // Deallocate the last block in the list of free lists,
00581               // and insert the new one in its correct position.
00582               ::operator delete(static_cast<void*>(__free_list.back()));
00583               __free_list.pop_back();
00584             }
00585         }
00586           
00587       // Just add the block to the list of free lists unconditionally.
00588       iterator __temp = __detail::__lower_bound
00589         (__free_list.begin(), __free_list.end(), 
00590          *__addr, _LT_pointer_compare());
00591 
00592       // We may insert the new free list before _temp;
00593       __free_list.insert(__temp, __addr);
00594     }
00595 
00596     /** @brief  Decides whether the wastage of memory is acceptable for
00597      *  the current memory request and returns accordingly.
00598      *
00599      *  @param __block_size The size of the block available in the free
00600      *  list.
00601      *
00602      *  @param __required_size The required size of the memory block.
00603      *
00604      *  @return true if the wastage incurred is acceptable, else returns
00605      *  false.
00606      */
00607     bool 
00608     _M_should_i_give(size_t __block_size, 
00609                      size_t __required_size) throw()
00610     {
00611       const size_t __max_wastage_percentage = 36;
00612       if (__block_size >= __required_size && 
00613           (((__block_size - __required_size) * 100 / __block_size)
00614            < __max_wastage_percentage))
00615         return true;
00616       else
00617         return false;
00618     }
00619 
00620   public:
00621     /** @brief This function returns the block of memory to the
00622      *  internal free list.
00623      *
00624      *  @param  __addr The pointer to the memory block that was given
00625      *  by a call to the _M_get function.
00626      */
00627     inline void 
00628     _M_insert(size_t* __addr) throw()
00629     {
00630 #if defined __GTHREADS
00631       __scoped_lock __bfl_lock(_M_get_mutex());
00632 #endif
00633       // Call _M_validate to decide what should be done with
00634       // this particular free list.
00635       this->_M_validate(reinterpret_cast<size_t*>(__addr) - 1);
00636       // See discussion as to why this is 1!
00637     }
00638     
00639     /** @brief  This function gets a block of memory of the specified
00640      *  size from the free list.
00641      *
00642      *  @param  __sz The size in bytes of the memory required.
00643      *
00644      *  @return  A pointer to the new memory block of size at least
00645      *  equal to that requested.
00646      */
00647     size_t*
00648     _M_get(size_t __sz) _GLIBCXX_THROW(std::bad_alloc);
00649 
00650     /** @brief  This function just clears the internal Free List, and
00651      *  gives back all the memory to the OS.
00652      */
00653     void 
00654     _M_clear();
00655   };
00656 
00657 
00658   // Forward declare the class.
00659   template<typename _Tp> 
00660     class bitmap_allocator;
00661 
00662   // Specialize for void:
00663   template<>
00664     class bitmap_allocator<void>
00665     {
00666     public:
00667       typedef void*       pointer;
00668       typedef const void* const_pointer;
00669 
00670       // Reference-to-void members are impossible.
00671       typedef void  value_type;
00672       template<typename _Tp1>
00673         struct rebind
00674         {
00675           typedef bitmap_allocator<_Tp1> other;
00676         };
00677     };
00678 
00679   /**
00680    * @brief Bitmap Allocator, primary template.
00681    * @ingroup allocators
00682    */
00683   template<typename _Tp>
00684     class bitmap_allocator : private free_list
00685     {
00686     public:
00687       typedef size_t                    size_type;
00688       typedef ptrdiff_t                 difference_type;
00689       typedef _Tp*                      pointer;
00690       typedef const _Tp*                const_pointer;
00691       typedef _Tp&                      reference;
00692       typedef const _Tp&                const_reference;
00693       typedef _Tp                       value_type;
00694       typedef free_list::__mutex_type   __mutex_type;
00695 
00696       template<typename _Tp1>
00697         struct rebind
00698         {
00699           typedef bitmap_allocator<_Tp1> other;
00700         };
00701 
00702 #if __cplusplus >= 201103L
00703       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00704       // 2103. propagate_on_container_move_assignment
00705       typedef std::true_type propagate_on_container_move_assignment;
00706 #endif
00707 
00708     private:
00709       template<size_t _BSize, size_t _AlignSize>
00710         struct aligned_size
00711         {
00712           enum
00713             { 
00714               modulus = _BSize % _AlignSize,
00715               value = _BSize + (modulus ? _AlignSize - (modulus) : 0)
00716             };
00717         };
00718 
00719       struct _Alloc_block
00720       {
00721         char __M_unused[aligned_size<sizeof(value_type),
00722                         _BALLOC_ALIGN_BYTES>::value];
00723       };
00724 
00725 
00726       typedef typename std::pair<_Alloc_block*, _Alloc_block*> _Block_pair;
00727 
00728       typedef typename __detail::__mini_vector<_Block_pair> _BPVector;
00729       typedef typename _BPVector::iterator _BPiter;
00730 
00731       template<typename _Predicate>
00732         static _BPiter
00733         _S_find(_Predicate __p)
00734         {
00735           _BPiter __first = _S_mem_blocks.begin();
00736           while (__first != _S_mem_blocks.end() && !__p(*__first))
00737             ++__first;
00738           return __first;
00739         }
00740 
00741 #if defined _GLIBCXX_DEBUG
00742       // Complexity: O(lg(N)). Where, N is the number of block of size
00743       // sizeof(value_type).
00744       void 
00745       _S_check_for_free_blocks() throw()
00746       {
00747         typedef typename __detail::_Ffit_finder<_Alloc_block*> _FFF;
00748         _BPiter __bpi = _S_find(_FFF());
00749 
00750         _GLIBCXX_DEBUG_ASSERT(__bpi == _S_mem_blocks.end());
00751       }
00752 #endif
00753 
00754       /** @brief  Responsible for exponentially growing the internal
00755        *  memory pool.
00756        *
00757        *  @throw  std::bad_alloc. If memory cannot be allocated.
00758        *
00759        *  Complexity: O(1), but internally depends upon the
00760        *  complexity of the function free_list::_M_get. The part where
00761        *  the bitmap headers are written has complexity: O(X),where X
00762        *  is the number of blocks of size sizeof(value_type) within
00763        *  the newly acquired block. Having a tight bound.
00764        */
00765       void 
00766       _S_refill_pool() _GLIBCXX_THROW(std::bad_alloc)
00767       {
00768 #if defined _GLIBCXX_DEBUG
00769         _S_check_for_free_blocks();
00770 #endif
00771 
00772         const size_t __num_bitmaps = (_S_block_size
00773                                       / size_t(__detail::bits_per_block));
00774         const size_t __size_to_allocate = sizeof(size_t) 
00775           + _S_block_size * sizeof(_Alloc_block) 
00776           + __num_bitmaps * sizeof(size_t);
00777 
00778         size_t* __temp =
00779           reinterpret_cast<size_t*>(this->_M_get(__size_to_allocate));
00780         *__temp = 0;
00781         ++__temp;
00782 
00783         // The Header information goes at the Beginning of the Block.
00784         _Block_pair __bp = 
00785           std::make_pair(reinterpret_cast<_Alloc_block*>
00786                          (__temp + __num_bitmaps), 
00787                          reinterpret_cast<_Alloc_block*>
00788                          (__temp + __num_bitmaps) 
00789                          + _S_block_size - 1);
00790         
00791         // Fill the Vector with this information.
00792         _S_mem_blocks.push_back(__bp);
00793 
00794         for (size_t __i = 0; __i < __num_bitmaps; ++__i)
00795           __temp[__i] = ~static_cast<size_t>(0); // 1 Indicates all Free.
00796 
00797         _S_block_size *= 2;
00798       }
00799 
00800       static _BPVector _S_mem_blocks;
00801       static size_t _S_block_size;
00802       static __detail::_Bitmap_counter<_Alloc_block*> _S_last_request;
00803       static typename _BPVector::size_type _S_last_dealloc_index;
00804 #if defined __GTHREADS
00805       static __mutex_type _S_mut;
00806 #endif
00807 
00808     public:
00809 
00810       /** @brief  Allocates memory for a single object of size
00811        *  sizeof(_Tp).
00812        *
00813        *  @throw  std::bad_alloc. If memory cannot be allocated.
00814        *
00815        *  Complexity: Worst case complexity is O(N), but that
00816        *  is hardly ever hit. If and when this particular case is
00817        *  encountered, the next few cases are guaranteed to have a
00818        *  worst case complexity of O(1)!  That's why this function
00819        *  performs very well on average. You can consider this
00820        *  function to have a complexity referred to commonly as:
00821        *  Amortized Constant time.
00822        */
00823       pointer 
00824       _M_allocate_single_object() _GLIBCXX_THROW(std::bad_alloc)
00825       {
00826 #if defined __GTHREADS
00827         __scoped_lock __bit_lock(_S_mut);
00828 #endif
00829 
00830         // The algorithm is something like this: The last_request
00831         // variable points to the last accessed Bit Map. When such a
00832         // condition occurs, we try to find a free block in the
00833         // current bitmap, or succeeding bitmaps until the last bitmap
00834         // is reached. If no free block turns up, we resort to First
00835         // Fit method.
00836 
00837         // WARNING: Do not re-order the condition in the while
00838         // statement below, because it relies on C++'s short-circuit
00839         // evaluation. The return from _S_last_request->_M_get() will
00840         // NOT be dereference able if _S_last_request->_M_finished()
00841         // returns true. This would inevitably lead to a NULL pointer
00842         // dereference if tinkered with.
00843         while (_S_last_request._M_finished() == false
00844                && (*(_S_last_request._M_get()) == 0))
00845           _S_last_request.operator++();
00846 
00847         if (__builtin_expect(_S_last_request._M_finished() == true, false))
00848           {
00849             // Fall Back to First Fit algorithm.
00850             typedef typename __detail::_Ffit_finder<_Alloc_block*> _FFF;
00851             _FFF __fff;
00852             _BPiter __bpi = _S_find(__detail::_Functor_Ref<_FFF>(__fff));
00853 
00854             if (__bpi != _S_mem_blocks.end())
00855               {
00856                 // Search was successful. Ok, now mark the first bit from
00857                 // the right as 0, meaning Allocated. This bit is obtained
00858                 // by calling _M_get() on __fff.
00859                 size_t __nz_bit = _Bit_scan_forward(*__fff._M_get());
00860                 __detail::__bit_allocate(__fff._M_get(), __nz_bit);
00861 
00862                 _S_last_request._M_reset(__bpi - _S_mem_blocks.begin());
00863 
00864                 // Now, get the address of the bit we marked as allocated.
00865                 pointer __ret = reinterpret_cast<pointer>
00866                   (__bpi->first + __fff._M_offset() + __nz_bit);
00867                 size_t* __puse_count = 
00868                   reinterpret_cast<size_t*>
00869                   (__bpi->first) - (__detail::__num_bitmaps(*__bpi) + 1);
00870                 
00871                 ++(*__puse_count);
00872                 return __ret;
00873               }
00874             else
00875               {
00876                 // Search was unsuccessful. We Add more memory to the
00877                 // pool by calling _S_refill_pool().
00878                 _S_refill_pool();
00879 
00880                 // _M_Reset the _S_last_request structure to the first
00881                 // free block's bit map.
00882                 _S_last_request._M_reset(_S_mem_blocks.size() - 1);
00883 
00884                 // Now, mark that bit as allocated.
00885               }
00886           }
00887 
00888         // _S_last_request holds a pointer to a valid bit map, that
00889         // points to a free block in memory.
00890         size_t __nz_bit = _Bit_scan_forward(*_S_last_request._M_get());
00891         __detail::__bit_allocate(_S_last_request._M_get(), __nz_bit);
00892 
00893         pointer __ret = reinterpret_cast<pointer>
00894           (_S_last_request._M_base() + _S_last_request._M_offset() + __nz_bit);
00895 
00896         size_t* __puse_count = reinterpret_cast<size_t*>
00897           (_S_mem_blocks[_S_last_request._M_where()].first)
00898           - (__detail::
00899              __num_bitmaps(_S_mem_blocks[_S_last_request._M_where()]) + 1);
00900 
00901         ++(*__puse_count);
00902         return __ret;
00903       }
00904 
00905       /** @brief  Deallocates memory that belongs to a single object of
00906        *  size sizeof(_Tp).
00907        *
00908        *  Complexity: O(lg(N)), but the worst case is not hit
00909        *  often!  This is because containers usually deallocate memory
00910        *  close to each other and this case is handled in O(1) time by
00911        *  the deallocate function.
00912        */
00913       void 
00914       _M_deallocate_single_object(pointer __p) throw()
00915       {
00916 #if defined __GTHREADS
00917         __scoped_lock __bit_lock(_S_mut);
00918 #endif
00919         _Alloc_block* __real_p = reinterpret_cast<_Alloc_block*>(__p);
00920 
00921         typedef typename _BPVector::iterator _Iterator;
00922         typedef typename _BPVector::difference_type _Difference_type;
00923 
00924         _Difference_type __diff;
00925         long __displacement;
00926 
00927         _GLIBCXX_DEBUG_ASSERT(_S_last_dealloc_index >= 0);
00928 
00929         __detail::_Inclusive_between<_Alloc_block*> __ibt(__real_p);
00930         if (__ibt(_S_mem_blocks[_S_last_dealloc_index]))
00931           {
00932             _GLIBCXX_DEBUG_ASSERT(_S_last_dealloc_index
00933                                   <= _S_mem_blocks.size() - 1);
00934 
00935             // Initial Assumption was correct!
00936             __diff = _S_last_dealloc_index;
00937             __displacement = __real_p - _S_mem_blocks[__diff].first;
00938           }
00939         else
00940           {
00941             _Iterator _iter = _S_find(__ibt);
00942 
00943             _GLIBCXX_DEBUG_ASSERT(_iter != _S_mem_blocks.end());
00944 
00945             __diff = _iter - _S_mem_blocks.begin();
00946             __displacement = __real_p - _S_mem_blocks[__diff].first;
00947             _S_last_dealloc_index = __diff;
00948           }
00949 
00950         // Get the position of the iterator that has been found.
00951         const size_t __rotate = (__displacement
00952                                  % size_t(__detail::bits_per_block));
00953         size_t* __bitmapC = 
00954           reinterpret_cast<size_t*>
00955           (_S_mem_blocks[__diff].first) - 1;
00956         __bitmapC -= (__displacement / size_t(__detail::bits_per_block));
00957       
00958         __detail::__bit_free(__bitmapC, __rotate);
00959         size_t* __puse_count = reinterpret_cast<size_t*>
00960           (_S_mem_blocks[__diff].first)
00961           - (__detail::__num_bitmaps(_S_mem_blocks[__diff]) + 1);
00962         
00963         _GLIBCXX_DEBUG_ASSERT(*__puse_count != 0);
00964 
00965         --(*__puse_count);
00966 
00967         if (__builtin_expect(*__puse_count == 0, false))
00968           {
00969             _S_block_size /= 2;
00970           
00971             // We can safely remove this block.
00972             // _Block_pair __bp = _S_mem_blocks[__diff];
00973             this->_M_insert(__puse_count);
00974             _S_mem_blocks.erase(_S_mem_blocks.begin() + __diff);
00975 
00976             // Reset the _S_last_request variable to reflect the
00977             // erased block. We do this to protect future requests
00978             // after the last block has been removed from a particular
00979             // memory Chunk, which in turn has been returned to the
00980             // free list, and hence had been erased from the vector,
00981             // so the size of the vector gets reduced by 1.
00982             if ((_Difference_type)_S_last_request._M_where() >= __diff--)
00983               _S_last_request._M_reset(__diff); 
00984 
00985             // If the Index into the vector of the region of memory
00986             // that might hold the next address that will be passed to
00987             // deallocated may have been invalidated due to the above
00988             // erase procedure being called on the vector, hence we
00989             // try to restore this invariant too.
00990             if (_S_last_dealloc_index >= _S_mem_blocks.size())
00991               {
00992                 _S_last_dealloc_index =(__diff != -1 ? __diff : 0);
00993                 _GLIBCXX_DEBUG_ASSERT(_S_last_dealloc_index >= 0);
00994               }
00995           }
00996       }
00997 
00998     public:
00999       bitmap_allocator() _GLIBCXX_USE_NOEXCEPT
01000       { }
01001 
01002       bitmap_allocator(const bitmap_allocator&) _GLIBCXX_USE_NOEXCEPT
01003       { }
01004 
01005       template<typename _Tp1>
01006         bitmap_allocator(const bitmap_allocator<_Tp1>&) _GLIBCXX_USE_NOEXCEPT
01007         { }
01008 
01009       ~bitmap_allocator() _GLIBCXX_USE_NOEXCEPT
01010       { }
01011 
01012       _GLIBCXX_NODISCARD pointer 
01013       allocate(size_type __n)
01014       {
01015         if (__n > this->max_size())
01016           std::__throw_bad_alloc();
01017 
01018 #if __cpp_aligned_new
01019         if (alignof(value_type) > __STDCPP_DEFAULT_NEW_ALIGNMENT__)
01020           {
01021             const size_type __b = __n * sizeof(value_type);
01022             std::align_val_t __al = std::align_val_t(alignof(value_type));
01023             return static_cast<pointer>(::operator new(__b, __al));
01024           }
01025 #endif
01026 
01027         if (__builtin_expect(__n == 1, true))
01028           return this->_M_allocate_single_object();
01029         else
01030           { 
01031             const size_type __b = __n * sizeof(value_type);
01032             return reinterpret_cast<pointer>(::operator new(__b));
01033           }
01034       }
01035 
01036       _GLIBCXX_NODISCARD pointer 
01037       allocate(size_type __n, typename bitmap_allocator<void>::const_pointer)
01038       { return allocate(__n); }
01039 
01040       void 
01041       deallocate(pointer __p, size_type __n) throw()
01042       {
01043         if (__builtin_expect(__p != 0, true))
01044           {
01045 #if __cpp_aligned_new
01046             // Types with extended alignment are handled by operator delete.
01047             if (alignof(value_type) > __STDCPP_DEFAULT_NEW_ALIGNMENT__)
01048               {
01049                 ::operator delete(__p, std::align_val_t(alignof(value_type)));
01050                 return;
01051               }
01052 #endif
01053 
01054             if (__builtin_expect(__n == 1, true))
01055               this->_M_deallocate_single_object(__p);
01056             else
01057 	      ::operator delete(__p);
01058           }
01059       }
01060 
01061       pointer 
01062       address(reference __r) const _GLIBCXX_NOEXCEPT
01063       { return std::__addressof(__r); }
01064 
01065       const_pointer 
01066       address(const_reference __r) const _GLIBCXX_NOEXCEPT
01067       { return std::__addressof(__r); }
01068 
01069       size_type 
01070       max_size() const _GLIBCXX_USE_NOEXCEPT
01071       { return size_type(-1) / sizeof(value_type); }
01072 
01073 #if __cplusplus >= 201103L
01074       template<typename _Up, typename... _Args>
01075         void
01076         construct(_Up* __p, _Args&&... __args)
01077         { ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }
01078 
01079       template<typename _Up>
01080         void 
01081         destroy(_Up* __p)
01082         { __p->~_Up(); }
01083 #else
01084       void 
01085       construct(pointer __p, const_reference __data)
01086       { ::new((void *)__p) value_type(__data); }
01087 
01088       void 
01089       destroy(pointer __p)
01090       { __p->~value_type(); }
01091 #endif
01092     };
01093 
01094   template<typename _Tp1, typename _Tp2>
01095     bool 
01096     operator==(const bitmap_allocator<_Tp1>&, 
01097                const bitmap_allocator<_Tp2>&) throw()
01098     { return true; }
01099   
01100   template<typename _Tp1, typename _Tp2>
01101     bool 
01102     operator!=(const bitmap_allocator<_Tp1>&, 
01103                const bitmap_allocator<_Tp2>&) throw() 
01104   { return false; }
01105 
01106   // Static member definitions.
01107   template<typename _Tp>
01108     typename bitmap_allocator<_Tp>::_BPVector
01109     bitmap_allocator<_Tp>::_S_mem_blocks;
01110 
01111   template<typename _Tp>
01112     size_t bitmap_allocator<_Tp>::_S_block_size = 
01113     2 * size_t(__detail::bits_per_block);
01114 
01115   template<typename _Tp>
01116     typename bitmap_allocator<_Tp>::_BPVector::size_type 
01117     bitmap_allocator<_Tp>::_S_last_dealloc_index = 0;
01118 
01119   template<typename _Tp>
01120     __detail::_Bitmap_counter
01121       <typename bitmap_allocator<_Tp>::_Alloc_block*>
01122     bitmap_allocator<_Tp>::_S_last_request(_S_mem_blocks);
01123 
01124 #if defined __GTHREADS
01125   template<typename _Tp>
01126     typename bitmap_allocator<_Tp>::__mutex_type
01127     bitmap_allocator<_Tp>::_S_mut;
01128 #endif
01129 
01130 _GLIBCXX_END_NAMESPACE_VERSION
01131 } // namespace __gnu_cxx
01132 
01133 #endif