30 #ifndef _BITMAP_ALLOCATOR_H
31 #define _BITMAP_ALLOCATOR_H 1
44 #define _BALLOC_ALIGN_BYTES 8
46 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
53 _GLIBCXX_BEGIN_NAMESPACE_VERSION
69 template<
typename _Tp>
76 typedef _Tp value_type;
78 typedef _Tp& reference;
79 typedef const _Tp& const_reference;
80 typedef size_t size_type;
81 typedef ptrdiff_t difference_type;
82 typedef pointer iterator;
87 pointer _M_end_of_storage;
90 _M_space_left()
const throw()
91 {
return _M_end_of_storage - _M_finish; }
94 allocate(size_type __n)
95 {
return static_cast<pointer
>(::operator
new(__n *
sizeof(_Tp))); }
98 deallocate(pointer __p, size_type)
99 { ::operator
delete(__p); }
107 : _M_start(0), _M_finish(0), _M_end_of_storage(0) { }
111 {
return _M_finish - _M_start; }
114 begin()
const throw()
115 {
return this->_M_start; }
119 {
return this->_M_finish; }
123 {
return *(this->end() - 1); }
126 operator[](
const size_type __pos)
const throw()
127 {
return this->_M_start[__pos]; }
130 insert(iterator __pos, const_reference __x);
133 push_back(const_reference __x)
135 if (this->_M_space_left())
141 this->insert(this->end(), __x);
146 { --this->_M_finish; }
149 erase(iterator __pos)
throw();
153 { this->_M_finish = this->_M_start; }
157 template<
typename _Tp>
161 if (this->_M_space_left())
163 size_type __to_move = this->_M_finish - __pos;
171 --__dest; --__src; --__to_move;
177 size_type __new_size = this->
size() ? this->
size() * 2 : 1;
178 iterator __new_start = this->allocate(__new_size);
179 iterator __first = this->
begin();
180 iterator __start = __new_start;
181 while (__first != __pos)
184 ++__start; ++__first;
188 while (__first != this->
end())
191 ++__start; ++__first;
194 this->deallocate(this->_M_start, this->
size());
196 this->_M_start = __new_start;
197 this->_M_finish = __start;
198 this->_M_end_of_storage = this->_M_start + __new_size;
202 template<
typename _Tp>
203 void __mini_vector<_Tp>::
204 erase(iterator __pos)
throw()
206 while (__pos + 1 != this->
end())
215 template<
typename _Tp>
216 struct __mv_iter_traits
218 typedef typename _Tp::value_type value_type;
219 typedef typename _Tp::difference_type difference_type;
222 template<
typename _Tp>
223 struct __mv_iter_traits<_Tp*>
225 typedef _Tp value_type;
226 typedef ptrdiff_t difference_type;
232 bits_per_block =
sizeof(size_t) *
size_t(bits_per_byte)
235 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
237 __lower_bound(_ForwardIterator __first, _ForwardIterator __last,
238 const _Tp& __val, _Compare __comp)
240 typedef typename __mv_iter_traits<_ForwardIterator>::difference_type
243 _DistanceType __len = __last - __first;
244 _DistanceType __half;
245 _ForwardIterator __middle;
252 if (__comp(*__middle, __val))
256 __len = __len - __half - 1;
267 template<
typename _AddrPair>
270 {
return (__ap.second - __ap.first) + 1; }
275 template<
typename _AddrPair>
281 template<
typename _Tp>
282 class _Inclusive_between
286 pointer _M_ptr_value;
290 _Inclusive_between(pointer __ptr) : _M_ptr_value(__ptr)
294 operator()(_Block_pair __bp)
const throw()
305 template<
typename _Functor>
308 typename _Functor::result_type>
313 typedef typename _Functor::argument_type argument_type;
314 typedef typename _Functor::result_type result_type;
316 _Functor_Ref(_Functor& __fref) : _M_fref(__fref)
320 operator()(argument_type __arg)
321 {
return _M_fref(__arg); }
331 template<
typename _Tp>
337 typedef typename _BPVector::difference_type _Counter_type;
340 _Counter_type _M_data_offset;
361 if (*(reinterpret_cast<size_t*>
365 size_t* __rover =
reinterpret_cast<size_t*
>(__bp.
first) - 1;
367 for (_Counter_type __i = 0; __i < __diff; ++__i)
369 _M_data_offset = __i;
372 _M_pbitmap = __rover;
381 _M_get()
const throw()
382 {
return _M_pbitmap; }
385 _M_offset()
const throw()
386 {
return _M_data_offset * size_t(bits_per_block); }
396 template<
typename _Tp>
401 typedef typename _BPVector::size_type _Index_type;
405 size_t* _M_curr_bmap;
406 size_t* _M_last_bmap_in_block;
407 _Index_type _M_curr_index;
414 { this->_M_reset(__index); }
417 _M_reset(
long __index = -1)
throw()
422 _M_curr_index =
static_cast<_Index_type
>(-1);
426 _M_curr_index = __index;
427 _M_curr_bmap =
reinterpret_cast<size_t*
>
428 (_M_vbp[_M_curr_index].first) - 1;
430 _GLIBCXX_DEBUG_ASSERT(__index <= (
long)_M_vbp.size() - 1);
432 _M_last_bmap_in_block = _M_curr_bmap
433 - ((_M_vbp[_M_curr_index].second
434 - _M_vbp[_M_curr_index].first + 1)
435 /
size_t(bits_per_block) - 1);
442 _M_set_internal_bitmap(
size_t* __new_internal_marker)
throw()
443 { _M_curr_bmap = __new_internal_marker; }
446 _M_finished()
const throw()
447 {
return(_M_curr_bmap == 0); }
452 if (_M_curr_bmap == _M_last_bmap_in_block)
454 if (++_M_curr_index == _M_vbp.size())
457 this->_M_reset(_M_curr_index);
465 _M_get()
const throw()
466 {
return _M_curr_bmap; }
469 _M_base()
const throw()
470 {
return _M_vbp[_M_curr_index].first; }
473 _M_offset()
const throw()
475 return size_t(bits_per_block)
476 * ((
reinterpret_cast<size_t*
>(this->_M_base())
477 - _M_curr_bmap) - 1);
481 _M_where()
const throw()
482 {
return _M_curr_index; }
491 size_t __mask = 1 << __pos;
502 size_t __mask = 1 << __pos;
506 _GLIBCXX_END_NAMESPACE_VERSION
509 _GLIBCXX_BEGIN_NAMESPACE_VERSION
515 {
return static_cast<size_t>(__builtin_ctzl(__num)); }
525 typedef size_t* value_type;
527 typedef vector_type::iterator iterator;
528 typedef __mutex __mutex_type;
531 struct _LT_pointer_compare
534 operator()(
const size_t* __pui,
535 const size_t __cui)
const throw()
536 {
return *__pui < __cui; }
539 #if defined __GTHREADS
543 static __mutex_type _S_mutex;
566 _M_validate(
size_t* __addr)
throw()
569 const vector_type::size_type __max_size = 64;
570 if (__free_list.size() >= __max_size)
574 if (*__addr >= *__free_list.back())
579 ::operator
delete(
static_cast<void*
>(__addr));
586 ::operator
delete(
static_cast<void*
>(__free_list.back()));
587 __free_list.pop_back();
592 iterator __temp = __detail::__lower_bound
593 (__free_list.begin(), __free_list.end(),
594 *__addr, _LT_pointer_compare());
597 __free_list.insert(__temp, __addr);
612 _M_should_i_give(
size_t __block_size,
613 size_t __required_size)
throw()
615 const size_t __max_wastage_percentage = 36;
616 if (__block_size >= __required_size &&
617 (((__block_size - __required_size) * 100 / __block_size)
618 < __max_wastage_percentage))
634 #if defined __GTHREADS
639 this->_M_validate(reinterpret_cast<size_t*>(__addr) - 1);
663 template<
typename _Tp>
664 class bitmap_allocator;
668 class bitmap_allocator<void>
671 typedef void* pointer;
672 typedef const void* const_pointer;
675 typedef void value_type;
676 template<
typename _Tp1>
679 typedef bitmap_allocator<_Tp1> other;
687 template<
typename _Tp>
691 typedef size_t size_type;
692 typedef ptrdiff_t difference_type;
693 typedef _Tp* pointer;
694 typedef const _Tp* const_pointer;
695 typedef _Tp& reference;
696 typedef const _Tp& const_reference;
697 typedef _Tp value_type;
698 typedef free_list::__mutex_type __mutex_type;
700 template<
typename _Tp1>
707 template<
size_t _BSize,
size_t _AlignSize>
712 modulus = _BSize % _AlignSize,
713 value = _BSize + (modulus ? _AlignSize - (modulus) : 0)
719 char __M_unused[aligned_size<
sizeof(value_type),
727 typedef typename _BPVector::iterator _BPiter;
729 template<
typename _Predicate>
731 _S_find(_Predicate __p)
733 _BPiter __first = _S_mem_blocks.begin();
734 while (__first != _S_mem_blocks.end() && !__p(*__first))
739 #if defined _GLIBCXX_DEBUG
743 _S_check_for_free_blocks()
throw()
746 _BPiter __bpi = _S_find(_FFF());
748 _GLIBCXX_DEBUG_ASSERT(__bpi == _S_mem_blocks.end());
766 #if defined _GLIBCXX_DEBUG
767 _S_check_for_free_blocks();
771 / size_t(__detail::bits_per_block));
772 const size_t __size_to_allocate =
sizeof(size_t)
773 + _S_block_size *
sizeof(_Alloc_block)
774 + __num_bitmaps *
sizeof(size_t);
777 reinterpret_cast<size_t*
>(this->
_M_get(__size_to_allocate));
784 (__temp + __num_bitmaps),
785 reinterpret_cast<_Alloc_block*>
786 (__temp + __num_bitmaps)
787 + _S_block_size - 1);
790 _S_mem_blocks.push_back(__bp);
793 __temp[__i] = ~static_cast<size_t>(0);
799 static size_t _S_block_size;
801 static typename _BPVector::size_type _S_last_dealloc_index;
802 #if defined __GTHREADS
803 static __mutex_type _S_mut;
824 #if defined __GTHREADS
841 while (_S_last_request._M_finished() ==
false
842 && (*(_S_last_request._M_get()) == 0))
843 _S_last_request.operator++();
845 if (__builtin_expect(_S_last_request._M_finished() ==
true,
false))
850 _BPiter __bpi = _S_find(__detail::_Functor_Ref<_FFF>(__fff));
852 if (__bpi != _S_mem_blocks.end())
860 _S_last_request._M_reset(__bpi - _S_mem_blocks.begin());
863 pointer __ret =
reinterpret_cast<pointer
>
864 (__bpi->first + __fff._M_offset() + __nz_bit);
865 size_t* __puse_count =
866 reinterpret_cast<size_t*
>
880 _S_last_request._M_reset(_S_mem_blocks.size() - 1);
891 pointer __ret =
reinterpret_cast<pointer
>
892 (_S_last_request._M_base() + _S_last_request._M_offset() + __nz_bit);
894 size_t* __puse_count =
reinterpret_cast<size_t*
>
895 (_S_mem_blocks[_S_last_request._M_where()].first)
897 __num_bitmaps(_S_mem_blocks[_S_last_request._M_where()]) + 1);
914 #if defined __GTHREADS
917 _Alloc_block* __real_p =
reinterpret_cast<_Alloc_block*
>(__p);
919 typedef typename _BPVector::iterator _Iterator;
920 typedef typename _BPVector::difference_type _Difference_type;
922 _Difference_type __diff;
925 _GLIBCXX_DEBUG_ASSERT(_S_last_dealloc_index >= 0);
927 __detail::_Inclusive_between<_Alloc_block*> __ibt(__real_p);
928 if (__ibt(_S_mem_blocks[_S_last_dealloc_index]))
930 _GLIBCXX_DEBUG_ASSERT(_S_last_dealloc_index
931 <= _S_mem_blocks.size() - 1);
934 __diff = _S_last_dealloc_index;
935 __displacement = __real_p - _S_mem_blocks[__diff].first;
939 _Iterator _iter = _S_find(__ibt);
941 _GLIBCXX_DEBUG_ASSERT(_iter != _S_mem_blocks.end());
943 __diff = _iter - _S_mem_blocks.begin();
944 __displacement = __real_p - _S_mem_blocks[__diff].first;
945 _S_last_dealloc_index = __diff;
949 const size_t __rotate = (__displacement
950 % size_t(__detail::bits_per_block));
952 reinterpret_cast<size_t*
>
953 (_S_mem_blocks[__diff].first) - 1;
954 __bitmapC -= (__displacement / size_t(__detail::bits_per_block));
957 size_t* __puse_count =
reinterpret_cast<size_t*
>
958 (_S_mem_blocks[__diff].first)
961 _GLIBCXX_DEBUG_ASSERT(*__puse_count != 0);
965 if (__builtin_expect(*__puse_count == 0,
false))
972 _S_mem_blocks.erase(_S_mem_blocks.begin() + __diff);
980 if ((_Difference_type)_S_last_request._M_where() >= __diff--)
981 _S_last_request._M_reset(__diff);
988 if (_S_last_dealloc_index >= _S_mem_blocks.size())
990 _S_last_dealloc_index =(__diff != -1 ? __diff : 0);
991 _GLIBCXX_DEBUG_ASSERT(_S_last_dealloc_index >= 0);
1000 bitmap_allocator(
const bitmap_allocator&) _GLIBCXX_USE_NOEXCEPT
1003 template<
typename _Tp1>
1004 bitmap_allocator(
const bitmap_allocator<_Tp1>&) _GLIBCXX_USE_NOEXCEPT
1007 ~bitmap_allocator() _GLIBCXX_USE_NOEXCEPT
1011 allocate(size_type __n)
1013 if (__n > this->max_size())
1014 std::__throw_bad_alloc();
1016 if (__builtin_expect(__n == 1,
true))
1020 const size_type __b = __n *
sizeof(value_type);
1021 return reinterpret_cast<pointer
>(::operator
new(__b));
1026 allocate(size_type __n,
typename bitmap_allocator<void>::const_pointer)
1027 {
return allocate(__n); }
1030 deallocate(pointer __p, size_type __n)
throw()
1032 if (__builtin_expect(__p != 0,
true))
1034 if (__builtin_expect(__n == 1,
true))
1037 ::operator
delete(__p);
1042 address(reference __r)
const _GLIBCXX_NOEXCEPT
1046 address(const_reference __r)
const _GLIBCXX_NOEXCEPT
1050 max_size() const _GLIBCXX_USE_NOEXCEPT
1051 {
return size_type(-1) /
sizeof(value_type); }
1053 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1054 template<
typename _Up,
typename... _Args>
1056 construct(_Up* __p, _Args&&... __args)
1057 { ::new((
void *)__p) _Up(std::
forward<_Args>(__args)...); }
1059 template<typename _Up>
1065 construct(pointer __p, const_reference __data)
1066 { ::new((
void *)__p) value_type(__data); }
1069 destroy(pointer __p)
1070 { __p->~value_type(); }
1074 template<
typename _Tp1,
typename _Tp2>
1076 operator==(
const bitmap_allocator<_Tp1>&,
1077 const bitmap_allocator<_Tp2>&) throw()
1080 template<
typename _Tp1,
typename _Tp2>
1082 operator!=(
const bitmap_allocator<_Tp1>&,
1083 const bitmap_allocator<_Tp2>&) throw()
1087 template<
typename _Tp>
1088 typename bitmap_allocator<_Tp>::_BPVector
1089 bitmap_allocator<_Tp>::_S_mem_blocks;
1091 template<
typename _Tp>
1092 size_t bitmap_allocator<_Tp>::_S_block_size =
1093 2 * size_t(__detail::bits_per_block);
1095 template<
typename _Tp>
1096 typename bitmap_allocator<_Tp>::_BPVector::size_type
1097 bitmap_allocator<_Tp>::_S_last_dealloc_index = 0;
1099 template<
typename _Tp>
1100 __detail::_Bitmap_counter
1101 <
typename bitmap_allocator<_Tp>::_Alloc_block*>
1102 bitmap_allocator<_Tp>::_S_last_request(_S_mem_blocks);
1104 #if defined __GTHREADS
1105 template<
typename _Tp>
1106 typename bitmap_allocator<_Tp>::__mutex_type
1107 bitmap_allocator<_Tp>::_S_mut;
1110 _GLIBCXX_END_NAMESPACE_VERSION