@@ -485,21 +485,34 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
&& this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
{
- list __carry;
- list __tmp[64];
- list * __fill = __tmp;
- list * __counter;
+ using __detail::_Scratch_list;
+ // The algorithm used here is largely unchanged from the SGI STL
+ // and is described in The C++ Standard Template Library by Plauger,
+ // Stepanov, Lee, Musser.
+ // Each element of *this is spliced out and merged into one of the
+ // sorted lists in __tmp, then all the lists in __tmp are merged
+ // together and then swapped back into *this.
+ // Because all nodes end up back in *this we do not need to update
+ // this->size() while nodes are temporarily moved out.
+ _Scratch_list __carry;
+ _Scratch_list __tmp[64];
+ _Scratch_list* __fill = __tmp;
+ _Scratch_list* __counter;
+
+ _Scratch_list::_Ptr_cmp<const_iterator, void> __ptr_comp;
+
__try
{
do
{
- __carry.splice(__carry.begin(), *this, begin());
+ __carry._M_take_one(begin()._M_node);
for(__counter = __tmp;
__counter != __fill && !__counter->empty();
++__counter)
{
- __counter->merge(__carry);
+
+ __counter->merge(__carry, __ptr_comp);
__carry.swap(*__counter);
}
__carry.swap(*__counter);
@@ -509,14 +522,15 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
while ( !empty() );
for (__counter = __tmp + 1; __counter != __fill; ++__counter)
- __counter->merge(*(__counter - 1));
- swap( *(__fill - 1) );
+ __counter->merge(__counter[-1], __ptr_comp);
+ __fill[-1].swap(this->_M_impl._M_node);
}
__catch(...)
{
- this->splice(this->end(), __carry);
+ // Move all nodes back into *this.
+ __carry._M_put_all(end()._M_node);
for (int __i = 0; __i < sizeof(__tmp)/sizeof(__tmp[0]); ++__i)
- this->splice(this->end(), __tmp[__i]);
+ __tmp[__i]._M_put_all(end()._M_node);
__throw_exception_again;
}
}
@@ -602,42 +616,49 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
// Do nothing if the list has length 0 or 1.
if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
&& this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
- {
- list __carry;
- list __tmp[64];
- list * __fill = __tmp;
- list * __counter;
- __try
- {
- do
- {
- __carry.splice(__carry.begin(), *this, begin());
+ {
+ using __detail::_Scratch_list;
+ _Scratch_list __carry;
+ _Scratch_list __tmp[64];
+ _Scratch_list* __fill = __tmp;
+ _Scratch_list* __counter;
- for(__counter = __tmp;
- __counter != __fill && !__counter->empty();
- ++__counter)
- {
- __counter->merge(__carry, __comp);
- __carry.swap(*__counter);
- }
- __carry.swap(*__counter);
- if (__counter == __fill)
- ++__fill;
- }
- while ( !empty() );
+ _Scratch_list::_Ptr_cmp<const_iterator, _StrictWeakOrdering> __ptr_comp
+ = { __comp };
- for (__counter = __tmp + 1; __counter != __fill; ++__counter)
- __counter->merge(*(__counter - 1), __comp);
- swap(*(__fill - 1));
- }
- __catch(...)
- {
- this->splice(this->end(), __carry);
- for (int __i = 0; __i < sizeof(__tmp)/sizeof(__tmp[0]); ++__i)
- this->splice(this->end(), __tmp[__i]);
- __throw_exception_again;
- }
- }
+ __try
+ {
+ do
+ {
+ __carry._M_take_one(begin()._M_node);
+
+ for(__counter = __tmp;
+ __counter != __fill && !__counter->empty();
+ ++__counter)
+ {
+
+ __counter->merge(__carry, __ptr_comp);
+ __carry.swap(*__counter);
+ }
+ __carry.swap(*__counter);
+ if (__counter == __fill)
+ ++__fill;
+ }
+ while ( !empty() );
+
+ for (__counter = __tmp + 1; __counter != __fill; ++__counter)
+ __counter->merge(__counter[-1], __ptr_comp);
+ __fill[-1].swap(this->_M_impl._M_node);
+ }
+ __catch(...)
+ {
+ // Move all nodes back into *this.
+ __carry._M_put_all(end()._M_node);
+ for (int __i = 0; __i < sizeof(__tmp)/sizeof(__tmp[0]); ++__i)
+ __tmp[__i]._M_put_all(end()._M_node);
+ __throw_exception_again;
+ }
+ }
}
_GLIBCXX_END_NAMESPACE_CONTAINER
@@ -158,6 +158,73 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
private:
_List_node_base* _M_base() { return this; }
};
+
+ // Used by list::sort to hold nodes being sorted.
+ struct _Scratch_list : _List_node_base
+ {
+ _Scratch_list() { _M_next = _M_prev = this; }
+
+ bool empty() const { return _M_next == this; }
+
+ void swap(_List_node_base& __l) { _List_node_base::swap(*this, __l); }
+
+ template<typename _Iter, typename _Cmp>
+ struct _Ptr_cmp
+ {
+ _Cmp _M_cmp;
+
+ bool
+ operator()(const __detail::_List_node_base* __lhs,
+ const __detail::_List_node_base* __rhs) /* not const */
+ { return _M_cmp(*_Iter(__lhs), *_Iter(__rhs)); }
+ };
+
+ template<typename _Iter>
+ struct _Ptr_cmp<_Iter, void>
+ {
+ bool
+ operator()(const __detail::_List_node_base* __lhs,
+ const __detail::_List_node_base* __rhs) const
+ { return *_Iter(__lhs) < *_Iter(__rhs); }
+ };
+
+ // Merge nodes from __x into *this. Both lists must be sorted wrt _Cmp.
+ template<typename _Cmp>
+ void
+ merge(_List_node_base& __x, _Cmp __comp)
+ {
+ _List_node_base* __first1 = _M_next;
+ _List_node_base* const __last1 = this;
+ _List_node_base* __first2 = __x._M_next;
+ _List_node_base* const __last2 = std::__addressof(__x);
+
+ while (__first1 != __last1 && __first2 != __last2)
+ {
+ if (__comp(__first2, __first1))
+ {
+ _List_node_base* __next = __first2->_M_next;
+ __first1->_M_transfer(__first2, __next);
+ __first2 = __next;
+ }
+ else
+ __first1 = __first1->_M_next;
+ }
+ if (__first2 != __last2)
+ this->_M_transfer(__first2, __last2);
+ }
+
+ // Splice the node at __i into *this.
+ void _M_take_one(_List_node_base* __i)
+ { this->_M_transfer(__i, __i->_M_next); }
+
+ // Splice all nodes from *this after __i.
+ void _M_put_all(_List_node_base* __i)
+ {
+ if (!empty())
+ __i->_M_transfer(_M_next, this);
+ }
+ };
+
} // namespace detail
_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
@@ -94,6 +94,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_transfer(_List_node_base * const __first,
_List_node_base * const __last) _GLIBCXX_USE_NOEXCEPT
{
+ __glibcxx_assert(__first != __last);
+
if (this != __last)
{
// Remove [first, last) from its old position.
new file mode 100644
@@ -0,0 +1,55 @@
+// { dg-do run { target c++11 } }
+
+#include <list>
+#include <testsuite_allocator.h>
+#include <testsuite_hooks.h>
+
+// PR libstdc++/66742
+// abort on sorting list with custom allocator that is not stateless
+
+template<typename List, typename Cmp = std::less<typename List::value_type>>
+bool is_sorted(const List& l, Cmp cmp = {})
+{
+ auto it = l.begin();
+ auto next = it;
+ const auto end = l.end();
+ if (it == end)
+ return true;
+ while (++next != end)
+ if (cmp(*next, *it))
+ return false;
+ else
+ it = next;
+ return true;
+}
+
+void
+test01()
+{
+ using Alloc = __gnu_test::uneq_allocator<int>;
+ Alloc a1(1);
+ std::list<int, Alloc> l(a1);
+ for (int i = 0; i < 1000; ++i)
+ {
+ l.push_front(i);
+ l.push_back(i + (i % 3));
+ }
+ const auto orig = l;
+
+ l.sort();
+ VERIFY( is_sorted(l) );
+ l.sort();
+ VERIFY( is_sorted(l) );
+
+ l = orig;
+ l.sort(std::less<int>());
+ VERIFY( is_sorted(l) );
+ l.sort(std::greater<int>());
+ VERIFY( is_sorted(l, std::greater<int>()) );
+}
+
+int
+main()
+{
+ test01();
+}