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() : _M_start(0), _M_finish(0),
00108 _M_end_of_storage(0)
00109 { }
00110
00111 #if 0
00112 ~__mini_vector()
00113 {
00114 if (this->_M_start)
00115 {
00116 this->deallocate(this->_M_start, this->_M_end_of_storage
00117 - this->_M_start);
00118 }
00119 }
00120 #endif
00121
00122 size_type
00123 size() const throw()
00124 { return _M_finish - _M_start; }
00125
00126 iterator
00127 begin() const throw()
00128 { return this->_M_start; }
00129
00130 iterator
00131 end() const throw()
00132 { return this->_M_finish; }
00133
00134 reference
00135 back() const throw()
00136 { return *(this->end() - 1); }
00137
00138 reference
00139 operator[](const size_type __pos) const throw()
00140 { return this->_M_start[__pos]; }
00141
00142 void
00143 insert(iterator __pos, const_reference __x);
00144
00145 void
00146 push_back(const_reference __x)
00147 {
00148 if (this->_M_space_left())
00149 {
00150 *this->end() = __x;
00151 ++this->_M_finish;
00152 }
00153 else
00154 this->insert(this->end(), __x);
00155 }
00156
00157 void
00158 pop_back() throw()
00159 { --this->_M_finish; }
00160
00161 void
00162 erase(iterator __pos) throw();
00163
00164 void
00165 clear() throw()
00166 { this->_M_finish = this->_M_start; }
00167 };
00168
00169
00170 template<typename _Tp>
00171 void __mini_vector<_Tp>::
00172 insert(iterator __pos, const_reference __x)
00173 {
00174 if (this->_M_space_left())
00175 {
00176 size_type __to_move = this->_M_finish - __pos;
00177 iterator __dest = this->end();
00178 iterator __src = this->end() - 1;
00179
00180 ++this->_M_finish;
00181 while (__to_move)
00182 {
00183 *__dest = *__src;
00184 --__dest; --__src; --__to_move;
00185 }
00186 *__pos = __x;
00187 }
00188 else
00189 {
00190 size_type __new_size = this->size() ? this->size() * 2 : 1;
00191 iterator __new_start = this->allocate(__new_size);
00192 iterator __first = this->begin();
00193 iterator __start = __new_start;
00194 while (__first != __pos)
00195 {
00196 *__start = *__first;
00197 ++__start; ++__first;
00198 }
00199 *__start = __x;
00200 ++__start;
00201 while (__first != this->end())
00202 {
00203 *__start = *__first;
00204 ++__start; ++__first;
00205 }
00206 if (this->_M_start)
00207 this->deallocate(this->_M_start, this->size());
00208
00209 this->_M_start = __new_start;
00210 this->_M_finish = __start;
00211 this->_M_end_of_storage = this->_M_start + __new_size;
00212 }
00213 }
00214
00215 template<typename _Tp>
00216 void __mini_vector<_Tp>::
00217 erase(iterator __pos) throw()
00218 {
00219 while (__pos + 1 != this->end())
00220 {
00221 *__pos = __pos[1];
00222 ++__pos;
00223 }
00224 --this->_M_finish;
00225 }
00226
00227
00228 template<typename _Tp>
00229 struct __mv_iter_traits
00230 {
00231 typedef typename _Tp::value_type value_type;
00232 typedef typename _Tp::difference_type difference_type;
00233 };
00234
00235 template<typename _Tp>
00236 struct __mv_iter_traits<_Tp*>
00237 {
00238 typedef _Tp value_type;
00239 typedef ptrdiff_t difference_type;
00240 };
00241
00242 enum
00243 {
00244 bits_per_byte = 8,
00245 bits_per_block = sizeof(size_t) * size_t(bits_per_byte)
00246 };
00247
00248 template<typename _ForwardIterator, typename _Tp, typename _Compare>
00249 _ForwardIterator
00250 __lower_bound(_ForwardIterator __first, _ForwardIterator __last,
00251 const _Tp& __val, _Compare __comp)
00252 {
00253 typedef typename __mv_iter_traits<_ForwardIterator>::value_type
00254 _ValueType;
00255 typedef typename __mv_iter_traits<_ForwardIterator>::difference_type
00256 _DistanceType;
00257
00258 _DistanceType __len = __last - __first;
00259 _DistanceType __half;
00260 _ForwardIterator __middle;
00261
00262 while (__len > 0)
00263 {
00264 __half = __len >> 1;
00265 __middle = __first;
00266 __middle += __half;
00267 if (__comp(*__middle, __val))
00268 {
00269 __first = __middle;
00270 ++__first;
00271 __len = __len - __half - 1;
00272 }
00273 else
00274 __len = __half;
00275 }
00276 return __first;
00277 }
00278
00279 template<typename _InputIterator, typename _Predicate>
00280 inline _InputIterator
00281 __find_if(_InputIterator __first, _InputIterator __last, _Predicate __p)
00282 {
00283 while (__first != __last && !__p(*__first))
00284 ++__first;
00285 return __first;
00286 }
00287
00288
00289
00290
00291 template<typename _AddrPair>
00292 inline size_t
00293 __num_blocks(_AddrPair __ap)
00294 { return (__ap.second - __ap.first) + 1; }
00295
00296
00297
00298
00299 template<typename _AddrPair>
00300 inline size_t
00301 __num_bitmaps(_AddrPair __ap)
00302 { return __num_blocks(__ap) / size_t(bits_per_block); }
00303
00304
00305 template<typename _Tp>
00306 class _Inclusive_between
00307 : public std::unary_function<typename std::pair<_Tp, _Tp>, bool>
00308 {
00309 typedef _Tp pointer;
00310 pointer _M_ptr_value;
00311 typedef typename std::pair<_Tp, _Tp> _Block_pair;
00312
00313 public:
00314 _Inclusive_between(pointer __ptr) : _M_ptr_value(__ptr)
00315 { }
00316
00317 bool
00318 operator()(_Block_pair __bp) const throw()
00319 {
00320 if (std::less_equal<pointer>()(_M_ptr_value, __bp.second)
00321 && std::greater_equal<pointer>()(_M_ptr_value, __bp.first))
00322 return true;
00323 else
00324 return false;
00325 }
00326 };
00327
00328
00329 template<typename _Functor>
00330 class _Functor_Ref
00331 : public std::unary_function<typename _Functor::argument_type,
00332 typename _Functor::result_type>
00333 {
00334 _Functor& _M_fref;
00335
00336 public:
00337 typedef typename _Functor::argument_type argument_type;
00338 typedef typename _Functor::result_type result_type;
00339
00340 _Functor_Ref(_Functor& __fref) : _M_fref(__fref)
00341 { }
00342
00343 result_type
00344 operator()(argument_type __arg)
00345 { return _M_fref(__arg); }
00346 };
00347
00348
00349
00350
00351
00352
00353
00354
00355 template<typename _Tp>
00356 class _Ffit_finder
00357 : public std::unary_function<typename std::pair<_Tp, _Tp>, bool>
00358 {
00359 typedef typename std::pair<_Tp, _Tp> _Block_pair;
00360 typedef typename __detail::__mini_vector<_Block_pair> _BPVector;
00361 typedef typename _BPVector::difference_type _Counter_type;
00362
00363 size_t* _M_pbitmap;
00364 _Counter_type _M_data_offset;
00365
00366 public:
00367 _Ffit_finder() : _M_pbitmap(0), _M_data_offset(0)
00368 { }
00369
00370 bool
00371 operator()(_Block_pair __bp) throw()
00372 {
00373
00374
00375
00376
00377
00378
00379
00380
00381
00382
00383 _Counter_type __diff =
00384 __gnu_cxx::__detail::__num_bitmaps(__bp);
00385
00386 if (*(reinterpret_cast<size_t*>
00387 (__bp.first) - (__diff + 1))
00388 == __gnu_cxx::__detail::__num_blocks(__bp))
00389 return false;
00390
00391 size_t* __rover = reinterpret_cast<size_t*>(__bp.first) - 1;
00392
00393 for (_Counter_type __i = 0; __i < __diff; ++__i)
00394 {
00395 _M_data_offset = __i;
00396 if (*__rover)
00397 {
00398 _M_pbitmap = __rover;
00399 return true;
00400 }
00401 --__rover;
00402 }
00403 return false;
00404 }
00405
00406
00407 size_t*
00408 _M_get() const throw()
00409 { return _M_pbitmap; }
00410
00411 _Counter_type
00412 _M_offset() const throw()
00413 { return _M_data_offset * size_t(bits_per_block); }
00414 };
00415
00416
00417
00418
00419
00420
00421
00422
00423
00424 template<typename _Tp>
00425 class _Bitmap_counter
00426 {
00427 typedef typename __detail::__mini_vector<typename std::pair<_Tp, _Tp> >
00428 _BPVector;
00429 typedef typename _BPVector::size_type _Index_type;
00430 typedef _Tp pointer;
00431
00432 _BPVector& _M_vbp;
00433 size_t* _M_curr_bmap;
00434 size_t* _M_last_bmap_in_block;
00435 _Index_type _M_curr_index;
00436
00437 public:
00438
00439
00440
00441 _Bitmap_counter(_BPVector& Rvbp, long __index = -1) : _M_vbp(Rvbp)
00442 { this->_M_reset(__index); }
00443
00444 void
00445 _M_reset(long __index = -1) throw()
00446 {
00447 if (__index == -1)
00448 {
00449 _M_curr_bmap = 0;
00450 _M_curr_index = static_cast<_Index_type>(-1);
00451 return;
00452 }
00453
00454 _M_curr_index = __index;
00455 _M_curr_bmap = reinterpret_cast<size_t*>
00456 (_M_vbp[_M_curr_index].first) - 1;
00457
00458 _GLIBCXX_DEBUG_ASSERT(__index <= (long)_M_vbp.size() - 1);
00459
00460 _M_last_bmap_in_block = _M_curr_bmap
00461 - ((_M_vbp[_M_curr_index].second
00462 - _M_vbp[_M_curr_index].first + 1)
00463 / size_t(bits_per_block) - 1);
00464 }
00465
00466
00467
00468
00469 void
00470 _M_set_internal_bitmap(size_t* __new_internal_marker) throw()
00471 { _M_curr_bmap = __new_internal_marker; }
00472
00473 bool
00474 _M_finished() const throw()
00475 { return(_M_curr_bmap == 0); }
00476
00477 _Bitmap_counter&
00478 operator++() throw()
00479 {
00480 if (_M_curr_bmap == _M_last_bmap_in_block)
00481 {
00482 if (++_M_curr_index == _M_vbp.size())
00483 _M_curr_bmap = 0;
00484 else
00485 this->_M_reset(_M_curr_index);
00486 }
00487 else
00488 --_M_curr_bmap;
00489 return *this;
00490 }
00491
00492 size_t*
00493 _M_get() const throw()
00494 { return _M_curr_bmap; }
00495
00496 pointer
00497 _M_base() const throw()
00498 { return _M_vbp[_M_curr_index].first; }
00499
00500 _Index_type
00501 _M_offset() const throw()
00502 {
00503 return size_t(bits_per_block)
00504 * ((reinterpret_cast<size_t*>(this->_M_base())
00505 - _M_curr_bmap) - 1);
00506 }
00507
00508 _Index_type
00509 _M_where() const throw()
00510 { return _M_curr_index; }
00511 };
00512
00513
00514
00515
00516 inline void
00517 __bit_allocate(size_t* __pbmap, size_t __pos) throw()
00518 {
00519 size_t __mask = 1 << __pos;
00520 __mask = ~__mask;
00521 *__pbmap &= __mask;
00522 }
00523
00524
00525
00526
00527 inline void
00528 __bit_free(size_t* __pbmap, size_t __pos) throw()
00529 {
00530 size_t __mask = 1 << __pos;
00531 *__pbmap |= __mask;
00532 }
00533 }
00534
00535
00536
00537 inline size_t
00538 _Bit_scan_forward(size_t __num)
00539 { return static_cast<size_t>(__builtin_ctzl(__num)); }
00540
00541
00542
00543
00544
00545
00546 class free_list
00547 {
00548 typedef size_t* value_type;
00549 typedef __detail::__mini_vector<value_type> vector_type;
00550 typedef vector_type::iterator iterator;
00551 typedef __mutex __mutex_type;
00552
00553 struct _LT_pointer_compare
00554 {
00555 bool
00556 operator()(const size_t* __pui,
00557 const size_t __cui) const throw()
00558 { return *__pui < __cui; }
00559 };
00560
00561 #if defined __GTHREADS
00562 __mutex_type&
00563 _M_get_mutex()
00564 {
00565 static __mutex_type _S_mutex;
00566 return _S_mutex;
00567 }
00568 #endif
00569
00570 vector_type&
00571 _M_get_free_list()
00572 {
00573 static vector_type _S_free_list;
00574 return _S_free_list;
00575 }
00576
00577
00578
00579
00580
00581
00582
00583
00584
00585
00586
00587 void
00588 _M_validate(size_t* __addr) throw()
00589 {
00590 vector_type& __free_list = _M_get_free_list();
00591 const vector_type::size_type __max_size = 64;
00592 if (__free_list.size() >= __max_size)
00593 {
00594
00595
00596 if (*__addr >= *__free_list.back())
00597 {
00598
00599
00600
00601 ::operator delete(static_cast<void*>(__addr));
00602 return;
00603 }
00604 else
00605 {
00606
00607
00608 ::operator delete(static_cast<void*>(__free_list.back()));
00609 __free_list.pop_back();
00610 }
00611 }
00612
00613
00614 iterator __temp = __gnu_cxx::__detail::__lower_bound
00615 (__free_list.begin(), __free_list.end(),
00616 *__addr, _LT_pointer_compare());
00617
00618
00619 __free_list.insert(__temp, __addr);
00620 }
00621
00622
00623
00624
00625
00626
00627
00628
00629
00630
00631
00632
00633 bool
00634 _M_should_i_give(size_t __block_size,
00635 size_t __required_size) throw()
00636 {
00637 const size_t __max_wastage_percentage = 36;
00638 if (__block_size >= __required_size &&
00639 (((__block_size - __required_size) * 100 / __block_size)
00640 < __max_wastage_percentage))
00641 return true;
00642 else
00643 return false;
00644 }
00645
00646 public:
00647
00648
00649
00650
00651
00652
00653 inline void
00654 _M_insert(size_t* __addr) throw()
00655 {
00656 #if defined __GTHREADS
00657 __gnu_cxx::__scoped_lock __bfl_lock(_M_get_mutex());
00658 #endif
00659
00660
00661 this->_M_validate(reinterpret_cast<size_t*>(__addr) - 1);
00662
00663 }
00664
00665
00666
00667
00668
00669
00670
00671
00672
00673 size_t*
00674 _M_get(size_t __sz) throw(std::bad_alloc);
00675
00676
00677
00678
00679 void
00680 _M_clear();
00681 };
00682
00683
00684
00685 template<typename _Tp>
00686 class bitmap_allocator;
00687
00688
00689 template<>
00690 class bitmap_allocator<void>
00691 {
00692 public:
00693 typedef void* pointer;
00694 typedef const void* const_pointer;
00695
00696
00697 typedef void value_type;
00698 template<typename _Tp1>
00699 struct rebind
00700 {
00701 typedef bitmap_allocator<_Tp1> other;
00702 };
00703 };
00704
00705
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((void *)__p) value_type(__data); }
01093
01094 #ifdef __GXX_EXPERIMENTAL_CXX0X__
01095 template<typename... _Args>
01096 void
01097 construct(pointer __p, _Args&&... __args)
01098 { ::new((void *)__p) _Tp(std::forward<_Args>(__args)...); }
01099 #endif
01100
01101 void
01102 destroy(pointer __p)
01103 { __p->~value_type(); }
01104 };
01105
01106 template<typename _Tp1, typename _Tp2>
01107 bool
01108 operator==(const bitmap_allocator<_Tp1>&,
01109 const bitmap_allocator<_Tp2>&) throw()
01110 { return true; }
01111
01112 template<typename _Tp1, typename _Tp2>
01113 bool
01114 operator!=(const bitmap_allocator<_Tp1>&,
01115 const bitmap_allocator<_Tp2>&) throw()
01116 { return false; }
01117
01118
01119 template<typename _Tp>
01120 typename bitmap_allocator<_Tp>::_BPVector
01121 bitmap_allocator<_Tp>::_S_mem_blocks;
01122
01123 template<typename _Tp>
01124 size_t bitmap_allocator<_Tp>::_S_block_size =
01125 2 * size_t(__detail::bits_per_block);
01126
01127 template<typename _Tp>
01128 typename __gnu_cxx::bitmap_allocator<_Tp>::_BPVector::size_type
01129 bitmap_allocator<_Tp>::_S_last_dealloc_index = 0;
01130
01131 template<typename _Tp>
01132 __gnu_cxx::__detail::_Bitmap_counter
01133 <typename bitmap_allocator<_Tp>::_Alloc_block*>
01134 bitmap_allocator<_Tp>::_S_last_request(_S_mem_blocks);
01135
01136 #if defined __GTHREADS
01137 template<typename _Tp>
01138 typename bitmap_allocator<_Tp>::__mutex_type
01139 bitmap_allocator<_Tp>::_S_mut;
01140 #endif
01141
01142 _GLIBCXX_END_NAMESPACE
01143
01144 #endif
01145