This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[v3] Even more tweaks to forward_list
- From: Paolo Carlini <paolo dot carlini at oracle dot com>
- To: Gcc Patch List <gcc-patches at gcc dot gnu dot org>
- Cc: libstdc++ <libstdc++ at gcc dot gnu dot org>
- Date: Thu, 16 Oct 2008 12:24:03 +0200
- Subject: [v3] Even more tweaks to forward_list
Hi,
tested x86_64-linux, committed to mainline.
Paolo.
/////////////////////
2008-10-16 Paolo Carlini <paolo.carlini@oracle.com>
* include/bits/forward_list.h (_Fwd_list_base<>::_M_insert_after):
Move out of line, tweak to return _Fwd_list_node_base*.
(forward_list<>::insert_after(const_iterator, const _Tp&),
forward_list<>::insert_after(const_iterator, _Tp&&)): Use it.
* include/bits/forward_list.tcc (_Fwd_list_base<>::_M_insert_after):
Define.
* include/bits/forward_list.h (forward_list<>): Consistently qualify
calls of base class functions with this->.
* include/bits/forward_list.tcc (forward_list<>): Likewise.
* include/bits/forward_list.h: Move some functions out of line...
* include/bits/forward_list.tcc: ... here.
* include/bits/forward_list.h (forward_list<>::resize(size_type)): Fix.
Index: include/bits/forward_list.h
===================================================================
*** include/bits/forward_list.h (revision 141165)
--- include/bits/forward_list.h (working copy)
*************** _GLIBCXX_BEGIN_NAMESPACE(std)
*** 88,94 ****
_M_reverse_after()
{
_Fwd_list_node_base* __tail = this->_M_next;
! if (! __tail)
return;
while (_Fwd_list_node_base* __temp = __tail->_M_next)
{
--- 88,94 ----
_M_reverse_after()
{
_Fwd_list_node_base* __tail = this->_M_next;
! if (!__tail)
return;
while (_Fwd_list_node_base* __temp = __tail->_M_next)
{
*************** _GLIBCXX_BEGIN_NAMESPACE(std)
*** 293,299 ****
: _Node_alloc_type(), _M_head()
{ }
- explicit
_Fwd_list_impl(const _Node_alloc_type& __a)
: _Node_alloc_type(__a), _M_head()
{ }
--- 293,298 ----
*************** _GLIBCXX_BEGIN_NAMESPACE(std)
*** 347,378 ****
template<typename... _Args>
_Node*
_M_create_node(_Args&&... __args)
! {
! _Node* __node = this->_M_get_node();
! try
! {
! _M_get_Node_allocator().construct(__node,
! std::forward<_Args>(__args)...);
! __node->_M_next = 0;
! }
! catch(...)
! {
! this->_M_put_node(__node);
! __throw_exception_again;
! }
! return __node;
! }
template<typename... _Args>
! void
! _M_insert_after(const_iterator __pos, _Args&&... __args)
! {
! _Fwd_list_node_base* __to
! = const_cast<_Fwd_list_node_base*>(__pos._M_node);
! _Node* __thing = _M_create_node(std::forward<_Args>(__args)...);
! __thing->_M_next = __to->_M_next;
! __to->_M_next = __thing;
! }
void
_M_put_node(_Node* __p)
--- 346,370 ----
template<typename... _Args>
_Node*
_M_create_node(_Args&&... __args)
! {
! _Node* __node = this->_M_get_node();
! try
! {
! _M_get_Node_allocator().construct(__node,
! std::forward<_Args>(__args)...);
! __node->_M_next = 0;
! }
! catch(...)
! {
! this->_M_put_node(__node);
! __throw_exception_again;
! }
! return __node;
! }
template<typename... _Args>
! _Fwd_list_node_base*
! _M_insert_after(const_iterator __pos, _Args&&... __args);
void
_M_put_node(_Node* __p)
*************** _GLIBCXX_BEGIN_NAMESPACE(std)
*** 583,589 ****
* elements in the initializer_list @a il. This is linear in
* il.size().
*/
! forward_list
operator=(std::initializer_list<_Tp> __il)
{
assign(__il);
--- 575,581 ----
* elements in the initializer_list @a il. This is linear in
* il.size().
*/
! forward_list&
operator=(std::initializer_list<_Tp> __il)
{
assign(__il);
*************** _GLIBCXX_BEGIN_NAMESPACE(std)
*** 783,789 ****
template<typename... _Args>
void
emplace_front(_Args&&... __args)
! { _M_insert_after(cbefore_begin(), std::forward<_Args>(__args)...); }
/**
* @brief Add data to the front of the %forward_list.
--- 775,782 ----
template<typename... _Args>
void
emplace_front(_Args&&... __args)
! { this->_M_insert_after(cbefore_begin(),
! std::forward<_Args>(__args)...); }
/**
* @brief Add data to the front of the %forward_list.
*************** _GLIBCXX_BEGIN_NAMESPACE(std)
*** 797,810 ****
*/
void
push_front(const _Tp& __val)
! { _M_insert_after(cbefore_begin(), __val); }
/**
*
*/
void
push_front(_Tp&& __val)
! { _M_insert_after(cbefore_begin(), std::move(__val)); }
/**
* @brief Removes first element.
--- 790,803 ----
*/
void
push_front(const _Tp& __val)
! { this->_M_insert_after(cbefore_begin(), __val); }
/**
*
*/
void
push_front(_Tp&& __val)
! { this->_M_insert_after(cbefore_begin(), std::move(__val)); }
/**
* @brief Removes first element.
*************** _GLIBCXX_BEGIN_NAMESPACE(std)
*** 820,826 ****
*/
void
pop_front()
! { _M_erase_after(&this->_M_impl._M_head); }
/**
* @brief Constructs object in %forward_list after the specified
--- 813,819 ----
*/
void
pop_front()
! { this->_M_erase_after(&this->_M_impl._M_head); }
/**
* @brief Constructs object in %forward_list after the specified
*************** _GLIBCXX_BEGIN_NAMESPACE(std)
*** 838,844 ****
template<typename... _Args>
iterator
emplace_after(const_iterator __pos, _Args&&... __args)
! { _M_insert_after(__pos, std::forward<_Args>(__args)...); }
/**
* @brief Inserts given value into %forward_list after specified
--- 831,838 ----
template<typename... _Args>
iterator
emplace_after(const_iterator __pos, _Args&&... __args)
! { return iterator(this->_M_insert_after(__pos,
! std::forward<_Args>(__args)...)); }
/**
* @brief Inserts given value into %forward_list after specified
*************** _GLIBCXX_BEGIN_NAMESPACE(std)
*** 854,881 ****
*/
iterator
insert_after(const_iterator __pos, const _Tp& __val)
! {
! _Fwd_list_node_base* __to
! = const_cast<_Fwd_list_node_base*>(__pos._M_node);
! _Node* __thing = _M_create_node(__val);
! __thing->_M_next = __to->_M_next;
! __to->_M_next = __thing;
! return iterator(__to->_M_next);
! }
/**
*
*/
iterator
insert_after(const_iterator __pos, _Tp&& __val)
! {
! _Fwd_list_node_base* __to
! = const_cast<_Fwd_list_node_base*>(__pos._M_node);
! _Node* __thing = _M_create_node(std::move(__val));
! __thing->_M_next = __to->_M_next;
! __to->_M_next = __thing;
! return iterator(__to->_M_next);
! }
/**
* @brief Inserts a number of copies of given data into the
--- 848,861 ----
*/
iterator
insert_after(const_iterator __pos, const _Tp& __val)
! { return iterator(this->_M_insert_after(__pos, __val)); }
/**
*
*/
iterator
insert_after(const_iterator __pos, _Tp&& __val)
! { return iterator(this->_M_insert_after(__pos, std::move(__val))); }
/**
* @brief Inserts a number of copies of given data into the
*************** _GLIBCXX_BEGIN_NAMESPACE(std)
*** 891,898 ****
* does not invalidate iterators and references.
*/
void
! insert_after(const_iterator __pos, size_type __n,
! const _Tp& __val);
/**
* @brief Inserts a range into the %forward_list.
--- 871,877 ----
* does not invalidate iterators and references.
*/
void
! insert_after(const_iterator __pos, size_type __n, const _Tp& __val);
/**
* @brief Inserts a range into the %forward_list.
*************** _GLIBCXX_BEGIN_NAMESPACE(std)
*** 950,956 ****
_Fwd_list_node_base* __tmp
= const_cast<_Fwd_list_node_base*>(__pos._M_node);
if (__tmp)
! return iterator(_Base::_M_erase_after(__tmp));
else
return end();
}
--- 929,935 ----
_Fwd_list_node_base* __tmp
= const_cast<_Fwd_list_node_base*>(__pos._M_node);
if (__tmp)
! return iterator(this->_M_erase_after(__tmp));
else
return end();
}
*************** _GLIBCXX_BEGIN_NAMESPACE(std)
*** 979,985 ****
{
_Fwd_list_node_base* __tmp
= const_cast<_Fwd_list_node_base*>(__pos._M_node);
! return iterator(_M_erase_after(__tmp, __last._M_node));
}
/**
--- 958,964 ----
{
_Fwd_list_node_base* __tmp
= const_cast<_Fwd_list_node_base*>(__pos._M_node);
! return iterator(this->_M_erase_after(__tmp, __last._M_node));
}
/**
*************** _GLIBCXX_BEGIN_NAMESPACE(std)
*** 1010,1016 ****
*/
void
resize(size_type __sz)
! { resize(__sz, _Tp(0)); }
/**
* @brief Resizes the %forward_list to the specified number of
--- 989,995 ----
*/
void
resize(size_type __sz)
! { resize(__sz, _Tp()); }
/**
* @brief Resizes the %forward_list to the specified number of
*************** _GLIBCXX_BEGIN_NAMESPACE(std)
*** 1037,1043 ****
*/
void
clear()
! { _M_erase_after(&this->_M_impl._M_head, 0); }
// 23.2.3.5 forward_list operations:
--- 1016,1022 ----
*/
void
clear()
! { this->_M_erase_after(&this->_M_impl._M_head, 0); }
// 23.2.3.5 forward_list operations:
*************** _GLIBCXX_BEGIN_NAMESPACE(std)
*** 1053,1069 ****
* Requires this != @a x.
*/
void
! splice_after(const_iterator __pos, forward_list&& __list)
! {
! if (!__list.empty() && &__list != this)
! {
! _Fwd_list_node_base* __tmp
! = const_cast<_Fwd_list_node_base*>(__pos._M_node);
! const_iterator __before = __list.cbefore_begin();
! __tmp->_M_transfer_after(const_cast<_Fwd_list_node_base*>
! (__before._M_node));
! }
! }
/**
* @brief Insert element from another %forward_list.
--- 1032,1038 ----
* Requires this != @a x.
*/
void
! splice_after(const_iterator __pos, forward_list&& __list);
/**
* @brief Insert element from another %forward_list.
*************** _GLIBCXX_BEGIN_NAMESPACE(std)
*** 1095,1109 ****
*/
void
splice_after(const_iterator __pos, forward_list&& __list,
! const_iterator __before, const_iterator __last)
! {
! _Fwd_list_node_base* __tmp
! = const_cast<_Fwd_list_node_base*>(__pos._M_node);
! __tmp->_M_transfer_after(const_cast<_Fwd_list_node_base*>
! (__before._M_node),
! const_cast<_Fwd_list_node_base*>
! (__last._M_node));
! }
/**
* @brief Remove all elements equal to value.
--- 1064,1070 ----
*/
void
splice_after(const_iterator __pos, forward_list&& __list,
! const_iterator __before, const_iterator __last);
/**
* @brief Remove all elements equal to value.
*************** _GLIBCXX_BEGIN_NAMESPACE(std)
*** 1224,1231 ****
* Reverse the order of elements in the list in linear time.
*/
void
! reverse()
! { this->_M_impl._M_head._M_reverse_after(); }
};
/**
--- 1185,1191 ----
* Reverse the order of elements in the list in linear time.
*/
void
! reverse();
};
/**
*************** _GLIBCXX_BEGIN_NAMESPACE(std)
*** 1241,1266 ****
template<typename _Tp, typename _Alloc>
bool
operator==(const forward_list<_Tp, _Alloc>& __lx,
! const forward_list<_Tp, _Alloc>& __ly)
! {
! // We don't have size() so we need to walk through both lists
! // making sure both iterators are valid.
! typename std::forward_list<_Tp, _Alloc>::const_iterator __ix
! = __lx.cbegin();
! typename std::forward_list<_Tp, _Alloc>::const_iterator __iy
! = __ly.cbegin();
! while (__ix != __lx.cend() && __iy != __ly.cend())
! {
! if (*__ix != *__iy)
! return false;
! ++__ix;
! ++__iy;
! }
! if (__ix == __lx.cend() && __iy == __ly.cend())
! return true;
! else
! return false;
! }
/**
* @brief Forward list ordering relation.
--- 1201,1207 ----
template<typename _Tp, typename _Alloc>
bool
operator==(const forward_list<_Tp, _Alloc>& __lx,
! const forward_list<_Tp, _Alloc>& __ly);
/**
* @brief Forward list ordering relation.
*************** _GLIBCXX_BEGIN_NAMESPACE(std)
*** 1285,1291 ****
inline bool
operator!=(const forward_list<_Tp, _Alloc>& __lx,
const forward_list<_Tp, _Alloc>& __ly)
! { return ! (__lx == __ly); }
/// Based on operator<
template<typename _Tp, typename _Alloc>
--- 1226,1232 ----
inline bool
operator!=(const forward_list<_Tp, _Alloc>& __lx,
const forward_list<_Tp, _Alloc>& __ly)
! { return !(__lx == __ly); }
/// Based on operator<
template<typename _Tp, typename _Alloc>
*************** _GLIBCXX_BEGIN_NAMESPACE(std)
*** 1299,1312 ****
inline bool
operator>=(const forward_list<_Tp, _Alloc>& __lx,
const forward_list<_Tp, _Alloc>& __ly)
! { return ! (__lx < __ly); }
/// Based on operator<
template<typename _Tp, typename _Alloc>
inline bool
operator<=(const forward_list<_Tp, _Alloc>& __lx,
const forward_list<_Tp, _Alloc>& __ly)
! { return ! (__ly < __lx); }
/// See std::forward_list::forward_swap().
template<typename _Tp, typename _Alloc>
--- 1240,1253 ----
inline bool
operator>=(const forward_list<_Tp, _Alloc>& __lx,
const forward_list<_Tp, _Alloc>& __ly)
! { return !(__lx < __ly); }
/// Based on operator<
template<typename _Tp, typename _Alloc>
inline bool
operator<=(const forward_list<_Tp, _Alloc>& __lx,
const forward_list<_Tp, _Alloc>& __ly)
! { return !(__ly < __lx); }
/// See std::forward_list::forward_swap().
template<typename _Tp, typename _Alloc>
Index: include/bits/forward_list.tcc
===================================================================
*** include/bits/forward_list.tcc (revision 141165)
--- include/bits/forward_list.tcc (working copy)
*************** _GLIBCXX_BEGIN_NAMESPACE(std)
*** 158,163 ****
--- 158,177 ----
}
template<typename _Tp, typename _Alloc>
+ template<typename... _Args>
+ _Fwd_list_node_base*
+ _Fwd_list_base<_Tp, _Alloc>::
+ _M_insert_after(const_iterator __pos, _Args&&... __args)
+ {
+ _Fwd_list_node_base* __to
+ = const_cast<_Fwd_list_node_base*>(__pos._M_node);
+ _Node* __thing = _M_create_node(std::forward<_Args>(__args)...);
+ __thing->_M_next = __to->_M_next;
+ __to->_M_next = __thing;
+ return __to->_M_next;
+ }
+
+ template<typename _Tp, typename _Alloc>
_Fwd_list_node_base*
_Fwd_list_base<_Tp, _Alloc>::
_M_erase_after(_Fwd_list_node_base* __pos)
*************** _GLIBCXX_BEGIN_NAMESPACE(std)
*** 200,206 ****
_Fwd_list_node_base* __to = &this->_M_impl._M_head;
for (size_type __i = 0; __i < __n; ++__i)
{
! __to->_M_next = _M_create_node(_Tp());
__to = __to->_M_next;
}
}
--- 214,220 ----
_Fwd_list_node_base* __to = &this->_M_impl._M_head;
for (size_type __i = 0; __i < __n; ++__i)
{
! __to->_M_next = this->_M_create_node(_Tp());
__to = __to->_M_next;
}
}
*************** _GLIBCXX_BEGIN_NAMESPACE(std)
*** 213,219 ****
_Fwd_list_node_base* __to = &this->_M_impl._M_head;
for (size_type __i = 0; __i < __n; ++__i)
{
! __to->_M_next = _M_create_node(__value);
__to = __to->_M_next;
}
}
--- 227,233 ----
_Fwd_list_node_base* __to = &this->_M_impl._M_head;
for (size_type __i = 0; __i < __n; ++__i)
{
! __to->_M_next = this->_M_create_node(__value);
__to = __to->_M_next;
}
}
*************** _GLIBCXX_BEGIN_NAMESPACE(std)
*** 229,235 ****
_InputIterator __curr = __first;
while (__curr != __last)
{
! __to->_M_next = _M_create_node(*__curr);
__to = __to->_M_next;
++__curr;
}
--- 243,249 ----
_InputIterator __curr = __first;
while (__curr != __last)
{
! __to->_M_next = this->_M_create_node(*__curr);
__to = __to->_M_next;
++__curr;
}
*************** _GLIBCXX_BEGIN_NAMESPACE(std)
*** 245,251 ****
while (__from->_M_next != 0)
{
const _Node* __temp = static_cast<_Node*>(__from->_M_next);
! __to->_M_next = _M_create_node(__temp->_M_value);
__from = __from->_M_next;
__to = __to->_M_next;
}
--- 259,265 ----
while (__from->_M_next != 0)
{
const _Node* __temp = static_cast<_Node*>(__from->_M_next);
! __to->_M_next = this->_M_create_node(__temp->_M_value);
__from = __from->_M_next;
__to = __to->_M_next;
}
*************** _GLIBCXX_BEGIN_NAMESPACE(std)
*** 260,266 ****
for (const _Tp* __item = __il.begin();
__item != __il.end(); ++__item)
{
! __to->_M_next = _M_create_node(*__item);
__to = __to->_M_next;
}
}
--- 274,280 ----
for (const _Tp* __item = __il.begin();
__item != __il.end(); ++__item)
{
! __to->_M_next = this->_M_create_node(*__item);
__to = __to->_M_next;
}
}
*************** _GLIBCXX_BEGIN_NAMESPACE(std)
*** 303,309 ****
_Fwd_list_node_base* __keep = __to->_M_next;
for (size_type __i = 0; __i < __n; ++__i)
{
! __to->_M_next = _M_create_node(__val);
__to = __to->_M_next;
}
__to->_M_next = __keep;
--- 317,323 ----
_Fwd_list_node_base* __keep = __to->_M_next;
for (size_type __i = 0; __i < __n; ++__i)
{
! __to->_M_next = this->_M_create_node(__val);
__to = __to->_M_next;
}
__to->_M_next = __keep;
*************** _GLIBCXX_BEGIN_NAMESPACE(std)
*** 322,328 ****
_InputIterator __curr = __first;
while (__curr != __last)
{
! __to->_M_next = _M_create_node(*__curr);
__to = __to->_M_next;
++__curr;
}
--- 336,342 ----
_InputIterator __curr = __first;
while (__curr != __last)
{
! __to->_M_next = this->_M_create_node(*__curr);
__to = __to->_M_next;
++__curr;
}
*************** _GLIBCXX_BEGIN_NAMESPACE(std)
*** 340,346 ****
const _Tp* __item = __il.begin();
while (__item != __il.end())
{
! __to->_M_next = _M_create_node(*__item);
__to = __to->_M_next;
++__item;
}
--- 354,360 ----
const _Tp* __item = __il.begin();
while (__item != __il.end())
{
! __to->_M_next = this->_M_create_node(*__item);
__to = __to->_M_next;
++__item;
}
*************** _GLIBCXX_BEGIN_NAMESPACE(std)
*** 369,381 ****
template<typename _Tp, typename _Alloc>
void
forward_list<_Tp, _Alloc>::
remove(const _Tp& __val)
{
_Node* __curr = static_cast<_Node*>(&this->_M_impl._M_head);
while (_Node* __temp = static_cast<_Node*>(__curr->_M_next))
{
if (__temp->_M_value == __val)
! _M_erase_after(__curr);
else
__curr = static_cast<_Node*>(__curr->_M_next);
}
--- 383,424 ----
template<typename _Tp, typename _Alloc>
void
forward_list<_Tp, _Alloc>::
+ splice_after(const_iterator __pos, forward_list&& __list)
+ {
+ if (!__list.empty() && &__list != this)
+ {
+ _Fwd_list_node_base* __tmp
+ = const_cast<_Fwd_list_node_base*>(__pos._M_node);
+ const_iterator __before = __list.cbefore_begin();
+ __tmp->_M_transfer_after(const_cast<_Fwd_list_node_base*>
+ (__before._M_node));
+ }
+ }
+
+ template<typename _Tp, typename _Alloc>
+ void
+ forward_list<_Tp, _Alloc>::
+ splice_after(const_iterator __pos, forward_list&& __list,
+ const_iterator __before, const_iterator __last)
+ {
+ _Fwd_list_node_base* __tmp
+ = const_cast<_Fwd_list_node_base*>(__pos._M_node);
+ __tmp->_M_transfer_after(const_cast<_Fwd_list_node_base*>
+ (__before._M_node),
+ const_cast<_Fwd_list_node_base*>
+ (__last._M_node));
+ }
+
+ template<typename _Tp, typename _Alloc>
+ void
+ forward_list<_Tp, _Alloc>::
remove(const _Tp& __val)
{
_Node* __curr = static_cast<_Node*>(&this->_M_impl._M_head);
while (_Node* __temp = static_cast<_Node*>(__curr->_M_next))
{
if (__temp->_M_value == __val)
! this->_M_erase_after(__curr);
else
__curr = static_cast<_Node*>(__curr->_M_next);
}
*************** _GLIBCXX_BEGIN_NAMESPACE(std)
*** 391,397 ****
while (_Node* __temp = static_cast<_Node*>(__curr->_M_next))
{
if (__pred(__temp->_M_value))
! _M_erase_after(__curr);
else
__curr = static_cast<_Node*>(__curr->_M_next);
}
--- 434,440 ----
while (_Node* __temp = static_cast<_Node*>(__curr->_M_next))
{
if (__pred(__temp->_M_value))
! this->_M_erase_after(__curr);
else
__curr = static_cast<_Node*>(__curr->_M_next);
}
*************** _GLIBCXX_BEGIN_NAMESPACE(std)
*** 462,467 ****
--- 505,540 ----
}
}
+ template<typename _Tp, typename _Alloc>
+ void
+ forward_list<_Tp, _Alloc>::
+ reverse()
+ { this->_M_impl._M_head._M_reverse_after(); }
+
+ template<typename _Tp, typename _Alloc>
+ bool
+ operator==(const forward_list<_Tp, _Alloc>& __lx,
+ const forward_list<_Tp, _Alloc>& __ly)
+ {
+ // We don't have size() so we need to walk through both lists
+ // making sure both iterators are valid.
+ typename std::forward_list<_Tp, _Alloc>::const_iterator __ix
+ = __lx.cbegin();
+ typename std::forward_list<_Tp, _Alloc>::const_iterator __iy
+ = __ly.cbegin();
+ while (__ix != __lx.cend() && __iy != __ly.cend())
+ {
+ if (*__ix != *__iy)
+ return false;
+ ++__ix;
+ ++__iy;
+ }
+ if (__ix == __lx.cend() && __iy == __ly.cend())
+ return true;
+ else
+ return false;
+ }
+
_GLIBCXX_END_NAMESPACE // namespace std
#endif /* _FORWARD_LIST_TCC */