This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[v3] libstdc++/41316
- From: Paolo Carlini <paolo dot carlini at oracle dot com>
- To: "gcc-patches at gcc dot gnu dot org" <gcc-patches at gcc dot gnu dot org>
- Cc: libstdc++ <libstdc++ at gcc dot gnu dot org>
- Date: Fri, 11 Sep 2009 15:49:21 +0200
- Subject: [v3] libstdc++/41316
Hi,
I went ahead and implemented this straightforward change. Tested
x86_64-linux, committed to mainline.
Paolo.
/////////////////////
2009-09-11 Paolo Carlini <paolo.carlini@oracle.com>
PR libstdc++/41316
* include/bits/forward_list.h (_Fwd_list_node_base<>::_M_sort_after):
Remove.
(forward_list<>::sort(_Comp)): Only declare.
(forward_list<>::sort()): Forward to the latter.
* include/bits/forward_list.tcc (_Fwd_list_node_base<>::_M_sort_after):
Remove definition.
(forward_list<>::sort(_Comp)): Define.
* testsuite/23_containers/forward_list/requirements/dr438/
assign_neg.cc: Adjust dg-error line number.
* testsuite/23_containers/forward_list/requirements/dr438/
insert_neg.cc: Likewise.
* testsuite/23_containers/forward_list/requirements/dr438/
constructor_1_neg.cc: Likewise.
* testsuite/23_containers/forward_list/requirements/dr438/
constructor_2_neg.cc: Likewise.
Index: include/bits/forward_list.h
===================================================================
--- include/bits/forward_list.h (revision 151630)
+++ include/bits/forward_list.h (working copy)
@@ -92,10 +92,6 @@
: _Fwd_list_node_base<_Alloc>(),
_M_value(std::forward<_Args>(__args)...) { }
- template<typename _Comp>
- void
- _M_sort_after(_Comp __comp);
-
_Tp _M_value;
};
@@ -1149,7 +1145,7 @@
*/
void
merge(forward_list&& __list)
- { this->merge(std::forward<forward_list>(__list), std::less<_Tp>()); }
+ { this->merge(std::move(__list), std::less<_Tp>()); }
/**
* @brief Merge sorted lists according to comparison function.
@@ -1174,10 +1170,7 @@
*/
void
sort()
- {
- _Node* __tmp = __static_pointer_cast<_Node*>(&this->_M_impl._M_head);
- __tmp->_M_sort_after(std::less<_Tp>());
- }
+ { this->sort(std::less<_Tp>()); }
/**
* @brief Sort the forward_list using a comparison function.
@@ -1187,11 +1180,7 @@
*/
template<typename _Comp>
void
- sort(_Comp __comp)
- {
- _Node* __tmp = __static_pointer_cast<_Node*>(&this->_M_impl._M_head);
- __tmp->_M_sort_after(__comp);
- }
+ sort(_Comp __comp);
/**
* @brief Reverse the elements in list.
@@ -1285,7 +1274,7 @@
template<typename _Tp, typename _Alloc>
inline void
swap(forward_list<_Tp, _Alloc>& __lx,
- forward_list<_Tp, _Alloc>& __ly)
+ forward_list<_Tp, _Alloc>& __ly)
{ __lx.swap(__ly); }
_GLIBCXX_END_NAMESPACE // namespace std
Index: include/bits/forward_list.tcc
===================================================================
--- include/bits/forward_list.tcc (revision 151630)
+++ include/bits/forward_list.tcc (working copy)
@@ -75,111 +75,6 @@
}
}
- /**
- * @brief Sort the singly linked list starting after this node.
- * This node is assumed to be an empty head node (of type
- * _Fwd_list_node_base).
- */
- template<typename _Tp, class _Alloc>
- template<typename _Comp>
- void
- _Fwd_list_node<_Tp, _Alloc>::
- _M_sort_after(_Comp __comp)
- {
- // If `next' is 0, return immediately.
- _Pointer __list = __static_pointer_cast<_Pointer>(this->_M_next);
- if (!__list)
- return;
-
- unsigned long __insize = 1;
-
- while (1)
- {
- _Pointer __p = __list;
- __list = 0;
- _Pointer __tail = 0;
-
- // Count number of merges we do in this pass.
- unsigned long __nmerges = 0;
-
- while (__p)
- {
- ++__nmerges;
- // There exists a merge to be done.
- // Step `insize' places along from p.
- _Pointer __q = __p;
- unsigned long __psize = 0;
- for (unsigned long __i = 0; __i < __insize; ++__i)
- {
- ++__psize;
- __q = __static_pointer_cast<_Pointer>(__q->_M_next);
- if (!__q)
- break;
- }
-
- // If q hasn't fallen off end, we have two lists to merge.
- unsigned long __qsize = __insize;
-
- // Now we have two lists; merge them.
- while (__psize > 0 || (__qsize > 0 && __q))
- {
- // Decide whether next node of merge comes from p or q.
- _Pointer __e;
- if (__psize == 0)
- {
- // p is empty; e must come from q.
- __e = __q;
- __q = __static_pointer_cast<_Pointer>(__q->_M_next);
- --__qsize;
- }
- else if (__qsize == 0 || !__q)
- {
- // q is empty; e must come from p.
- __e = __p;
- __p = __static_pointer_cast<_Pointer>(__p->_M_next);
- --__psize;
- }
- else if (__comp(__p->_M_value, __q->_M_value))
- {
- // First node of p is lower; e must come from p.
- __e = __p;
- __p = __static_pointer_cast<_Pointer>(__p->_M_next);
- --__psize;
- }
- else
- {
- // First node of q is lower; e must come from q.
- __e = __q;
- __q = __static_pointer_cast<_Pointer>(__q->_M_next);
- --__qsize;
- }
-
- // Add the next node to the merged list.
- if (__tail)
- __tail->_M_next = __e;
- else
- __list = __e;
- __tail = __e;
- }
-
- // Now p has stepped `insize' places along, and q has too.
- __p = __q;
- }
- __tail->_M_next = 0;
-
- // If we have done only one merge, we're finished.
- // Allow for nmerges == 0, the empty list case.
- if (__nmerges <= 1)
- {
- this->_M_next = __list;
- return;
- }
-
- // Otherwise repeat, merging lists twice the size.
- __insize *= 2;
- }
- }
-
template<typename _Tp, typename _Alloc>
_Fwd_list_base<_Tp, _Alloc>::
_Fwd_list_base(const _Fwd_list_base& __lst, const _Alloc& __a)
@@ -472,6 +367,109 @@
return false;
}
+ template<typename _Tp, class _Alloc>
+ template<typename _Comp>
+ void
+ forward_list<_Tp, _Alloc>::
+ sort(_Comp __comp)
+ {
+ typedef typename _Node::_Pointer _Pointer;
+
+ // If `next' is 0, return immediately.
+ _Pointer __list =
+ __static_pointer_cast<_Pointer>(this->_M_impl._M_head._M_next);
+ if (!__list)
+ return;
+
+ unsigned long __insize = 1;
+
+ while (1)
+ {
+ _Pointer __p = __list;
+ __list = 0;
+ _Pointer __tail = 0;
+
+ // Count number of merges we do in this pass.
+ unsigned long __nmerges = 0;
+
+ while (__p)
+ {
+ ++__nmerges;
+ // There exists a merge to be done.
+ // Step `insize' places along from p.
+ _Pointer __q = __p;
+ unsigned long __psize = 0;
+ for (unsigned long __i = 0; __i < __insize; ++__i)
+ {
+ ++__psize;
+ __q = __static_pointer_cast<_Pointer>(__q->_M_next);
+ if (!__q)
+ break;
+ }
+
+ // If q hasn't fallen off end, we have two lists to merge.
+ unsigned long __qsize = __insize;
+
+ // Now we have two lists; merge them.
+ while (__psize > 0 || (__qsize > 0 && __q))
+ {
+ // Decide whether next node of merge comes from p or q.
+ _Pointer __e;
+ if (__psize == 0)
+ {
+ // p is empty; e must come from q.
+ __e = __q;
+ __q = __static_pointer_cast<_Pointer>(__q->_M_next);
+ --__qsize;
+ }
+ else if (__qsize == 0 || !__q)
+ {
+ // q is empty; e must come from p.
+ __e = __p;
+ __p = __static_pointer_cast<_Pointer>(__p->_M_next);
+ --__psize;
+ }
+ else if (__comp(__p->_M_value, __q->_M_value))
+ {
+ // First node of p is lower; e must come from p.
+ __e = __p;
+ __p = __static_pointer_cast<_Pointer>(__p->_M_next);
+ --__psize;
+ }
+ else
+ {
+ // First node of q is lower; e must come from q.
+ __e = __q;
+ __q = __static_pointer_cast<_Pointer>(__q->_M_next);
+ --__qsize;
+ }
+
+ // Add the next node to the merged list.
+ if (__tail)
+ __tail->_M_next = __e;
+ else
+ __list = __e;
+ __tail = __e;
+ }
+
+ // Now p has stepped `insize' places along, and q has too.
+ __p = __q;
+ }
+ __tail->_M_next = 0;
+
+ // If we have done only one merge, we're finished.
+ // Allow for nmerges == 0, the empty list case.
+ if (__nmerges <= 1)
+ {
+ this->_M_impl._M_head._M_next = __list;
+ return;
+ }
+
+ // Otherwise repeat, merging lists twice the size.
+ __insize *= 2;
+ }
+ }
+
_GLIBCXX_END_NAMESPACE // namespace std
#endif /* _FORWARD_LIST_TCC */
Index: testsuite/23_containers/forward_list/requirements/dr438/assign_neg.cc
===================================================================
--- testsuite/23_containers/forward_list/requirements/dr438/assign_neg.cc (revision 151630)
+++ testsuite/23_containers/forward_list/requirements/dr438/assign_neg.cc (working copy)
@@ -1,6 +1,6 @@
// { dg-do compile }
// { dg-options "-std=gnu++0x" }
-// { dg-error "no matching" "" { target *-*-* } 1209 }
+// { dg-error "no matching" "" { target *-*-* } 1198 }
// { dg-excess-errors "" }
// Copyright (C) 2009 Free Software Foundation
Index: testsuite/23_containers/forward_list/requirements/dr438/insert_neg.cc
===================================================================
--- testsuite/23_containers/forward_list/requirements/dr438/insert_neg.cc (revision 151630)
+++ testsuite/23_containers/forward_list/requirements/dr438/insert_neg.cc (working copy)
@@ -1,6 +1,6 @@
// { dg-do compile }
// { dg-options "-std=gnu++0x" }
-// { dg-error "no matching" "" { target *-*-* } 1209 }
+// { dg-error "no matching" "" { target *-*-* } 1198 }
// { dg-excess-errors "" }
// Copyright (C) 2009 Free Software Foundation
Index: testsuite/23_containers/forward_list/requirements/dr438/constructor_1_neg.cc
===================================================================
--- testsuite/23_containers/forward_list/requirements/dr438/constructor_1_neg.cc (revision 151630)
+++ testsuite/23_containers/forward_list/requirements/dr438/constructor_1_neg.cc (working copy)
@@ -1,6 +1,6 @@
// { dg-do compile }
// { dg-options "-std=gnu++0x" }
-// { dg-error "no matching" "" { target *-*-* } 1209 }
+// { dg-error "no matching" "" { target *-*-* } 1198 }
// { dg-excess-errors "" }
// Copyright (C) 2009 Free Software Foundation
Index: testsuite/23_containers/forward_list/requirements/dr438/constructor_2_neg.cc
===================================================================
--- testsuite/23_containers/forward_list/requirements/dr438/constructor_2_neg.cc (revision 151630)
+++ testsuite/23_containers/forward_list/requirements/dr438/constructor_2_neg.cc (working copy)
@@ -1,6 +1,6 @@
// { dg-do compile }
// { dg-options "-std=gnu++0x" }
-// { dg-error "no matching" "" { target *-*-* } 1209 }
+// { dg-error "no matching" "" { target *-*-* } 1198 }
// { dg-excess-errors "" }
// Copyright (C) 2009 Free Software Foundation