29#ifndef _BITMAP_ALLOCATOR_H
30#define _BITMAP_ALLOCATOR_H 1
45#define _BALLOC_ALIGN_BYTES 8
47namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
49_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 std::size_t size_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; }
92 _GLIBCXX_NODISCARD pointer
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>
158 insert(iterator __pos, const_reference __x)
160 if (this->_M_space_left())
162 size_type __to_move = this->_M_finish - __pos;
163 iterator __dest = this->end();
164 iterator __src = this->end() - 1;
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;
231 bits_per_block =
sizeof(std::size_t) * std::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>
277 {
return __num_blocks(__ap) / std::size_t(bits_per_block); }
280 template<
typename _Tp>
281 class _Inclusive_between
284 pointer _M_ptr_value;
288 _Inclusive_between(pointer __ptr) : _M_ptr_value(__ptr)
292 operator()(_Block_pair __bp)
const throw()
303 template<
typename _Functor>
309 typedef typename _Functor::argument_type argument_type;
310 typedef typename _Functor::result_type result_type;
312 _Functor_Ref(_Functor& __fref) : _M_fref(__fref)
316 operator()(argument_type __arg)
317 {
return _M_fref(__arg); }
327 template<
typename _Tp>
334 std::size_t* _M_pbitmap;
338 typedef bool result_type;
360 if (*(
reinterpret_cast<size_t*
>
364 size_t* __rover =
reinterpret_cast<size_t*
>(__bp.first) - 1;
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 * std::size_t(bits_per_block); }
395 template<
typename _Tp>
400 typedef typename _BPVector::size_type _Index_type;
404 std::size_t* _M_curr_bmap;
405 std::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<std::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 / std::size_t(bits_per_block) - 1);
441 _M_set_internal_bitmap(std::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 std::size_t(bits_per_block)
475 * ((
reinterpret_cast<std::size_t*
>(this->_M_base())
476 - _M_curr_bmap) - 1);
480 _M_where()
const throw()
481 {
return _M_curr_index; }
490 std::size_t __mask = 1 << __pos;
501 std::size_t __mask = 1 << __pos;
510 {
return static_cast<std::size_t
>(__builtin_ctzl(__num)); }
520 typedef std::size_t* value_type;
522 typedef vector_type::iterator iterator;
523 typedef __mutex __mutex_type;
526 struct _LT_pointer_compare
529 operator()(
const std::size_t* __pui,
530 const std::size_t __cui)
const throw()
531 {
return *__pui < __cui; }
534#if defined __GTHREADS
538 static __mutex_type _S_mutex;
561 _M_validate(std::size_t* __addr)
throw()
564 const vector_type::size_type __max_size = 64;
565 if (__free_list.size() >= __max_size)
569 if (*__addr >= *__free_list.back())
574 ::operator
delete(
static_cast<void*
>(__addr));
581 ::operator
delete(
static_cast<void*
>(__free_list.back()));
582 __free_list.pop_back();
587 iterator __temp = __detail::__lower_bound
588 (__free_list.begin(), __free_list.end(),
589 *__addr, _LT_pointer_compare());
592 __free_list.insert(__temp, __addr);
607 _M_should_i_give(std::size_t __block_size,
608 std::size_t __required_size)
throw()
610 const std::size_t __max_wastage_percentage = 36;
611 if (__block_size >= __required_size &&
612 (((__block_size - __required_size) * 100 / __block_size)
613 < __max_wastage_percentage))
629#if defined __GTHREADS
634 this->_M_validate(
reinterpret_cast<std::size_t*
>(__addr) - 1);
658 template<
typename _Tp>
666 typedef void* pointer;
667 typedef const void* const_pointer;
670 typedef void value_type;
671 template<
typename _Tp1>
682 template<
typename _Tp>
686 typedef std::size_t size_type;
688 typedef _Tp* pointer;
689 typedef const _Tp* const_pointer;
690 typedef _Tp& reference;
691 typedef const _Tp& const_reference;
692 typedef _Tp value_type;
693 typedef free_list::__mutex_type __mutex_type;
695 template<
typename _Tp1>
701#if __cplusplus >= 201103L
708 template<std::
size_t _BSize, std::
size_t _AlignSize>
713 modulus = _BSize % _AlignSize,
714 value = _BSize + (modulus ? _AlignSize - (modulus) : 0)
720 char __M_unused[aligned_size<
sizeof(value_type),
728 typedef typename _BPVector::iterator _BPiter;
730 template<
typename _Predicate>
732 _S_find(_Predicate __p)
734 _BPiter __first = _S_mem_blocks.begin();
735 while (__first != _S_mem_blocks.end() && !__p(*__first))
740#if defined _GLIBCXX_DEBUG
744 _S_check_for_free_blocks()
throw()
747 _BPiter __bpi = _S_find(_FFF());
749 _GLIBCXX_DEBUG_ASSERT(__bpi == _S_mem_blocks.end());
768#if defined _GLIBCXX_DEBUG
769 _S_check_for_free_blocks();
772 const size_t __num_bitmaps = (_S_block_size
773 / size_t(__detail::bits_per_block));
774 const size_t __size_to_allocate =
sizeof(size_t)
775 + _S_block_size *
sizeof(_Alloc_block)
776 + __num_bitmaps *
sizeof(size_t);
779 reinterpret_cast<size_t*
>(this->
_M_get(__size_to_allocate));
785 std::make_pair(
reinterpret_cast<_Alloc_block*
>
786 (__temp + __num_bitmaps),
787 reinterpret_cast<_Alloc_block*
>
788 (__temp + __num_bitmaps)
789 + _S_block_size - 1);
792 _S_mem_blocks.push_back(__bp);
794 for (
size_t __i = 0; __i < __num_bitmaps; ++__i)
795 __temp[__i] = ~
static_cast<size_t>(0);
801 static std::size_t _S_block_size;
803 static typename _BPVector::size_type _S_last_dealloc_index;
804#if defined __GTHREADS
805 static __mutex_type _S_mut;
827#if defined __GTHREADS
844 while (_S_last_request._M_finished() ==
false
845 && (*(_S_last_request._M_get()) == 0))
846 _S_last_request.operator++();
848 if (__builtin_expect(_S_last_request._M_finished() ==
true,
false))
853 _BPiter __bpi = _S_find(__detail::_Functor_Ref<_FFF>(__fff));
855 if (__bpi != _S_mem_blocks.end())
863 _S_last_request._M_reset(__bpi - _S_mem_blocks.begin());
866 pointer __ret =
reinterpret_cast<pointer
>
867 (__bpi->first + __fff._M_offset() + __nz_bit);
868 size_t* __puse_count =
869 reinterpret_cast<size_t*
>
883 _S_last_request._M_reset(_S_mem_blocks.size() - 1);
894 pointer __ret =
reinterpret_cast<pointer
>
895 (_S_last_request._M_base() + _S_last_request._M_offset() + __nz_bit);
897 size_t* __puse_count =
reinterpret_cast<size_t*
>
898 (_S_mem_blocks[_S_last_request._M_where()].first)
900 __num_bitmaps(_S_mem_blocks[_S_last_request._M_where()]) + 1);
918#if defined __GTHREADS
921 _Alloc_block* __real_p =
reinterpret_cast<_Alloc_block*
>(__p);
923 typedef typename _BPVector::iterator _Iterator;
926 _Difference_type __diff;
929 _GLIBCXX_DEBUG_ASSERT(_S_last_dealloc_index >= 0);
931 __detail::_Inclusive_between<_Alloc_block*> __ibt(__real_p);
932 if (__ibt(_S_mem_blocks[_S_last_dealloc_index]))
934 _GLIBCXX_DEBUG_ASSERT(_S_last_dealloc_index
935 <= _S_mem_blocks.size() - 1);
938 __diff = _S_last_dealloc_index;
939 __displacement = __real_p - _S_mem_blocks[__diff].first;
943 _Iterator _iter = _S_find(__ibt);
945 _GLIBCXX_DEBUG_ASSERT(_iter != _S_mem_blocks.end());
947 __diff = _iter - _S_mem_blocks.begin();
948 __displacement = __real_p - _S_mem_blocks[__diff].first;
949 _S_last_dealloc_index = __diff;
953 const size_t __rotate = (__displacement
954 % size_t(__detail::bits_per_block));
956 reinterpret_cast<size_t*
>
957 (_S_mem_blocks[__diff].first) - 1;
958 __bitmapC -= (__displacement / size_t(__detail::bits_per_block));
961 size_t* __puse_count =
reinterpret_cast<size_t*
>
962 (_S_mem_blocks[__diff].first)
965 _GLIBCXX_DEBUG_ASSERT(*__puse_count != 0);
969 if (__builtin_expect(*__puse_count == 0,
false))
976 _S_mem_blocks.erase(_S_mem_blocks.begin() + __diff);
984 if ((_Difference_type)_S_last_request._M_where() >= __diff--)
985 _S_last_request._M_reset(__diff);
992 if (_S_last_dealloc_index >= _S_mem_blocks.size())
994 _S_last_dealloc_index =(__diff != -1 ? __diff : 0);
995 _GLIBCXX_DEBUG_ASSERT(_S_last_dealloc_index >= 0);
1004 bitmap_allocator(
const bitmap_allocator&) _GLIBCXX_USE_NOEXCEPT
1007 template<
typename _Tp1>
1008 bitmap_allocator(
const bitmap_allocator<_Tp1>&) _GLIBCXX_USE_NOEXCEPT
1011 ~bitmap_allocator() _GLIBCXX_USE_NOEXCEPT
1014 _GLIBCXX_NODISCARD pointer
1015 allocate(size_type __n)
1017 if (__n > this->max_size())
1018 std::__throw_bad_alloc();
1020#if __cpp_aligned_new && __cplusplus >= 201103L
1021 if (
alignof(value_type) > __STDCPP_DEFAULT_NEW_ALIGNMENT__)
1023 const size_type __b = __n *
sizeof(value_type);
1024 std::align_val_t __al = std::align_val_t(
alignof(value_type));
1025 return static_cast<pointer
>(::operator
new(__b, __al));
1029 if (__builtin_expect(__n == 1,
true))
1033 const size_type __b = __n *
sizeof(value_type);
1034 return reinterpret_cast<pointer
>(::operator
new(__b));
1038 _GLIBCXX_NODISCARD pointer
1039 allocate(size_type __n,
typename bitmap_allocator<void>::const_pointer)
1040 {
return allocate(__n); }
1043 deallocate(pointer __p, size_type __n)
throw()
1045 if (__builtin_expect(__p != 0,
true))
1047#if __cpp_aligned_new && __cplusplus >= 201103L
1049 if (
alignof(value_type) > __STDCPP_DEFAULT_NEW_ALIGNMENT__)
1051 ::operator
delete(__p, std::align_val_t(
alignof(value_type)));
1056 if (__builtin_expect(__n == 1,
true))
1059 ::operator
delete(__p);
1064 address(reference __r)
const _GLIBCXX_NOEXCEPT
1068 address(const_reference __r)
const _GLIBCXX_NOEXCEPT
1072 max_size() const _GLIBCXX_USE_NOEXCEPT
1073 {
return size_type(-1) /
sizeof(value_type); }
1075#if __cplusplus >= 201103L
1076 template<
typename _Up,
typename... _Args>
1078 construct(_Up* __p, _Args&&... __args)
1081 template<
typename _Up>
1087 construct(pointer __p, const_reference __data)
1088 { ::new((
void *)__p) value_type(__data); }
1091 destroy(pointer __p)
1092 { __p->~value_type(); }
1096 template<
typename _Tp1,
typename _Tp2>
1098 operator==(
const bitmap_allocator<_Tp1>&,
1099 const bitmap_allocator<_Tp2>&)
throw()
1102#if __cpp_impl_three_way_comparison < 201907L
1103 template<
typename _Tp1,
typename _Tp2>
1105 operator!=(
const bitmap_allocator<_Tp1>&,
1106 const bitmap_allocator<_Tp2>&)
throw()
1111 template<
typename _Tp>
1112 typename bitmap_allocator<_Tp>::_BPVector
1113 bitmap_allocator<_Tp>::_S_mem_blocks;
1115 template<
typename _Tp>
1116 std::size_t bitmap_allocator<_Tp>::_S_block_size
1117 = 2 * std::size_t(__detail::bits_per_block);
1119 template<
typename _Tp>
1120 typename bitmap_allocator<_Tp>::_BPVector::size_type
1121 bitmap_allocator<_Tp>::_S_last_dealloc_index = 0;
1123 template<
typename _Tp>
1124 __detail::_Bitmap_counter
1125 <
typename bitmap_allocator<_Tp>::_Alloc_block*>
1126 bitmap_allocator<_Tp>::_S_last_request(_S_mem_blocks);
1128#if defined __GTHREADS
1129 template<
typename _Tp>
1130 typename bitmap_allocator<_Tp>::__mutex_type
1131 bitmap_allocator<_Tp>::_S_mut;
1134_GLIBCXX_END_NAMESPACE_VERSION
#define _BALLOC_ALIGN_BYTES
The constant in the expression below is the alignment required in bytes.
__bool_constant< true > true_type
The type used as a compile-time boolean with true value.
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
_Tp * end(valarray< _Tp > &__va) noexcept
Return an iterator pointing to one past the last element of the valarray.
ISO C++ entities toplevel namespace is std.
constexpr auto size(const _Container &__cont) noexcept(noexcept(__cont.size())) -> decltype(__cont.size())
Return the size of a container.
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).