29#ifndef _BITMAP_ALLOCATOR_H
30#define _BITMAP_ALLOCATOR_H 1
43#define _BALLOC_ALIGN_BYTES 8
45namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
47_GLIBCXX_BEGIN_NAMESPACE_VERSION
66 template<
typename _Tp>
73 typedef _Tp value_type;
75 typedef _Tp& reference;
76 typedef const _Tp& const_reference;
77 typedef std::size_t size_type;
78 typedef std::ptrdiff_t difference_type;
79 typedef pointer iterator;
84 pointer _M_end_of_storage;
87 _M_space_left()
const throw()
88 {
return _M_end_of_storage - _M_finish; }
90 _GLIBCXX_NODISCARD pointer
91 allocate(size_type __n)
92 {
return static_cast<pointer
>(::operator
new(__n *
sizeof(_Tp))); }
95 deallocate(pointer __p, size_type)
96 { ::operator
delete(__p); }
104 : _M_start(0), _M_finish(0), _M_end_of_storage(0) { }
108 {
return _M_finish - _M_start; }
111 begin()
const throw()
112 {
return this->_M_start; }
116 {
return this->_M_finish; }
120 {
return *(this->end() - 1); }
123 operator[](
const size_type __pos)
const throw()
124 {
return this->_M_start[__pos]; }
127 insert(iterator __pos, const_reference __x);
130 push_back(const_reference __x)
132 if (this->_M_space_left())
138 this->insert(this->end(), __x);
143 { --this->_M_finish; }
146 erase(iterator __pos)
throw();
150 { this->_M_finish = this->_M_start; }
154 template<
typename _Tp>
156 insert(iterator __pos, const_reference __x)
158 if (this->_M_space_left())
160 size_type __to_move = this->_M_finish - __pos;
161 iterator __dest = this->end();
162 iterator __src = this->end() - 1;
168 --__dest; --__src; --__to_move;
174 size_type __new_size = this->size() ? this->size() * 2 : 1;
175 iterator __new_start = this->allocate(__new_size);
176 iterator __first = this->begin();
177 iterator __start = __new_start;
178 while (__first != __pos)
181 ++__start; ++__first;
185 while (__first != this->end())
188 ++__start; ++__first;
191 this->deallocate(this->_M_start, this->size());
193 this->_M_start = __new_start;
194 this->_M_finish = __start;
195 this->_M_end_of_storage = this->_M_start + __new_size;
199 template<
typename _Tp>
200 void __mini_vector<_Tp>::
201 erase(iterator __pos)
throw()
203 while (__pos + 1 != this->end())
212 template<
typename _Tp>
213 struct __mv_iter_traits
215 typedef typename _Tp::value_type value_type;
216 typedef typename _Tp::difference_type difference_type;
219 template<
typename _Tp>
220 struct __mv_iter_traits<_Tp*>
222 typedef _Tp value_type;
223 typedef std::ptrdiff_t difference_type;
229 bits_per_block =
sizeof(std::size_t) * std::size_t(bits_per_byte)
232 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
234 __lower_bound(_ForwardIterator __first, _ForwardIterator __last,
235 const _Tp& __val, _Compare __comp)
237 typedef typename __mv_iter_traits<_ForwardIterator>::difference_type
240 _DistanceType __len = __last - __first;
241 _DistanceType __half;
242 _ForwardIterator __middle;
249 if (__comp(*__middle, __val))
253 __len = __len - __half - 1;
264 template<
typename _AddrPair>
267 {
return (__ap.second - __ap.first) + 1; }
272 template<
typename _AddrPair>
275 {
return __num_blocks(__ap) / std::size_t(bits_per_block); }
278 template<
typename _Tp>
279 class _Inclusive_between
282 pointer _M_ptr_value;
286 _Inclusive_between(pointer __ptr) : _M_ptr_value(__ptr)
290 operator()(_Block_pair __bp)
const throw()
301 template<
typename _Functor>
307 typedef typename _Functor::argument_type argument_type;
308 typedef typename _Functor::result_type result_type;
310 _Functor_Ref(_Functor& __fref) : _M_fref(__fref)
314 operator()(argument_type __arg)
315 {
return _M_fref(__arg); }
325 template<
typename _Tp>
330 typedef typename _BPVector::difference_type _Counter_type;
332 std::size_t* _M_pbitmap;
333 _Counter_type _M_data_offset;
336 typedef bool result_type;
358 if (*(
reinterpret_cast<size_t*
>
362 size_t* __rover =
reinterpret_cast<size_t*
>(__bp.first) - 1;
364 for (_Counter_type __i = 0; __i < __diff; ++__i)
366 _M_data_offset = __i;
369 _M_pbitmap = __rover;
378 _M_get()
const throw()
379 {
return _M_pbitmap; }
382 _M_offset()
const throw()
383 {
return _M_data_offset * std::size_t(bits_per_block); }
393 template<
typename _Tp>
398 typedef typename _BPVector::size_type _Index_type;
402 std::size_t* _M_curr_bmap;
403 std::size_t* _M_last_bmap_in_block;
404 _Index_type _M_curr_index;
411 { this->_M_reset(__index); }
414 _M_reset(
long __index = -1)
throw()
419 _M_curr_index =
static_cast<_Index_type
>(-1);
423 _M_curr_index = __index;
424 _M_curr_bmap =
reinterpret_cast<std::size_t*
>
425 (_M_vbp[_M_curr_index].first) - 1;
427 _GLIBCXX_DEBUG_ASSERT(__index <= (
long)_M_vbp.size() - 1);
429 _M_last_bmap_in_block = _M_curr_bmap
430 - ((_M_vbp[_M_curr_index].second
431 - _M_vbp[_M_curr_index].first + 1)
432 / std::size_t(bits_per_block) - 1);
439 _M_set_internal_bitmap(std::size_t* __new_internal_marker)
throw()
440 { _M_curr_bmap = __new_internal_marker; }
443 _M_finished()
const throw()
444 {
return(_M_curr_bmap == 0); }
449 if (_M_curr_bmap == _M_last_bmap_in_block)
451 if (++_M_curr_index == _M_vbp.size())
454 this->_M_reset(_M_curr_index);
462 _M_get()
const throw()
463 {
return _M_curr_bmap; }
466 _M_base()
const throw()
467 {
return _M_vbp[_M_curr_index].first; }
470 _M_offset()
const throw()
472 return std::size_t(bits_per_block)
473 * ((
reinterpret_cast<std::size_t*
>(this->_M_base())
474 - _M_curr_bmap) - 1);
478 _M_where()
const throw()
479 {
return _M_curr_index; }
488 std::size_t __mask = 1 << __pos;
499 std::size_t __mask = 1 << __pos;
508 {
return static_cast<std::size_t
>(__builtin_ctzl(__num)); }
518 typedef std::size_t* value_type;
520 typedef vector_type::iterator iterator;
521 typedef __mutex __mutex_type;
524 struct _LT_pointer_compare
527 operator()(
const std::size_t* __pui,
528 const std::size_t __cui)
const throw()
529 {
return *__pui < __cui; }
532#if defined __GTHREADS
536 static __mutex_type _S_mutex;
559 _M_validate(std::size_t* __addr)
throw()
562 const vector_type::size_type __max_size = 64;
563 if (__free_list.size() >= __max_size)
567 if (*__addr >= *__free_list.back())
572 ::operator
delete(
static_cast<void*
>(__addr));
579 ::operator
delete(
static_cast<void*
>(__free_list.back()));
580 __free_list.pop_back();
585 iterator __temp = __detail::__lower_bound
586 (__free_list.begin(), __free_list.end(),
587 *__addr, _LT_pointer_compare());
590 __free_list.insert(__temp, __addr);
605 _M_should_i_give(std::size_t __block_size,
606 std::size_t __required_size)
throw()
608 const std::size_t __max_wastage_percentage = 36;
609 if (__block_size >= __required_size &&
610 (((__block_size - __required_size) * 100 / __block_size)
611 < __max_wastage_percentage))
627#if defined __GTHREADS
632 this->_M_validate(
reinterpret_cast<std::size_t*
>(__addr) - 1);
656 template<
typename _Tp>
664 typedef void* pointer;
665 typedef const void* const_pointer;
668 typedef void value_type;
669 template<
typename _Tp1>
680 template<
typename _Tp>
684 typedef std::size_t size_type;
685 typedef std::ptrdiff_t difference_type;
686 typedef _Tp* pointer;
687 typedef const _Tp* const_pointer;
688 typedef _Tp& reference;
689 typedef const _Tp& const_reference;
690 typedef _Tp value_type;
691 typedef free_list::__mutex_type __mutex_type;
693 template<
typename _Tp1>
699#if __cplusplus >= 201103L
706 template<std::
size_t _BSize, std::
size_t _AlignSize>
711 modulus = _BSize % _AlignSize,
712 value = _BSize + (modulus ? _AlignSize - (modulus) : 0)
718 char __M_unused[aligned_size<
sizeof(value_type),
726 typedef typename _BPVector::iterator _BPiter;
728 template<
typename _Predicate>
730 _S_find(_Predicate __p)
732 _BPiter __first = _S_mem_blocks.begin();
733 while (__first != _S_mem_blocks.end() && !__p(*__first))
738#if defined _GLIBCXX_DEBUG
742 _S_check_for_free_blocks()
throw()
745 _BPiter __bpi = _S_find(_FFF());
747 _GLIBCXX_DEBUG_ASSERT(__bpi == _S_mem_blocks.end());
766#if defined _GLIBCXX_DEBUG
767 _S_check_for_free_blocks();
770 const size_t __num_bitmaps = (_S_block_size
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));
783 std::make_pair(
reinterpret_cast<_Alloc_block*
>
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);
792 for (
size_t __i = 0; __i < __num_bitmaps; ++__i)
793 __temp[__i] = ~
static_cast<size_t>(0);
799 static std::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;
825#if defined __GTHREADS
842 while (_S_last_request._M_finished() ==
false
843 && (*(_S_last_request._M_get()) == 0))
844 _S_last_request.operator++();
846 if (__builtin_expect(_S_last_request._M_finished() ==
true,
false))
851 _BPiter __bpi = _S_find(__detail::_Functor_Ref<_FFF>(__fff));
853 if (__bpi != _S_mem_blocks.end())
861 _S_last_request._M_reset(__bpi - _S_mem_blocks.begin());
864 pointer __ret =
reinterpret_cast<pointer
>
865 (__bpi->first + __fff._M_offset() + __nz_bit);
866 size_t* __puse_count =
867 reinterpret_cast<size_t*
>
881 _S_last_request._M_reset(_S_mem_blocks.size() - 1);
892 pointer __ret =
reinterpret_cast<pointer
>
893 (_S_last_request._M_base() + _S_last_request._M_offset() + __nz_bit);
895 size_t* __puse_count =
reinterpret_cast<size_t*
>
896 (_S_mem_blocks[_S_last_request._M_where()].first)
898 __num_bitmaps(_S_mem_blocks[_S_last_request._M_where()]) + 1);
916#if defined __GTHREADS
919 _Alloc_block* __real_p =
reinterpret_cast<_Alloc_block*
>(__p);
921 typedef typename _BPVector::iterator _Iterator;
922 typedef typename _BPVector::difference_type _Difference_type;
924 _Difference_type __diff;
927 _GLIBCXX_DEBUG_ASSERT(_S_last_dealloc_index >= 0);
929 __detail::_Inclusive_between<_Alloc_block*> __ibt(__real_p);
930 if (__ibt(_S_mem_blocks[_S_last_dealloc_index]))
932 _GLIBCXX_DEBUG_ASSERT(_S_last_dealloc_index
933 <= _S_mem_blocks.size() - 1);
936 __diff = _S_last_dealloc_index;
937 __displacement = __real_p - _S_mem_blocks[__diff].first;
941 _Iterator _iter = _S_find(__ibt);
943 _GLIBCXX_DEBUG_ASSERT(_iter != _S_mem_blocks.end());
945 __diff = _iter - _S_mem_blocks.begin();
946 __displacement = __real_p - _S_mem_blocks[__diff].first;
947 _S_last_dealloc_index = __diff;
951 const size_t __rotate = (__displacement
952 % size_t(__detail::bits_per_block));
954 reinterpret_cast<size_t*
>
955 (_S_mem_blocks[__diff].first) - 1;
956 __bitmapC -= (__displacement / size_t(__detail::bits_per_block));
959 size_t* __puse_count =
reinterpret_cast<size_t*
>
960 (_S_mem_blocks[__diff].first)
963 _GLIBCXX_DEBUG_ASSERT(*__puse_count != 0);
967 if (__builtin_expect(*__puse_count == 0,
false))
974 _S_mem_blocks.erase(_S_mem_blocks.begin() + __diff);
982 if ((_Difference_type)_S_last_request._M_where() >= __diff--)
983 _S_last_request._M_reset(__diff);
990 if (_S_last_dealloc_index >= _S_mem_blocks.size())
992 _S_last_dealloc_index =(__diff != -1 ? __diff : 0);
993 _GLIBCXX_DEBUG_ASSERT(_S_last_dealloc_index >= 0);
1002 bitmap_allocator(
const bitmap_allocator&) _GLIBCXX_USE_NOEXCEPT
1005 template<
typename _Tp1>
1006 bitmap_allocator(
const bitmap_allocator<_Tp1>&) _GLIBCXX_USE_NOEXCEPT
1009 ~bitmap_allocator() _GLIBCXX_USE_NOEXCEPT
1012 _GLIBCXX_NODISCARD pointer
1013 allocate(size_type __n)
1015 if (__n > this->max_size())
1016 std::__throw_bad_alloc();
1018#if __cpp_aligned_new
1019 if (
alignof(value_type) > __STDCPP_DEFAULT_NEW_ALIGNMENT__)
1021 const size_type __b = __n *
sizeof(value_type);
1022 std::align_val_t __al = std::align_val_t(
alignof(value_type));
1023 return static_cast<pointer
>(::operator
new(__b, __al));
1027 if (__builtin_expect(__n == 1,
true))
1031 const size_type __b = __n *
sizeof(value_type);
1032 return reinterpret_cast<pointer
>(::operator
new(__b));
1036 _GLIBCXX_NODISCARD pointer
1037 allocate(size_type __n,
typename bitmap_allocator<void>::const_pointer)
1038 {
return allocate(__n); }
1041 deallocate(pointer __p, size_type __n)
throw()
1043 if (__builtin_expect(__p != 0,
true))
1045#if __cpp_aligned_new
1047 if (
alignof(value_type) > __STDCPP_DEFAULT_NEW_ALIGNMENT__)
1049 ::operator
delete(__p, std::align_val_t(
alignof(value_type)));
1054 if (__builtin_expect(__n == 1,
true))
1057 ::operator
delete(__p);
1062 address(reference __r)
const _GLIBCXX_NOEXCEPT
1066 address(const_reference __r)
const _GLIBCXX_NOEXCEPT
1070 max_size() const _GLIBCXX_USE_NOEXCEPT
1071 {
return size_type(-1) /
sizeof(value_type); }
1073#if __cplusplus >= 201103L
1074 template<
typename _Up,
typename... _Args>
1076 construct(_Up* __p, _Args&&... __args)
1079 template<
typename _Up>
1085 construct(pointer __p, const_reference __data)
1086 { ::new((
void *)__p) value_type(__data); }
1089 destroy(pointer __p)
1090 { __p->~value_type(); }
1094 template<
typename _Tp1,
typename _Tp2>
1096 operator==(
const bitmap_allocator<_Tp1>&,
1097 const bitmap_allocator<_Tp2>&)
throw()
1100#if __cpp_impl_three_way_comparison < 201907L
1101 template<
typename _Tp1,
typename _Tp2>
1103 operator!=(
const bitmap_allocator<_Tp1>&,
1104 const bitmap_allocator<_Tp2>&)
throw()
1109 template<
typename _Tp>
1110 typename bitmap_allocator<_Tp>::_BPVector
1111 bitmap_allocator<_Tp>::_S_mem_blocks;
1113 template<
typename _Tp>
1114 std::size_t bitmap_allocator<_Tp>::_S_block_size
1115 = 2 * std::size_t(__detail::bits_per_block);
1117 template<
typename _Tp>
1118 typename bitmap_allocator<_Tp>::_BPVector::size_type
1119 bitmap_allocator<_Tp>::_S_last_dealloc_index = 0;
1121 template<
typename _Tp>
1122 __detail::_Bitmap_counter
1123 <
typename bitmap_allocator<_Tp>::_Alloc_block*>
1124 bitmap_allocator<_Tp>::_S_last_request(_S_mem_blocks);
1126#if defined __GTHREADS
1127 template<
typename _Tp>
1128 typename bitmap_allocator<_Tp>::__mutex_type
1129 bitmap_allocator<_Tp>::_S_mut;
1132_GLIBCXX_END_NAMESPACE_VERSION
#define _BALLOC_ALIGN_BYTES
The constant in the expression below is the alignment required in bytes.
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
ISO C++ entities toplevel namespace is std.
GNU extensions for public use.
std::size_t _Bit_scan_forward(std::size_t __num)
Generic Version of the bsf instruction.
void __bit_free(std::size_t *__pbmap, std::size_t __pos)
Mark a memory address as free by setting the corresponding bit in the bit-map.
std::size_t __num_bitmaps(_AddrPair __ap)
The number of Bit-maps pointed to by the address pair passed to the function.
void __bit_allocate(std::size_t *__pbmap, std::size_t __pos)
Mark a memory address as allocated by re-setting the corresponding bit in the bit-map.
std::size_t __num_blocks(_AddrPair __ap)
The number of Blocks pointed to by the address pair passed to the function.
Exception possibly thrown by new.
__mini_vector<> is a stripped down version of the full-fledged std::vector<>.
The class which acts as a predicate for applying the first-fit memory allocation policy for the bitma...
The bitmap counter which acts as the bitmap manipulator, and manages the bit-manipulation functions a...
The free list class for managing chunks of memory to be given to and returned by the bitmap_allocator...
std::size_t * _M_get(std::size_t __sz)
This function gets a block of memory of the specified size from the free list.
void _M_insert(std::size_t *__addr)
This function returns the block of memory to the internal free list.
void _M_clear()
This function just clears the internal Free List, and gives back all the memory to the OS.
Bitmap Allocator, primary template.
pointer _M_allocate_single_object()
Allocates memory for a single object of size sizeof(_Tp).
void _M_deallocate_single_object(pointer __p)
Deallocates memory that belongs to a single object of size sizeof(_Tp).