libstdc++
|
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