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
00030
00031
00032
00033
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
00059
00060
00061
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 {
00077
00078
00079
00080
00081 bool const __threads_enabled = __gthread_active_p();
00082 }
00083 #endif
00084
00085 #if defined __GTHREADS
00086
00087
00088
00089
00090
00091
00092
00093
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
00125
00126
00127
00128
00129
00130
00131
00132
00133
00134
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
00175
00176
00177
00178
00179
00180
00181
00182
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 {
00214
00215
00216
00217
00218
00219
00220
00221
00222
00223
00224
00225
00226
00227
00228
00229
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
00448
00449
00450
00451 template<typename _AddrPair>
00452 inline size_t
00453 __num_blocks(_AddrPair __ap)
00454 { return (__ap.second - __ap.first) + 1; }
00455
00456
00457
00458
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
00508
00509
00510
00511
00512
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
00577
00578
00579
00580
00581
00582
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
00673
00674
00675
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
00684
00685
00686
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
00695
00696
00697 inline size_t
00698 _Bit_scan_forward(size_t __num)
00699 { return static_cast<size_t>(__builtin_ctzl(__num)); }
00700
00701
00702
00703
00704
00705
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
00736
00737
00738
00739
00740
00741
00742
00743
00744
00745
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
00781
00782
00783
00784
00785
00786
00787
00788
00789
00790
00791
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:
00806
00807
00808
00809
00810
00811
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
00824
00825
00826
00827
00828
00829
00830
00831
00832 size_t*
00833 _M_get(size_t __sz) throw(std::bad_alloc);
00834
00835
00836
00837
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
00923
00924
00925
00926
00927
00928
00929
00930
00931
00932
00933
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
00985
00986
00987
00988
00989
00990
00991
00992
00993
00994
00995
00996
00997
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
01088
01089
01090
01091
01092
01093
01094
01095
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