bitmap_allocator.h

00001 // Bitmapped Allocator. -*- C++ -*- 00002 00003 // Copyright (C) 2004 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 2, 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 // You should have received a copy of the GNU General Public License along 00017 // with this library; see the file COPYING. If not, write to the Free 00018 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 00019 // USA. 00020 00021 // As a special exception, you may use this file as part of a free software 00022 // library without restriction. Specifically, if other files instantiate 00023 // templates or use macros or inline functions from this file, or you compile 00024 // this file and link it with other files to produce an executable, this 00025 // file does not by itself cause the resulting executable to be covered by 00026 // the GNU General Public License. This exception does not however 00027 // invalidate any other reasons why the executable file might be covered by 00028 // the GNU General Public License. 00029 00030 00031 00032 #if !defined _BITMAP_ALLOCATOR_H 00033 #define _BITMAP_ALLOCATOR_H 1 00034 00035 #include <cstddef> 00036 //For std::size_t, and ptrdiff_t. 00037 #include <utility> 00038 //For std::pair. 00039 #include <algorithm> 00040 //std::find_if, and std::lower_bound. 00041 #include <vector> 00042 //For the free list of exponentially growing memory blocks. At max, 00043 //size of the vector should be not more than the number of bits in an 00044 //integer or an unsigned integer. 00045 #include <functional> 00046 //For greater_equal, and less_equal. 00047 #include <new> 00048 //For operator new. 00049 #include <bits/gthr.h> 00050 //For __gthread_mutex_t, __gthread_mutex_lock and __gthread_mutex_unlock. 00051 #include <ext/new_allocator.h> 00052 //For __gnu_cxx::new_allocator for std::vector. 00053 00054 #include <cassert> 00055 #define NDEBUG 00056 00057 //#define CHECK_FOR_ERRORS 00058 //#define __CPU_HAS_BACKWARD_BRANCH_PREDICTION 00059 00060 namespace __gnu_cxx 00061 { 00062 namespace { 00063 #if defined __GTHREADS 00064 bool const __threads_enabled = __gthread_active_p(); 00065 #endif 00066 00067 } 00068 00069 #if defined __GTHREADS 00070 class _Mutex { 00071 __gthread_mutex_t _M_mut; 00072 //Prevent Copying and assignment. 00073 _Mutex (_Mutex const&); 00074 _Mutex& operator= (_Mutex const&); 00075 public: 00076 _Mutex () 00077 { 00078 if (__threads_enabled) 00079 { 00080 #if !defined __GTHREAD_MUTEX_INIT 00081 __GTHREAD_MUTEX_INIT_FUNCTION(&_M_mut); 00082 #else 00083 __gthread_mutex_t __mtemp = __GTHREAD_MUTEX_INIT; 00084 _M_mut = __mtemp; 00085 #endif 00086 } 00087 } 00088 ~_Mutex () 00089 { 00090 //Gthreads does not define a Mutex Destruction Function. 00091 } 00092 __gthread_mutex_t *_M_get() { return &_M_mut; } 00093 }; 00094 00095 class _Lock { 00096 _Mutex* _M_pmt; 00097 bool _M_locked; 00098 //Prevent Copying and assignment. 00099 _Lock (_Lock const&); 00100 _Lock& operator= (_Lock const&); 00101 public: 00102 _Lock(_Mutex* __mptr) 00103 : _M_pmt(__mptr), _M_locked(false) 00104 { this->_M_lock(); } 00105 void _M_lock() 00106 { 00107 if (__threads_enabled) 00108 { 00109 _M_locked = true; 00110 __gthread_mutex_lock(_M_pmt->_M_get()); 00111 } 00112 } 00113 void _M_unlock() 00114 { 00115 if (__threads_enabled) 00116 { 00117 if (__builtin_expect(_M_locked, true)) 00118 { 00119 __gthread_mutex_unlock(_M_pmt->_M_get()); 00120 _M_locked = false; 00121 } 00122 } 00123 } 00124 ~_Lock() { this->_M_unlock(); } 00125 }; 00126 #endif 00127 00128 00129 00130 namespace __aux_balloc { 00131 static const unsigned int _Bits_Per_Byte = 8; 00132 static const unsigned int _Bits_Per_Block = sizeof(unsigned int) * _Bits_Per_Byte; 00133 00134 template <typename _Addr_Pair_t> 00135 inline size_t __balloc_num_blocks (_Addr_Pair_t __ap) 00136 { 00137 return (__ap.second - __ap.first) + 1; 00138 } 00139 00140 template <typename _Addr_Pair_t> 00141 inline size_t __balloc_num_bit_maps (_Addr_Pair_t __ap) 00142 { 00143 return __balloc_num_blocks(__ap) / _Bits_Per_Block; 00144 } 00145 00146 //T should be a pointer type. 00147 template <typename _Tp> 00148 class _Inclusive_between : public std::unary_function<typename std::pair<_Tp, _Tp>, bool> { 00149 typedef _Tp pointer; 00150 pointer _M_ptr_value; 00151 typedef typename std::pair<_Tp, _Tp> _Block_pair; 00152 00153 public: 00154 _Inclusive_between (pointer __ptr) : _M_ptr_value(__ptr) { } 00155 bool operator () (_Block_pair __bp) const throw () 00156 { 00157 if (std::less_equal<pointer> ()(_M_ptr_value, __bp.second) && 00158 std::greater_equal<pointer> ()(_M_ptr_value, __bp.first)) 00159 return true; 00160 else 00161 return false; 00162 } 00163 }; 00164 00165 //Used to pass a Functor to functions by reference. 00166 template <typename _Functor> 00167 class _Functor_Ref : 00168 public std::unary_function<typename _Functor::argument_type, typename _Functor::result_type> { 00169 _Functor& _M_fref; 00170 00171 public: 00172 typedef typename _Functor::argument_type argument_type; 00173 typedef typename _Functor::result_type result_type; 00174 00175 _Functor_Ref (_Functor& __fref) : _M_fref(__fref) { } 00176 result_type operator() (argument_type __arg) { return _M_fref (__arg); } 00177 }; 00178 00179 00180 //T should be a pointer type, and A is the Allocator for the vector. 00181 template <typename _Tp, typename _Alloc> 00182 class _Ffit_finder 00183 : public std::unary_function<typename std::pair<_Tp, _Tp>, bool> { 00184 typedef typename std::vector<std::pair<_Tp, _Tp>, _Alloc> _BPVector; 00185 typedef typename _BPVector::difference_type _Counter_type; 00186 typedef typename std::pair<_Tp, _Tp> _Block_pair; 00187 00188 unsigned int *_M_pbitmap; 00189 unsigned int _M_data_offset; 00190 00191 public: 00192 _Ffit_finder () 00193 : _M_pbitmap (0), _M_data_offset (0) 00194 { } 00195 00196 bool operator() (_Block_pair __bp) throw() 00197 { 00198 //Set the _rover to the last unsigned integer, which is the 00199 //bitmap to the first free block. Thus, the bitmaps are in exact 00200 //reverse order of the actual memory layout. So, we count down 00201 //the bimaps, which is the same as moving up the memory. 00202 00203 //If the used count stored at the start of the Bit Map headers 00204 //is equal to the number of Objects that the current Block can 00205 //store, then there is definitely no space for another single 00206 //object, so just return false. 00207 _Counter_type __diff = __gnu_cxx::__aux_balloc::__balloc_num_bit_maps (__bp); 00208 00209 assert (*(reinterpret_cast<unsigned int*>(__bp.first) - (__diff + 1)) <= 00210 __gnu_cxx::__aux_balloc::__balloc_num_blocks (__bp)); 00211 00212 if (*(reinterpret_cast<unsigned int*>(__bp.first) - (__diff + 1)) == 00213 __gnu_cxx::__aux_balloc::__balloc_num_blocks (__bp)) 00214 return false; 00215 00216 unsigned int *__rover = reinterpret_cast<unsigned int*>(__bp.first) - 1; 00217 for (_Counter_type __i = 0; __i < __diff; ++__i) 00218 { 00219 _M_data_offset = __i; 00220 if (*__rover) 00221 { 00222 _M_pbitmap = __rover; 00223 return true; 00224 } 00225 --__rover; 00226 } 00227 return false; 00228 } 00229 00230 unsigned int *_M_get () { return _M_pbitmap; } 00231 unsigned int _M_offset () { return _M_data_offset * _Bits_Per_Block; } 00232 }; 00233 00234 //T should be a pointer type. 00235 template <typename _Tp, typename _Alloc> 00236 class _Bit_map_counter { 00237 00238 typedef typename std::vector<std::pair<_Tp, _Tp>, _Alloc> _BPVector; 00239 typedef typename _BPVector::size_type _Index_type; 00240 typedef _Tp pointer; 00241 00242 _BPVector& _M_vbp; 00243 unsigned int *_M_curr_bmap; 00244 unsigned int *_M_last_bmap_in_block; 00245 _Index_type _M_curr_index; 00246 00247 public: 00248 //Use the 2nd parameter with care. Make sure that such an entry 00249 //exists in the vector before passing that particular index to 00250 //this ctor. 00251 _Bit_map_counter (_BPVector& Rvbp, int __index = -1) 00252 : _M_vbp(Rvbp) 00253 { 00254 this->_M_reset(__index); 00255 } 00256 00257 void _M_reset (int __index = -1) throw() 00258 { 00259 if (__index == -1) 00260 { 00261 _M_curr_bmap = 0; 00262 _M_curr_index = (_Index_type)-1; 00263 return; 00264 } 00265 00266 _M_curr_index = __index; 00267 _M_curr_bmap = reinterpret_cast<unsigned int*>(_M_vbp[_M_curr_index].first) - 1; 00268 00269 assert (__index <= (int)_M_vbp.size() - 1); 00270 00271 _M_last_bmap_in_block = _M_curr_bmap - 00272 ((_M_vbp[_M_curr_index].second - _M_vbp[_M_curr_index].first + 1) / _Bits_Per_Block - 1); 00273 } 00274 00275 //Dangerous Function! Use with extreme care. Pass to this 00276 //function ONLY those values that are known to be correct, 00277 //otherwise this will mess up big time. 00278 void _M_set_internal_bit_map (unsigned int *__new_internal_marker) throw() 00279 { 00280 _M_curr_bmap = __new_internal_marker; 00281 } 00282 00283 bool _M_finished () const throw() 00284 { 00285 return (_M_curr_bmap == 0); 00286 } 00287 00288 _Bit_map_counter& operator++ () throw() 00289 { 00290 if (_M_curr_bmap == _M_last_bmap_in_block) 00291 { 00292 if (++_M_curr_index == _M_vbp.size()) 00293 { 00294 _M_curr_bmap = 0; 00295 } 00296 else 00297 { 00298 this->_M_reset (_M_curr_index); 00299 } 00300 } 00301 else 00302 { 00303 --_M_curr_bmap; 00304 } 00305 return *this; 00306 } 00307 00308 unsigned int *_M_get () 00309 { 00310 return _M_curr_bmap; 00311 } 00312 00313 pointer _M_base () { return _M_vbp[_M_curr_index].first; } 00314 unsigned int _M_offset () 00315 { 00316 return _Bits_Per_Block * ((reinterpret_cast<unsigned int*>(this->_M_base()) - _M_curr_bmap) - 1); 00317 } 00318 00319 unsigned int _M_where () { return _M_curr_index; } 00320 }; 00321 } 00322 00323 //Generic Version of the bsf instruction. 00324 typedef unsigned int _Bit_map_type; 00325 static inline unsigned int _Bit_scan_forward (register _Bit_map_type __num) 00326 { 00327 return static_cast<unsigned int>(__builtin_ctz(__num)); 00328 } 00329 00330 struct _OOM_handler { 00331 static std::new_handler _S_old_handler; 00332 static bool _S_handled_oom; 00333 typedef void (*_FL_clear_proc)(void); 00334 static _FL_clear_proc _S_oom_fcp; 00335 00336 _OOM_handler (_FL_clear_proc __fcp) 00337 { 00338 _S_oom_fcp = __fcp; 00339 _S_old_handler = std::set_new_handler (_S_handle_oom_proc); 00340 _S_handled_oom = false; 00341 } 00342 00343 static void _S_handle_oom_proc() 00344 { 00345 _S_oom_fcp(); 00346 std::set_new_handler (_S_old_handler); 00347 _S_handled_oom = true; 00348 } 00349 00350 ~_OOM_handler () 00351 { 00352 if (!_S_handled_oom) 00353 std::set_new_handler (_S_old_handler); 00354 } 00355 }; 00356 00357 std::new_handler _OOM_handler::_S_old_handler; 00358 bool _OOM_handler::_S_handled_oom = false; 00359 _OOM_handler::_FL_clear_proc _OOM_handler::_S_oom_fcp = 0; 00360 00361 00362 class _BA_free_list_store { 00363 struct _LT_pointer_compare { 00364 template <typename _Tp> 00365 bool operator() (_Tp* __pt, _Tp const& __crt) const throw() 00366 { 00367 return *__pt < __crt; 00368 } 00369 }; 00370 00371 #if defined __GTHREADS 00372 static _Mutex _S_bfl_mutex; 00373 #endif 00374 static std::vector<unsigned int*> _S_free_list; 00375 typedef std::vector<unsigned int*>::iterator _FLIter; 00376 00377 static void _S_validate_free_list(unsigned int *__addr) throw() 00378 { 00379 const unsigned int __max_size = 64; 00380 if (_S_free_list.size() >= __max_size) 00381 { 00382 //Ok, the threshold value has been reached. 00383 //We determine which block to remove from the list of free 00384 //blocks. 00385 if (*__addr >= *_S_free_list.back()) 00386 { 00387 //Ok, the new block is greater than or equal to the last 00388 //block in the list of free blocks. We just free the new 00389 //block. 00390 operator delete((void*)__addr); 00391 return; 00392 } 00393 else 00394 { 00395 //Deallocate the last block in the list of free lists, and 00396 //insert the new one in it's correct position. 00397 operator delete((void*)_S_free_list.back()); 00398 _S_free_list.pop_back(); 00399 } 00400 } 00401 00402 //Just add the block to the list of free lists 00403 //unconditionally. 00404 _FLIter __temp = std::lower_bound(_S_free_list.begin(), _S_free_list.end(), 00405 *__addr, _LT_pointer_compare ()); 00406 //We may insert the new free list before _temp; 00407 _S_free_list.insert(__temp, __addr); 00408 } 00409 00410 static bool _S_should_i_give(unsigned int __block_size, unsigned int __required_size) throw() 00411 { 00412 const unsigned int __max_wastage_percentage = 36; 00413 if (__block_size >= __required_size && 00414 (((__block_size - __required_size) * 100 / __block_size) < __max_wastage_percentage)) 00415 return true; 00416 else 00417 return false; 00418 } 00419 00420 public: 00421 typedef _BA_free_list_store _BFL_type; 00422 00423 static inline void _S_insert_free_list(unsigned int *__addr) throw() 00424 { 00425 #if defined __GTHREADS 00426 _Lock __bfl_lock(&_S_bfl_mutex); 00427 #endif 00428 //Call _S_validate_free_list to decide what should be done with this 00429 //particular free list. 00430 _S_validate_free_list(--__addr); 00431 } 00432 00433 static unsigned int *_S_get_free_list(unsigned int __sz) throw (std::bad_alloc) 00434 { 00435 #if defined __GTHREADS 00436 _Lock __bfl_lock(&_S_bfl_mutex); 00437 #endif 00438 _FLIter __temp = std::lower_bound(_S_free_list.begin(), _S_free_list.end(), 00439 __sz, _LT_pointer_compare()); 00440 if (__temp == _S_free_list.end() || !_S_should_i_give (**__temp, __sz)) 00441 { 00442 //We hold the lock because the OOM_Handler is a stateless 00443 //entity. 00444 _OOM_handler __set_handler(_BFL_type::_S_clear); 00445 unsigned int *__ret_val = reinterpret_cast<unsigned int*> 00446 (operator new (__sz + sizeof(unsigned int))); 00447 *__ret_val = __sz; 00448 return ++__ret_val; 00449 } 00450 else 00451 { 00452 unsigned int* __ret_val = *__temp; 00453 _S_free_list.erase (__temp); 00454 return ++__ret_val; 00455 } 00456 } 00457 00458 //This function just clears the internal Free List, and gives back 00459 //all the memory to the OS. 00460 static void _S_clear() 00461 { 00462 #if defined __GTHREADS 00463 _Lock __bfl_lock(&_S_bfl_mutex); 00464 #endif 00465 _FLIter __iter = _S_free_list.begin(); 00466 while (__iter != _S_free_list.end()) 00467 { 00468 operator delete((void*)*__iter); 00469 ++__iter; 00470 } 00471 _S_free_list.clear(); 00472 } 00473 00474 }; 00475 00476 #if defined __GTHREADS 00477 _Mutex _BA_free_list_store::_S_bfl_mutex; 00478 #endif 00479 std::vector<unsigned int*> _BA_free_list_store::_S_free_list; 00480 00481 template <typename _Tp> class bitmap_allocator; 00482 // specialize for void: 00483 template <> class bitmap_allocator<void> { 00484 public: 00485 typedef void* pointer; 00486 typedef const void* const_pointer; 00487 // reference-to-void members are impossible. 00488 typedef void value_type; 00489 template <typename _Tp1> struct rebind { typedef bitmap_allocator<_Tp1> other; }; 00490 }; 00491 00492 template <typename _Tp> class bitmap_allocator : private _BA_free_list_store { 00493 public: 00494 typedef size_t size_type; 00495 typedef ptrdiff_t difference_type; 00496 typedef _Tp* pointer; 00497 typedef const _Tp* const_pointer; 00498 typedef _Tp& reference; 00499 typedef const _Tp& const_reference; 00500 typedef _Tp value_type; 00501 template <typename _Tp1> struct rebind { typedef bitmap_allocator<_Tp1> other; }; 00502 00503 private: 00504 static const unsigned int _Bits_Per_Byte = 8; 00505 static const unsigned int _Bits_Per_Block = sizeof(unsigned int) * _Bits_Per_Byte; 00506 00507 static inline void _S_bit_allocate(unsigned int *__pbmap, unsigned int __pos) throw() 00508 { 00509 unsigned int __mask = 1 << __pos; 00510 __mask = ~__mask; 00511 *__pbmap &= __mask; 00512 } 00513 00514 static inline void _S_bit_free(unsigned int *__pbmap, unsigned int __pos) throw() 00515 { 00516 unsigned int __mask = 1 << __pos; 00517 *__pbmap |= __mask; 00518 } 00519 00520 static inline void *_S_memory_get(size_t __sz) throw (std::bad_alloc) 00521 { 00522 return operator new(__sz); 00523 } 00524 00525 static inline void _S_memory_put(void *__vptr) throw () 00526 { 00527 operator delete(__vptr); 00528 } 00529 00530 typedef typename std::pair<pointer, pointer> _Block_pair; 00531 typedef typename __gnu_cxx::new_allocator<_Block_pair> _BPVec_allocator_type; 00532 typedef typename std::vector<_Block_pair, _BPVec_allocator_type> _BPVector; 00533 00534 00535 #if defined CHECK_FOR_ERRORS 00536 //Complexity: O(lg(N)). Where, N is the number of block of size 00537 //sizeof(value_type). 00538 static void _S_check_for_free_blocks() throw() 00539 { 00540 typedef typename __gnu_cxx::__aux_balloc::_Ffit_finder<pointer, _BPVec_allocator_type> _FFF; 00541 _FFF __fff; 00542 typedef typename _BPVector::iterator _BPiter; 00543 _BPiter __bpi = std::find_if(_S_mem_blocks.begin(), _S_mem_blocks.end(), 00544 __gnu_cxx::__aux_balloc::_Functor_Ref<_FFF>(__fff)); 00545 assert(__bpi == _S_mem_blocks.end()); 00546 } 00547 #endif 00548 00549 00550 //Complexity: O(1), but internally depends upon the complexity of 00551 //the function _BA_free_list_store::_S_get_free_list. The part 00552 //where the bitmap headers are written is of worst case complexity: 00553 //O(X),where X is the number of blocks of size sizeof(value_type) 00554 //within the newly acquired block. Having a tight bound. 00555 static void _S_refill_pool() throw (std::bad_alloc) 00556 { 00557 #if defined CHECK_FOR_ERRORS 00558 _S_check_for_free_blocks(); 00559 #endif 00560 00561 const unsigned int __num_bit_maps = _S_block_size / _Bits_Per_Block; 00562 const unsigned int __size_to_allocate = sizeof(unsigned int) + 00563 _S_block_size * sizeof(value_type) + __num_bit_maps*sizeof(unsigned int); 00564 00565 unsigned int *__temp = 00566 reinterpret_cast<unsigned int*>(_BA_free_list_store::_S_get_free_list(__size_to_allocate)); 00567 *__temp = 0; 00568 ++__temp; 00569 00570 //The Header information goes at the Beginning of the Block. 00571 _Block_pair __bp = std::make_pair(reinterpret_cast<pointer>(__temp + __num_bit_maps), 00572 reinterpret_cast<pointer>(__temp + __num_bit_maps) 00573 + _S_block_size - 1); 00574 00575 //Fill the Vector with this information. 00576 _S_mem_blocks.push_back(__bp); 00577 00578 unsigned int __bit_mask = 0; //0 Indicates all Allocated. 00579 __bit_mask = ~__bit_mask; //1 Indicates all Free. 00580 00581 for (unsigned int __i = 0; __i < __num_bit_maps; ++__i) 00582 __temp[__i] = __bit_mask; 00583 00584 //On some implementations, operator new might throw bad_alloc, or 00585 //malloc might fail if the size passed is too large, therefore, we 00586 //limit the size passed to malloc or operator new. 00587 _S_block_size *= 2; 00588 } 00589 00590 static _BPVector _S_mem_blocks; 00591 static unsigned int _S_block_size; 00592 static __gnu_cxx::__aux_balloc::_Bit_map_counter<pointer, _BPVec_allocator_type> _S_last_request; 00593 static typename _BPVector::size_type _S_last_dealloc_index; 00594 #if defined __GTHREADS 00595 static _Mutex _S_mut; 00596 #endif 00597 00598 //Complexity: Worst case complexity is O(N), but that is hardly ever 00599 //hit. if and when this particular case is encountered, the next few 00600 //cases are guaranteed to have a worst case complexity of O(1)! 00601 //That's why this function performs very well on the average. you 00602 //can consider this function to be having a complexity refrred to 00603 //commonly as: Amortized Constant time. 00604 static pointer _S_allocate_single_object() 00605 { 00606 #if defined __GTHREADS 00607 _Lock __bit_lock(&_S_mut); 00608 #endif 00609 00610 //The algorithm is something like this: The last_requst variable 00611 //points to the last accessed Bit Map. When such a condition 00612 //occurs, we try to find a free block in the current bitmap, or 00613 //succeeding bitmaps until the last bitmap is reached. If no free 00614 //block turns up, we resort to First Fit method. 00615 00616 //WARNING: Do not re-order the condition in the while statement 00617 //below, because it relies on C++'s short-circuit 00618 //evaluation. The return from _S_last_request->_M_get() will NOT 00619 //be dereferenceable if _S_last_request->_M_finished() returns 00620 //true. This would inevitibly lead to a NULL pointer dereference 00621 //if tinkered with. 00622 while (_S_last_request._M_finished() == false && (*(_S_last_request._M_get()) == 0)) 00623 { 00624 _S_last_request.operator++(); 00625 } 00626 00627 if (__builtin_expect(_S_last_request._M_finished() == true, false)) 00628 { 00629 //Fall Back to First Fit algorithm. 00630 typedef typename __gnu_cxx::__aux_balloc::_Ffit_finder<pointer, _BPVec_allocator_type> _FFF; 00631 _FFF __fff; 00632 typedef typename _BPVector::iterator _BPiter; 00633 _BPiter __bpi = std::find_if(_S_mem_blocks.begin(), _S_mem_blocks.end(), 00634 __gnu_cxx::__aux_balloc::_Functor_Ref<_FFF>(__fff)); 00635 00636 if (__bpi != _S_mem_blocks.end()) 00637 { 00638 //Search was successful. Ok, now mark the first bit from 00639 //the right as 0, meaning Allocated. This bit is obtained 00640 //by calling _M_get() on __fff. 00641 unsigned int __nz_bit = _Bit_scan_forward(*__fff._M_get()); 00642 _S_bit_allocate(__fff._M_get(), __nz_bit); 00643 00644 _S_last_request._M_reset(__bpi - _S_mem_blocks.begin()); 00645 00646 //Now, get the address of the bit we marked as allocated. 00647 pointer __ret_val = __bpi->first + __fff._M_offset() + __nz_bit; 00648 unsigned int *__puse_count = reinterpret_cast<unsigned int*>(__bpi->first) - 00649 (__gnu_cxx::__aux_balloc::__balloc_num_bit_maps(*__bpi) + 1); 00650 ++(*__puse_count); 00651 return __ret_val; 00652 } 00653 else 00654 { 00655 //Search was unsuccessful. We Add more memory to the pool 00656 //by calling _S_refill_pool(). 00657 _S_refill_pool(); 00658 00659 //_M_Reset the _S_last_request structure to the first free 00660 //block's bit map. 00661 _S_last_request._M_reset(_S_mem_blocks.size() - 1); 00662 00663 //Now, mark that bit as allocated. 00664 } 00665 } 00666 //_S_last_request holds a pointer to a valid bit map, that points 00667 //to a free block in memory. 00668 unsigned int __nz_bit = _Bit_scan_forward(*_S_last_request._M_get()); 00669 _S_bit_allocate(_S_last_request._M_get(), __nz_bit); 00670 00671 pointer __ret_val = _S_last_request._M_base() + _S_last_request._M_offset() + __nz_bit; 00672 00673 unsigned int *__puse_count = reinterpret_cast<unsigned int*> 00674 (_S_mem_blocks[_S_last_request._M_where()].first) - 00675 (__gnu_cxx::__aux_balloc::__balloc_num_bit_maps(_S_mem_blocks[_S_last_request._M_where()]) + 1); 00676 ++(*__puse_count); 00677 return __ret_val; 00678 } 00679 00680 //Complexity: O(lg(N)), but the worst case is hit quite often! I 00681 //need to do something about this. I'll be able to work on it, only 00682 //when I have some solid figures from a few real apps. 00683 static void _S_deallocate_single_object(pointer __p) throw() 00684 { 00685 #if defined __GTHREADS 00686 _Lock __bit_lock(&_S_mut); 00687 #endif 00688 00689 typedef typename _BPVector::iterator _Iterator; 00690 typedef typename _BPVector::difference_type _Difference_type; 00691 00692 _Difference_type __diff; 00693 int __displacement; 00694 00695 assert(_S_last_dealloc_index >= 0); 00696 00697 if (__gnu_cxx::__aux_balloc::_Inclusive_between<pointer>(__p)(_S_mem_blocks[_S_last_dealloc_index])) 00698 { 00699 assert(_S_last_dealloc_index <= _S_mem_blocks.size() - 1); 00700 00701 //Initial Assumption was correct! 00702 __diff = _S_last_dealloc_index; 00703 __displacement = __p - _S_mem_blocks[__diff].first; 00704 } 00705 else 00706 { 00707 _Iterator _iter = (std::find_if(_S_mem_blocks.begin(), _S_mem_blocks.end(), 00708 __gnu_cxx::__aux_balloc::_Inclusive_between<pointer>(__p))); 00709 assert(_iter != _S_mem_blocks.end()); 00710 00711 __diff = _iter - _S_mem_blocks.begin(); 00712 __displacement = __p - _S_mem_blocks[__diff].first; 00713 _S_last_dealloc_index = __diff; 00714 } 00715 00716 //Get the position of the iterator that has been found. 00717 const unsigned int __rotate = __displacement % _Bits_Per_Block; 00718 unsigned int *__bit_mapC = reinterpret_cast<unsigned int*>(_S_mem_blocks[__diff].first) - 1; 00719 __bit_mapC -= (__displacement / _Bits_Per_Block); 00720 00721 _S_bit_free(__bit_mapC, __rotate); 00722 unsigned int *__puse_count = reinterpret_cast<unsigned int*> 00723 (_S_mem_blocks[__diff].first) - 00724 (__gnu_cxx::__aux_balloc::__balloc_num_bit_maps(_S_mem_blocks[__diff]) + 1); 00725 00726 assert(*__puse_count != 0); 00727 00728 --(*__puse_count); 00729 00730 if (__builtin_expect(*__puse_count == 0, false)) 00731 { 00732 _S_block_size /= 2; 00733 00734 //We may safely remove this block. 00735 _Block_pair __bp = _S_mem_blocks[__diff]; 00736 _S_insert_free_list(__puse_count); 00737 _S_mem_blocks.erase(_S_mem_blocks.begin() + __diff); 00738 00739 //We reset the _S_last_request variable to reflect the erased 00740 //block. We do this to protect future requests after the last 00741 //block has been removed from a particular memory Chunk, 00742 //which in turn has been returned to the free list, and 00743 //hence had been erased from the vector, so the size of the 00744 //vector gets reduced by 1. 00745 if ((_Difference_type)_S_last_request._M_where() >= __diff--) 00746 { 00747 _S_last_request._M_reset(__diff); 00748 // assert(__diff >= 0); 00749 } 00750 00751 //If the Index into the vector of the region of memory that 00752 //might hold the next address that will be passed to 00753 //deallocated may have been invalidated due to the above 00754 //erase procedure being called on the vector, hence we try 00755 //to restore this invariant too. 00756 if (_S_last_dealloc_index >= _S_mem_blocks.size()) 00757 { 00758 _S_last_dealloc_index =(__diff != -1 ? __diff : 0); 00759 assert(_S_last_dealloc_index >= 0); 00760 } 00761 } 00762 } 00763 00764 public: 00765 bitmap_allocator() throw() 00766 { } 00767 00768 bitmap_allocator(const bitmap_allocator&) { } 00769 00770 template <typename _Tp1> bitmap_allocator(const bitmap_allocator<_Tp1>&) throw() 00771 { } 00772 00773 ~bitmap_allocator() throw() 00774 { } 00775 00776 //Complexity: O(1), but internally the complexity depends upon the 00777 //complexity of the function(s) _S_allocate_single_object and 00778 //_S_memory_get. 00779 pointer allocate(size_type __n) 00780 { 00781 if (__builtin_expect(__n == 1, true)) 00782 return _S_allocate_single_object(); 00783 else 00784 return reinterpret_cast<pointer>(_S_memory_get(__n * sizeof(value_type))); 00785 } 00786 00787 //Complexity: Worst case complexity is O(N) where N is the number of 00788 //blocks of size sizeof(value_type) within the free lists that the 00789 //allocator holds. However, this worst case is hit only when the 00790 //user supplies a bogus argument to hint. If the hint argument is 00791 //sensible, then the complexity drops to O(lg(N)), and in extreme 00792 //cases, even drops to as low as O(1). So, if the user supplied 00793 //argument is good, then this function performs very well. 00794 pointer allocate(size_type __n, typename bitmap_allocator<void>::const_pointer) 00795 { 00796 return allocate(__n); 00797 } 00798 00799 void deallocate(pointer __p, size_type __n) throw() 00800 { 00801 if (__builtin_expect(__n == 1, true)) 00802 _S_deallocate_single_object(__p); 00803 else 00804 _S_memory_put(__p); 00805 } 00806 00807 pointer address(reference r) const { return &r; } 00808 const_pointer address(const_reference r) const { return &r; } 00809 00810 size_type max_size(void) const throw() { return (size_type()-1)/sizeof(value_type); } 00811 00812 void construct (pointer p, const_reference __data) 00813 { 00814 ::new(p) value_type(__data); 00815 } 00816 00817 void destroy (pointer p) 00818 { 00819 p->~value_type(); 00820 } 00821 00822 }; 00823 00824 template <typename _Tp> 00825 typename bitmap_allocator<_Tp>::_BPVector bitmap_allocator<_Tp>::_S_mem_blocks; 00826 00827 template <typename _Tp> 00828 unsigned int bitmap_allocator<_Tp>::_S_block_size = bitmap_allocator<_Tp>::_Bits_Per_Block; 00829 00830 template <typename _Tp> 00831 typename __gnu_cxx::bitmap_allocator<_Tp>::_BPVector::size_type 00832 bitmap_allocator<_Tp>::_S_last_dealloc_index = 0; 00833 00834 template <typename _Tp> 00835 __gnu_cxx::__aux_balloc::_Bit_map_counter 00836 <typename bitmap_allocator<_Tp>::pointer, typename bitmap_allocator<_Tp>::_BPVec_allocator_type> 00837 bitmap_allocator<_Tp>::_S_last_request(_S_mem_blocks); 00838 00839 #if defined __GTHREADS 00840 template <typename _Tp> 00841 __gnu_cxx::_Mutex 00842 bitmap_allocator<_Tp>::_S_mut; 00843 #endif 00844 00845 template <typename _Tp1, typename _Tp2> 00846 bool operator== (const bitmap_allocator<_Tp1>&, const bitmap_allocator<_Tp2>&) throw() 00847 { 00848 return true; 00849 } 00850 00851 template <typename _Tp1, typename _Tp2> 00852 bool operator!= (const bitmap_allocator<_Tp1>&, const bitmap_allocator<_Tp2>&) throw() 00853 { 00854 return false; 00855 } 00856 } 00857 00858 00859 #endif //_BITMAP_ALLOCATOR_H

Generated on Wed Jun 9 11:18:15 2004 for libstdc++-v3 Source by doxygen 1.3.7