[PATCH] PR libstdc++/90105 make forward_list::sort stable
Jonathan Wakely
jwakely@redhat.com
Wed Apr 17 02:40:00 GMT 2019
While testing the fix I also discovered that operator== assumes the
elements are comparable with operator!= which is not required.
PR libstdc++/90105
* include/bits/forward_list.h (operator==): Do not use operator!= to
compare elements.
(forward_list<T, A>::sort(Comp)): When elements are equal take the one
earlier in the list, so that sort is stable.
* testsuite/23_containers/forward_list/operations/90105.cc: New test.
* testsuite/23_containers/forward_list/comparable.cc: Test with
types that meet the minimum EqualityComparable and LessThanComparable
requirements. Remove irrelevant comment.
Tested powerpc64le-linux.
I'm surprised nobody has noticed either of these bugs before! I think
this is safe for stage 4, and for backporting to active branches. Any
objections?
-------------- next part --------------
commit 2618f400ea46ce881c056543457daa33b3141e7c
Author: Jonathan Wakely <jwakely@redhat.com>
Date: Tue Apr 16 20:37:57 2019 +0100
PR libstdc++/90105 make forward_list::sort stable
While testing the fix I also discovered that operator== assumes the
elements are comparable with operator!= which is not required.
PR libstdc++/90105
* include/bits/forward_list.h (operator==): Do not use operator!= to
compare elements.
(forward_list<T, A>::sort(Comp)): When elements are equal take the one
earlier in the list, so that sort is stable.
* testsuite/23_containers/forward_list/operations/90105.cc: New test.
* testsuite/23_containers/forward_list/comparable.cc: Test with
types that meet the minimum EqualityComparable and LessThanComparable
requirements. Remove irrelevant comment.
diff --git a/libstdc++-v3/include/bits/forward_list.tcc b/libstdc++-v3/include/bits/forward_list.tcc
index 4fac52a8438..088111e3330 100644
--- a/libstdc++-v3/include/bits/forward_list.tcc
+++ b/libstdc++-v3/include/bits/forward_list.tcc
@@ -399,7 +399,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
auto __iy = __ly.cbegin();
while (__ix != __lx.cend() && __iy != __ly.cend())
{
- if (*__ix != *__iy)
+ if (!(*__ix == *__iy))
return false;
++__ix;
++__iy;
@@ -469,9 +469,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
__p = static_cast<_Node*>(__p->_M_next);
--__psize;
}
- else if (__comp(*__p->_M_valptr(), *__q->_M_valptr()))
+ else if (!__comp(*__q->_M_valptr(), *__p->_M_valptr()))
{
- // First node of p is lower; e must come from p.
+ // First node of q is not lower; e must come from p.
__e = __p;
__p = static_cast<_Node*>(__p->_M_next);
--__psize;
diff --git a/libstdc++-v3/testsuite/23_containers/forward_list/comparable.cc b/libstdc++-v3/testsuite/23_containers/forward_list/comparable.cc
index cd921b7bc6b..252d9b5a423 100644
--- a/libstdc++-v3/testsuite/23_containers/forward_list/comparable.cc
+++ b/libstdc++-v3/testsuite/23_containers/forward_list/comparable.cc
@@ -17,15 +17,11 @@
// with this library; see the file COPYING3. If not see
// <http://www.gnu.org/licenses/>.
-
-// NOTE: This makes use of the fact that we know how moveable
-// is implemented on list (via swap). If the implementation changed
-// this test may begin to fail.
-
#include <forward_list>
#include <testsuite_hooks.h>
-int main()
+void
+test01()
{
std::forward_list<double> a = {0.0, 1.0, 2.0, 3.0, 4.0};
std::forward_list<double> b = {0.0, 1.0, 2.0, 3.0, 4.0, 5.0};
@@ -43,6 +39,40 @@ int main()
VERIFY((b > a) == true);
VERIFY((b >= a) == true);
VERIFY((b <= a) == false);
-
- return 0;
+}
+
+void
+test02()
+{
+ // The EqualityComparable requirements only require ==
+ struct X {
+ bool operator==(const X&) const { return true; }
+ };
+
+ std::forward_list<X> a(2);
+ const auto b = a;
+ VERIFY( a == b );
+}
+
+void
+test03()
+{
+ // The LessThanComparable requirements only require <
+ struct X {
+ bool operator<(const X&) const { return false; }
+ };
+
+ std::forward_list<X> a(2);
+ const auto b = a;
+ VERIFY( !(a < b) );
+ VERIFY( !(a > b) );
+ VERIFY( a <= b );
+ VERIFY( a >= b );
+}
+
+int main()
+{
+ test01();
+ test02();
+ test03();
}
diff --git a/libstdc++-v3/testsuite/23_containers/forward_list/operations/90105.cc b/libstdc++-v3/testsuite/23_containers/forward_list/operations/90105.cc
new file mode 100644
index 00000000000..3c1478e2e34
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/forward_list/operations/90105.cc
@@ -0,0 +1,60 @@
+// Copyright (C) 2019 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-do run { target c++11 } }
+
+#include <forward_list>
+#include <testsuite_hooks.h>
+
+// PR libstdc++/90105 - std::forward_list::sort() is not "stable"
+
+struct X
+{
+ int key;
+ int val;
+};
+
+bool operator<(const X& l, const X& r)
+{ return l.key < r.key; }
+
+bool operator==(const X& l, const X& r)
+{ return l.key == r.key && l.val == r.val; }
+
+void
+test01()
+{
+ std::forward_list<X> l{ {1, 1}, {2, 2}, {1, 3}, {0, 4}, {2, 5}, {0, 6} };
+ l.sort();
+ std::forward_list<X> exp{ {0, 4}, {0, 6}, {1, 1}, {1, 3}, {2, 2}, {2, 5} };
+ VERIFY( l == exp );
+}
+
+void
+test02()
+{
+ std::forward_list<X> l{ {1, 1}, {1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 6} };
+ const std::forward_list<X> exp = l;
+ l.sort();
+ VERIFY( l == exp );
+}
+
+int
+main()
+{
+ test01();
+ test02();
+}
More information about the Gcc-patches
mailing list