[PATCH] libstdc++: Define std::lexicographical_compare_three_way for C++20
Jonathan Wakely
jwakely@redhat.com
Thu Dec 5 12:46:00 GMT 2019
* include/bits/stl_algobase.h (lexicographical_compare_three_way):
Define for C++20.
* testsuite/25_algorithms/lexicographical_compare_three_way/1.cc: New
test.
* testsuite/25_algorithms/lexicographical_compare_three_way/
constexpr.cc: New test.
Tested powerpc64le-linux, committed to trunk.
-------------- next part --------------
commit 5012548fd62526fdf5e04aeacee2b127efbac0e0
Author: Jonathan Wakely <jwakely@redhat.com>
Date: Thu Dec 5 12:23:53 2019 +0000
libstdc++: Define std::lexicographical_compare_three_way for C++20
* include/bits/stl_algobase.h (lexicographical_compare_three_way):
Define for C++20.
* testsuite/25_algorithms/lexicographical_compare_three_way/1.cc: New
test.
* testsuite/25_algorithms/lexicographical_compare_three_way/
constexpr.cc: New test.
diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h
index 98d324827ed..a2fd306e6d0 100644
--- a/libstdc++-v3/include/bits/stl_algobase.h
+++ b/libstdc++-v3/include/bits/stl_algobase.h
@@ -72,6 +72,9 @@
#if __cplusplus >= 201103L
# include <type_traits>
#endif
+#if __cplusplus > 201703L
+# include <compare>
+#endif
namespace std _GLIBCXX_VISIBILITY(default)
{
@@ -1456,6 +1459,104 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
__gnu_cxx::__ops::__iter_comp_iter(__comp));
}
+#if __cpp_lib_three_way_comparison
+#if __cpp_lib_concepts
+ // Iter points to a contiguous range of unsigned narrow character type
+ // or std::byte, suitable for comparison by memcmp.
+ template<typename _Iter>
+ concept __is_byte_iter = contiguous_iterator<_Iter>
+ && __is_byte<iter_value_t<_Iter>>::__value != 0
+ && !__gnu_cxx::__numeric_traits<iter_value_t<_Iter>>::__is_signed;
+
+ // Return a struct with two members, initialized to the smaller of x and y
+ // (or x if they compare equal) and the result of the comparison x <=> y.
+ template<typename _Tp>
+ constexpr auto
+ __min_cmp(_Tp __x, _Tp __y)
+ {
+ struct _Res {
+ _Tp _M_min;
+ decltype(__x <=> __y) _M_cmp;
+ };
+ auto __c = __x <=> __y;
+ if (__c > 0)
+ return _Res{__y, __c};
+ return _Res{__x, __c};
+ }
+#endif
+
+ /**
+ * @brief Performs dictionary comparison on ranges.
+ * @ingroup sorting_algorithms
+ * @param __first1 An input iterator.
+ * @param __last1 An input iterator.
+ * @param __first2 An input iterator.
+ * @param __last2 An input iterator.
+ * @param __comp A @link comparison_functors comparison functor@endlink.
+ * @return The comparison category that `__comp(*__first1, *__first2)`
+ * returns.
+ */
+ template<typename _InputIter1, typename _InputIter2, typename _Comp>
+ constexpr auto
+ lexicographical_compare_three_way(_InputIter1 __first1,
+ _InputIter1 __last1,
+ _InputIter2 __first2,
+ _InputIter2 __last2,
+ _Comp __comp)
+ -> decltype(__comp(*__first1, *__first2))
+ {
+ // concept requirements
+ __glibcxx_function_requires(_InputIteratorConcept<_InputIter1>)
+ __glibcxx_function_requires(_InputIteratorConcept<_InputIter2>)
+ __glibcxx_requires_valid_range(__first1, __last1);
+ __glibcxx_requires_valid_range(__first2, __last2);
+
+#if __cpp_lib_concepts && __cpp_lib_is_constant_evaluated
+ using _Cat = decltype(__comp(*__first1, *__first2));
+ static_assert(same_as<common_comparison_category_t<_Cat>, _Cat>);
+
+ if (!std::is_constant_evaluated())
+ if constexpr (same_as<_Comp, __detail::_Synth3way>
+ || same_as<_Comp, compare_three_way>)
+ if constexpr (__is_byte_iter<_InputIter1>)
+ if constexpr (__is_byte_iter<_InputIter2>)
+ {
+ const auto [__len, __lencmp]
+ = std::__min_cmp(__last1 - __first1, __last2 - __first2);
+ if (__len)
+ {
+ const auto __c
+ = __builtin_memcmp(&*__first1, &*__first2, __len) <=> 0;
+ if (__c != 0)
+ return __c;
+ }
+ return __lencmp;
+ }
+#endif // concepts && is_constant_evaluated
+ while (__first1 != __last1 && __first2 != __last2)
+ {
+ if (auto __cmp = __comp(*__first1, *__first2); __cmp != 0)
+ return __cmp;
+ ++__first1;
+ ++__first2;
+ }
+ return __first1 != __last1 ? strong_ordering::greater
+ : __first2 != __last2 ? strong_ordering::less : strong_ordering::equal;
+ }
+
+ template<typename _InputIter1, typename _InputIter2>
+ constexpr auto
+ lexicographical_compare_three_way(_InputIter1 __first1,
+ _InputIter1 __last1,
+ _InputIter2 __first2,
+ _InputIter2 __last2)
+ {
+ return std::lexicographical_compare_three_way(__first1, __last1,
+ __first2, __last2,
+ compare_three_way{});
+ }
+#endif // three_way_comparison
+
template<typename _InputIterator1, typename _InputIterator2,
typename _BinaryPredicate>
_GLIBCXX20_CONSTEXPR
diff --git a/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare_three_way/1.cc b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare_three_way/1.cc
new file mode 100644
index 00000000000..b1e70e80de7
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare_three_way/1.cc
@@ -0,0 +1,129 @@
+// 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-options "-std=gnu++2a" }
+// { dg-do run { target c++2a } }
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+
+// Lambda that calls lexicographical_compare_three_way on two ranges.
+// Arguments are passed by value intentionally, so that a copy of the range
+// is traversed and the original is not modified. Otherwise when the range
+// has input iterators the range will be consumed after the first comparison.
+auto lexicomp3 = [](auto r1, auto r2) {
+ return std::lexicographical_compare_three_way(r1.begin(), r1.end(),
+ r2.begin(), r2.end());
+};
+
+void
+test01()
+{
+ using __gnu_test::test_container;
+ using __gnu_test::input_iterator_wrapper;
+ using __gnu_test::forward_iterator_wrapper;
+ int arr1[] = { 0, 1, 2, 3, 4, 5, 6, 7 };
+ int arr2[] = { 0, 1, 2, 3, 4, 5, 6, 777 };
+
+ {
+ test_container<int, input_iterator_wrapper> c1(arr1);
+ test_container<int, input_iterator_wrapper> c2(arr2);
+ VERIFY( lexicomp3(c1, c1) == 0 );
+ VERIFY( lexicomp3(c1, c2) < 0 );
+ VERIFY( lexicomp3(c2, c1) > 0 );
+ }
+
+ {
+ test_container<int, input_iterator_wrapper> c1(arr1, arr1+6);
+ test_container<int, input_iterator_wrapper> c2(arr2, arr2+6);
+ VERIFY( lexicomp3(c1, c1) == 0 );
+ VERIFY( lexicomp3(c1, c2) == 0 );
+ VERIFY( lexicomp3(c2, c1) == 0 );
+ }
+
+ {
+ test_container<int, input_iterator_wrapper> c1(arr1);
+ test_container<int, input_iterator_wrapper> c2(arr2, arr2+7);
+ VERIFY( lexicomp3(c1, c1) == 0 );
+ VERIFY( lexicomp3(c1, c2) > 0 );
+ VERIFY( lexicomp3(c2, c1) < 0 );
+ }
+
+ {
+ test_container<int, input_iterator_wrapper> c1(arr1);
+ test_container<int, forward_iterator_wrapper> c2(arr2);
+ VERIFY( lexicomp3(c1, c1) == 0 );
+ VERIFY( lexicomp3(c1, c2) < 0 );
+ VERIFY( lexicomp3(c2, c1) > 0 );
+ }
+
+ {
+ test_container<int, input_iterator_wrapper> c1(arr1);
+ test_container<int, forward_iterator_wrapper> c2(arr2, arr2+7);
+ VERIFY( lexicomp3(c1, c1) == 0 );
+ VERIFY( lexicomp3(c2, c2) == 0 );
+ VERIFY( lexicomp3(c1, c2) > 0 );
+ VERIFY( lexicomp3(c2, c1) < 0 );
+ }
+
+ {
+ test_container<int, forward_iterator_wrapper> c1(arr1, arr1+7);
+ test_container<int, input_iterator_wrapper> c2(arr2);
+ VERIFY( lexicomp3(c1, c1) == 0 );
+ VERIFY( lexicomp3(c2, c2) == 0 );
+ VERIFY( lexicomp3(c1, c2) < 0 );
+ VERIFY( lexicomp3(c2, c1) > 0 );
+ }
+}
+
+void
+test02()
+{
+ using __gnu_test::test_container;
+ using __gnu_test::input_iterator_wrapper;
+ using __gnu_test::forward_iterator_wrapper;
+ std::array<unsigned char, 8> c1 = { 0, 1, 2, 3, 4, 5, 6, 7 };
+ std::array<unsigned char, 8> c2 = { 0, 1, 2, 3, 4, 5, 6, 77 };
+
+ VERIFY( lexicomp3(c1, c1) == 0 );
+ VERIFY( lexicomp3(c1, c2) < 0 );
+ VERIFY( lexicomp3(c2, c1) > 0 );
+
+ std::array<unsigned char, 7> c3 = { 0, 1, 2, 3, 4, 5, 6 };
+ VERIFY( lexicomp3(c3, c3) == 0 );
+ VERIFY( lexicomp3(c1, c3) > 0 );
+ VERIFY( lexicomp3(c3, c1) < 0 );
+}
+
+void
+test03()
+{
+ unsigned char a[2] = { 1, 2 };
+ unsigned char* p = nullptr;
+ // ensure memcmp not called with nullptr
+ VERIFY( std::lexicographical_compare_three_way(p, p, a, a+2) < 0 );
+ VERIFY( std::lexicographical_compare_three_way(a, a+2, p, p) > 0 );
+}
+
+int
+main()
+{
+ test01();
+ test02();
+ test03();
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare_three_way/constexpr.cc b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare_three_way/constexpr.cc
new file mode 100644
index 00000000000..5d1e15cc4f3
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare_three_way/constexpr.cc
@@ -0,0 +1,65 @@
+// 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-options "-std=gnu++2a" }
+// { dg-do compile { target c++2a } }
+
+#include <algorithm>
+
+constexpr bool
+test01(int i)
+{
+ int a1[] = { 0, 1, 2, 3, 4, 5, 6, i, 8 };
+ long a2[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8 };
+
+ return std::lexicographical_compare_three_way(a1, a1+0, a2, a2+0) == 0
+ && std::lexicographical_compare_three_way(a1, a1+9, a2, a2+9) == (i <=> 7)
+ && std::lexicographical_compare_three_way(a1, a1+7, a2, a2+7) == 0
+ && std::lexicographical_compare_three_way(a1, a1+8, a2, a2+7) > 0
+ && std::lexicographical_compare_three_way(a1, a1+7, a2, a2+8) < 0;
+}
+
+static_assert( test01(~7) );
+static_assert( test01(7) );
+static_assert( test01(8) );
+
+constexpr bool
+test02(unsigned char i)
+{
+ unsigned char a1[] = { 0, 1, 2, 3, 4, 5, 6, i, 8 };
+ unsigned char a2[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8 };
+
+ return std::lexicographical_compare_three_way(a1, a1+0, a2, a2+0) == 0
+ && std::lexicographical_compare_three_way(a1, a1+9, a2, a2+9) == (i <=> 7)
+ && std::lexicographical_compare_three_way(a1, a1+7, a2, a2+7) == 0
+ && std::lexicographical_compare_three_way(a1, a1+8, a2, a2+7) > 0
+ && std::lexicographical_compare_three_way(a1, a1+7, a2, a2+8) < 0;
+}
+
+static_assert( test02(248) );
+static_assert( test02(7) );
+static_assert( test02(8) );
+
+constexpr bool
+test03(unsigned char* p)
+{
+ unsigned char a[2] = { 1, 2 };
+ return std::lexicographical_compare_three_way(p, p, a, a+2) < 0
+ && std::lexicographical_compare_three_way(a, a+2, p, p) > 0;
+}
+
+static_assert( test03(nullptr) ); // ensure memcmp not called with nullptr
More information about the Gcc-patches
mailing list