In list::sort() we use 65 list objects to use as temporary storage,
splicing and swapping elements between lists.
However the lists are default constructed, with no allocator argument,
which is wrong because the allocator type might not be default
constructible, and even more wrong because splicing and merging
between lists with non-equal allocators is undefined behaviour.
So if this->get_allocator() != allocator_type() then we have undefined
behaviour.
The attached patch replaces the fixed-size array of 64
default-constructed lists with a new container-like type,
_ListSortBuf, which is initially empty (so we don't create lists we
don't need) but will grow up to a maximum size (which I kept at 64).
As the container grows it initializes new elements with the correct
allocator, so that every list used in the sort uses the same
allocator.
As well as reducing the number of lists we construct when sorting this
also allows us to range-check and ensure we don't overflow the
fixed-size array (we now get an exception if that happens, although
that's probably not possible even on a 64-bit machine).
Unfortunately this seems to hurt performance, presumably the extra
indirections to the _ListSOrtBuf rather than just an array of lists
confuse the optimisers.
Does anyone see any better solution to this? (other than rewriting the
whole sort function, which I think has been proposed)
commit ba5b393a09022907f9aee2b539ad14fc1fc8a42d
Author: Jonathan Wakely <jwak...@redhat.com>
Date: Fri Jul 3 15:20:36 2015 +0100
PR libstdc++/66742
* include/bits/list.tcc (_ListSortBuf): Define.
(list::sort): Use _ListSortBuf.
* testsuite/23_containers/list/operations/66742.cc: New.
diff --git a/libstdc++-v3/include/bits/list.tcc b/libstdc++-v3/include/bits/list.tcc
index 714d9b5..f335af4 100644
--- a/libstdc++-v3/include/bits/list.tcc
+++ b/libstdc++-v3/include/bits/list.tcc
@@ -440,6 +440,53 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
}
}
+ // A simple array-like container with a fixed maximum size.
+ template<typename _List, size_t _Size>
+ class _ListSortBuf
+ {
+ template<typename _Tp, typename _Alloc>
+ friend class list;
+
+ struct __attribute__((__aligned__(__alignof__(_List)))) _Elem
+ {
+ unsigned char _M_buf[sizeof(_List)];
+ operator _List*() { return reinterpret_cast<_List*>(_M_buf); }
+ };
+ _Elem _M_buf[_Size];
+
+ typedef typename _List::allocator_type allocator_type;
+
+ struct _Impl : allocator_type
+ {
+ _Impl(const allocator_type& __a) : allocator_type(__a), _M_size(0) { }
+ size_t _M_size;
+ } _M_impl;
+
+ _ListSortBuf(const allocator_type& __a) : _M_impl(__a) { }
+
+ ~_ListSortBuf()
+ {
+ while (_M_impl._M_size)
+ static_cast<_List*>(_M_buf[--_M_impl._M_size])->~_List();
+ }
+
+ _List* begin() { return _M_buf[0]; }
+ _List* end() { return begin() + _M_impl._M_size; }
+
+ void _M_grow()
+ {
+ if (_M_impl._M_size == _Size)
+ __throw_bad_alloc();
+ ::new(static_cast<void*>(_M_buf + _M_impl._M_size)) _List(_M_impl);
+ ++_M_impl._M_size;
+ }
+
+ bool empty() const { return _M_impl._M_size == 0; }
+
+ _ListSortBuf(const _ListSortBuf&);
+ _ListSortBuf& operator=(const _ListSortBuf&);
+ };
+
template<typename _Tp, typename _Alloc>
void
list<_Tp, _Alloc>::
@@ -448,33 +495,36 @@ _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;
+ {
+ list __carry(get_allocator());
+ _ListSortBuf<list, 64> __tmp(get_allocator());
+ list* __counter;
- do
- {
- __carry.splice(__carry.begin(), *this, begin());
+ do
+ {
+ __carry.splice(__carry.begin(), *this, begin());
- for(__counter = __tmp;
- __counter != __fill && !__counter->empty();
- ++__counter)
- {
- __counter->merge(__carry);
- __carry.swap(*__counter);
- }
- __carry.swap(*__counter);
- if (__counter == __fill)
- ++__fill;
- }
- while ( !empty() );
+ for(__counter = __tmp.begin();
+ __counter != __tmp.end() && !__counter->empty();
+ ++__counter)
+ {
+ __counter->merge(__carry);
+ __carry.swap(*__counter);
+ }
+ if (__counter == __tmp.end())
+ __tmp._M_grow();
+ __carry.swap(*__counter);
+ }
+ while ( !empty() );
- for (__counter = __tmp + 1; __counter != __fill; ++__counter)
- __counter->merge(*(__counter - 1));
- swap( *(__fill - 1) );
- }
+ if (!__tmp.empty())
+ {
+ for (__counter = __tmp.begin() + 1; __counter != __tmp.end();
+ ++__counter)
+ __counter->merge(*(__counter - 1));
+ swap( *(__tmp.end() - 1) );
+ }
+ }
}
template<typename _Tp, typename _Alloc>
@@ -526,31 +576,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;
+ list __carry(get_allocator());
+ _ListSortBuf<list, 64> __tmp(get_allocator());
+ list* __counter;
do
{
__carry.splice(__carry.begin(), *this, begin());
- for(__counter = __tmp;
- __counter != __fill && !__counter->empty();
+ for(__counter = __tmp.begin();
+ __counter != __tmp.end() && !__counter->empty();
++__counter)
{
__counter->merge(__carry, __comp);
__carry.swap(*__counter);
}
+ if (__counter == __tmp.end())
+ __tmp._M_grow();
__carry.swap(*__counter);
- if (__counter == __fill)
- ++__fill;
}
while ( !empty() );
- for (__counter = __tmp + 1; __counter != __fill; ++__counter)
- __counter->merge(*(__counter - 1), __comp);
- swap(*(__fill - 1));
+ if (!__tmp.empty())
+ {
+ for (__counter = __tmp.begin() + 1; __counter != __tmp.end();
+ ++__counter)
+ __counter->merge(*(__counter - 1), __comp);
+ swap( *(__tmp.end() - 1) );
+ }
}
}
diff --git a/libstdc++-v3/testsuite/23_containers/list/operations/66742.cc b/libstdc++-v3/testsuite/23_containers/list/operations/66742.cc
new file mode 100644
index 0000000..252d1d4
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/list/operations/66742.cc
@@ -0,0 +1,60 @@
+// Copyright (C) 2015 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++11" }
+
+#include <list>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+template<typename T>
+struct NonDefaultConstructibleAlloc : __gnu_test::SimpleAllocator<T>
+{
+ NonDefaultConstructibleAlloc(int) { }
+
+ template<typename U>
+ NonDefaultConstructibleAlloc(const NonDefaultConstructibleAlloc<U>) { }
+};
+
+void
+test01()
+{
+ using A = NonDefaultConstructibleAlloc<int>;
+ std::list<int, A> l{ A{1} };
+ l.sort();
+}
+
+void
+test02()
+{
+ using A = __gnu_test::uneq_allocator<int>;
+ std::list<int, A> l{ A{1} };
+ l.push_back(1);
+ l.push_back(3);
+ l.push_back(2);
+ l.sort();
+ VERIFY( l.size() == 3 );
+ VERIFY( l.front() == 1 );
+ VERIFY( l.back() == 3 );
+}
+
+int
+main()
+{
+ test01();
+ test02();
+}
