29 #ifndef _BITMAP_ALLOCATOR_H
30 #define _BITMAP_ALLOCATOR_H 1
43 #define _BALLOC_ALIGN_BYTES 8
45 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
52 _GLIBCXX_BEGIN_NAMESPACE_VERSION
68 template<
typename _Tp>
75 typedef _Tp value_type;
77 typedef _Tp& reference;
78 typedef const _Tp& const_reference;
79 typedef size_t size_type;
80 typedef ptrdiff_t difference_type;
81 typedef pointer iterator;
86 pointer _M_end_of_storage;
89 _M_space_left()
const throw()
90 {
return _M_end_of_storage - _M_finish; }
93 allocate(size_type __n)
94 {
return static_cast<pointer
>(::operator
new(__n *
sizeof(_Tp))); }
97 deallocate(pointer __p, size_type)
98 { ::operator
delete(__p); }
106 : _M_start(0), _M_finish(0), _M_end_of_storage(0) { }
110 {
return _M_finish - _M_start; }
113 begin()
const throw()
114 {
return this->_M_start; }
118 {
return this->_M_finish; }
122 {
return *(this->end() - 1); }
125 operator[](
const size_type __pos)
const throw()
126 {
return this->_M_start[__pos]; }
129 insert(iterator __pos, const_reference __x);
132 push_back(const_reference __x)
134 if (this->_M_space_left())
140 this->insert(this->end(), __x);
145 { --this->_M_finish; }
148 erase(iterator __pos)
throw();
152 { this->_M_finish = this->_M_start; }
156 template<
typename _Tp>
160 if (this->_M_space_left())
162 size_type __to_move = this->_M_finish - __pos;
170 --__dest; --__src; --__to_move;
176 size_type __new_size = this->size() ? this->size() * 2 : 1;
177 iterator __new_start = this->allocate(__new_size);
178 iterator __first = this->
begin();
179 iterator __start = __new_start;
180 while (__first != __pos)
183 ++__start; ++__first;
187 while (__first != this->
end())
190 ++__start; ++__first;
193 this->deallocate(this->_M_start, this->size());
195 this->_M_start = __new_start;
196 this->_M_finish = __start;
197 this->_M_end_of_storage = this->_M_start + __new_size;
201 template<
typename _Tp>
202 void __mini_vector<_Tp>::
203 erase(iterator __pos)
throw()
205 while (__pos + 1 != this->
end())
214 template<
typename _Tp>
215 struct __mv_iter_traits
217 typedef typename _Tp::value_type value_type;
218 typedef typename _Tp::difference_type difference_type;
221 template<
typename _Tp>
222 struct __mv_iter_traits<_Tp*>
224 typedef _Tp value_type;
225 typedef ptrdiff_t difference_type;
231 bits_per_block =
sizeof(size_t) *
size_t(bits_per_byte)
234 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
236 __lower_bound(_ForwardIterator __first, _ForwardIterator __last,
237 const _Tp& __val, _Compare __comp)
239 typedef typename __mv_iter_traits<_ForwardIterator>::difference_type
242 _DistanceType __len = __last - __first;
243 _DistanceType __half;
244 _ForwardIterator __middle;
251 if (__comp(*__middle, __val))
255 __len = __len - __half - 1;
266 template<
typename _AddrPair>
269 {
return (__ap.second - __ap.first) + 1; }
274 template<
typename _AddrPair>
280 template<
typename _Tp>
281 class _Inclusive_between
285 pointer _M_ptr_value;
289 _Inclusive_between(pointer __ptr) : _M_ptr_value(__ptr)
293 operator()(_Block_pair __bp)
const throw()
304 template<
typename _Functor>
307 typename _Functor::result_type>
312 typedef typename _Functor::argument_type argument_type;
313 typedef typename _Functor::result_type result_type;
315 _Functor_Ref(_Functor& __fref) : _M_fref(__fref)
319 operator()(argument_type __arg)
320 {
return _M_fref(__arg); }
330 template<
typename _Tp>
336 typedef typename _BPVector::difference_type _Counter_type;
339 _Counter_type _M_data_offset;
360 if (*(reinterpret_cast<size_t*>
364 size_t* __rover =
reinterpret_cast<size_t*
>(__bp.
first) - 1;
366 for (_Counter_type __i = 0; __i < __diff; ++__i)
368 _M_data_offset = __i;
371 _M_pbitmap = __rover;
380 _M_get()
const throw()
381 {
return _M_pbitmap; }
384 _M_offset()
const throw()
385 {
return _M_data_offset * size_t(bits_per_block); }
395 template<
typename _Tp>
400 typedef typename _BPVector::size_type _Index_type;
404 size_t* _M_curr_bmap;
405 size_t* _M_last_bmap_in_block;
406 _Index_type _M_curr_index;
413 { this->_M_reset(__index); }
416 _M_reset(
long __index = -1)
throw()
421 _M_curr_index =
static_cast<_Index_type
>(-1);
425 _M_curr_index = __index;
426 _M_curr_bmap =
reinterpret_cast<size_t*
>
427 (_M_vbp[_M_curr_index].first) - 1;
429 _GLIBCXX_DEBUG_ASSERT(__index <= (
long)_M_vbp.size() - 1);
431 _M_last_bmap_in_block = _M_curr_bmap
432 - ((_M_vbp[_M_curr_index].second
433 - _M_vbp[_M_curr_index].first + 1)
434 /
size_t(bits_per_block) - 1);
441 _M_set_internal_bitmap(
size_t* __new_internal_marker)
throw()
442 { _M_curr_bmap = __new_internal_marker; }
445 _M_finished()
const throw()
446 {
return(_M_curr_bmap == 0); }
451 if (_M_curr_bmap == _M_last_bmap_in_block)
453 if (++_M_curr_index == _M_vbp.size())
456 this->_M_reset(_M_curr_index);
464 _M_get()
const throw()
465 {
return _M_curr_bmap; }
468 _M_base()
const throw()
469 {
return _M_vbp[_M_curr_index].first; }
472 _M_offset()
const throw()
474 return size_t(bits_per_block)
475 * ((
reinterpret_cast<size_t*
>(this->_M_base())
476 - _M_curr_bmap) - 1);
480 _M_where()
const throw()
481 {
return _M_curr_index; }
490 size_t __mask = 1 << __pos;
501 size_t __mask = 1 << __pos;
505 _GLIBCXX_END_NAMESPACE_VERSION
508 _GLIBCXX_BEGIN_NAMESPACE_VERSION
514 {
return static_cast<size_t>(__builtin_ctzl(__num)); }
524 typedef size_t* value_type;
526 typedef vector_type::iterator iterator;
527 typedef __mutex __mutex_type;
530 struct _LT_pointer_compare
533 operator()(
const size_t* __pui,
534 const size_t __cui)
const throw()
535 {
return *__pui < __cui; }
538 #if defined __GTHREADS
542 static __mutex_type _S_mutex;
565 _M_validate(
size_t* __addr)
throw()
568 const vector_type::size_type __max_size = 64;
569 if (__free_list.size() >= __max_size)
573 if (*__addr >= *__free_list.back())
578 ::operator
delete(
static_cast<void*
>(__addr));
585 ::operator
delete(
static_cast<void*
>(__free_list.back()));
586 __free_list.pop_back();
591 iterator __temp = __detail::__lower_bound
592 (__free_list.begin(), __free_list.end(),
593 *__addr, _LT_pointer_compare());
596 __free_list.insert(__temp, __addr);
611 _M_should_i_give(
size_t __block_size,
612 size_t __required_size)
throw()
614 const size_t __max_wastage_percentage = 36;
615 if (__block_size >= __required_size &&
616 (((__block_size - __required_size) * 100 / __block_size)
617 < __max_wastage_percentage))
633 #if defined __GTHREADS
638 this->_M_validate(reinterpret_cast<size_t*>(__addr) - 1);
662 template<
typename _Tp>
670 typedef void* pointer;
671 typedef const void* const_pointer;
674 typedef void value_type;
675 template<
typename _Tp1>
686 template<
typename _Tp>
687 class bitmap_allocator :
private free_list
690 typedef size_t size_type;
691 typedef ptrdiff_t difference_type;
692 typedef _Tp* pointer;
693 typedef const _Tp* const_pointer;
694 typedef _Tp& reference;
695 typedef const _Tp& const_reference;
696 typedef _Tp value_type;
697 typedef free_list::__mutex_type __mutex_type;
699 template<
typename _Tp1>
702 typedef bitmap_allocator<_Tp1> other;
705 #if __cplusplus >= 201103L
712 template<
size_t _BSize,
size_t _AlignSize>
717 modulus = _BSize % _AlignSize,
718 value = _BSize + (modulus ? _AlignSize - (modulus) : 0)
724 char __M_unused[aligned_size<
sizeof(value_type),
731 typedef typename __detail::__mini_vector<_Block_pair> _BPVector;
732 typedef typename _BPVector::iterator _BPiter;
734 template<
typename _Predicate>
736 _S_find(_Predicate __p)
738 _BPiter __first = _S_mem_blocks.begin();
739 while (__first != _S_mem_blocks.end() && !__p(*__first))
744 #if defined _GLIBCXX_DEBUG
748 _S_check_for_free_blocks() throw()
750 typedef typename __detail::_Ffit_finder<_Alloc_block*> _FFF;
751 _BPiter __bpi = _S_find(_FFF());
753 _GLIBCXX_DEBUG_ASSERT(__bpi == _S_mem_blocks.end());
769 _S_refill_pool() _GLIBCXX_THROW(std::bad_alloc)
771 #if defined _GLIBCXX_DEBUG
772 _S_check_for_free_blocks();
776 / size_t(__detail::bits_per_block));
777 const size_t __size_to_allocate =
sizeof(size_t)
778 + _S_block_size *
sizeof(_Alloc_block)
779 + __num_bitmaps *
sizeof(size_t);
782 reinterpret_cast<size_t*
>(this->
_M_get(__size_to_allocate));
789 (__temp + __num_bitmaps),
790 reinterpret_cast<_Alloc_block*>
791 (__temp + __num_bitmaps)
792 + _S_block_size - 1);
795 _S_mem_blocks.push_back(__bp);
798 __temp[__i] = ~static_cast<size_t>(0);
803 static _BPVector _S_mem_blocks;
804 static size_t _S_block_size;
805 static __detail::_Bitmap_counter<_Alloc_block*> _S_last_request;
806 static typename _BPVector::size_type _S_last_dealloc_index;
807 #if defined __GTHREADS
808 static __mutex_type _S_mut;
829 #if defined __GTHREADS
846 while (_S_last_request._M_finished() ==
false
847 && (*(_S_last_request._M_get()) == 0))
848 _S_last_request.operator++();
850 if (__builtin_expect(_S_last_request._M_finished() ==
true,
false))
855 _BPiter __bpi = _S_find(__detail::_Functor_Ref<_FFF>(__fff));
857 if (__bpi != _S_mem_blocks.end())
865 _S_last_request._M_reset(__bpi - _S_mem_blocks.begin());
868 pointer __ret =
reinterpret_cast<pointer
>
869 (__bpi->first + __fff._M_offset() + __nz_bit);
870 size_t* __puse_count =
871 reinterpret_cast<size_t*
>
885 _S_last_request._M_reset(_S_mem_blocks.size() - 1);
896 pointer __ret =
reinterpret_cast<pointer
>
897 (_S_last_request._M_base() + _S_last_request._M_offset() + __nz_bit);
899 size_t* __puse_count =
reinterpret_cast<size_t*
>
900 (_S_mem_blocks[_S_last_request._M_where()].first)
902 __num_bitmaps(_S_mem_blocks[_S_last_request._M_where()]) + 1);
919 #if defined __GTHREADS
922 _Alloc_block* __real_p =
reinterpret_cast<_Alloc_block*
>(__p);
924 typedef typename _BPVector::iterator _Iterator;
925 typedef typename _BPVector::difference_type _Difference_type;
927 _Difference_type __diff;
930 _GLIBCXX_DEBUG_ASSERT(_S_last_dealloc_index >= 0);
932 __detail::_Inclusive_between<_Alloc_block*> __ibt(__real_p);
933 if (__ibt(_S_mem_blocks[_S_last_dealloc_index]))
935 _GLIBCXX_DEBUG_ASSERT(_S_last_dealloc_index
936 <= _S_mem_blocks.size() - 1);
939 __diff = _S_last_dealloc_index;
940 __displacement = __real_p - _S_mem_blocks[__diff].first;
944 _Iterator _iter = _S_find(__ibt);
946 _GLIBCXX_DEBUG_ASSERT(_iter != _S_mem_blocks.end());
948 __diff = _iter - _S_mem_blocks.begin();
949 __displacement = __real_p - _S_mem_blocks[__diff].first;
950 _S_last_dealloc_index = __diff;
954 const size_t __rotate = (__displacement
955 % size_t(__detail::bits_per_block));
957 reinterpret_cast<size_t*
>
958 (_S_mem_blocks[__diff].first) - 1;
959 __bitmapC -= (__displacement / size_t(__detail::bits_per_block));
962 size_t* __puse_count =
reinterpret_cast<size_t*
>
963 (_S_mem_blocks[__diff].first)
966 _GLIBCXX_DEBUG_ASSERT(*__puse_count != 0);
970 if (__builtin_expect(*__puse_count == 0,
false))
977 _S_mem_blocks.erase(_S_mem_blocks.begin() + __diff);
985 if ((_Difference_type)_S_last_request._M_where() >= __diff--)
986 _S_last_request._M_reset(__diff);
993 if (_S_last_dealloc_index >= _S_mem_blocks.size())
995 _S_last_dealloc_index =(__diff != -1 ? __diff : 0);
996 _GLIBCXX_DEBUG_ASSERT(_S_last_dealloc_index >= 0);
1005 bitmap_allocator(
const bitmap_allocator&) _GLIBCXX_USE_NOEXCEPT
1008 template<
typename _Tp1>
1009 bitmap_allocator(
const bitmap_allocator<_Tp1>&) _GLIBCXX_USE_NOEXCEPT
1012 ~bitmap_allocator() _GLIBCXX_USE_NOEXCEPT
1016 allocate(size_type __n)
1018 if (__n > this->max_size())
1019 std::__throw_bad_alloc();
1021 #if __cpp_aligned_new
1022 if (
alignof(value_type) > __STDCPP_DEFAULT_NEW_ALIGNMENT__)
1024 const size_type __b = __n *
sizeof(value_type);
1025 std::align_val_t __al = std::align_val_t(
alignof(value_type));
1026 return static_cast<pointer
>(::operator
new(__b, __al));
1030 if (__builtin_expect(__n == 1,
true))
1034 const size_type __b = __n *
sizeof(value_type);
1035 return reinterpret_cast<pointer
>(::operator
new(__b));
1040 allocate(size_type __n,
typename bitmap_allocator<void>::const_pointer)
1041 {
return allocate(__n); }
1044 deallocate(pointer __p, size_type __n)
throw()
1046 if (__builtin_expect(__p != 0,
true))
1048 #if __cpp_aligned_new
1050 if (
alignof(value_type) > __STDCPP_DEFAULT_NEW_ALIGNMENT__)
1052 ::operator
delete(__p, std::align_val_t(
alignof(value_type)));
1057 if (__builtin_expect(__n == 1,
true))
1060 ::operator
delete(__p);
1065 address(reference __r)
const _GLIBCXX_NOEXCEPT
1069 address(const_reference __r)
const _GLIBCXX_NOEXCEPT
1073 max_size() const _GLIBCXX_USE_NOEXCEPT
1074 {
return size_type(-1) /
sizeof(value_type); }
1076 #if __cplusplus >= 201103L
1077 template<
typename _Up,
typename... _Args>
1079 construct(_Up* __p, _Args&&... __args)
1080 { ::new((
void *)__p) _Up(std::
forward<_Args>(__args)...); }
1082 template<typename _Up>
1088 construct(pointer __p, const_reference __data)
1089 { ::new((
void *)__p) value_type(__data); }
1092 destroy(pointer __p)
1093 { __p->~value_type(); }
1097 template<
typename _Tp1,
typename _Tp2>
1099 operator==(
const bitmap_allocator<_Tp1>&,
1100 const bitmap_allocator<_Tp2>&) throw()
1103 template<
typename _Tp1,
typename _Tp2>
1105 operator!=(
const bitmap_allocator<_Tp1>&,
1106 const bitmap_allocator<_Tp2>&) throw()
1110 template<
typename _Tp>
1111 typename bitmap_allocator<_Tp>::_BPVector
1112 bitmap_allocator<_Tp>::_S_mem_blocks;
1114 template<
typename _Tp>
1115 size_t bitmap_allocator<_Tp>::_S_block_size =
1116 2 * size_t(__detail::bits_per_block);
1118 template<
typename _Tp>
1119 typename bitmap_allocator<_Tp>::_BPVector::size_type
1120 bitmap_allocator<_Tp>::_S_last_dealloc_index = 0;
1122 template<
typename _Tp>
1123 __detail::_Bitmap_counter
1124 <
typename bitmap_allocator<_Tp>::_Alloc_block*>
1125 bitmap_allocator<_Tp>::_S_last_request(_S_mem_blocks);
1127 #if defined __GTHREADS
1128 template<
typename _Tp>
1129 typename bitmap_allocator<_Tp>::__mutex_type
1130 bitmap_allocator<_Tp>::_S_mut;
1133 _GLIBCXX_END_NAMESPACE_VERSION
size_t * _M_get(size_t __sz)
This function gets a block of memory of the specified size from the free list.
The bitmap counter which acts as the bitmap manipulator, and manages the bit-manipulation functions a...
size_t __num_bitmaps(_AddrPair __ap)
The number of Bit-maps pointed to by the address pair passed to the function.
constexpr const _Tp * end(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to one past the last element of the initializer_list. ...
void _M_deallocate_single_object(pointer __p)
Deallocates memory that belongs to a single object of size sizeof(_Tp).
constexpr _Tp && forward(typename std::remove_reference< _Tp >::type &__t) noexcept
Forward an lvalue.
constexpr pair< typename __decay_and_strip< _T1 >::__type, typename __decay_and_strip< _T2 >::__type > make_pair(_T1 &&__x, _T2 &&__y)
A convenience wrapper for creating a pair from two objects.
void __bit_free(size_t *__pbmap, size_t __pos)
Mark a memory address as free by setting the corresponding bit in the bit-map.
void __bit_allocate(size_t *__pbmap, size_t __pos)
Mark a memory address as allocated by re-setting the corresponding bit in the bit-map.
#define _BALLOC_ALIGN_BYTES
The constant in the expression below is the alignment required in bytes.
pointer _M_allocate_single_object()
Allocates memory for a single object of size sizeof(_Tp).
constexpr const _Tp * begin(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to the first element of the initializer_list.
__mini_vector<> is a stripped down version of the full-fledged std::vector<>.
void _M_clear()
This function just clears the internal Free List, and gives back all the memory to the OS...
Exception possibly thrown by new.bad_alloc (or classes derived from it) is used to report allocation ...
One of the comparison functors.
The free list class for managing chunks of memory to be given to and returned by the bitmap_allocator...
Bitmap Allocator, primary template.
The class which acts as a predicate for applying the first-fit memory allocation policy for the bitma...
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
size_t _Bit_scan_forward(size_t __num)
Generic Version of the bsf instruction.
void _M_insert(size_t *__addr)
This function returns the block of memory to the internal free list.
Struct holding two objects of arbitrary type.
size_t __num_blocks(_AddrPair __ap)
The number of Blocks pointed to by the address pair passed to the function.
One of the comparison functors.
_T1 first
second_type is the second bound type