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