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