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 <utility>
00034 #include <bits/functexcept.h>
00035 #include <functional>
00036 #include <new>
00037 #include <debug/debug.h>
00038 #include <ext/concurrence.h>
00039 #include <bits/move.h>
00040
00041
00042
00043
00044 #define _BALLOC_ALIGN_BYTES 8
00045
00046 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
00047 {
00048 using std::size_t;
00049 using std::ptrdiff_t;
00050
00051 namespace __detail
00052 {
00053 _GLIBCXX_BEGIN_NAMESPACE_VERSION
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 _GLIBCXX_END_NAMESPACE_VERSION
00510 }
00511
00512 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00513
00514
00515
00516 inline size_t
00517 _Bit_scan_forward(size_t __num)
00518 { return static_cast<size_t>(__builtin_ctzl(__num)); }
00519
00520
00521
00522
00523
00524
00525 class free_list
00526 {
00527 public:
00528 typedef size_t* value_type;
00529 typedef __detail::__mini_vector<value_type> vector_type;
00530 typedef vector_type::iterator iterator;
00531 typedef __mutex __mutex_type;
00532
00533 private:
00534 struct _LT_pointer_compare
00535 {
00536 bool
00537 operator()(const size_t* __pui,
00538 const size_t __cui) const throw()
00539 { return *__pui < __cui; }
00540 };
00541
00542 #if defined __GTHREADS
00543 __mutex_type&
00544 _M_get_mutex()
00545 {
00546 static __mutex_type _S_mutex;
00547 return _S_mutex;
00548 }
00549 #endif
00550
00551 vector_type&
00552 _M_get_free_list()
00553 {
00554 static vector_type _S_free_list;
00555 return _S_free_list;
00556 }
00557
00558
00559
00560
00561
00562
00563
00564
00565
00566
00567
00568 void
00569 _M_validate(size_t* __addr) throw()
00570 {
00571 vector_type& __free_list = _M_get_free_list();
00572 const vector_type::size_type __max_size = 64;
00573 if (__free_list.size() >= __max_size)
00574 {
00575
00576
00577 if (*__addr >= *__free_list.back())
00578 {
00579
00580
00581
00582 ::operator delete(static_cast<void*>(__addr));
00583 return;
00584 }
00585 else
00586 {
00587
00588
00589 ::operator delete(static_cast<void*>(__free_list.back()));
00590 __free_list.pop_back();
00591 }
00592 }
00593
00594
00595 iterator __temp = __detail::__lower_bound
00596 (__free_list.begin(), __free_list.end(),
00597 *__addr, _LT_pointer_compare());
00598
00599
00600 __free_list.insert(__temp, __addr);
00601 }
00602
00603
00604
00605
00606
00607
00608
00609
00610
00611
00612
00613
00614 bool
00615 _M_should_i_give(size_t __block_size,
00616 size_t __required_size) throw()
00617 {
00618 const size_t __max_wastage_percentage = 36;
00619 if (__block_size >= __required_size &&
00620 (((__block_size - __required_size) * 100 / __block_size)
00621 < __max_wastage_percentage))
00622 return true;
00623 else
00624 return false;
00625 }
00626
00627 public:
00628
00629
00630
00631
00632
00633
00634 inline void
00635 _M_insert(size_t* __addr) throw()
00636 {
00637 #if defined __GTHREADS
00638 __scoped_lock __bfl_lock(_M_get_mutex());
00639 #endif
00640
00641
00642 this->_M_validate(reinterpret_cast<size_t*>(__addr) - 1);
00643
00644 }
00645
00646
00647
00648
00649
00650
00651
00652
00653
00654 size_t*
00655 _M_get(size_t __sz) throw(std::bad_alloc);
00656
00657
00658
00659
00660 void
00661 _M_clear();
00662 };
00663
00664
00665
00666 template<typename _Tp>
00667 class bitmap_allocator;
00668
00669
00670 template<>
00671 class bitmap_allocator<void>
00672 {
00673 public:
00674 typedef void* pointer;
00675 typedef const void* const_pointer;
00676
00677
00678 typedef void value_type;
00679 template<typename _Tp1>
00680 struct rebind
00681 {
00682 typedef bitmap_allocator<_Tp1> other;
00683 };
00684 };
00685
00686
00687
00688
00689
00690 template<typename _Tp>
00691 class bitmap_allocator : private free_list
00692 {
00693 public:
00694 typedef size_t size_type;
00695 typedef ptrdiff_t difference_type;
00696 typedef _Tp* pointer;
00697 typedef const _Tp* const_pointer;
00698 typedef _Tp& reference;
00699 typedef const _Tp& const_reference;
00700 typedef _Tp value_type;
00701 typedef free_list::__mutex_type __mutex_type;
00702
00703 template<typename _Tp1>
00704 struct rebind
00705 {
00706 typedef bitmap_allocator<_Tp1> other;
00707 };
00708
00709 private:
00710 template<size_t _BSize, size_t _AlignSize>
00711 struct aligned_size
00712 {
00713 enum
00714 {
00715 modulus = _BSize % _AlignSize,
00716 value = _BSize + (modulus ? _AlignSize - (modulus) : 0)
00717 };
00718 };
00719
00720 struct _Alloc_block
00721 {
00722 char __M_unused[aligned_size<sizeof(value_type),
00723 _BALLOC_ALIGN_BYTES>::value];
00724 };
00725
00726
00727 typedef typename std::pair<_Alloc_block*, _Alloc_block*> _Block_pair;
00728
00729 typedef typename __detail::__mini_vector<_Block_pair> _BPVector;
00730 typedef typename _BPVector::iterator _BPiter;
00731
00732 template<typename _Predicate>
00733 static _BPiter
00734 _S_find(_Predicate __p)
00735 {
00736 _BPiter __first = _S_mem_blocks.begin();
00737 while (__first != _S_mem_blocks.end() && !__p(*__first))
00738 ++__first;
00739 return __first;
00740 }
00741
00742 #if defined _GLIBCXX_DEBUG
00743
00744
00745 void
00746 _S_check_for_free_blocks() throw()
00747 {
00748 typedef typename __detail::_Ffit_finder<_Alloc_block*> _FFF;
00749 _BPiter __bpi = _S_find(_FFF());
00750
00751 _GLIBCXX_DEBUG_ASSERT(__bpi == _S_mem_blocks.end());
00752 }
00753 #endif
00754
00755
00756
00757
00758
00759
00760
00761
00762
00763
00764
00765
00766 void
00767 _S_refill_pool() throw(std::bad_alloc)
00768 {
00769 #if defined _GLIBCXX_DEBUG
00770 _S_check_for_free_blocks();
00771 #endif
00772
00773 const size_t __num_bitmaps = (_S_block_size
00774 / size_t(__detail::bits_per_block));
00775 const size_t __size_to_allocate = sizeof(size_t)
00776 + _S_block_size * sizeof(_Alloc_block)
00777 + __num_bitmaps * sizeof(size_t);
00778
00779 size_t* __temp =
00780 reinterpret_cast<size_t*>(this->_M_get(__size_to_allocate));
00781 *__temp = 0;
00782 ++__temp;
00783
00784
00785 _Block_pair __bp =
00786 std::make_pair(reinterpret_cast<_Alloc_block*>
00787 (__temp + __num_bitmaps),
00788 reinterpret_cast<_Alloc_block*>
00789 (__temp + __num_bitmaps)
00790 + _S_block_size - 1);
00791
00792
00793 _S_mem_blocks.push_back(__bp);
00794
00795 for (size_t __i = 0; __i < __num_bitmaps; ++__i)
00796 __temp[__i] = ~static_cast<size_t>(0);
00797
00798 _S_block_size *= 2;
00799 }
00800
00801 static _BPVector _S_mem_blocks;
00802 static size_t _S_block_size;
00803 static __detail::_Bitmap_counter<_Alloc_block*> _S_last_request;
00804 static typename _BPVector::size_type _S_last_dealloc_index;
00805 #if defined __GTHREADS
00806 static __mutex_type _S_mut;
00807 #endif
00808
00809 public:
00810
00811
00812
00813
00814
00815
00816
00817
00818
00819
00820
00821
00822
00823
00824 pointer
00825 _M_allocate_single_object() throw(std::bad_alloc)
00826 {
00827 #if defined __GTHREADS
00828 __scoped_lock __bit_lock(_S_mut);
00829 #endif
00830
00831
00832
00833
00834
00835
00836
00837
00838
00839
00840
00841
00842
00843
00844 while (_S_last_request._M_finished() == false
00845 && (*(_S_last_request._M_get()) == 0))
00846 _S_last_request.operator++();
00847
00848 if (__builtin_expect(_S_last_request._M_finished() == true, false))
00849 {
00850
00851 typedef typename __detail::_Ffit_finder<_Alloc_block*> _FFF;
00852 _FFF __fff;
00853 _BPiter __bpi = _S_find(__detail::_Functor_Ref<_FFF>(__fff));
00854
00855 if (__bpi != _S_mem_blocks.end())
00856 {
00857
00858
00859
00860 size_t __nz_bit = _Bit_scan_forward(*__fff._M_get());
00861 __detail::__bit_allocate(__fff._M_get(), __nz_bit);
00862
00863 _S_last_request._M_reset(__bpi - _S_mem_blocks.begin());
00864
00865
00866 pointer __ret = reinterpret_cast<pointer>
00867 (__bpi->first + __fff._M_offset() + __nz_bit);
00868 size_t* __puse_count =
00869 reinterpret_cast<size_t*>
00870 (__bpi->first) - (__detail::__num_bitmaps(*__bpi) + 1);
00871
00872 ++(*__puse_count);
00873 return __ret;
00874 }
00875 else
00876 {
00877
00878
00879 _S_refill_pool();
00880
00881
00882
00883 _S_last_request._M_reset(_S_mem_blocks.size() - 1);
00884
00885
00886 }
00887 }
00888
00889
00890
00891 size_t __nz_bit = _Bit_scan_forward(*_S_last_request._M_get());
00892 __detail::__bit_allocate(_S_last_request._M_get(), __nz_bit);
00893
00894 pointer __ret = reinterpret_cast<pointer>
00895 (_S_last_request._M_base() + _S_last_request._M_offset() + __nz_bit);
00896
00897 size_t* __puse_count = reinterpret_cast<size_t*>
00898 (_S_mem_blocks[_S_last_request._M_where()].first)
00899 - (__detail::
00900 __num_bitmaps(_S_mem_blocks[_S_last_request._M_where()]) + 1);
00901
00902 ++(*__puse_count);
00903 return __ret;
00904 }
00905
00906
00907
00908
00909
00910
00911
00912
00913
00914 void
00915 _M_deallocate_single_object(pointer __p) throw()
00916 {
00917 #if defined __GTHREADS
00918 __scoped_lock __bit_lock(_S_mut);
00919 #endif
00920 _Alloc_block* __real_p = reinterpret_cast<_Alloc_block*>(__p);
00921
00922 typedef typename _BPVector::iterator _Iterator;
00923 typedef typename _BPVector::difference_type _Difference_type;
00924
00925 _Difference_type __diff;
00926 long __displacement;
00927
00928 _GLIBCXX_DEBUG_ASSERT(_S_last_dealloc_index >= 0);
00929
00930 __detail::_Inclusive_between<_Alloc_block*> __ibt(__real_p);
00931 if (__ibt(_S_mem_blocks[_S_last_dealloc_index]))
00932 {
00933 _GLIBCXX_DEBUG_ASSERT(_S_last_dealloc_index
00934 <= _S_mem_blocks.size() - 1);
00935
00936
00937 __diff = _S_last_dealloc_index;
00938 __displacement = __real_p - _S_mem_blocks[__diff].first;
00939 }
00940 else
00941 {
00942 _Iterator _iter = _S_find(__ibt);
00943
00944 _GLIBCXX_DEBUG_ASSERT(_iter != _S_mem_blocks.end());
00945
00946 __diff = _iter - _S_mem_blocks.begin();
00947 __displacement = __real_p - _S_mem_blocks[__diff].first;
00948 _S_last_dealloc_index = __diff;
00949 }
00950
00951
00952 const size_t __rotate = (__displacement
00953 % size_t(__detail::bits_per_block));
00954 size_t* __bitmapC =
00955 reinterpret_cast<size_t*>
00956 (_S_mem_blocks[__diff].first) - 1;
00957 __bitmapC -= (__displacement / size_t(__detail::bits_per_block));
00958
00959 __detail::__bit_free(__bitmapC, __rotate);
00960 size_t* __puse_count = reinterpret_cast<size_t*>
00961 (_S_mem_blocks[__diff].first)
00962 - (__detail::__num_bitmaps(_S_mem_blocks[__diff]) + 1);
00963
00964 _GLIBCXX_DEBUG_ASSERT(*__puse_count != 0);
00965
00966 --(*__puse_count);
00967
00968 if (__builtin_expect(*__puse_count == 0, false))
00969 {
00970 _S_block_size /= 2;
00971
00972
00973
00974 this->_M_insert(__puse_count);
00975 _S_mem_blocks.erase(_S_mem_blocks.begin() + __diff);
00976
00977
00978
00979
00980
00981
00982
00983 if ((_Difference_type)_S_last_request._M_where() >= __diff--)
00984 _S_last_request._M_reset(__diff);
00985
00986
00987
00988
00989
00990
00991 if (_S_last_dealloc_index >= _S_mem_blocks.size())
00992 {
00993 _S_last_dealloc_index =(__diff != -1 ? __diff : 0);
00994 _GLIBCXX_DEBUG_ASSERT(_S_last_dealloc_index >= 0);
00995 }
00996 }
00997 }
00998
00999 public:
01000 bitmap_allocator() throw()
01001 { }
01002
01003 bitmap_allocator(const bitmap_allocator&)
01004 { }
01005
01006 template<typename _Tp1>
01007 bitmap_allocator(const bitmap_allocator<_Tp1>&) throw()
01008 { }
01009
01010 ~bitmap_allocator() throw()
01011 { }
01012
01013 pointer
01014 allocate(size_type __n)
01015 {
01016 if (__n > this->max_size())
01017 std::__throw_bad_alloc();
01018
01019 if (__builtin_expect(__n == 1, true))
01020 return this->_M_allocate_single_object();
01021 else
01022 {
01023 const size_type __b = __n * sizeof(value_type);
01024 return reinterpret_cast<pointer>(::operator new(__b));
01025 }
01026 }
01027
01028 pointer
01029 allocate(size_type __n, typename bitmap_allocator<void>::const_pointer)
01030 { return allocate(__n); }
01031
01032 void
01033 deallocate(pointer __p, size_type __n) throw()
01034 {
01035 if (__builtin_expect(__p != 0, true))
01036 {
01037 if (__builtin_expect(__n == 1, true))
01038 this->_M_deallocate_single_object(__p);
01039 else
01040 ::operator delete(__p);
01041 }
01042 }
01043
01044 pointer
01045 address(reference __r) const
01046 { return std::__addressof(__r); }
01047
01048 const_pointer
01049 address(const_reference __r) const
01050 { return std::__addressof(__r); }
01051
01052 size_type
01053 max_size() const throw()
01054 { return size_type(-1) / sizeof(value_type); }
01055
01056 void
01057 construct(pointer __p, const_reference __data)
01058 { ::new((void *)__p) value_type(__data); }
01059
01060 #ifdef __GXX_EXPERIMENTAL_CXX0X__
01061 template<typename... _Args>
01062 void
01063 construct(pointer __p, _Args&&... __args)
01064 { ::new((void *)__p) _Tp(std::forward<_Args>(__args)...); }
01065 #endif
01066
01067 void
01068 destroy(pointer __p)
01069 { __p->~value_type(); }
01070 };
01071
01072 template<typename _Tp1, typename _Tp2>
01073 bool
01074 operator==(const bitmap_allocator<_Tp1>&,
01075 const bitmap_allocator<_Tp2>&) throw()
01076 { return true; }
01077
01078 template<typename _Tp1, typename _Tp2>
01079 bool
01080 operator!=(const bitmap_allocator<_Tp1>&,
01081 const bitmap_allocator<_Tp2>&) throw()
01082 { return false; }
01083
01084
01085 template<typename _Tp>
01086 typename bitmap_allocator<_Tp>::_BPVector
01087 bitmap_allocator<_Tp>::_S_mem_blocks;
01088
01089 template<typename _Tp>
01090 size_t bitmap_allocator<_Tp>::_S_block_size =
01091 2 * size_t(__detail::bits_per_block);
01092
01093 template<typename _Tp>
01094 typename bitmap_allocator<_Tp>::_BPVector::size_type
01095 bitmap_allocator<_Tp>::_S_last_dealloc_index = 0;
01096
01097 template<typename _Tp>
01098 __detail::_Bitmap_counter
01099 <typename bitmap_allocator<_Tp>::_Alloc_block*>
01100 bitmap_allocator<_Tp>::_S_last_request(_S_mem_blocks);
01101
01102 #if defined __GTHREADS
01103 template<typename _Tp>
01104 typename bitmap_allocator<_Tp>::__mutex_type
01105 bitmap_allocator<_Tp>::_S_mut;
01106 #endif
01107
01108 _GLIBCXX_END_NAMESPACE_VERSION
01109 }
01110
01111 #endif
01112