// Bitmap Allocator. -*- C++ -*-
-// Copyright (C) 2004-2014 Free Software Foundation, Inc.
+// Copyright (C) 2004-2024 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the
#ifndef _BITMAP_ALLOCATOR_H
#define _BITMAP_ALLOCATOR_H 1
+#include <bits/requires_hosted.h> // GNU extensions are currently omitted
+
#include <utility> // For std::pair.
#include <bits/functexcept.h> // For __throw_bad_alloc().
-#include <functional> // For greater_equal, and less_equal.
+#include <bits/stl_function.h> // For greater_equal, and less_equal.
#include <new> // For operator new.
#include <debug/debug.h> // _GLIBCXX_DEBUG_ASSERT
#include <ext/concurrence.h>
namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
{
- using std::size_t;
- using std::ptrdiff_t;
+_GLIBCXX_BEGIN_NAMESPACE_VERSION
namespace __detail
{
- _GLIBCXX_BEGIN_NAMESPACE_VERSION
/** @class __mini_vector bitmap_allocator.h bitmap_allocator.h
*
* @brief __mini_vector<> is a stripped down version of the
typedef _Tp* pointer;
typedef _Tp& reference;
typedef const _Tp& const_reference;
- typedef size_t size_type;
- typedef ptrdiff_t difference_type;
+ typedef std::size_t size_type;
+ typedef std::ptrdiff_t difference_type;
typedef pointer iterator;
private:
_M_space_left() const throw()
{ return _M_end_of_storage - _M_finish; }
- pointer
+ _GLIBCXX_NODISCARD pointer
allocate(size_type __n)
{ return static_cast<pointer>(::operator new(__n * sizeof(_Tp))); }
struct __mv_iter_traits<_Tp*>
{
typedef _Tp value_type;
- typedef ptrdiff_t difference_type;
+ typedef std::ptrdiff_t difference_type;
};
enum
{
bits_per_byte = 8,
- bits_per_block = sizeof(size_t) * size_t(bits_per_byte)
+ bits_per_block = sizeof(std::size_t) * std::size_t(bits_per_byte)
};
template<typename _ForwardIterator, typename _Tp, typename _Compare>
* passed to the function.
*/
template<typename _AddrPair>
- inline size_t
+ inline std::size_t
__num_blocks(_AddrPair __ap)
{ return (__ap.second - __ap.first) + 1; }
* passed to the function.
*/
template<typename _AddrPair>
- inline size_t
+ inline std::size_t
__num_bitmaps(_AddrPair __ap)
- { return __num_blocks(__ap) / size_t(bits_per_block); }
+ { return __num_blocks(__ap) / std::size_t(bits_per_block); }
// _Tp should be a pointer type.
template<typename _Tp>
class _Inclusive_between
- : public std::unary_function<typename std::pair<_Tp, _Tp>, bool>
{
typedef _Tp pointer;
pointer _M_ptr_value;
// Used to pass a Functor to functions by reference.
template<typename _Functor>
class _Functor_Ref
- : public std::unary_function<typename _Functor::argument_type,
- typename _Functor::result_type>
{
_Functor& _M_fref;
// the vector.
template<typename _Tp>
class _Ffit_finder
- : public std::unary_function<typename std::pair<_Tp, _Tp>, bool>
{
- typedef typename std::pair<_Tp, _Tp> _Block_pair;
- typedef typename __detail::__mini_vector<_Block_pair> _BPVector;
+ typedef std::pair<_Tp, _Tp> _Block_pair;
+ typedef __detail::__mini_vector<_Block_pair> _BPVector;
typedef typename _BPVector::difference_type _Counter_type;
- size_t* _M_pbitmap;
+ std::size_t* _M_pbitmap;
_Counter_type _M_data_offset;
public:
+ typedef bool result_type;
+ typedef _Block_pair argument_type;
+
_Ffit_finder() : _M_pbitmap(0), _M_data_offset(0)
{ }
bool
operator()(_Block_pair __bp) throw()
{
+ using std::size_t;
// Set the _rover to the last physical location bitmap,
// which is the bitmap which belongs to the first free
// block. Thus, the bitmaps are in exact reverse order of
return false;
}
- size_t*
+ std::size_t*
_M_get() const throw()
{ return _M_pbitmap; }
_Counter_type
_M_offset() const throw()
- { return _M_data_offset * size_t(bits_per_block); }
+ { return _M_data_offset * std::size_t(bits_per_block); }
};
/** @class _Bitmap_counter bitmap_allocator.h bitmap_allocator.h
typedef _Tp pointer;
_BPVector& _M_vbp;
- size_t* _M_curr_bmap;
- size_t* _M_last_bmap_in_block;
+ std::size_t* _M_curr_bmap;
+ std::size_t* _M_last_bmap_in_block;
_Index_type _M_curr_index;
public:
}
_M_curr_index = __index;
- _M_curr_bmap = reinterpret_cast<size_t*>
+ _M_curr_bmap = reinterpret_cast<std::size_t*>
(_M_vbp[_M_curr_index].first) - 1;
_GLIBCXX_DEBUG_ASSERT(__index <= (long)_M_vbp.size() - 1);
_M_last_bmap_in_block = _M_curr_bmap
- ((_M_vbp[_M_curr_index].second
- _M_vbp[_M_curr_index].first + 1)
- / size_t(bits_per_block) - 1);
+ / std::size_t(bits_per_block) - 1);
}
// Dangerous Function! Use with extreme care. Pass to this
// function ONLY those values that are known to be correct,
// otherwise this will mess up big time.
void
- _M_set_internal_bitmap(size_t* __new_internal_marker) throw()
+ _M_set_internal_bitmap(std::size_t* __new_internal_marker) throw()
{ _M_curr_bmap = __new_internal_marker; }
bool
return *this;
}
- size_t*
+ std::size_t*
_M_get() const throw()
{ return _M_curr_bmap; }
_Index_type
_M_offset() const throw()
{
- return size_t(bits_per_block)
- * ((reinterpret_cast<size_t*>(this->_M_base())
+ return std::size_t(bits_per_block)
+ * ((reinterpret_cast<std::size_t*>(this->_M_base())
- _M_curr_bmap) - 1);
}
* corresponding bit in the bit-map.
*/
inline void
- __bit_allocate(size_t* __pbmap, size_t __pos) throw()
+ __bit_allocate(std::size_t* __pbmap, std::size_t __pos) throw()
{
- size_t __mask = 1 << __pos;
+ std::size_t __mask = 1 << __pos;
__mask = ~__mask;
*__pbmap &= __mask;
}
* corresponding bit in the bit-map.
*/
inline void
- __bit_free(size_t* __pbmap, size_t __pos) throw()
+ __bit_free(std::size_t* __pbmap, std::size_t __pos) throw()
{
- size_t __mask = 1 << __pos;
+ std::size_t __mask = 1 << __pos;
*__pbmap |= __mask;
}
-
- _GLIBCXX_END_NAMESPACE_VERSION
} // namespace __detail
-_GLIBCXX_BEGIN_NAMESPACE_VERSION
-
/** @brief Generic Version of the bsf instruction.
*/
- inline size_t
- _Bit_scan_forward(size_t __num)
- { return static_cast<size_t>(__builtin_ctzl(__num)); }
+ inline std::size_t
+ _Bit_scan_forward(std::size_t __num)
+ { return static_cast<std::size_t>(__builtin_ctzl(__num)); }
/** @class free_list bitmap_allocator.h bitmap_allocator.h
*
class free_list
{
public:
- typedef size_t* value_type;
+ typedef std::size_t* value_type;
typedef __detail::__mini_vector<value_type> vector_type;
typedef vector_type::iterator iterator;
typedef __mutex __mutex_type;
struct _LT_pointer_compare
{
bool
- operator()(const size_t* __pui,
- const size_t __cui) const throw()
+ operator()(const std::size_t* __pui,
+ const std::size_t __cui) const throw()
{ return *__pui < __cui; }
};
* or larger blocks from the free list.
*/
void
- _M_validate(size_t* __addr) throw()
+ _M_validate(std::size_t* __addr) throw()
{
vector_type& __free_list = _M_get_free_list();
const vector_type::size_type __max_size = 64;
* false.
*/
bool
- _M_should_i_give(size_t __block_size,
- size_t __required_size) throw()
+ _M_should_i_give(std::size_t __block_size,
+ std::size_t __required_size) throw()
{
- const size_t __max_wastage_percentage = 36;
+ const std::size_t __max_wastage_percentage = 36;
if (__block_size >= __required_size &&
(((__block_size - __required_size) * 100 / __block_size)
< __max_wastage_percentage))
* by a call to the _M_get function.
*/
inline void
- _M_insert(size_t* __addr) throw()
+ _M_insert(std::size_t* __addr) throw()
{
#if defined __GTHREADS
__scoped_lock __bfl_lock(_M_get_mutex());
#endif
// Call _M_validate to decide what should be done with
// this particular free list.
- this->_M_validate(reinterpret_cast<size_t*>(__addr) - 1);
+ this->_M_validate(reinterpret_cast<std::size_t*>(__addr) - 1);
// See discussion as to why this is 1!
}
* @return A pointer to the new memory block of size at least
* equal to that requested.
*/
- size_t*
- _M_get(size_t __sz) throw(std::bad_alloc);
+ std::size_t*
+ _M_get(std::size_t __sz) _GLIBCXX_THROW(std::bad_alloc);
/** @brief This function just clears the internal Free List, and
* gives back all the memory to the OS.
class bitmap_allocator : private free_list
{
public:
- typedef size_t size_type;
- typedef ptrdiff_t difference_type;
+ typedef std::size_t size_type;
+ typedef std::ptrdiff_t difference_type;
typedef _Tp* pointer;
typedef const _Tp* const_pointer;
typedef _Tp& reference;
#endif
private:
- template<size_t _BSize, size_t _AlignSize>
+ template<std::size_t _BSize, std::size_t _AlignSize>
struct aligned_size
{
enum
/** @brief Responsible for exponentially growing the internal
* memory pool.
*
- * @throw std::bad_alloc. If memory can not be allocated.
+ * @throw std::bad_alloc. If memory cannot be allocated.
*
* Complexity: O(1), but internally depends upon the
* complexity of the function free_list::_M_get. The part where
* the newly acquired block. Having a tight bound.
*/
void
- _S_refill_pool() throw(std::bad_alloc)
+ _S_refill_pool() _GLIBCXX_THROW(std::bad_alloc)
{
+ using std::size_t;
#if defined _GLIBCXX_DEBUG
_S_check_for_free_blocks();
#endif
}
static _BPVector _S_mem_blocks;
- static size_t _S_block_size;
+ static std::size_t _S_block_size;
static __detail::_Bitmap_counter<_Alloc_block*> _S_last_request;
static typename _BPVector::size_type _S_last_dealloc_index;
#if defined __GTHREADS
/** @brief Allocates memory for a single object of size
* sizeof(_Tp).
*
- * @throw std::bad_alloc. If memory can not be allocated.
+ * @throw std::bad_alloc. If memory cannot be allocated.
*
* Complexity: Worst case complexity is O(N), but that
* is hardly ever hit. If and when this particular case is
* Amortized Constant time.
*/
pointer
- _M_allocate_single_object() throw(std::bad_alloc)
+ _M_allocate_single_object() _GLIBCXX_THROW(std::bad_alloc)
{
+ using std::size_t;
#if defined __GTHREADS
__scoped_lock __bit_lock(_S_mut);
#endif
void
_M_deallocate_single_object(pointer __p) throw()
{
+ using std::size_t;
#if defined __GTHREADS
__scoped_lock __bit_lock(_S_mut);
#endif
~bitmap_allocator() _GLIBCXX_USE_NOEXCEPT
{ }
- pointer
+ _GLIBCXX_NODISCARD pointer
allocate(size_type __n)
{
if (__n > this->max_size())
std::__throw_bad_alloc();
+#if __cpp_aligned_new
+ if (alignof(value_type) > __STDCPP_DEFAULT_NEW_ALIGNMENT__)
+ {
+ const size_type __b = __n * sizeof(value_type);
+ std::align_val_t __al = std::align_val_t(alignof(value_type));
+ return static_cast<pointer>(::operator new(__b, __al));
+ }
+#endif
+
if (__builtin_expect(__n == 1, true))
return this->_M_allocate_single_object();
else
}
}
- pointer
+ _GLIBCXX_NODISCARD pointer
allocate(size_type __n, typename bitmap_allocator<void>::const_pointer)
{ return allocate(__n); }
{
if (__builtin_expect(__p != 0, true))
{
+#if __cpp_aligned_new
+ // Types with extended alignment are handled by operator delete.
+ if (alignof(value_type) > __STDCPP_DEFAULT_NEW_ALIGNMENT__)
+ {
+ ::operator delete(__p, std::align_val_t(alignof(value_type)));
+ return;
+ }
+#endif
+
if (__builtin_expect(__n == 1, true))
this->_M_deallocate_single_object(__p);
else
const bitmap_allocator<_Tp2>&) throw()
{ return true; }
+#if __cpp_impl_three_way_comparison < 201907L
template<typename _Tp1, typename _Tp2>
bool
operator!=(const bitmap_allocator<_Tp1>&,
const bitmap_allocator<_Tp2>&) throw()
- { return false; }
+ { return false; }
+#endif
// Static member definitions.
template<typename _Tp>
bitmap_allocator<_Tp>::_S_mem_blocks;
template<typename _Tp>
- size_t bitmap_allocator<_Tp>::_S_block_size =
- 2 * size_t(__detail::bits_per_block);
+ std::size_t bitmap_allocator<_Tp>::_S_block_size
+ = 2 * std::size_t(__detail::bits_per_block);
template<typename _Tp>
typename bitmap_allocator<_Tp>::_BPVector::size_type
} // namespace __gnu_cxx
#endif
-