30 #ifndef _BITMAP_ALLOCATOR_H
31 #define _BITMAP_ALLOCATOR_H 1
45 #define _BALLOC_ALIGN_BYTES 8
47 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)
70 template<
typename _Tp>
77 typedef _Tp value_type;
79 typedef _Tp& reference;
80 typedef const _Tp& const_reference;
81 typedef size_t size_type;
82 typedef ptrdiff_t difference_type;
83 typedef pointer iterator;
88 pointer _M_end_of_storage;
91 _M_space_left()
const throw()
92 {
return _M_end_of_storage - _M_finish; }
95 allocate(size_type __n)
96 {
return static_cast<pointer
>(::operator
new(__n *
sizeof(_Tp))); }
99 deallocate(pointer __p, size_type)
100 { ::operator
delete(__p); }
116 this->deallocate(this->_M_start, this->_M_end_of_storage
124 {
return _M_finish - _M_start; }
127 begin()
const throw()
128 {
return this->_M_start; }
132 {
return this->_M_finish; }
136 {
return *(this->end() - 1); }
139 operator[](
const size_type __pos)
const throw()
140 {
return this->_M_start[__pos]; }
143 insert(iterator __pos, const_reference __x);
146 push_back(const_reference __x)
148 if (this->_M_space_left())
154 this->insert(this->end(), __x);
159 { --this->_M_finish; }
162 erase(iterator __pos)
throw();
166 { this->_M_finish = this->_M_start; }
170 template<
typename _Tp>
174 if (this->_M_space_left())
176 size_type __to_move = this->_M_finish - __pos;
184 --__dest; --__src; --__to_move;
190 size_type __new_size = this->size() ? this->size() * 2 : 1;
191 iterator __new_start = this->allocate(__new_size);
192 iterator __first = this->begin();
193 iterator __start = __new_start;
194 while (__first != __pos)
197 ++__start; ++__first;
201 while (__first != this->end())
204 ++__start; ++__first;
207 this->deallocate(this->_M_start, this->size());
209 this->_M_start = __new_start;
210 this->_M_finish = __start;
211 this->_M_end_of_storage = this->_M_start + __new_size;
215 template<
typename _Tp>
216 void __mini_vector<_Tp>::
217 erase(iterator __pos)
throw()
219 while (__pos + 1 != this->end())
228 template<
typename _Tp>
229 struct __mv_iter_traits
231 typedef typename _Tp::value_type value_type;
232 typedef typename _Tp::difference_type difference_type;
235 template<
typename _Tp>
236 struct __mv_iter_traits<_Tp*>
238 typedef _Tp value_type;
239 typedef ptrdiff_t difference_type;
245 bits_per_block =
sizeof(size_t) *
size_t(bits_per_byte)
248 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
250 __lower_bound(_ForwardIterator __first, _ForwardIterator __last,
251 const _Tp& __val, _Compare __comp)
253 typedef typename __mv_iter_traits<_ForwardIterator>::value_type
255 typedef typename __mv_iter_traits<_ForwardIterator>::difference_type
258 _DistanceType __len = __last - __first;
259 _DistanceType __half;
260 _ForwardIterator __middle;
267 if (__comp(*__middle, __val))
271 __len = __len - __half - 1;
279 template<
typename _InputIterator,
typename _Predicate>
280 inline _InputIterator
281 __find_if(_InputIterator __first, _InputIterator __last, _Predicate __p)
283 while (__first != __last && !__p(*__first))
291 template<
typename _AddrPair>
294 {
return (__ap.second - __ap.first) + 1; }
299 template<
typename _AddrPair>
305 template<
typename _Tp>
306 class _Inclusive_between
310 pointer _M_ptr_value;
314 _Inclusive_between(pointer __ptr) : _M_ptr_value(__ptr)
318 operator()(_Block_pair __bp)
const throw()
329 template<
typename _Functor>
332 typename _Functor::result_type>
338 typedef typename _Functor::result_type
result_type;
340 _Functor_Ref(_Functor& __fref) : _M_fref(__fref)
344 operator()(argument_type __arg)
345 {
return _M_fref(__arg); }
355 template<
typename _Tp>
361 typedef typename _BPVector::difference_type _Counter_type;
364 _Counter_type _M_data_offset;
383 _Counter_type __diff =
386 if (*(reinterpret_cast<size_t*>
387 (__bp.
first) - (__diff + 1))
391 size_t* __rover =
reinterpret_cast<size_t*
>(__bp.
first) - 1;
393 for (_Counter_type __i = 0; __i < __diff; ++__i)
395 _M_data_offset = __i;
398 _M_pbitmap = __rover;
408 _M_get()
const throw()
409 {
return _M_pbitmap; }
412 _M_offset()
const throw()
413 {
return _M_data_offset * size_t(bits_per_block); }
424 template<
typename _Tp>
429 typedef typename _BPVector::size_type _Index_type;
433 size_t* _M_curr_bmap;
434 size_t* _M_last_bmap_in_block;
435 _Index_type _M_curr_index;
442 { this->_M_reset(__index); }
445 _M_reset(
long __index = -1)
throw()
450 _M_curr_index =
static_cast<_Index_type
>(-1);
454 _M_curr_index = __index;
455 _M_curr_bmap =
reinterpret_cast<size_t*
>
456 (_M_vbp[_M_curr_index].first) - 1;
458 _GLIBCXX_DEBUG_ASSERT(__index <= (
long)_M_vbp.size() - 1);
460 _M_last_bmap_in_block = _M_curr_bmap
461 - ((_M_vbp[_M_curr_index].second
462 - _M_vbp[_M_curr_index].first + 1)
463 /
size_t(bits_per_block) - 1);
470 _M_set_internal_bitmap(
size_t* __new_internal_marker)
throw()
471 { _M_curr_bmap = __new_internal_marker; }
474 _M_finished()
const throw()
475 {
return(_M_curr_bmap == 0); }
480 if (_M_curr_bmap == _M_last_bmap_in_block)
482 if (++_M_curr_index == _M_vbp.size())
485 this->_M_reset(_M_curr_index);
493 _M_get()
const throw()
494 {
return _M_curr_bmap; }
497 _M_base()
const throw()
498 {
return _M_vbp[_M_curr_index].first; }
501 _M_offset()
const throw()
503 return size_t(bits_per_block)
504 * ((
reinterpret_cast<size_t*
>(this->_M_base())
505 - _M_curr_bmap) - 1);
509 _M_where()
const throw()
510 {
return _M_curr_index; }
519 size_t __mask = 1 << __pos;
530 size_t __mask = 1 << __pos;
539 {
return static_cast<size_t>(__builtin_ctzl(__num)); }
548 typedef size_t* value_type;
550 typedef vector_type::iterator iterator;
551 typedef __mutex __mutex_type;
553 struct _LT_pointer_compare
556 operator()(
const size_t* __pui,
557 const size_t __cui)
const throw()
558 {
return *__pui < __cui; }
561 #if defined __GTHREADS
565 static __mutex_type _S_mutex;
588 _M_validate(
size_t* __addr)
throw()
591 const vector_type::size_type __max_size = 64;
592 if (__free_list.size() >= __max_size)
596 if (*__addr >= *__free_list.back())
601 ::operator
delete(
static_cast<void*
>(__addr));
608 ::operator
delete(
static_cast<void*
>(__free_list.back()));
609 __free_list.pop_back();
614 iterator __temp = __gnu_cxx::__detail::__lower_bound
615 (__free_list.begin(), __free_list.end(),
616 *__addr, _LT_pointer_compare());
619 __free_list.insert(__temp, __addr);
634 _M_should_i_give(
size_t __block_size,
635 size_t __required_size)
throw()
637 const size_t __max_wastage_percentage = 36;
638 if (__block_size >= __required_size &&
639 (((__block_size - __required_size) * 100 / __block_size)
640 < __max_wastage_percentage))
654 _M_insert(
size_t* __addr)
throw()
656 #if defined __GTHREADS
661 this->_M_validate(reinterpret_cast<size_t*>(__addr) - 1);
685 template<
typename _Tp>
693 typedef void* pointer;
694 typedef const void* const_pointer;
697 typedef void value_type;
698 template<
typename _Tp1>
709 template<
typename _Tp>
710 class bitmap_allocator :
private free_list
713 typedef size_t size_type;
714 typedef ptrdiff_t difference_type;
715 typedef _Tp* pointer;
716 typedef const _Tp* const_pointer;
717 typedef _Tp& reference;
718 typedef const _Tp& const_reference;
719 typedef _Tp value_type;
720 typedef free_list::__mutex_type __mutex_type;
722 template<
typename _Tp1>
725 typedef bitmap_allocator<_Tp1> other;
729 template<
size_t _BSize,
size_t _AlignSize>
734 modulus = _BSize % _AlignSize,
735 value = _BSize + (modulus ? _AlignSize - (modulus) : 0)
741 char __M_unused[aligned_size<
sizeof(value_type),
749 __detail::__mini_vector<_Block_pair> _BPVector;
751 #if defined _GLIBCXX_DEBUG
755 _S_check_for_free_blocks() throw()
760 typedef typename _BPVector::iterator _BPiter;
762 __gnu_cxx::__detail::__find_if
763 (_S_mem_blocks.begin(), _S_mem_blocks.end(),
764 __gnu_cxx::__detail::_Functor_Ref<_FFF>(__fff));
766 _GLIBCXX_DEBUG_ASSERT(__bpi == _S_mem_blocks.end());
782 _S_refill_pool() throw(std::bad_alloc)
784 #if defined _GLIBCXX_DEBUG
785 _S_check_for_free_blocks();
789 / size_t(__detail::bits_per_block));
790 const size_t __size_to_allocate =
sizeof(size_t)
791 + _S_block_size *
sizeof(_Alloc_block)
792 + __num_bitmaps *
sizeof(size_t);
795 reinterpret_cast<size_t*
>
796 (this->_M_get(__size_to_allocate));
802 std::make_pair(reinterpret_cast<_Alloc_block*>
803 (__temp + __num_bitmaps),
804 reinterpret_cast<_Alloc_block*>
805 (__temp + __num_bitmaps)
806 + _S_block_size - 1);
809 _S_mem_blocks.push_back(__bp);
811 size_t __bit_mask = 0;
812 __bit_mask = ~__bit_mask;
815 __temp[__i] = __bit_mask;
821 static _BPVector _S_mem_blocks;
822 static size_t _S_block_size;
825 static typename _BPVector::size_type _S_last_dealloc_index;
826 #if defined __GTHREADS
827 static __mutex_type _S_mut;
846 _M_allocate_single_object() throw(std::bad_alloc)
848 #if defined __GTHREADS
865 while (_S_last_request._M_finished() ==
false
866 && (*(_S_last_request._M_get()) == 0))
868 _S_last_request.operator++();
871 if (__builtin_expect(_S_last_request._M_finished() ==
true,
false))
877 typedef typename _BPVector::iterator _BPiter;
879 __gnu_cxx::__detail::__find_if
880 (_S_mem_blocks.begin(), _S_mem_blocks.end(),
881 __gnu_cxx::__detail::_Functor_Ref<_FFF>(__fff));
883 if (__bpi != _S_mem_blocks.end())
891 _S_last_request._M_reset(__bpi - _S_mem_blocks.begin());
894 pointer __ret =
reinterpret_cast<pointer
>
895 (__bpi->first + __fff._M_offset() + __nz_bit);
896 size_t* __puse_count =
897 reinterpret_cast<size_t*
>
912 _S_last_request._M_reset(_S_mem_blocks.size() - 1);
923 pointer __ret =
reinterpret_cast<pointer
>
924 (_S_last_request._M_base() + _S_last_request._M_offset() + __nz_bit);
926 size_t* __puse_count =
reinterpret_cast<size_t*
>
927 (_S_mem_blocks[_S_last_request._M_where()].first)
928 - (__gnu_cxx::__detail::
929 __num_bitmaps(_S_mem_blocks[_S_last_request._M_where()]) + 1);
944 _M_deallocate_single_object(pointer __p)
throw()
946 #if defined __GTHREADS
949 _Alloc_block* __real_p =
reinterpret_cast<_Alloc_block*
>(__p);
951 typedef typename _BPVector::iterator _Iterator;
952 typedef typename _BPVector::difference_type _Difference_type;
954 _Difference_type __diff;
957 _GLIBCXX_DEBUG_ASSERT(_S_last_dealloc_index >= 0);
960 if (__gnu_cxx::__detail::_Inclusive_between<_Alloc_block*>
961 (__real_p) (_S_mem_blocks[_S_last_dealloc_index]))
963 _GLIBCXX_DEBUG_ASSERT(_S_last_dealloc_index
964 <= _S_mem_blocks.size() - 1);
967 __diff = _S_last_dealloc_index;
968 __displacement = __real_p - _S_mem_blocks[__diff].first;
972 _Iterator _iter = __gnu_cxx::__detail::
973 __find_if(_S_mem_blocks.begin(),
975 __gnu_cxx::__detail::
976 _Inclusive_between<_Alloc_block*>(__real_p));
978 _GLIBCXX_DEBUG_ASSERT(_iter != _S_mem_blocks.end());
980 __diff = _iter - _S_mem_blocks.begin();
981 __displacement = __real_p - _S_mem_blocks[__diff].first;
982 _S_last_dealloc_index = __diff;
986 const size_t __rotate = (__displacement
987 % size_t(__detail::bits_per_block));
989 reinterpret_cast<size_t*
>
990 (_S_mem_blocks[__diff].first) - 1;
991 __bitmapC -= (__displacement / size_t(__detail::bits_per_block));
994 size_t* __puse_count =
reinterpret_cast<size_t*
>
995 (_S_mem_blocks[__diff].first)
998 _GLIBCXX_DEBUG_ASSERT(*__puse_count != 0);
1002 if (__builtin_expect(*__puse_count == 0,
false))
1008 this->_M_insert(__puse_count);
1009 _S_mem_blocks.erase(_S_mem_blocks.begin() + __diff);
1017 if ((_Difference_type)_S_last_request._M_where() >= __diff--)
1018 _S_last_request._M_reset(__diff);
1025 if (_S_last_dealloc_index >= _S_mem_blocks.size())
1027 _S_last_dealloc_index =(__diff != -1 ? __diff : 0);
1028 _GLIBCXX_DEBUG_ASSERT(_S_last_dealloc_index >= 0);
1037 bitmap_allocator(
const bitmap_allocator&)
1040 template<
typename _Tp1>
1041 bitmap_allocator(
const bitmap_allocator<_Tp1>&) throw()
1044 ~bitmap_allocator() throw()
1048 allocate(size_type __n)
1050 if (__builtin_expect(__n > this->max_size(),
false))
1051 std::__throw_bad_alloc();
1053 if (__builtin_expect(__n == 1,
true))
1054 return this->_M_allocate_single_object();
1057 const size_type __b = __n *
sizeof(value_type);
1058 return reinterpret_cast<pointer
>(::operator
new(__b));
1063 allocate(size_type __n,
typename bitmap_allocator<void>::const_pointer)
1064 {
return allocate(__n); }
1067 deallocate(pointer __p, size_type __n)
throw()
1069 if (__builtin_expect(__p != 0,
true))
1071 if (__builtin_expect(__n == 1,
true))
1072 this->_M_deallocate_single_object(__p);
1074 ::operator
delete(__p);
1079 address(reference __r)
const
1083 address(const_reference __r)
const
1087 max_size()
const throw()
1088 {
return size_type(-1) /
sizeof(value_type); }
1091 construct(pointer __p, const_reference __data)
1092 { ::new((
void *)__p) value_type(__data); }
1094 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1095 template<
typename... _Args>
1097 construct(pointer __p, _Args&&... __args)
1098 { ::new((
void *)__p) _Tp(std::forward<_Args>(__args)...); }
1102 destroy(pointer __p)
1103 { __p->~value_type(); }
1106 template<
typename _Tp1,
typename _Tp2>
1108 operator==(
const bitmap_allocator<_Tp1>&,
1109 const bitmap_allocator<_Tp2>&) throw()
1112 template<
typename _Tp1,
typename _Tp2>
1114 operator!=(
const bitmap_allocator<_Tp1>&,
1115 const bitmap_allocator<_Tp2>&) throw()
1119 template<
typename _Tp>
1120 typename bitmap_allocator<_Tp>::_BPVector
1121 bitmap_allocator<_Tp>::_S_mem_blocks;
1123 template<
typename _Tp>
1124 size_t bitmap_allocator<_Tp>::_S_block_size =
1125 2 * size_t(__detail::bits_per_block);
1127 template<
typename _Tp>
1128 typename __gnu_cxx::bitmap_allocator<_Tp>::_BPVector::size_type
1129 bitmap_allocator<_Tp>::_S_last_dealloc_index = 0;
1131 template<
typename _Tp>
1133 <
typename bitmap_allocator<_Tp>::_Alloc_block*>
1134 bitmap_allocator<_Tp>::_S_last_request(_S_mem_blocks);
1136 #if defined __GTHREADS
1137 template<
typename _Tp>
1138 typename bitmap_allocator<_Tp>::__mutex_type
1139 bitmap_allocator<_Tp>::_S_mut;
1142 _GLIBCXX_END_NAMESPACE