commit 4db4982f72c14be120b941b3ee8822e1044ab3e5
Author: Jonathan Wakely <jwakely@redhat.com>
Date: Tue Oct 4 15:28:21 2016 +0100
Do not allocate memory for empty deques
@@ -133,6 +133,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
deque<_Tp, _Alloc>::
emplace_front(_Args&&... __args)
{
+ if (!_M_valid_map())
+ _M_reallocate_map(_Base::_S_initial_map_size, true);
if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first)
{
_Alloc_traits::construct(this->_M_impl,
@@ -150,6 +152,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
deque<_Tp, _Alloc>::
emplace_back(_Args&&... __args)
{
+ if (!_M_valid_map())
+ _M_reallocate_map(_Base::_S_initial_map_size, false);
if (this->_M_impl._M_finish._M_cur
!= this->_M_impl._M_finish._M_last - 1)
{
@@ -903,8 +907,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
deque<_Tp, _Alloc>::
_M_reallocate_map(size_type __nodes_to_add, bool __add_at_front)
{
- const size_type __old_num_nodes
- = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1;
+ const size_type __old_num_nodes = _M_valid_map()
+ ? this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1
+ : 0;
const size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
_Map_pointer __new_nstart;
@@ -931,17 +936,38 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
_Map_pointer __new_map = this->_M_allocate_map(__new_map_size);
__new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
+ (__add_at_front ? __nodes_to_add : 0);
- std::copy(this->_M_impl._M_start._M_node,
- this->_M_impl._M_finish._M_node + 1,
- __new_nstart);
- _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
+ if (_M_valid_map())
+ {
+ std::copy(this->_M_impl._M_start._M_node,
+ this->_M_impl._M_finish._M_node + 1,
+ __new_nstart);
+ _M_deallocate_map(this->_M_impl._M_map,
+ this->_M_impl._M_map_size);
+ }
+ else
+ __try
+ {
+ *__new_nstart = this->_M_really_allocate_node();
+ }
+ __catch(...)
+ {
+ _M_deallocate_map(__new_map, __new_map_size);
+ __throw_exception_again;
+ }
this->_M_impl._M_map = __new_map;
this->_M_impl._M_map_size = __new_map_size;
}
this->_M_impl._M_start._M_set_node(__new_nstart);
- this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
+ if (__old_num_nodes)
+ this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
+ else
+ {
+ this->_M_impl._M_finish._M_set_node(__new_nstart);
+ this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first;
+ this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first;
+ }
}
// Overload for deque::iterators, exploiting the "segmented-iterator
@@ -154,7 +154,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
iterator
_M_const_cast() const _GLIBCXX_NOEXCEPT
- { return iterator(_M_cur, _M_node); }
+ { return _M_cur ? iterator(_M_cur, _M_node) : iterator(); }
reference
operator*() const _GLIBCXX_NOEXCEPT
@@ -351,6 +351,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
operator-(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) _GLIBCXX_NOEXCEPT
{
+ if (!__x._M_node && !__y._M_node)
+ return 0;
return typename _Deque_iterator<_Tp, _Ref, _Ptr>::difference_type
(_Deque_iterator<_Tp, _Ref, _Ptr>::_S_buffer_size())
* (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first)
@@ -363,6 +365,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
operator-(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) _GLIBCXX_NOEXCEPT
{
+ if (!__x._M_node && !__y._M_node)
+ return 0;
return typename _Deque_iterator<_Tp, _RefL, _PtrL>::difference_type
(_Deque_iterator<_Tp, _RefL, _PtrL>::_S_buffer_size())
* (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first)
@@ -473,6 +477,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
#endif
static const bool _S_recycle_nodes = bool(_GLIBCXX_INLINE_VERSION);
+ static const bool _S_allow_null_map = bool(_GLIBCXX_INLINE_VERSION);
typedef typename _Alloc_traits::template rebind<_Ptr>::other
_Map_alloc_type;
@@ -518,7 +523,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
this->_M_impl._M_swap_data(__x._M_impl);
}
- _Deque_base(_Deque_base&& __x)
+ _Deque_base(_Deque_base&& __x) noexcept(_S_allow_null_map)
: _Deque_base(std::move(__x), typename _Alloc_traits::is_always_equal{})
{ }
@@ -684,6 +689,20 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
if (!_M_impl._M_map)
return std::move(_M_impl);
+ if (_S_allow_null_map)
+ {
+ _Deque_impl __ret{std::move(_M_get_Tp_allocator())};
+ _M_impl._M_swap_data(__ret);
+ return __ret;
+ }
+
+ // This path is complicated because the standard allows a moved-from
+ // allocator to compare unequal to its previous value. To be exception
+ // safe we need to create an empty map using a moved-from allocator
+ // before making any changes to this->_M_impl. This relies on the
+ // assumption that the two moved-from allocators compare equal, but
+ // there doesn't seem to be any way to avoid that.
+
// Create a copy of the current allocator.
_Tp_alloc_type __alloc{_M_get_Tp_allocator()};
// Put that copy in a moved-from state.
@@ -725,6 +744,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
_Deque_base<_Tp, _Alloc>::
_M_initialize_map(size_t __num_elements)
{
+ if (_S_allow_null_map && __num_elements == 0)
+ return;
+
const size_t __num_nodes = (__num_elements/ __deque_buf_size(sizeof(_Tp))
+ 1);
@@ -927,7 +949,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
/**
* @brief Creates a %deque with no elements.
*/
- deque() : _Base() { }
+ deque() _GLIBCXX_NOEXCEPT_IF(_Base::_S_allow_null_map)
+ : _Base() { }
/**
* @brief Creates a %deque with no elements.
@@ -1001,11 +1024,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
* The newly-created %deque contains the exact contents of @a __x.
* The contents of @a __x are a valid, but unspecified %deque.
*/
- deque(deque&& __x)
+ deque(deque&& __x) noexcept(_Base::_S_allow_null_map)
: _Base(std::move(__x)) { }
/// Copy constructor with alternative allocator
deque(const deque& __x, const allocator_type& __a)
+ noexcept(_Base::_S_allow_null_map
+ && _Alloc_traits::is_always_equal::value)
: _Base(__a, __x.size())
{ std::__uninitialized_copy_a(__x.begin(), __x.end(),
this->_M_impl._M_start,
@@ -1546,6 +1571,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
void
push_front(const value_type& __x)
{
+ if (!_M_valid_map())
+ _M_reallocate_map(_Base::_S_initial_map_size, true);
if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first)
{
_Alloc_traits::construct(this->_M_impl,
@@ -1567,6 +1594,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
emplace_front(_Args&&... __args);
#endif
+ bool
+ _M_valid_map() const _GLIBCXX_NOEXCEPT
+ { return !_Base::_S_allow_null_map || this->_M_impl._M_map; }
+
/**
* @brief Add data to the end of the %deque.
* @param __x Data to be added.
@@ -1579,6 +1610,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
void
push_back(const value_type& __x)
{
+ if (!_M_valid_map())
+ _M_reallocate_map(_Base::_S_initial_map_size, false);
if (this->_M_impl._M_finish._M_cur
!= this->_M_impl._M_finish._M_last - 1)
{
@@ -2156,10 +2189,15 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
iterator
_M_reserve_elements_at_back(size_type __n)
{
- const size_type __vacancies = (this->_M_impl._M_finish._M_last
- - this->_M_impl._M_finish._M_cur) - 1;
- if (__n > __vacancies)
- _M_new_elements_at_back(__n - __vacancies);
+ if (!_M_valid_map())
+ _M_new_elements_at_back(__n);
+ else
+ {
+ const size_type __vacancies = (this->_M_impl._M_finish._M_last
+ - this->_M_impl._M_finish._M_cur) - 1;
+ if (__n > __vacancies)
+ _M_new_elements_at_back(__n - __vacancies);
+ }
return this->_M_impl._M_finish + difference_type(__n);
}
@@ -2229,12 +2267,16 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
{
// Create new data first, so if allocation fails there are no effects.
deque __newobj(std::forward<_Args>(__args)...);
- // Free existing storage using existing allocator.
- clear();
- _M_deallocate_node(*begin()._M_node); // one node left after clear()
- _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
- this->_M_impl._M_map = nullptr;
- this->_M_impl._M_map_size = 0;
+ if (this->_M_impl._M_map)
+ {
+ // Free existing storage using existing allocator.
+ clear();
+ // Free the single node left after clear(), then free the map.
+ _M_deallocate_node(*this->_M_impl._M_start._M_node);
+ _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
+ this->_M_impl._M_map = nullptr;
+ this->_M_impl._M_map_size = 0;
+ }
// Take ownership of replacement memory.
this->_M_impl._M_swap_data(__newobj._M_impl);
}
commit 2c816add85ea0a8c720d5e790b162b9fe2732c19
Author: Jonathan Wakely <jwakely@redhat.com>
Date: Mon Oct 3 16:59:43 2016 +0100
Recycle deque nodes
@@ -532,7 +532,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
void deque<_Tp, _Alloc>::
_M_pop_back_aux()
{
- _M_deallocate_node(this->_M_impl._M_finish._M_first);
+ this->_M_dispose_node(this->_M_impl._M_finish._M_first);
this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1);
this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1;
_Alloc_traits::destroy(_M_get_Tp_allocator(),
@@ -550,7 +550,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
{
_Alloc_traits::destroy(_M_get_Tp_allocator(),
this->_M_impl._M_start._M_cur);
- _M_deallocate_node(this->_M_impl._M_start._M_first);
+ this->_M_dispose_node(this->_M_impl._M_start._M_first);
this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node + 1);
this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first;
}
@@ -472,6 +472,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
typedef typename _Alloc_traits::const_pointer _Ptr_const;
#endif
+ static const bool _S_recycle_nodes = bool(_GLIBCXX_INLINE_VERSION);
+
typedef typename _Alloc_traits::template rebind<_Ptr>::other
_Map_alloc_type;
typedef __gnu_cxx::__alloc_traits<_Map_alloc_type> _Map_alloc_traits;
@@ -596,7 +598,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
{ return _Map_alloc_type(_M_get_Tp_allocator()); }
_Ptr
- _M_allocate_node()
+ _M_really_allocate_node()
{
typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Traits;
return _Traits::allocate(_M_impl, __deque_buf_size(sizeof(_Tp)));
@@ -609,20 +611,62 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
_Traits::deallocate(_M_impl, __p, __deque_buf_size(sizeof(_Tp)));
}
+ _Ptr
+ _M_allocate_node()
+ {
+ if (_S_recycle_nodes)
+ if (_Ptr& __cached = _M_cached_node())
+ {
+ _Ptr __ret = __cached;
+ __cached = _Ptr();
+ return __ret;
+ }
+ return _M_really_allocate_node();
+ }
+
+ void
+ _M_dispose_node(_Ptr __p) _GLIBCXX_NOEXCEPT
+ {
+ if (_S_recycle_nodes)
+ {
+ _Ptr& __cached = _M_cached_node();
+ if (!__cached)
+ {
+ __cached = __p;
+ return;
+ }
+ }
+ _M_deallocate_node(__p);
+ }
+
_Map_pointer
_M_allocate_map(size_t __n)
{
+ __n += size_t(_S_recycle_nodes);
_Map_alloc_type __map_alloc = _M_get_map_allocator();
- return _Map_alloc_traits::allocate(__map_alloc, __n);
+ _Map_pointer __p = _Map_alloc_traits::allocate(__map_alloc, __n);
+ if (_S_recycle_nodes)
+ *__p++ = _Ptr();
+ return __p;
}
void
_M_deallocate_map(_Map_pointer __p, size_t __n) _GLIBCXX_NOEXCEPT
{
+ if (_S_recycle_nodes)
+ {
+ ++__n;
+ if (*--__p)
+ _M_deallocate_node(*__p);
+ }
_Map_alloc_type __map_alloc = _M_get_map_allocator();
_Map_alloc_traits::deallocate(__map_alloc, __p, __n);
}
+ _Ptr&
+ _M_cached_node() _GLIBCXX_NOEXCEPT
+ { return *(_M_impl._M_map - 1); }
+
protected:
void _M_initialize_map(size_t);
void _M_create_nodes(_Map_pointer __nstart, _Map_pointer __nfinish);
@@ -724,7 +768,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
__try
{
for (__cur = __nstart; __cur < __nfinish; ++__cur)
- *__cur = this->_M_allocate_node();
+ *__cur = this->_M_really_allocate_node();
}
__catch(...)
{