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 #include <cstddef>
00038 #include <bits/functexcept.h>
00039 #include <utility>
00040 #include <functional>
00041 #include <new>
00042 #include <debug/debug.h>
00043 #include <ext/concurrence.h>
00044
00045
00046
00047
00048
00049 #define _BALLOC_ALIGN_BYTES 8
00050
00051 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)
00052
00053 using std::size_t;
00054 using std::ptrdiff_t;
00055
00056 namespace __detail
00057 {
00058
00059
00060
00061
00062
00063
00064
00065
00066
00067
00068
00069
00070
00071
00072
00073
00074 template<typename _Tp>
00075 class __mini_vector
00076 {
00077 __mini_vector(const __mini_vector&);
00078 __mini_vector& operator=(const __mini_vector&);
00079
00080 public:
00081 typedef _Tp value_type;
00082 typedef _Tp* pointer;
00083 typedef _Tp& reference;
00084 typedef const _Tp& const_reference;
00085 typedef size_t size_type;
00086 typedef ptrdiff_t difference_type;
00087 typedef pointer iterator;
00088
00089 private:
00090 pointer _M_start;
00091 pointer _M_finish;
00092 pointer _M_end_of_storage;
00093
00094 size_type
00095 _M_space_left() const throw()
00096 { return _M_end_of_storage - _M_finish; }
00097
00098 pointer
00099 allocate(size_type __n)
00100 { return static_cast<pointer>(::operator new(__n * sizeof(_Tp))); }
00101
00102 void
00103 deallocate(pointer __p, size_type)
00104 { ::operator delete(__p); }
00105
00106 public:
00107
00108
00109
00110
00111 __mini_vector() : _M_start(0), _M_finish(0),
00112 _M_end_of_storage(0)
00113 { }
00114
00115 #if 0
00116 ~__mini_vector()
00117 {
00118 if (this->_M_start)
00119 {
00120 this->deallocate(this->_M_start, this->_M_end_of_storage
00121 - this->_M_start);
00122 }
00123 }
00124 #endif
00125
00126 size_type
00127 size() const throw()
00128 { return _M_finish - _M_start; }
00129
00130 iterator
00131 begin() const throw()
00132 { return this->_M_start; }
00133
00134 iterator
00135 end() const throw()
00136 { return this->_M_finish; }
00137
00138 reference
00139 back() const throw()
00140 { return *(this->end() - 1); }
00141
00142 reference
00143 operator[](const size_type __pos) const throw()
00144 { return this->_M_start[__pos]; }
00145
00146 void
00147 insert(iterator __pos, const_reference __x);
00148
00149 void
00150 push_back(const_reference __x)
00151 {
00152 if (this->_M_space_left())
00153 {
00154 *this->end() = __x;
00155 ++this->_M_finish;
00156 }
00157 else
00158 this->insert(this->end(), __x);
00159 }
00160
00161 void
00162 pop_back() throw()
00163 { --this->_M_finish; }
00164
00165 void
00166 erase(iterator __pos) throw();
00167
00168 void
00169 clear() throw()
00170 { this->_M_finish = this->_M_start; }
00171 };
00172
00173
00174 template<typename _Tp>
00175 void __mini_vector<_Tp>::
00176 insert(iterator __pos, const_reference __x)
00177 {
00178 if (this->_M_space_left())
00179 {
00180 size_type __to_move = this->_M_finish - __pos;
00181 iterator __dest = this->end();
00182 iterator __src = this->end() - 1;
00183
00184 ++this->_M_finish;
00185 while (__to_move)
00186 {
00187 *__dest = *__src;
00188 --__dest; --__src; --__to_move;
00189 }
00190 *__pos = __x;
00191 }
00192 else
00193 {
00194 size_type __new_size = this->size() ? this->size() * 2 : 1;
00195 iterator __new_start = this->allocate(__new_size);
00196 iterator __first = this->begin();
00197 iterator __start = __new_start;
00198 while (__first != __pos)
00199 {
00200 *__start = *__first;
00201 ++__start; ++__first;
00202 }
00203 *__start = __x;
00204 ++__start;
00205 while (__first != this->end())
00206 {
00207 *__start = *__first;
00208 ++__start; ++__first;
00209 }
00210 if (this->_M_start)
00211 this->deallocate(this->_M_start, this->size());
00212
00213 this->_M_start = __new_start;
00214 this->_M_finish = __start;
00215 this->_M_end_of_storage = this->_M_start + __new_size;
00216 }
00217 }
00218
00219 template<typename _Tp>
00220 void __mini_vector<_Tp>::
00221 erase(iterator __pos) throw()
00222 {
00223 while (__pos + 1 != this->end())
00224 {
00225 *__pos = __pos[1];
00226 ++__pos;
00227 }
00228 --this->_M_finish;
00229 }
00230
00231
00232 template<typename _Tp>
00233 struct __mv_iter_traits
00234 {
00235 typedef typename _Tp::value_type value_type;
00236 typedef typename _Tp::difference_type difference_type;
00237 };
00238
00239 template<typename _Tp>
00240 struct __mv_iter_traits<_Tp*>
00241 {
00242 typedef _Tp value_type;
00243 typedef ptrdiff_t difference_type;
00244 };
00245
00246 enum
00247 {
00248 bits_per_byte = 8,
00249 bits_per_block = sizeof(size_t) * size_t(bits_per_byte)
00250 };
00251
00252 template<typename _ForwardIterator, typename _Tp, typename _Compare>
00253 _ForwardIterator
00254 __lower_bound(_ForwardIterator __first, _ForwardIterator __last,
00255 const _Tp& __val, _Compare __comp)
00256 {
00257 typedef typename __mv_iter_traits<_ForwardIterator>::value_type
00258 _ValueType;
00259 typedef typename __mv_iter_traits<_ForwardIterator>::difference_type
00260 _DistanceType;
00261
00262 _DistanceType __len = __last - __first;
00263 _DistanceType __half;
00264 _ForwardIterator __middle;
00265
00266 while (__len > 0)
00267 {
00268 __half = __len >> 1;
00269 __middle = __first;
00270 __middle += __half;
00271 if (__comp(*__middle, __val))
00272 {
00273 __first = __middle;
00274 ++__first;
00275 __len = __len - __half - 1;
00276 }
00277 else
00278 __len = __half;
00279 }
00280 return __first;
00281 }
00282
00283 template<typename _InputIterator, typename _Predicate>
00284 inline _InputIterator
00285 __find_if(_InputIterator __first, _InputIterator __last, _Predicate __p)
00286 {
00287 while (__first != __last && !__p(*__first))
00288 ++__first;
00289 return __first;
00290 }
00291
00292
00293
00294
00295 template<typename _AddrPair>
00296 inline size_t
00297 __num_blocks(_AddrPair __ap)
00298 { return (__ap.second - __ap.first) + 1; }
00299
00300
00301
00302
00303 template<typename _AddrPair>
00304 inline size_t
00305 __num_bitmaps(_AddrPair __ap)
00306 { return __num_blocks(__ap) / size_t(bits_per_block); }
00307
00308
00309 template<typename _Tp>
00310 class _Inclusive_between
00311 : public std::unary_function<typename std::pair<_Tp, _Tp>, bool>
00312 {
00313 typedef _Tp pointer;
00314 pointer _M_ptr_value;
00315 typedef typename std::pair<_Tp, _Tp> _Block_pair;
00316
00317 public:
00318 _Inclusive_between(pointer __ptr) : _M_ptr_value(__ptr)
00319 { }
00320
00321 bool
00322 operator()(_Block_pair __bp) const throw()
00323 {
00324 if (std::less_equal<pointer>()(_M_ptr_value, __bp.second)
00325 && std::greater_equal<pointer>()(_M_ptr_value, __bp.first))
00326 return true;
00327 else
00328 return false;
00329 }
00330 };
00331
00332
00333 template<typename _Functor>
00334 class _Functor_Ref
00335 : public std::unary_function<typename _Functor::argument_type,
00336 typename _Functor::result_type>
00337 {
00338 _Functor& _M_fref;
00339
00340 public:
00341 typedef typename _Functor::argument_type argument_type;
00342 typedef typename _Functor::result_type result_type;
00343
00344 _Functor_Ref(_Functor& __fref) : _M_fref(__fref)
00345 { }
00346
00347 result_type
00348 operator()(argument_type __arg)
00349 { return _M_fref(__arg); }
00350 };
00351
00352
00353
00354
00355
00356
00357
00358
00359 template<typename _Tp>
00360 class _Ffit_finder
00361 : public std::unary_function<typename std::pair<_Tp, _Tp>, bool>
00362 {
00363 typedef typename std::pair<_Tp, _Tp> _Block_pair;
00364 typedef typename __detail::__mini_vector<_Block_pair> _BPVector;
00365 typedef typename _BPVector::difference_type _Counter_type;
00366
00367 size_t* _M_pbitmap;
00368 _Counter_type _M_data_offset;
00369
00370 public:
00371 _Ffit_finder() : _M_pbitmap(0), _M_data_offset(0)
00372 { }
00373
00374 bool
00375 operator()(_Block_pair __bp) throw()
00376 {
00377
00378
00379
00380
00381
00382
00383
00384
00385
00386
00387 _Counter_type __diff =
00388 __gnu_cxx::__detail::__num_bitmaps(__bp);
00389
00390 if (*(reinterpret_cast<size_t*>
00391 (__bp.first) - (__diff + 1))
00392 == __gnu_cxx::__detail::__num_blocks(__bp))
00393 return false;
00394
00395 size_t* __rover = reinterpret_cast<size_t*>(__bp.first) - 1;
00396
00397 for (_Counter_type __i = 0; __i < __diff; ++__i)
00398 {
00399 _M_data_offset = __i;
00400 if (*__rover)
00401 {
00402 _M_pbitmap = __rover;
00403 return true;
00404 }
00405 --__rover;
00406 }
00407 return false;
00408 }
00409
00410
00411 size_t*
00412 _M_get() const throw()
00413 { return _M_pbitmap; }
00414
00415 _Counter_type
00416 _M_offset() const throw()
00417 { return _M_data_offset * size_t(bits_per_block); }
00418 };
00419
00420
00421
00422
00423
00424
00425
00426
00427
00428 template<typename _Tp>
00429 class _Bitmap_counter
00430 {
00431 typedef typename __detail::__mini_vector<typename std::pair<_Tp, _Tp> >
00432 _BPVector;
00433 typedef typename _BPVector::size_type _Index_type;
00434 typedef _Tp pointer;
00435
00436 _BPVector& _M_vbp;
00437 size_t* _M_curr_bmap;
00438 size_t* _M_last_bmap_in_block;
00439 _Index_type _M_curr_index;
00440
00441 public:
00442
00443
00444
00445 _Bitmap_counter(_BPVector& Rvbp, long __index = -1) : _M_vbp(Rvbp)
00446 { this->_M_reset(__index); }
00447
00448 void
00449 _M_reset(long __index = -1) throw()
00450 {
00451 if (__index == -1)
00452 {
00453 _M_curr_bmap = 0;
00454 _M_curr_index = static_cast<_Index_type>(-1);
00455 return;
00456 }
00457
00458 _M_curr_index = __index;
00459 _M_curr_bmap = reinterpret_cast<size_t*>
00460 (_M_vbp[_M_curr_index].first) - 1;
00461
00462 _GLIBCXX_DEBUG_ASSERT(__index <= (long)_M_vbp.size() - 1);
00463
00464 _M_last_bmap_in_block = _M_curr_bmap
00465 - ((_M_vbp[_M_curr_index].second
00466 - _M_vbp[_M_curr_index].first + 1)
00467 / size_t(bits_per_block) - 1);
00468 }
00469
00470
00471
00472
00473 void
00474 _M_set_internal_bitmap(size_t* __new_internal_marker) throw()
00475 { _M_curr_bmap = __new_internal_marker; }
00476
00477 bool
00478 _M_finished() const throw()
00479 { return(_M_curr_bmap == 0); }
00480
00481 _Bitmap_counter&
00482 operator++() throw()
00483 {
00484 if (_M_curr_bmap == _M_last_bmap_in_block)
00485 {
00486 if (++_M_curr_index == _M_vbp.size())
00487 _M_curr_bmap = 0;
00488 else
00489 this->_M_reset(_M_curr_index);
00490 }
00491 else
00492 --_M_curr_bmap;
00493 return *this;
00494 }
00495
00496 size_t*
00497 _M_get() const throw()
00498 { return _M_curr_bmap; }
00499
00500 pointer
00501 _M_base() const throw()
00502 { return _M_vbp[_M_curr_index].first; }
00503
00504 _Index_type
00505 _M_offset() const throw()
00506 {
00507 return size_t(bits_per_block)
00508 * ((reinterpret_cast<size_t*>(this->_M_base())
00509 - _M_curr_bmap) - 1);
00510 }
00511
00512 _Index_type
00513 _M_where() const throw()
00514 { return _M_curr_index; }
00515 };
00516
00517
00518
00519
00520 inline void
00521 __bit_allocate(size_t* __pbmap, size_t __pos) throw()
00522 {
00523 size_t __mask = 1 << __pos;
00524 __mask = ~__mask;
00525 *__pbmap &= __mask;
00526 }
00527
00528
00529
00530
00531 inline void
00532 __bit_free(size_t* __pbmap, size_t __pos) throw()
00533 {
00534 size_t __mask = 1 << __pos;
00535 *__pbmap |= __mask;
00536 }
00537 }
00538
00539
00540
00541 inline size_t
00542 _Bit_scan_forward(size_t __num)
00543 { return static_cast<size_t>(__builtin_ctzl(__num)); }
00544
00545
00546
00547
00548
00549
00550 class free_list
00551 {
00552 typedef size_t* value_type;
00553 typedef __detail::__mini_vector<value_type> vector_type;
00554 typedef vector_type::iterator iterator;
00555 typedef __mutex __mutex_type;
00556
00557 struct _LT_pointer_compare
00558 {
00559 bool
00560 operator()(const size_t* __pui,
00561 const size_t __cui) const throw()
00562 { return *__pui < __cui; }
00563 };
00564
00565 #if defined __GTHREADS
00566 __mutex_type&
00567 _M_get_mutex()
00568 {
00569 static __mutex_type _S_mutex;
00570 return _S_mutex;
00571 }
00572 #endif
00573
00574 vector_type&
00575 _M_get_free_list()
00576 {
00577 static vector_type _S_free_list;
00578 return _S_free_list;
00579 }
00580
00581
00582
00583
00584
00585
00586
00587
00588
00589
00590
00591 void
00592 _M_validate(size_t* __addr) throw()
00593 {
00594 vector_type& __free_list = _M_get_free_list();
00595 const vector_type::size_type __max_size = 64;
00596 if (__free_list.size() >= __max_size)
00597 {
00598
00599
00600 if (*__addr >= *__free_list.back())
00601 {
00602
00603
00604
00605 ::operator delete(static_cast<void*>(__addr));
00606 return;
00607 }
00608 else
00609 {
00610
00611
00612 ::operator delete(static_cast<void*>(__free_list.back()));
00613 __free_list.pop_back();
00614 }
00615 }
00616
00617
00618 iterator __temp = __gnu_cxx::__detail::__lower_bound
00619 (__free_list.begin(), __free_list.end(),
00620 *__addr, _LT_pointer_compare());
00621
00622
00623 __free_list.insert(__temp, __addr);
00624 }
00625
00626
00627
00628
00629
00630
00631
00632
00633
00634
00635
00636
00637 bool
00638 _M_should_i_give(size_t __block_size,
00639 size_t __required_size) throw()
00640 {
00641 const size_t __max_wastage_percentage = 36;
00642 if (__block_size >= __required_size &&
00643 (((__block_size - __required_size) * 100 / __block_size)
00644 < __max_wastage_percentage))
00645 return true;
00646 else
00647 return false;
00648 }
00649
00650 public:
00651
00652
00653
00654
00655
00656
00657 inline void
00658 _M_insert(size_t* __addr) throw()
00659 {
00660 #if defined __GTHREADS
00661 __gnu_cxx::__scoped_lock __bfl_lock(_M_get_mutex());
00662 #endif
00663
00664
00665 this->_M_validate(reinterpret_cast<size_t*>(__addr) - 1);
00666
00667 }
00668
00669
00670
00671
00672
00673
00674
00675
00676
00677 size_t*
00678 _M_get(size_t __sz) throw(std::bad_alloc);
00679
00680
00681
00682
00683 void
00684 _M_clear();
00685 };
00686
00687
00688
00689 template<typename _Tp>
00690 class bitmap_allocator;
00691
00692
00693 template<>
00694 class bitmap_allocator<void>
00695 {
00696 public:
00697 typedef void* pointer;
00698 typedef const void* const_pointer;
00699
00700
00701 typedef void value_type;
00702 template<typename _Tp1>
00703 struct rebind
00704 {
00705 typedef bitmap_allocator<_Tp1> other;
00706 };
00707 };
00708
00709 template<typename _Tp>
00710 class bitmap_allocator : private free_list
00711 {
00712 public:
00713 typedef size_t size_type;
00714 typedef ptrdiff_t difference_type;
00715 typedef _Tp* pointer;
00716 typedef const _Tp* const_pointer;
00717 typedef _Tp& reference;
00718 typedef const _Tp& const_reference;
00719 typedef _Tp value_type;
00720 typedef free_list::__mutex_type __mutex_type;
00721
00722 template<typename _Tp1>
00723 struct rebind
00724 {
00725 typedef bitmap_allocator<_Tp1> other;
00726 };
00727
00728 private:
00729 template<size_t _BSize, size_t _AlignSize>
00730 struct aligned_size
00731 {
00732 enum
00733 {
00734 modulus = _BSize % _AlignSize,
00735 value = _BSize + (modulus ? _AlignSize - (modulus) : 0)
00736 };
00737 };
00738
00739 struct _Alloc_block
00740 {
00741 char __M_unused[aligned_size<sizeof(value_type),
00742 _BALLOC_ALIGN_BYTES>::value];
00743 };
00744
00745
00746 typedef typename std::pair<_Alloc_block*, _Alloc_block*> _Block_pair;
00747
00748 typedef typename
00749 __detail::__mini_vector<_Block_pair> _BPVector;
00750
00751 #if defined _GLIBCXX_DEBUG
00752
00753
00754 void
00755 _S_check_for_free_blocks() throw()
00756 {
00757 typedef typename
00758 __gnu_cxx::__detail::_Ffit_finder<_Alloc_block*> _FFF;
00759 _FFF __fff;
00760 typedef typename _BPVector::iterator _BPiter;
00761 _BPiter __bpi =
00762 __gnu_cxx::__detail::__find_if
00763 (_S_mem_blocks.begin(), _S_mem_blocks.end(),
00764 __gnu_cxx::__detail::_Functor_Ref<_FFF>(__fff));
00765
00766 _GLIBCXX_DEBUG_ASSERT(__bpi == _S_mem_blocks.end());
00767 }
00768 #endif
00769
00770
00771
00772
00773
00774
00775
00776
00777
00778
00779
00780
00781 void
00782 _S_refill_pool() throw(std::bad_alloc)
00783 {
00784 #if defined _GLIBCXX_DEBUG
00785 _S_check_for_free_blocks();
00786 #endif
00787
00788 const size_t __num_bitmaps = (_S_block_size
00789 / size_t(__detail::bits_per_block));
00790 const size_t __size_to_allocate = sizeof(size_t)
00791 + _S_block_size * sizeof(_Alloc_block)
00792 + __num_bitmaps * sizeof(size_t);
00793
00794 size_t* __temp =
00795 reinterpret_cast<size_t*>
00796 (this->_M_get(__size_to_allocate));
00797 *__temp = 0;
00798 ++__temp;
00799
00800
00801 _Block_pair __bp =
00802 std::make_pair(reinterpret_cast<_Alloc_block*>
00803 (__temp + __num_bitmaps),
00804 reinterpret_cast<_Alloc_block*>
00805 (__temp + __num_bitmaps)
00806 + _S_block_size - 1);
00807
00808
00809 _S_mem_blocks.push_back(__bp);
00810
00811 size_t __bit_mask = 0;
00812 __bit_mask = ~__bit_mask;
00813
00814 for (size_t __i = 0; __i < __num_bitmaps; ++__i)
00815 __temp[__i] = __bit_mask;
00816
00817 _S_block_size *= 2;
00818 }
00819
00820
00821 static _BPVector _S_mem_blocks;
00822 static size_t _S_block_size;
00823 static __gnu_cxx::__detail::
00824 _Bitmap_counter<_Alloc_block*> _S_last_request;
00825 static typename _BPVector::size_type _S_last_dealloc_index;
00826 #if defined __GTHREADS
00827 static __mutex_type _S_mut;
00828 #endif
00829
00830 public:
00831
00832
00833
00834
00835
00836
00837
00838
00839
00840
00841
00842
00843
00844
00845 pointer
00846 _M_allocate_single_object() throw(std::bad_alloc)
00847 {
00848 #if defined __GTHREADS
00849 __gnu_cxx::__scoped_lock __bit_lock(_S_mut);
00850 #endif
00851
00852
00853
00854
00855
00856
00857
00858
00859
00860
00861
00862
00863
00864
00865 while (_S_last_request._M_finished() == false
00866 && (*(_S_last_request._M_get()) == 0))
00867 {
00868 _S_last_request.operator++();
00869 }
00870
00871 if (__builtin_expect(_S_last_request._M_finished() == true, false))
00872 {
00873
00874 typedef typename
00875 __gnu_cxx::__detail::_Ffit_finder<_Alloc_block*> _FFF;
00876 _FFF __fff;
00877 typedef typename _BPVector::iterator _BPiter;
00878 _BPiter __bpi =
00879 __gnu_cxx::__detail::__find_if
00880 (_S_mem_blocks.begin(), _S_mem_blocks.end(),
00881 __gnu_cxx::__detail::_Functor_Ref<_FFF>(__fff));
00882
00883 if (__bpi != _S_mem_blocks.end())
00884 {
00885
00886
00887
00888 size_t __nz_bit = _Bit_scan_forward(*__fff._M_get());
00889 __detail::__bit_allocate(__fff._M_get(), __nz_bit);
00890
00891 _S_last_request._M_reset(__bpi - _S_mem_blocks.begin());
00892
00893
00894 pointer __ret = reinterpret_cast<pointer>
00895 (__bpi->first + __fff._M_offset() + __nz_bit);
00896 size_t* __puse_count =
00897 reinterpret_cast<size_t*>
00898 (__bpi->first)
00899 - (__gnu_cxx::__detail::__num_bitmaps(*__bpi) + 1);
00900
00901 ++(*__puse_count);
00902 return __ret;
00903 }
00904 else
00905 {
00906
00907
00908 _S_refill_pool();
00909
00910
00911
00912 _S_last_request._M_reset(_S_mem_blocks.size() - 1);
00913
00914
00915 }
00916 }
00917
00918
00919
00920 size_t __nz_bit = _Bit_scan_forward(*_S_last_request._M_get());
00921 __detail::__bit_allocate(_S_last_request._M_get(), __nz_bit);
00922
00923 pointer __ret = reinterpret_cast<pointer>
00924 (_S_last_request._M_base() + _S_last_request._M_offset() + __nz_bit);
00925
00926 size_t* __puse_count = reinterpret_cast<size_t*>
00927 (_S_mem_blocks[_S_last_request._M_where()].first)
00928 - (__gnu_cxx::__detail::
00929 __num_bitmaps(_S_mem_blocks[_S_last_request._M_where()]) + 1);
00930
00931 ++(*__puse_count);
00932 return __ret;
00933 }
00934
00935
00936
00937
00938
00939
00940
00941
00942
00943 void
00944 _M_deallocate_single_object(pointer __p) throw()
00945 {
00946 #if defined __GTHREADS
00947 __gnu_cxx::__scoped_lock __bit_lock(_S_mut);
00948 #endif
00949 _Alloc_block* __real_p = reinterpret_cast<_Alloc_block*>(__p);
00950
00951 typedef typename _BPVector::iterator _Iterator;
00952 typedef typename _BPVector::difference_type _Difference_type;
00953
00954 _Difference_type __diff;
00955 long __displacement;
00956
00957 _GLIBCXX_DEBUG_ASSERT(_S_last_dealloc_index >= 0);
00958
00959
00960 if (__gnu_cxx::__detail::_Inclusive_between<_Alloc_block*>
00961 (__real_p) (_S_mem_blocks[_S_last_dealloc_index]))
00962 {
00963 _GLIBCXX_DEBUG_ASSERT(_S_last_dealloc_index
00964 <= _S_mem_blocks.size() - 1);
00965
00966
00967 __diff = _S_last_dealloc_index;
00968 __displacement = __real_p - _S_mem_blocks[__diff].first;
00969 }
00970 else
00971 {
00972 _Iterator _iter = __gnu_cxx::__detail::
00973 __find_if(_S_mem_blocks.begin(),
00974 _S_mem_blocks.end(),
00975 __gnu_cxx::__detail::
00976 _Inclusive_between<_Alloc_block*>(__real_p));
00977
00978 _GLIBCXX_DEBUG_ASSERT(_iter != _S_mem_blocks.end());
00979
00980 __diff = _iter - _S_mem_blocks.begin();
00981 __displacement = __real_p - _S_mem_blocks[__diff].first;
00982 _S_last_dealloc_index = __diff;
00983 }
00984
00985
00986 const size_t __rotate = (__displacement
00987 % size_t(__detail::bits_per_block));
00988 size_t* __bitmapC =
00989 reinterpret_cast<size_t*>
00990 (_S_mem_blocks[__diff].first) - 1;
00991 __bitmapC -= (__displacement / size_t(__detail::bits_per_block));
00992
00993 __detail::__bit_free(__bitmapC, __rotate);
00994 size_t* __puse_count = reinterpret_cast<size_t*>
00995 (_S_mem_blocks[__diff].first)
00996 - (__gnu_cxx::__detail::__num_bitmaps(_S_mem_blocks[__diff]) + 1);
00997
00998 _GLIBCXX_DEBUG_ASSERT(*__puse_count != 0);
00999
01000 --(*__puse_count);
01001
01002 if (__builtin_expect(*__puse_count == 0, false))
01003 {
01004 _S_block_size /= 2;
01005
01006
01007
01008 this->_M_insert(__puse_count);
01009 _S_mem_blocks.erase(_S_mem_blocks.begin() + __diff);
01010
01011
01012
01013
01014
01015
01016
01017 if ((_Difference_type)_S_last_request._M_where() >= __diff--)
01018 _S_last_request._M_reset(__diff);
01019
01020
01021
01022
01023
01024
01025 if (_S_last_dealloc_index >= _S_mem_blocks.size())
01026 {
01027 _S_last_dealloc_index =(__diff != -1 ? __diff : 0);
01028 _GLIBCXX_DEBUG_ASSERT(_S_last_dealloc_index >= 0);
01029 }
01030 }
01031 }
01032
01033 public:
01034 bitmap_allocator() throw()
01035 { }
01036
01037 bitmap_allocator(const bitmap_allocator&)
01038 { }
01039
01040 template<typename _Tp1>
01041 bitmap_allocator(const bitmap_allocator<_Tp1>&) throw()
01042 { }
01043
01044 ~bitmap_allocator() throw()
01045 { }
01046
01047 pointer
01048 allocate(size_type __n)
01049 {
01050 if (__builtin_expect(__n > this->max_size(), false))
01051 std::__throw_bad_alloc();
01052
01053 if (__builtin_expect(__n == 1, true))
01054 return this->_M_allocate_single_object();
01055 else
01056 {
01057 const size_type __b = __n * sizeof(value_type);
01058 return reinterpret_cast<pointer>(::operator new(__b));
01059 }
01060 }
01061
01062 pointer
01063 allocate(size_type __n, typename bitmap_allocator<void>::const_pointer)
01064 { return allocate(__n); }
01065
01066 void
01067 deallocate(pointer __p, size_type __n) throw()
01068 {
01069 if (__builtin_expect(__p != 0, true))
01070 {
01071 if (__builtin_expect(__n == 1, true))
01072 this->_M_deallocate_single_object(__p);
01073 else
01074 ::operator delete(__p);
01075 }
01076 }
01077
01078 pointer
01079 address(reference __r) const
01080 { return &__r; }
01081
01082 const_pointer
01083 address(const_reference __r) const
01084 { return &__r; }
01085
01086 size_type
01087 max_size() const throw()
01088 { return size_type(-1) / sizeof(value_type); }
01089
01090 void
01091 construct(pointer __p, const_reference __data)
01092 { ::new(__p) value_type(__data); }
01093
01094 void
01095 destroy(pointer __p)
01096 { __p->~value_type(); }
01097 };
01098
01099 template<typename _Tp1, typename _Tp2>
01100 bool
01101 operator==(const bitmap_allocator<_Tp1>&,
01102 const bitmap_allocator<_Tp2>&) throw()
01103 { return true; }
01104
01105 template<typename _Tp1, typename _Tp2>
01106 bool
01107 operator!=(const bitmap_allocator<_Tp1>&,
01108 const bitmap_allocator<_Tp2>&) throw()
01109 { return false; }
01110
01111
01112 template<typename _Tp>
01113 typename bitmap_allocator<_Tp>::_BPVector
01114 bitmap_allocator<_Tp>::_S_mem_blocks;
01115
01116 template<typename _Tp>
01117 size_t bitmap_allocator<_Tp>::_S_block_size =
01118 2 * size_t(__detail::bits_per_block);
01119
01120 template<typename _Tp>
01121 typename __gnu_cxx::bitmap_allocator<_Tp>::_BPVector::size_type
01122 bitmap_allocator<_Tp>::_S_last_dealloc_index = 0;
01123
01124 template<typename _Tp>
01125 __gnu_cxx::__detail::_Bitmap_counter
01126 <typename bitmap_allocator<_Tp>::_Alloc_block*>
01127 bitmap_allocator<_Tp>::_S_last_request(_S_mem_blocks);
01128
01129 #if defined __GTHREADS
01130 template<typename _Tp>
01131 typename bitmap_allocator<_Tp>::__mutex_type
01132 bitmap_allocator<_Tp>::_S_mut;
01133 #endif
01134
01135 _GLIBCXX_END_NAMESPACE
01136
01137 #endif
01138