diff options
| author | Paolo Carlini <paolo.carlini@oracle.com> | 2009-09-11 13:47:36 +0000 |
|---|---|---|
| committer | Paolo Carlini <paolo@gcc.gnu.org> | 2009-09-11 13:47:36 +0000 |
| commit | fc52f99da8f58e11eadd3d6ff668cc949d120917 (patch) | |
| tree | dec4567db8a428eae579faa2d0d8dfb0c421b037 /libstdc++-v3 | |
| parent | db689ed6ab4971e329c405bf9701e0605e98e059 (diff) | |
| download | gcc-fc52f99da8f58e11eadd3d6ff668cc949d120917.zip gcc-fc52f99da8f58e11eadd3d6ff668cc949d120917.tar.gz gcc-fc52f99da8f58e11eadd3d6ff668cc949d120917.tar.bz2 | |
re PR libstdc++/41316 ([C++0x] forward_list::sort violates strict aliasing rules)
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.
From-SVN: r151635
Diffstat (limited to 'libstdc++-v3')
7 files changed, 130 insertions, 124 deletions
diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index 0fc0a4f..7d1ce93 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,22 @@ +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. + 2009-09-11 Ralf Wildenhues <Ralf.Wildenhues@gmx.de> * src/Makefile.am (libstdc___la_LINK): New. diff --git a/libstdc++-v3/include/bits/forward_list.h b/libstdc++-v3/include/bits/forward_list.h index 5158f2d..0ec5a11 100644 --- a/libstdc++-v3/include/bits/forward_list.h +++ b/libstdc++-v3/include/bits/forward_list.h @@ -92,10 +92,6 @@ _GLIBCXX_BEGIN_NAMESPACE(std) : _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 @@ _GLIBCXX_BEGIN_NAMESPACE(std) */ 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 @@ _GLIBCXX_BEGIN_NAMESPACE(std) */ 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 @@ _GLIBCXX_BEGIN_NAMESPACE(std) */ 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 @@ _GLIBCXX_BEGIN_NAMESPACE(std) 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 diff --git a/libstdc++-v3/include/bits/forward_list.tcc b/libstdc++-v3/include/bits/forward_list.tcc index 8458e7e..1357369 100644 --- a/libstdc++-v3/include/bits/forward_list.tcc +++ b/libstdc++-v3/include/bits/forward_list.tcc @@ -75,111 +75,6 @@ _GLIBCXX_BEGIN_NAMESPACE(std) } } - /** - * @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 @@ _GLIBCXX_BEGIN_NAMESPACE(std) 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 */ diff --git a/libstdc++-v3/testsuite/23_containers/forward_list/requirements/dr438/assign_neg.cc b/libstdc++-v3/testsuite/23_containers/forward_list/requirements/dr438/assign_neg.cc index 93f0e6d..5062ddf 100644 --- a/libstdc++-v3/testsuite/23_containers/forward_list/requirements/dr438/assign_neg.cc +++ b/libstdc++-v3/testsuite/23_containers/forward_list/requirements/dr438/assign_neg.cc @@ -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 diff --git a/libstdc++-v3/testsuite/23_containers/forward_list/requirements/dr438/constructor_1_neg.cc b/libstdc++-v3/testsuite/23_containers/forward_list/requirements/dr438/constructor_1_neg.cc index 70d0447..6347d96 100644 --- a/libstdc++-v3/testsuite/23_containers/forward_list/requirements/dr438/constructor_1_neg.cc +++ b/libstdc++-v3/testsuite/23_containers/forward_list/requirements/dr438/constructor_1_neg.cc @@ -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 diff --git a/libstdc++-v3/testsuite/23_containers/forward_list/requirements/dr438/constructor_2_neg.cc b/libstdc++-v3/testsuite/23_containers/forward_list/requirements/dr438/constructor_2_neg.cc index 2ee8b9f..af66852 100644 --- a/libstdc++-v3/testsuite/23_containers/forward_list/requirements/dr438/constructor_2_neg.cc +++ b/libstdc++-v3/testsuite/23_containers/forward_list/requirements/dr438/constructor_2_neg.cc @@ -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 diff --git a/libstdc++-v3/testsuite/23_containers/forward_list/requirements/dr438/insert_neg.cc b/libstdc++-v3/testsuite/23_containers/forward_list/requirements/dr438/insert_neg.cc index a21c222..bc8a62d 100644 --- a/libstdc++-v3/testsuite/23_containers/forward_list/requirements/dr438/insert_neg.cc +++ b/libstdc++-v3/testsuite/23_containers/forward_list/requirements/dr438/insert_neg.cc @@ -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 |