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) * 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) / 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 * 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 / 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 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 static _Mutex _S_bfl_mutex;
00722 #endif
00723 static vector_type _S_free_list;
00724
00725
00726
00727
00728
00729
00730
00731
00732
00733
00734
00735 void
00736 _M_validate(size_t* __addr) throw()
00737 {
00738 const vector_type::size_type __max_size = 64;
00739 if (_S_free_list.size() >= __max_size)
00740 {
00741
00742
00743 if (*__addr >= *_S_free_list.back())
00744 {
00745
00746
00747
00748 ::operator delete(static_cast<void*>(__addr));
00749 return;
00750 }
00751 else
00752 {
00753
00754
00755 ::operator delete(static_cast<void*>(_S_free_list.back()));
00756 _S_free_list.pop_back();
00757 }
00758 }
00759
00760
00761 iterator __temp = __gnu_cxx::balloc::__lower_bound
00762 (_S_free_list.begin(), _S_free_list.end(),
00763 *__addr, _LT_pointer_compare());
00764
00765
00766 _S_free_list.insert(__temp, __addr);
00767 }
00768
00769
00770
00771
00772
00773
00774
00775
00776
00777
00778
00779
00780 bool
00781 _M_should_i_give(size_t __block_size,
00782 size_t __required_size) throw()
00783 {
00784 const size_t __max_wastage_percentage = 36;
00785 if (__block_size >= __required_size &&
00786 (((__block_size - __required_size) * 100 / __block_size)
00787 < __max_wastage_percentage))
00788 return true;
00789 else
00790 return false;
00791 }
00792
00793 public:
00794
00795
00796
00797
00798
00799
00800 inline void
00801 _M_insert(size_t* __addr) throw()
00802 {
00803 #if defined __GTHREADS
00804 _Auto_Lock __bfl_lock(&_S_bfl_mutex);
00805 #endif
00806
00807
00808 this->_M_validate(reinterpret_cast<size_t*>(__addr) - 1);
00809
00810 }
00811
00812
00813
00814
00815
00816
00817
00818
00819
00820 size_t*
00821 _M_get(size_t __sz) throw(std::bad_alloc);
00822
00823
00824
00825
00826 void
00827 _M_clear();
00828 };
00829
00830
00831
00832 template<typename _Tp>
00833 class bitmap_allocator;
00834
00835
00836 template<>
00837 class bitmap_allocator<void>
00838 {
00839 public:
00840 typedef void* pointer;
00841 typedef const void* const_pointer;
00842
00843
00844 typedef void value_type;
00845 template<typename _Tp1>
00846 struct rebind
00847 {
00848 typedef bitmap_allocator<_Tp1> other;
00849 };
00850 };
00851
00852 template<typename _Tp>
00853 class bitmap_allocator : private free_list
00854 {
00855 public:
00856 typedef std::size_t size_type;
00857 typedef std::ptrdiff_t difference_type;
00858 typedef _Tp* pointer;
00859 typedef const _Tp* const_pointer;
00860 typedef _Tp& reference;
00861 typedef const _Tp& const_reference;
00862 typedef _Tp value_type;
00863 template<typename _Tp1>
00864 struct rebind
00865 {
00866 typedef bitmap_allocator<_Tp1> other;
00867 };
00868
00869 private:
00870 template<size_t _BSize, size_t _AlignSize>
00871 struct aligned_size
00872 {
00873 enum
00874 {
00875 modulus = _BSize % _AlignSize,
00876 value = _BSize + (modulus ? _AlignSize - (modulus) : 0)
00877 };
00878 };
00879
00880 struct _Alloc_block
00881 {
00882 char __M_unused[aligned_size<sizeof(value_type),
00883 _BALLOC_ALIGN_BYTES>::value];
00884 };
00885
00886
00887 typedef typename std::pair<_Alloc_block*, _Alloc_block*> _Block_pair;
00888
00889 typedef typename
00890 balloc::__mini_vector<_Block_pair> _BPVector;
00891
00892 #if defined _BALLOC_SANITY_CHECK
00893
00894
00895 void
00896 _S_check_for_free_blocks() throw()
00897 {
00898 typedef typename
00899 __gnu_cxx::balloc::_Ffit_finder<_Alloc_block*> _FFF;
00900 _FFF __fff;
00901 typedef typename _BPVector::iterator _BPiter;
00902 _BPiter __bpi =
00903 __gnu_cxx::balloc::__find_if
00904 (_S_mem_blocks.begin(), _S_mem_blocks.end(),
00905 __gnu_cxx::balloc::_Functor_Ref<_FFF>(__fff));
00906
00907 _BALLOC_ASSERT(__bpi == _S_mem_blocks.end());
00908 }
00909 #endif
00910
00911
00912
00913
00914
00915
00916
00917
00918
00919
00920
00921
00922 void
00923 _S_refill_pool() throw(std::bad_alloc)
00924 {
00925 #if defined _BALLOC_SANITY_CHECK
00926 _S_check_for_free_blocks();
00927 #endif
00928
00929 const size_t __num_bitmaps = _S_block_size / balloc::bits_per_block;
00930 const size_t __size_to_allocate = sizeof(size_t)
00931 + _S_block_size * sizeof(_Alloc_block)
00932 + __num_bitmaps * sizeof(size_t);
00933
00934 size_t* __temp =
00935 reinterpret_cast<size_t*>
00936 (this->_M_get(__size_to_allocate));
00937 *__temp = 0;
00938 ++__temp;
00939
00940
00941 _Block_pair __bp =
00942 std::make_pair(reinterpret_cast<_Alloc_block*>
00943 (__temp + __num_bitmaps),
00944 reinterpret_cast<_Alloc_block*>
00945 (__temp + __num_bitmaps)
00946 + _S_block_size - 1);
00947
00948
00949 _S_mem_blocks.push_back(__bp);
00950
00951 size_t __bit_mask = 0;
00952 __bit_mask = ~__bit_mask;
00953
00954 for (size_t __i = 0; __i < __num_bitmaps; ++__i)
00955 __temp[__i] = __bit_mask;
00956
00957 _S_block_size *= 2;
00958 }
00959
00960
00961 static _BPVector _S_mem_blocks;
00962 static size_t _S_block_size;
00963 static __gnu_cxx::balloc::
00964 _Bitmap_counter<_Alloc_block*> _S_last_request;
00965 static typename _BPVector::size_type _S_last_dealloc_index;
00966 #if defined __GTHREADS
00967 static _Mutex _S_mut;
00968 #endif
00969
00970 public:
00971
00972
00973
00974
00975
00976
00977
00978
00979
00980
00981
00982
00983
00984
00985 pointer
00986 _M_allocate_single_object() throw(std::bad_alloc)
00987 {
00988 #if defined __GTHREADS
00989 _Auto_Lock __bit_lock(&_S_mut);
00990 #endif
00991
00992
00993
00994
00995
00996
00997
00998
00999
01000
01001
01002
01003
01004
01005 while (_S_last_request._M_finished() == false
01006 && (*(_S_last_request._M_get()) == 0))
01007 {
01008 _S_last_request.operator++();
01009 }
01010
01011 if (__builtin_expect(_S_last_request._M_finished() == true, false))
01012 {
01013
01014 typedef typename
01015 __gnu_cxx::balloc::_Ffit_finder<_Alloc_block*> _FFF;
01016 _FFF __fff;
01017 typedef typename _BPVector::iterator _BPiter;
01018 _BPiter __bpi =
01019 __gnu_cxx::balloc::__find_if
01020 (_S_mem_blocks.begin(), _S_mem_blocks.end(),
01021 __gnu_cxx::balloc::_Functor_Ref<_FFF>(__fff));
01022
01023 if (__bpi != _S_mem_blocks.end())
01024 {
01025
01026
01027
01028 size_t __nz_bit = _Bit_scan_forward(*__fff._M_get());
01029 balloc::__bit_allocate(__fff._M_get(), __nz_bit);
01030
01031 _S_last_request._M_reset(__bpi - _S_mem_blocks.begin());
01032
01033
01034 pointer __ret = reinterpret_cast<pointer>
01035 (__bpi->first + __fff._M_offset() + __nz_bit);
01036 size_t* __puse_count =
01037 reinterpret_cast<size_t*>
01038 (__bpi->first)
01039 - (__gnu_cxx::balloc::__num_bitmaps(*__bpi) + 1);
01040
01041 ++(*__puse_count);
01042 return __ret;
01043 }
01044 else
01045 {
01046
01047
01048 _S_refill_pool();
01049
01050
01051
01052 _S_last_request._M_reset(_S_mem_blocks.size() - 1);
01053
01054
01055 }
01056 }
01057
01058
01059
01060 size_t __nz_bit = _Bit_scan_forward(*_S_last_request._M_get());
01061 balloc::__bit_allocate(_S_last_request._M_get(), __nz_bit);
01062
01063 pointer __ret = reinterpret_cast<pointer>
01064 (_S_last_request._M_base() + _S_last_request._M_offset() + __nz_bit);
01065
01066 size_t* __puse_count = reinterpret_cast<size_t*>
01067 (_S_mem_blocks[_S_last_request._M_where()].first)
01068 - (__gnu_cxx::balloc::
01069 __num_bitmaps(_S_mem_blocks[_S_last_request._M_where()]) + 1);
01070
01071 ++(*__puse_count);
01072 return __ret;
01073 }
01074
01075
01076
01077
01078
01079
01080
01081
01082
01083 void
01084 _M_deallocate_single_object(pointer __p) throw()
01085 {
01086 #if defined __GTHREADS
01087 _Auto_Lock __bit_lock(&_S_mut);
01088 #endif
01089 _Alloc_block* __real_p = reinterpret_cast<_Alloc_block*>(__p);
01090
01091 typedef typename _BPVector::iterator _Iterator;
01092 typedef typename _BPVector::difference_type _Difference_type;
01093
01094 _Difference_type __diff;
01095 long __displacement;
01096
01097 _BALLOC_ASSERT(_S_last_dealloc_index >= 0);
01098
01099
01100 if (__gnu_cxx::balloc::_Inclusive_between<_Alloc_block*>
01101 (__real_p)
01102 (_S_mem_blocks[_S_last_dealloc_index]))
01103 {
01104 _BALLOC_ASSERT(_S_last_dealloc_index <= _S_mem_blocks.size() - 1);
01105
01106
01107 __diff = _S_last_dealloc_index;
01108 __displacement = __real_p - _S_mem_blocks[__diff].first;
01109 }
01110 else
01111 {
01112 _Iterator _iter =
01113 __gnu_cxx::balloc::
01114 __find_if(_S_mem_blocks.begin(),
01115 _S_mem_blocks.end(),
01116 __gnu_cxx::balloc::
01117 _Inclusive_between<_Alloc_block*>(__real_p));
01118
01119 _BALLOC_ASSERT(_iter != _S_mem_blocks.end());
01120
01121 __diff = _iter - _S_mem_blocks.begin();
01122 __displacement = __real_p - _S_mem_blocks[__diff].first;
01123 _S_last_dealloc_index = __diff;
01124 }
01125
01126
01127 const size_t __rotate = __displacement % balloc::bits_per_block;
01128 size_t* __bitmapC =
01129 reinterpret_cast<size_t*>
01130 (_S_mem_blocks[__diff].first) - 1;
01131 __bitmapC -= (__displacement / balloc::bits_per_block);
01132
01133 balloc::__bit_free(__bitmapC, __rotate);
01134 size_t* __puse_count = reinterpret_cast<size_t*>
01135 (_S_mem_blocks[__diff].first)
01136 - (__gnu_cxx::balloc::__num_bitmaps(_S_mem_blocks[__diff]) + 1);
01137
01138 _BALLOC_ASSERT(*__puse_count != 0);
01139
01140 --(*__puse_count);
01141
01142 if (__builtin_expect(*__puse_count == 0, false))
01143 {
01144 _S_block_size /= 2;
01145
01146
01147
01148 this->_M_insert(__puse_count);
01149 _S_mem_blocks.erase(_S_mem_blocks.begin() + __diff);
01150
01151
01152
01153
01154
01155
01156
01157 if ((_Difference_type)_S_last_request._M_where() >= __diff--)
01158 _S_last_request._M_reset(__diff);
01159
01160
01161
01162
01163
01164
01165 if (_S_last_dealloc_index >= _S_mem_blocks.size())
01166 {
01167 _S_last_dealloc_index =(__diff != -1 ? __diff : 0);
01168 _BALLOC_ASSERT(_S_last_dealloc_index >= 0);
01169 }
01170 }
01171 }
01172
01173 public:
01174 bitmap_allocator() throw()
01175 { }
01176
01177 bitmap_allocator(const bitmap_allocator&)
01178 { }
01179
01180 template<typename _Tp1>
01181 bitmap_allocator(const bitmap_allocator<_Tp1>&) throw()
01182 { }
01183
01184 ~bitmap_allocator() throw()
01185 { }
01186
01187 pointer
01188 allocate(size_type __n)
01189 {
01190 if (__builtin_expect(__n > this->max_size(), false))
01191 std::__throw_bad_alloc();
01192
01193 if (__builtin_expect(__n == 1, true))
01194 return this->_M_allocate_single_object();
01195 else
01196 {
01197 const size_type __b = __n * sizeof(value_type);
01198 return reinterpret_cast<pointer>(::operator new(__b));
01199 }
01200 }
01201
01202 pointer
01203 allocate(size_type __n, typename bitmap_allocator<void>::const_pointer)
01204 { return allocate(__n); }
01205
01206 void
01207 deallocate(pointer __p, size_type __n) throw()
01208 {
01209 if (__builtin_expect(__p != 0, true))
01210 {
01211 if (__builtin_expect(__n == 1, true))
01212 this->_M_deallocate_single_object(__p);
01213 else
01214 ::operator delete(__p);
01215 }
01216 }
01217
01218 pointer
01219 address(reference __r) const
01220 { return &__r; }
01221
01222 const_pointer
01223 address(const_reference __r) const
01224 { return &__r; }
01225
01226 size_type
01227 max_size() const throw()
01228 { return size_type(-1) / sizeof(value_type); }
01229
01230 void
01231 construct(pointer __p, const_reference __data)
01232 { ::new(__p) value_type(__data); }
01233
01234 void
01235 destroy(pointer __p)
01236 { __p->~value_type(); }
01237 };
01238
01239 template<typename _Tp1, typename _Tp2>
01240 bool
01241 operator==(const bitmap_allocator<_Tp1>&,
01242 const bitmap_allocator<_Tp2>&) throw()
01243 { return true; }
01244
01245 template<typename _Tp1, typename _Tp2>
01246 bool
01247 operator!=(const bitmap_allocator<_Tp1>&,
01248 const bitmap_allocator<_Tp2>&) throw()
01249 { return false; }
01250
01251
01252 template<typename _Tp>
01253 typename bitmap_allocator<_Tp>::_BPVector
01254 bitmap_allocator<_Tp>::_S_mem_blocks;
01255
01256 template<typename _Tp>
01257 size_t bitmap_allocator<_Tp>::_S_block_size =
01258 2 * balloc::bits_per_block;
01259
01260 template<typename _Tp>
01261 typename __gnu_cxx::bitmap_allocator<_Tp>::_BPVector::size_type
01262 bitmap_allocator<_Tp>::_S_last_dealloc_index = 0;
01263
01264 template<typename _Tp>
01265 __gnu_cxx::balloc::_Bitmap_counter
01266 <typename bitmap_allocator<_Tp>::_Alloc_block*>
01267 bitmap_allocator<_Tp>::_S_last_request(_S_mem_blocks);
01268
01269 #if defined __GTHREADS
01270 template<typename _Tp>
01271 __gnu_cxx::_Mutex
01272 bitmap_allocator<_Tp>::_S_mut;
01273 #endif
01274
01275
01276 }
01277
01278 #endif
01279
01280