00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00034 #ifndef _BITMAP_ALLOCATOR_H
00035 #define _BITMAP_ALLOCATOR_H 1
00036
00037
00038 #include <cstddef>
00039
00040
00041 #include <bits/functexcept.h>
00042
00043
00044 #include <utility>
00045
00046
00047 #include <functional>
00048
00049
00050 #include <new>
00051
00052
00053 #include <bits/gthr.h>
00054
00055
00056
00057
00058
00062 #define _BALLOC_ALIGN_BYTES 8
00063
00064 #if defined _BALLOC_SANITY_CHECK
00065 #include <cassert>
00066 #define _BALLOC_ASSERT(_EXPR) assert(_EXPR)
00067 #else
00068 #define _BALLOC_ASSERT(_EXPR)
00069 #endif
00070
00071
00072 namespace __gnu_cxx
00073 {
00074 #if defined __GTHREADS
00075 namespace
00076 {
00081 bool const __threads_enabled = __gthread_active_p();
00082 }
00083 #endif
00084
00085 #if defined __GTHREADS
00086
00094 class _Mutex
00095 {
00096 __gthread_mutex_t _M_mut;
00097
00098
00099 _Mutex(_Mutex const&);
00100 _Mutex& operator=(_Mutex const&);
00101
00102 public:
00103 _Mutex()
00104 {
00105 if (__threads_enabled)
00106 {
00107 #if !defined __GTHREAD_MUTEX_INIT
00108 __GTHREAD_MUTEX_INIT_FUNCTION(&_M_mut);
00109 #else
00110 __gthread_mutex_t __mtemp = __GTHREAD_MUTEX_INIT;
00111 _M_mut = __mtemp;
00112 #endif
00113 }
00114 }
00115
00116 ~_Mutex()
00117 {
00118
00119 }
00120
00121 __gthread_mutex_t*
00122 _M_get() { return &_M_mut; }
00123 };
00124
00135 class _Lock
00136 {
00137 _Mutex* _M_pmt;
00138 bool _M_locked;
00139
00140
00141 _Lock(_Lock const&);
00142 _Lock& operator=(_Lock const&);
00143
00144 public:
00145 _Lock(_Mutex* __mptr)
00146 : _M_pmt(__mptr), _M_locked(false)
00147 { }
00148
00149 void
00150 _M_lock()
00151 {
00152 if (__threads_enabled)
00153 {
00154 _M_locked = true;
00155 __gthread_mutex_lock(_M_pmt->_M_get());
00156 }
00157 }
00158
00159 void
00160 _M_unlock()
00161 {
00162 if (__threads_enabled)
00163 {
00164 if (__builtin_expect(_M_locked, true))
00165 {
00166 __gthread_mutex_unlock(_M_pmt->_M_get());
00167 _M_locked = false;
00168 }
00169 }
00170 }
00171
00172 ~_Lock() { }
00173 };
00174
00183 class _Auto_Lock
00184 {
00185 _Mutex* _M_pmt;
00186
00187 _Auto_Lock(_Auto_Lock const&);
00188 _Auto_Lock& operator=(_Auto_Lock const&);
00189
00190 void
00191 _M_lock()
00192 {
00193 if (__threads_enabled)
00194 __gthread_mutex_lock(_M_pmt->_M_get());
00195 }
00196
00197 void
00198 _M_unlock()
00199 {
00200 if (__threads_enabled)
00201 __gthread_mutex_unlock(_M_pmt->_M_get());
00202 }
00203
00204 public:
00205 _Auto_Lock(_Mutex* __mptr) : _M_pmt(__mptr)
00206 { this->_M_lock(); }
00207
00208 ~_Auto_Lock() { this->_M_unlock(); }
00209 };
00210 #endif
00211
00212 namespace balloc
00213 {
00230 template<typename _Tp>
00231 class __mini_vector
00232 {
00233 __mini_vector(const __mini_vector&);
00234 __mini_vector& operator=(const __mini_vector&);
00235
00236 public:
00237 typedef _Tp value_type;
00238 typedef _Tp* pointer;
00239 typedef _Tp& reference;
00240 typedef const _Tp& const_reference;
00241 typedef std::size_t size_type;
00242 typedef std::ptrdiff_t difference_type;
00243 typedef pointer iterator;
00244
00245 private:
00246 pointer _M_start;
00247 pointer _M_finish;
00248 pointer _M_end_of_storage;
00249
00250 size_type
00251 _M_space_left() const throw()
00252 { return _M_end_of_storage - _M_finish; }
00253
00254 pointer
00255 allocate(size_type __n)
00256 { return static_cast<pointer>(::operator new(__n * sizeof(_Tp))); }
00257
00258 void
00259 deallocate(pointer __p, size_type)
00260 { ::operator delete(__p); }
00261
00262 public:
00263
00264
00265
00266
00267 __mini_vector() : _M_start(0), _M_finish(0),
00268 _M_end_of_storage(0)
00269 { }
00270
00271 #if 0
00272 ~__mini_vector()
00273 {
00274 if (this->_M_start)
00275 {
00276 this->deallocate(this->_M_start, this->_M_end_of_storage
00277 - this->_M_start);
00278 }
00279 }
00280 #endif
00281
00282 size_type
00283 size() const throw()
00284 { return _M_finish - _M_start; }
00285
00286 iterator
00287 begin() const throw()
00288 { return this->_M_start; }
00289
00290 iterator
00291 end() const throw()
00292 { return this->_M_finish; }
00293
00294 reference
00295 back() const throw()
00296 { return *(this->end() - 1); }
00297
00298 reference
00299 operator[](const size_type __pos) const throw()
00300 { return this->_M_start[__pos]; }
00301
00302 void
00303 insert(iterator __pos, const_reference __x);
00304
00305 void
00306 push_back(const_reference __x)
00307 {
00308 if (this->_M_space_left())
00309 {
00310 *this->end() = __x;
00311 ++this->_M_finish;
00312 }
00313 else
00314 this->insert(this->end(), __x);
00315 }
00316
00317 void
00318 pop_back() throw()
00319 { --this->_M_finish; }
00320
00321 void
00322 erase(iterator __pos) throw();
00323
00324 void
00325 clear() throw()
00326 { this->_M_finish = this->_M_start; }
00327 };
00328
00329
00330 template<typename _Tp>
00331 void __mini_vector<_Tp>::
00332 insert(iterator __pos, const_reference __x)
00333 {
00334 if (this->_M_space_left())
00335 {
00336 size_type __to_move = this->_M_finish - __pos;
00337 iterator __dest = this->end();
00338 iterator __src = this->end() - 1;
00339
00340 ++this->_M_finish;
00341 while (__to_move)
00342 {
00343 *__dest = *__src;
00344 --__dest; --__src; --__to_move;
00345 }
00346 *__pos = __x;
00347 }
00348 else
00349 {
00350 size_type __new_size = this->size() ? this->size() * 2 : 1;
00351 iterator __new_start = this->allocate(__new_size);
00352 iterator __first = this->begin();
00353 iterator __start = __new_start;
00354 while (__first != __pos)
00355 {
00356 *__start = *__first;
00357 ++__start; ++__first;
00358 }
00359 *__start = __x;
00360 ++__start;
00361 while (__first != this->end())
00362 {
00363 *__start = *__first;
00364 ++__start; ++__first;
00365 }
00366 if (this->_M_start)
00367 this->deallocate(this->_M_start, this->size());
00368
00369 this->_M_start = __new_start;
00370 this->_M_finish = __start;
00371 this->_M_end_of_storage = this->_M_start + __new_size;
00372 }
00373 }
00374
00375 template<typename _Tp>
00376 void __mini_vector<_Tp>::
00377 erase(iterator __pos) throw()
00378 {
00379 while (__pos + 1 != this->end())
00380 {
00381 *__pos = __pos[1];
00382 ++__pos;
00383 }
00384 --this->_M_finish;
00385 }
00386
00387
00388 template<typename _Tp>
00389 struct __mv_iter_traits
00390 {
00391 typedef typename _Tp::value_type value_type;
00392 typedef typename _Tp::difference_type difference_type;
00393 };
00394
00395 template<typename _Tp>
00396 struct __mv_iter_traits<_Tp*>
00397 {
00398 typedef _Tp value_type;
00399 typedef std::ptrdiff_t difference_type;
00400 };
00401
00402 enum
00403 {
00404 bits_per_byte = 8,
00405 bits_per_block = sizeof(size_t) * size_t(bits_per_byte)
00406 };
00407
00408 template<typename _ForwardIterator, typename _Tp, typename _Compare>
00409 _ForwardIterator
00410 __lower_bound(_ForwardIterator __first, _ForwardIterator __last,
00411 const _Tp& __val, _Compare __comp)
00412 {
00413 typedef typename __mv_iter_traits<_ForwardIterator>::value_type
00414 _ValueType;
00415 typedef typename __mv_iter_traits<_ForwardIterator>::difference_type
00416 _DistanceType;
00417
00418 _DistanceType __len = __last - __first;
00419 _DistanceType __half;
00420 _ForwardIterator __middle;
00421
00422 while (__len > 0)
00423 {
00424 __half = __len >> 1;
00425 __middle = __first;
00426 __middle += __half;
00427 if (__comp(*__middle, __val))
00428 {
00429 __first = __middle;
00430 ++__first;
00431 __len = __len - __half - 1;
00432 }
00433 else
00434 __len = __half;
00435 }
00436 return __first;
00437 }
00438
00439 template<typename _InputIterator, typename _Predicate>
00440 inline _InputIterator
00441 __find_if(_InputIterator __first, _InputIterator __last, _Predicate __p)
00442 {
00443 while (__first != __last && !__p(*__first))
00444 ++__first;
00445 return __first;
00446 }
00447
00451 template<typename _AddrPair>
00452 inline size_t
00453 __num_blocks(_AddrPair __ap)
00454 { return (__ap.second - __ap.first) + 1; }
00455
00459 template<typename _AddrPair>
00460 inline size_t
00461 __num_bitmaps(_AddrPair __ap)
00462 { return __num_blocks(__ap) / size_t(bits_per_block); }
00463
00464
00465 template<typename _Tp>
00466 class _Inclusive_between
00467 : public std::unary_function<typename std::pair<_Tp, _Tp>, bool>
00468 {
00469 typedef _Tp pointer;
00470 pointer _M_ptr_value;
00471 typedef typename std::pair<_Tp, _Tp> _Block_pair;
00472
00473 public:
00474 _Inclusive_between(pointer __ptr) : _M_ptr_value(__ptr)
00475 { }
00476
00477 bool
00478 operator()(_Block_pair __bp) const throw()
00479 {
00480 if (std::less_equal<pointer>()(_M_ptr_value, __bp.second)
00481 && std::greater_equal<pointer>()(_M_ptr_value, __bp.first))
00482 return true;
00483 else
00484 return false;
00485 }
00486 };
00487
00488
00489 template<typename _Functor>
00490 class _Functor_Ref
00491 : public std::unary_function<typename _Functor::argument_type,
00492 typename _Functor::result_type>
00493 {
00494 _Functor& _M_fref;
00495
00496 public:
00497 typedef typename _Functor::argument_type argument_type;
00498 typedef typename _Functor::result_type result_type;
00499
00500 _Functor_Ref(_Functor& __fref) : _M_fref(__fref)
00501 { }
00502
00503 result_type
00504 operator()(argument_type __arg)
00505 { return _M_fref(__arg); }
00506 };
00507
00513
00514
00515 template<typename _Tp>
00516 class _Ffit_finder
00517 : public std::unary_function<typename std::pair<_Tp, _Tp>, bool>
00518 {
00519 typedef typename std::pair<_Tp, _Tp> _Block_pair;
00520 typedef typename balloc::__mini_vector<_Block_pair> _BPVector;
00521 typedef typename _BPVector::difference_type _Counter_type;
00522
00523 size_t* _M_pbitmap;
00524 _Counter_type _M_data_offset;
00525
00526 public:
00527 _Ffit_finder() : _M_pbitmap(0), _M_data_offset(0)
00528 { }
00529
00530 bool
00531 operator()(_Block_pair __bp) throw()
00532 {
00533
00534
00535
00536
00537
00538
00539
00540
00541
00542
00543 _Counter_type __diff =
00544 __gnu_cxx::balloc::__num_bitmaps(__bp);
00545
00546 if (*(reinterpret_cast<size_t*>
00547 (__bp.first) - (__diff + 1))
00548 == __gnu_cxx::balloc::__num_blocks(__bp))
00549 return false;
00550
00551 size_t* __rover = reinterpret_cast<size_t*>(__bp.first) - 1;
00552
00553 for (_Counter_type __i = 0; __i < __diff; ++__i)
00554 {
00555 _M_data_offset = __i;
00556 if (*__rover)
00557 {
00558 _M_pbitmap = __rover;
00559 return true;
00560 }
00561 --__rover;
00562 }
00563 return false;
00564 }
00565
00566
00567 size_t*
00568 _M_get() const throw()
00569 { return _M_pbitmap; }
00570
00571 _Counter_type
00572 _M_offset() const throw()
00573 { return _M_data_offset * size_t(bits_per_block); }
00574 };
00575
00576
00583
00584 template<typename _Tp>
00585 class _Bitmap_counter
00586 {
00587 typedef typename balloc::__mini_vector<typename std::pair<_Tp, _Tp> >
00588 _BPVector;
00589 typedef typename _BPVector::size_type _Index_type;
00590 typedef _Tp pointer;
00591
00592 _BPVector& _M_vbp;
00593 size_t* _M_curr_bmap;
00594 size_t* _M_last_bmap_in_block;
00595 _Index_type _M_curr_index;
00596
00597 public:
00598
00599
00600
00601 _Bitmap_counter(_BPVector& Rvbp, long __index = -1) : _M_vbp(Rvbp)
00602 { this->_M_reset(__index); }
00603
00604 void
00605 _M_reset(long __index = -1) throw()
00606 {
00607 if (__index == -1)
00608 {
00609 _M_curr_bmap = 0;
00610 _M_curr_index = static_cast<_Index_type>(-1);
00611 return;
00612 }
00613
00614 _M_curr_index = __index;
00615 _M_curr_bmap = reinterpret_cast<size_t*>
00616 (_M_vbp[_M_curr_index].first) - 1;
00617
00618 _BALLOC_ASSERT(__index <= (long)_M_vbp.size() - 1);
00619
00620 _M_last_bmap_in_block = _M_curr_bmap
00621 - ((_M_vbp[_M_curr_index].second
00622 - _M_vbp[_M_curr_index].first + 1)
00623 / size_t(bits_per_block) - 1);
00624 }
00625
00626
00627
00628
00629 void
00630 _M_set_internal_bitmap(size_t* __new_internal_marker) throw()
00631 { _M_curr_bmap = __new_internal_marker; }
00632
00633 bool
00634 _M_finished() const throw()
00635 { return(_M_curr_bmap == 0); }
00636
00637 _Bitmap_counter&
00638 operator++() throw()
00639 {
00640 if (_M_curr_bmap == _M_last_bmap_in_block)
00641 {
00642 if (++_M_curr_index == _M_vbp.size())
00643 _M_curr_bmap = 0;
00644 else
00645 this->_M_reset(_M_curr_index);
00646 }
00647 else
00648 --_M_curr_bmap;
00649 return *this;
00650 }
00651
00652 size_t*
00653 _M_get() const throw()
00654 { return _M_curr_bmap; }
00655
00656 pointer
00657 _M_base() const throw()
00658 { return _M_vbp[_M_curr_index].first; }
00659
00660 _Index_type
00661 _M_offset() const throw()
00662 {
00663 return size_t(bits_per_block)
00664 * ((reinterpret_cast<size_t*>(this->_M_base())
00665 - _M_curr_bmap) - 1);
00666 }
00667
00668 _Index_type
00669 _M_where() const throw()
00670 { return _M_curr_index; }
00671 };
00672
00676 inline void
00677 __bit_allocate(size_t* __pbmap, size_t __pos) throw()
00678 {
00679 size_t __mask = 1 << __pos;
00680 __mask = ~__mask;
00681 *__pbmap &= __mask;
00682 }
00683
00687 inline void
00688 __bit_free(size_t* __pbmap, size_t __pos) throw()
00689 {
00690 size_t __mask = 1 << __pos;
00691 *__pbmap |= __mask;
00692 }
00693 }
00694
00697 inline size_t
00698 _Bit_scan_forward(size_t __num)
00699 { return static_cast<size_t>(__builtin_ctzl(__num)); }
00700
00706 class free_list
00707 {
00708 typedef size_t* value_type;
00709 typedef balloc::__mini_vector<value_type> vector_type;
00710 typedef vector_type::iterator iterator;
00711
00712 struct _LT_pointer_compare
00713 {
00714 bool
00715 operator()(const size_t* __pui,
00716 const size_t __cui) const throw()
00717 { return *__pui < __cui; }
00718 };
00719
00720 #if defined __GTHREADS
00721 _Mutex*
00722 _M_get_mutex()
00723 {
00724 static _Mutex _S_mutex;
00725 return &_S_mutex;
00726 }
00727 #endif
00728
00729 vector_type&
00730 _M_get_free_list()
00731 {
00732 static vector_type _S_free_list;
00733 return _S_free_list;
00734 }
00735
00746 void
00747 _M_validate(size_t* __addr) throw()
00748 {
00749 vector_type& __free_list = _M_get_free_list();
00750 const vector_type::size_type __max_size = 64;
00751 if (__free_list.size() >= __max_size)
00752 {
00753
00754
00755 if (*__addr >= *__free_list.back())
00756 {
00757
00758
00759
00760 ::operator delete(static_cast<void*>(__addr));
00761 return;
00762 }
00763 else
00764 {
00765
00766
00767 ::operator delete(static_cast<void*>(__free_list.back()));
00768 __free_list.pop_back();
00769 }
00770 }
00771
00772
00773 iterator __temp = __gnu_cxx::balloc::__lower_bound
00774 (__free_list.begin(), __free_list.end(),
00775 *__addr, _LT_pointer_compare());
00776
00777
00778 __free_list.insert(__temp, __addr);
00779 }
00780
00792 bool
00793 _M_should_i_give(size_t __block_size,
00794 size_t __required_size) throw()
00795 {
00796 const size_t __max_wastage_percentage = 36;
00797 if (__block_size >= __required_size &&
00798 (((__block_size - __required_size) * 100 / __block_size)
00799 < __max_wastage_percentage))
00800 return true;
00801 else
00802 return false;
00803 }
00804
00805 public:
00812 inline void
00813 _M_insert(size_t* __addr) throw()
00814 {
00815 #if defined __GTHREADS
00816 _Auto_Lock __bfl_lock(_M_get_mutex());
00817 #endif
00818
00819
00820 this->_M_validate(reinterpret_cast<size_t*>(__addr) - 1);
00821
00822 }
00823
00832 size_t*
00833 _M_get(size_t __sz) throw(std::bad_alloc);
00834
00838 void
00839 _M_clear();
00840 };
00841
00842
00843
00844 template<typename _Tp>
00845 class bitmap_allocator;
00846
00847
00848 template<>
00849 class bitmap_allocator<void>
00850 {
00851 public:
00852 typedef void* pointer;
00853 typedef const void* const_pointer;
00854
00855
00856 typedef void value_type;
00857 template<typename _Tp1>
00858 struct rebind
00859 {
00860 typedef bitmap_allocator<_Tp1> other;
00861 };
00862 };
00863
00864 template<typename _Tp>
00865 class bitmap_allocator : private free_list
00866 {
00867 public:
00868 typedef std::size_t size_type;
00869 typedef std::ptrdiff_t difference_type;
00870 typedef _Tp* pointer;
00871 typedef const _Tp* const_pointer;
00872 typedef _Tp& reference;
00873 typedef const _Tp& const_reference;
00874 typedef _Tp value_type;
00875 template<typename _Tp1>
00876 struct rebind
00877 {
00878 typedef bitmap_allocator<_Tp1> other;
00879 };
00880
00881 private:
00882 template<size_t _BSize, size_t _AlignSize>
00883 struct aligned_size
00884 {
00885 enum
00886 {
00887 modulus = _BSize % _AlignSize,
00888 value = _BSize + (modulus ? _AlignSize - (modulus) : 0)
00889 };
00890 };
00891
00892 struct _Alloc_block
00893 {
00894 char __M_unused[aligned_size<sizeof(value_type),
00895 _BALLOC_ALIGN_BYTES>::value];
00896 };
00897
00898
00899 typedef typename std::pair<_Alloc_block*, _Alloc_block*> _Block_pair;
00900
00901 typedef typename
00902 balloc::__mini_vector<_Block_pair> _BPVector;
00903
00904 #if defined _BALLOC_SANITY_CHECK
00905
00906
00907 void
00908 _S_check_for_free_blocks() throw()
00909 {
00910 typedef typename
00911 __gnu_cxx::balloc::_Ffit_finder<_Alloc_block*> _FFF;
00912 _FFF __fff;
00913 typedef typename _BPVector::iterator _BPiter;
00914 _BPiter __bpi =
00915 __gnu_cxx::balloc::__find_if
00916 (_S_mem_blocks.begin(), _S_mem_blocks.end(),
00917 __gnu_cxx::balloc::_Functor_Ref<_FFF>(__fff));
00918
00919 _BALLOC_ASSERT(__bpi == _S_mem_blocks.end());
00920 }
00921 #endif
00922
00934 void
00935 _S_refill_pool() throw(std::bad_alloc)
00936 {
00937 #if defined _BALLOC_SANITY_CHECK
00938 _S_check_for_free_blocks();
00939 #endif
00940
00941 const size_t __num_bitmaps = (_S_block_size
00942 / size_t(balloc::bits_per_block));
00943 const size_t __size_to_allocate = sizeof(size_t)
00944 + _S_block_size * sizeof(_Alloc_block)
00945 + __num_bitmaps * sizeof(size_t);
00946
00947 size_t* __temp =
00948 reinterpret_cast<size_t*>
00949 (this->_M_get(__size_to_allocate));
00950 *__temp = 0;
00951 ++__temp;
00952
00953
00954 _Block_pair __bp =
00955 std::make_pair(reinterpret_cast<_Alloc_block*>
00956 (__temp + __num_bitmaps),
00957 reinterpret_cast<_Alloc_block*>
00958 (__temp + __num_bitmaps)
00959 + _S_block_size - 1);
00960
00961
00962 _S_mem_blocks.push_back(__bp);
00963
00964 size_t __bit_mask = 0;
00965 __bit_mask = ~__bit_mask;
00966
00967 for (size_t __i = 0; __i < __num_bitmaps; ++__i)
00968 __temp[__i] = __bit_mask;
00969
00970 _S_block_size *= 2;
00971 }
00972
00973
00974 static _BPVector _S_mem_blocks;
00975 static size_t _S_block_size;
00976 static __gnu_cxx::balloc::
00977 _Bitmap_counter<_Alloc_block*> _S_last_request;
00978 static typename _BPVector::size_type _S_last_dealloc_index;
00979 #if defined __GTHREADS
00980 static _Mutex _S_mut;
00981 #endif
00982
00983 public:
00984
00998 pointer
00999 _M_allocate_single_object() throw(std::bad_alloc)
01000 {
01001 #if defined __GTHREADS
01002 _Auto_Lock __bit_lock(&_S_mut);
01003 #endif
01004
01005
01006
01007
01008
01009
01010
01011
01012
01013
01014
01015
01016
01017
01018 while (_S_last_request._M_finished() == false
01019 && (*(_S_last_request._M_get()) == 0))
01020 {
01021 _S_last_request.operator++();
01022 }
01023
01024 if (__builtin_expect(_S_last_request._M_finished() == true, false))
01025 {
01026
01027 typedef typename
01028 __gnu_cxx::balloc::_Ffit_finder<_Alloc_block*> _FFF;
01029 _FFF __fff;
01030 typedef typename _BPVector::iterator _BPiter;
01031 _BPiter __bpi =
01032 __gnu_cxx::balloc::__find_if
01033 (_S_mem_blocks.begin(), _S_mem_blocks.end(),
01034 __gnu_cxx::balloc::_Functor_Ref<_FFF>(__fff));
01035
01036 if (__bpi != _S_mem_blocks.end())
01037 {
01038
01039
01040
01041 size_t __nz_bit = _Bit_scan_forward(*__fff._M_get());
01042 balloc::__bit_allocate(__fff._M_get(), __nz_bit);
01043
01044 _S_last_request._M_reset(__bpi - _S_mem_blocks.begin());
01045
01046
01047 pointer __ret = reinterpret_cast<pointer>
01048 (__bpi->first + __fff._M_offset() + __nz_bit);
01049 size_t* __puse_count =
01050 reinterpret_cast<size_t*>
01051 (__bpi->first)
01052 - (__gnu_cxx::balloc::__num_bitmaps(*__bpi) + 1);
01053
01054 ++(*__puse_count);
01055 return __ret;
01056 }
01057 else
01058 {
01059
01060
01061 _S_refill_pool();
01062
01063
01064
01065 _S_last_request._M_reset(_S_mem_blocks.size() - 1);
01066
01067
01068 }
01069 }
01070
01071
01072
01073 size_t __nz_bit = _Bit_scan_forward(*_S_last_request._M_get());
01074 balloc::__bit_allocate(_S_last_request._M_get(), __nz_bit);
01075
01076 pointer __ret = reinterpret_cast<pointer>
01077 (_S_last_request._M_base() + _S_last_request._M_offset() + __nz_bit);
01078
01079 size_t* __puse_count = reinterpret_cast<size_t*>
01080 (_S_mem_blocks[_S_last_request._M_where()].first)
01081 - (__gnu_cxx::balloc::
01082 __num_bitmaps(_S_mem_blocks[_S_last_request._M_where()]) + 1);
01083
01084 ++(*__puse_count);
01085 return __ret;
01086 }
01087
01096 void
01097 _M_deallocate_single_object(pointer __p) throw()
01098 {
01099 #if defined __GTHREADS
01100 _Auto_Lock __bit_lock(&_S_mut);
01101 #endif
01102 _Alloc_block* __real_p = reinterpret_cast<_Alloc_block*>(__p);
01103
01104 typedef typename _BPVector::iterator _Iterator;
01105 typedef typename _BPVector::difference_type _Difference_type;
01106
01107 _Difference_type __diff;
01108 long __displacement;
01109
01110 _BALLOC_ASSERT(_S_last_dealloc_index >= 0);
01111
01112
01113 if (__gnu_cxx::balloc::_Inclusive_between<_Alloc_block*>
01114 (__real_p)
01115 (_S_mem_blocks[_S_last_dealloc_index]))
01116 {
01117 _BALLOC_ASSERT(_S_last_dealloc_index <= _S_mem_blocks.size() - 1);
01118
01119
01120 __diff = _S_last_dealloc_index;
01121 __displacement = __real_p - _S_mem_blocks[__diff].first;
01122 }
01123 else
01124 {
01125 _Iterator _iter =
01126 __gnu_cxx::balloc::
01127 __find_if(_S_mem_blocks.begin(),
01128 _S_mem_blocks.end(),
01129 __gnu_cxx::balloc::
01130 _Inclusive_between<_Alloc_block*>(__real_p));
01131
01132 _BALLOC_ASSERT(_iter != _S_mem_blocks.end());
01133
01134 __diff = _iter - _S_mem_blocks.begin();
01135 __displacement = __real_p - _S_mem_blocks[__diff].first;
01136 _S_last_dealloc_index = __diff;
01137 }
01138
01139
01140 const size_t __rotate = (__displacement
01141 % size_t(balloc::bits_per_block));
01142 size_t* __bitmapC =
01143 reinterpret_cast<size_t*>
01144 (_S_mem_blocks[__diff].first) - 1;
01145 __bitmapC -= (__displacement / size_t(balloc::bits_per_block));
01146
01147 balloc::__bit_free(__bitmapC, __rotate);
01148 size_t* __puse_count = reinterpret_cast<size_t*>
01149 (_S_mem_blocks[__diff].first)
01150 - (__gnu_cxx::balloc::__num_bitmaps(_S_mem_blocks[__diff]) + 1);
01151
01152 _BALLOC_ASSERT(*__puse_count != 0);
01153
01154 --(*__puse_count);
01155
01156 if (__builtin_expect(*__puse_count == 0, false))
01157 {
01158 _S_block_size /= 2;
01159
01160
01161
01162 this->_M_insert(__puse_count);
01163 _S_mem_blocks.erase(_S_mem_blocks.begin() + __diff);
01164
01165
01166
01167
01168
01169
01170
01171 if ((_Difference_type)_S_last_request._M_where() >= __diff--)
01172 _S_last_request._M_reset(__diff);
01173
01174
01175
01176
01177
01178
01179 if (_S_last_dealloc_index >= _S_mem_blocks.size())
01180 {
01181 _S_last_dealloc_index =(__diff != -1 ? __diff : 0);
01182 _BALLOC_ASSERT(_S_last_dealloc_index >= 0);
01183 }
01184 }
01185 }
01186
01187 public:
01188 bitmap_allocator() throw()
01189 { }
01190
01191 bitmap_allocator(const bitmap_allocator&)
01192 { }
01193
01194 template<typename _Tp1>
01195 bitmap_allocator(const bitmap_allocator<_Tp1>&) throw()
01196 { }
01197
01198 ~bitmap_allocator() throw()
01199 { }
01200
01201 pointer
01202 allocate(size_type __n)
01203 {
01204 if (__builtin_expect(__n > this->max_size(), false))
01205 std::__throw_bad_alloc();
01206
01207 if (__builtin_expect(__n == 1, true))
01208 return this->_M_allocate_single_object();
01209 else
01210 {
01211 const size_type __b = __n * sizeof(value_type);
01212 return reinterpret_cast<pointer>(::operator new(__b));
01213 }
01214 }
01215
01216 pointer
01217 allocate(size_type __n, typename bitmap_allocator<void>::const_pointer)
01218 { return allocate(__n); }
01219
01220 void
01221 deallocate(pointer __p, size_type __n) throw()
01222 {
01223 if (__builtin_expect(__p != 0, true))
01224 {
01225 if (__builtin_expect(__n == 1, true))
01226 this->_M_deallocate_single_object(__p);
01227 else
01228 ::operator delete(__p);
01229 }
01230 }
01231
01232 pointer
01233 address(reference __r) const
01234 { return &__r; }
01235
01236 const_pointer
01237 address(const_reference __r) const
01238 { return &__r; }
01239
01240 size_type
01241 max_size() const throw()
01242 { return size_type(-1) / sizeof(value_type); }
01243
01244 void
01245 construct(pointer __p, const_reference __data)
01246 { ::new(__p) value_type(__data); }
01247
01248 void
01249 destroy(pointer __p)
01250 { __p->~value_type(); }
01251 };
01252
01253 template<typename _Tp1, typename _Tp2>
01254 bool
01255 operator==(const bitmap_allocator<_Tp1>&,
01256 const bitmap_allocator<_Tp2>&) throw()
01257 { return true; }
01258
01259 template<typename _Tp1, typename _Tp2>
01260 bool
01261 operator!=(const bitmap_allocator<_Tp1>&,
01262 const bitmap_allocator<_Tp2>&) throw()
01263 { return false; }
01264
01265
01266 template<typename _Tp>
01267 typename bitmap_allocator<_Tp>::_BPVector
01268 bitmap_allocator<_Tp>::_S_mem_blocks;
01269
01270 template<typename _Tp>
01271 size_t bitmap_allocator<_Tp>::_S_block_size =
01272 2 * size_t(balloc::bits_per_block);
01273
01274 template<typename _Tp>
01275 typename __gnu_cxx::bitmap_allocator<_Tp>::_BPVector::size_type
01276 bitmap_allocator<_Tp>::_S_last_dealloc_index = 0;
01277
01278 template<typename _Tp>
01279 __gnu_cxx::balloc::_Bitmap_counter
01280 <typename bitmap_allocator<_Tp>::_Alloc_block*>
01281 bitmap_allocator<_Tp>::_S_last_request(_S_mem_blocks);
01282
01283 #if defined __GTHREADS
01284 template<typename _Tp>
01285 __gnu_cxx::_Mutex
01286 bitmap_allocator<_Tp>::_S_mut;
01287 #endif
01288
01289
01290 }
01291
01292 #endif
01293
01294