Hello,This patch adds constexpr to the stable_sort algorithms, implementing P2562R1 for C++26. Tested on x86-64 Linux.
Thanks, -- Giuseppe D'Angelo
From 951d76ee06abeda932f5c803bfe6d2691403c2e9 Mon Sep 17 00:00:00 2001
From: Giuseppe D'Angelo <giuseppe.dang...@kdab.com>
Date: Tue, 31 Dec 2024 18:04:45 +0100
Subject: [PATCH] libstdc++: add support for constexpr stable_sort (P2562R1)
stable_sort has been made constexpr in C++26. Apart from plastering a
few functions with constexpr, there's an implementation challenge, that
is: stable_sort takes different codepaths in case extra memory can be
allocated. Rather than doing some major refactorings, simply use the
non-allocating path during constant evaluation. That's the same codepath
used when extra memory could not be allocated, as well as by
freestanding.
libstdc++-v3/ChangeLog:
* include/bits/algorithmfwd.h: Add constexpr to stable_sort's
forward declaration.
* include/bits/ranges_algo.h (stable_sort_fn): Add constexpr
to the function call operators.
* include/bits/stl_algo.h (stable_sort): Add constexpr.
During constant evaluation, always use the non-allocating path.
(__stable_sort): Likewise.
(__inplace_stable_sort): Likewise.
(__merge_without_buffer): Likewise.
* include/bits/version.def: Bump the feature-testing macro.
* include/bits/version.h: Regenerate.
* testsuite/25_algorithms/cpp_lib_constexpr.cc: Test the bumped
feature-testing macro.
* testsuite/25_algorithms/headers/algorithm/synopsis.cc: Adapt
the test to constexpr stable_sort.
* testsuite/25_algorithms/stable_sort/constexpr.cc: New test.
Signed-off-by: Giuseppe D'Angelo <giuseppe.dang...@kdab.com>
---
libstdc++-v3/include/bits/algorithmfwd.h | 2 +
libstdc++-v3/include/bits/ranges_algo.h | 2 +
libstdc++-v3/include/bits/stl_algo.h | 11 ++++
libstdc++-v3/include/bits/version.def | 4 ++
libstdc++-v3/include/bits/version.h | 7 ++-
.../25_algorithms/cpp_lib_constexpr.cc | 4 ++
.../headers/algorithm/synopsis.cc | 2 +
.../25_algorithms/stable_sort/constexpr.cc | 62 +++++++++++++++++++
8 files changed, 93 insertions(+), 1 deletion(-)
create mode 100644 libstdc++-v3/testsuite/25_algorithms/stable_sort/constexpr.cc
diff --git a/libstdc++-v3/include/bits/algorithmfwd.h b/libstdc++-v3/include/bits/algorithmfwd.h
index 0016dcd42e9..5e0c9c07146 100644
--- a/libstdc++-v3/include/bits/algorithmfwd.h
+++ b/libstdc++-v3/include/bits/algorithmfwd.h
@@ -945,10 +945,12 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
sort(_RAIter, _RAIter, _Compare);
template<typename _RAIter>
+ _GLIBCXX26_CONSTEXPR
void
stable_sort(_RAIter, _RAIter);
template<typename _RAIter, typename _Compare>
+ _GLIBCXX26_CONSTEXPR
void
stable_sort(_RAIter, _RAIter, _Compare);
diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h
index 80d8123443f..f03b575520d 100644
--- a/libstdc++-v3/include/bits/ranges_algo.h
+++ b/libstdc++-v3/include/bits/ranges_algo.h
@@ -1842,6 +1842,7 @@ namespace ranges
template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
typename _Comp = ranges::less, typename _Proj = identity>
requires sortable<_Iter, _Comp, _Proj>
+ _GLIBCXX26_CONSTEXPR
_Iter
operator()(_Iter __first, _Sent __last,
_Comp __comp = {}, _Proj __proj = {}) const
@@ -1855,6 +1856,7 @@ namespace ranges
template<random_access_range _Range,
typename _Comp = ranges::less, typename _Proj = identity>
requires sortable<iterator_t<_Range>, _Comp, _Proj>
+ _GLIBCXX26_CONSTEXPR
borrowed_iterator_t<_Range>
operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
{
diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h
index d8a7668ff83..3155a744313 100644
--- a/libstdc++-v3/include/bits/stl_algo.h
+++ b/libstdc++-v3/include/bits/stl_algo.h
@@ -2415,6 +2415,7 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
/// This is a helper function for the merge routines.
template<typename _BidirectionalIterator, typename _Distance,
typename _Compare>
+ _GLIBCXX26_CONSTEXPR
void
__merge_without_buffer(_BidirectionalIterator __first,
_BidirectionalIterator __middle,
@@ -2723,6 +2724,7 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
/// This is a helper function for the stable sorting routines.
template<typename _RandomAccessIterator, typename _Compare>
+ _GLIBCXX26_CONSTEXPR
void
__inplace_stable_sort(_RandomAccessIterator __first,
_RandomAccessIterator __last, _Compare __comp)
@@ -4971,6 +4973,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
}
template<typename _RandomAccessIterator, typename _Compare>
+ _GLIBCXX26_CONSTEXPR
inline void
__stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Compare __comp)
@@ -4984,6 +4987,12 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
return;
#if _GLIBCXX_HOSTED
+ if (__is_constant_evaluated())
+ {
+ std::__inplace_stable_sort(__first, __last, __comp);
+ return;
+ }
+
typedef _Temporary_buffer<_RandomAccessIterator, _ValueType> _TmpBuf;
// __stable_sort_adaptive sorts the range in two halves,
// so the buffer only needs to fit half the range at once.
@@ -5021,6 +5030,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
* ordering after calling @p stable_sort().
*/
template<typename _RandomAccessIterator>
+ _GLIBCXX26_CONSTEXPR
inline void
stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
{
@@ -5055,6 +5065,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
* relative ordering after calling @p stable_sort().
*/
template<typename _RandomAccessIterator, typename _Compare>
+ _GLIBCXX26_CONSTEXPR
inline void
stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Compare __comp)
diff --git a/libstdc++-v3/include/bits/version.def b/libstdc++-v3/include/bits/version.def
index 08ca01803c0..1e8bda98f98 100644
--- a/libstdc++-v3/include/bits/version.def
+++ b/libstdc++-v3/include/bits/version.def
@@ -1114,6 +1114,10 @@ ftms = {
ftms = {
name = constexpr_algorithms;
+ values = {
+ v = 202306;
+ cxxmin = 26;
+ };
values = {
v = 201806;
cxxmin = 20;
diff --git a/libstdc++-v3/include/bits/version.h b/libstdc++-v3/include/bits/version.h
index 714235a599c..192e04dd3b4 100644
--- a/libstdc++-v3/include/bits/version.h
+++ b/libstdc++-v3/include/bits/version.h
@@ -1256,7 +1256,12 @@
#undef __glibcxx_want_constexpr_functional
#if !defined(__cpp_lib_constexpr_algorithms)
-# if (__cplusplus >= 202002L)
+# if (__cplusplus > 202302L)
+# define __glibcxx_constexpr_algorithms 202306L
+# if defined(__glibcxx_want_all) || defined(__glibcxx_want_constexpr_algorithms)
+# define __cpp_lib_constexpr_algorithms 202306L
+# endif
+# elif (__cplusplus >= 202002L)
# define __glibcxx_constexpr_algorithms 201806L
# if defined(__glibcxx_want_all) || defined(__glibcxx_want_constexpr_algorithms)
# define __cpp_lib_constexpr_algorithms 201806L
diff --git a/libstdc++-v3/testsuite/25_algorithms/cpp_lib_constexpr.cc b/libstdc++-v3/testsuite/25_algorithms/cpp_lib_constexpr.cc
index d298522c08a..e8bad7e348a 100644
--- a/libstdc++-v3/testsuite/25_algorithms/cpp_lib_constexpr.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/cpp_lib_constexpr.cc
@@ -22,6 +22,10 @@
#ifndef __cpp_lib_constexpr_algorithms
# error "Feature-test macro for constexpr algorithms missing"
+#elif __cplusplus > 202302L
+# if __cpp_lib_constexpr_algorithms < 202306L
+# error "Feature-test macro for constexpr algorithms has wrong value"
+# endif
#elif __cpp_lib_constexpr_algorithms < 201806L
# error "Feature-test macro for constexpr algorithms has wrong value"
#endif
diff --git a/libstdc++-v3/testsuite/25_algorithms/headers/algorithm/synopsis.cc b/libstdc++-v3/testsuite/25_algorithms/headers/algorithm/synopsis.cc
index 08a47aa95c3..c6bf1525aae 100644
--- a/libstdc++-v3/testsuite/25_algorithms/headers/algorithm/synopsis.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/headers/algorithm/synopsis.cc
@@ -365,10 +365,12 @@ namespace std
sort(_RAIter, _RAIter, _Compare);
template<typename _RAIter>
+ _GLIBCXX26_CONSTEXPR
void
stable_sort(_RAIter, _RAIter);
template<typename _RAIter, typename _Compare>
+ _GLIBCXX26_CONSTEXPR
void
stable_sort(_RAIter, _RAIter, _Compare);
diff --git a/libstdc++-v3/testsuite/25_algorithms/stable_sort/constexpr.cc b/libstdc++-v3/testsuite/25_algorithms/stable_sort/constexpr.cc
new file mode 100644
index 00000000000..f850278bda5
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/stable_sort/constexpr.cc
@@ -0,0 +1,62 @@
+// { dg-do compile { target c++26 } }
+
+#include <algorithm>
+#include <array>
+#include <functional>
+
+constexpr auto
+createArray()
+{
+ return std::to_array({10, 0, 1, 2, 5, 6, 7, 8, 3, 4, 9, 11});
+}
+
+constexpr bool
+test01()
+{
+ auto ar = createArray();
+ std::stable_sort(ar.begin(), ar.end());
+ return std::is_sorted(ar.begin(), ar.end());
+}
+
+static_assert(test01());
+
+constexpr bool
+test02()
+{
+ auto ar = createArray();
+ std::stable_sort(ar.begin(), ar.end(), std::greater<>());
+ return std::is_sorted(ar.begin(), ar.end(), std::greater<>());
+}
+
+static_assert(test02());
+
+constexpr bool
+test03()
+{
+ auto ar = createArray();
+ std::ranges::stable_sort(ar);
+ return std::ranges::is_sorted(ar);
+}
+
+static_assert(test03());
+
+constexpr bool
+test04()
+{
+ auto ar = createArray();
+ std::ranges::stable_sort(ar, std::ranges::greater());
+ return std::ranges::is_sorted(ar, std::ranges::greater());
+}
+
+static_assert(test04());
+
+constexpr bool
+test05()
+{
+ auto ar = createArray();
+ auto proj = [](int i) { return -i; };
+ std::ranges::stable_sort(ar, {}, proj);
+ return std::ranges::is_sorted(ar, {}, proj);
+}
+
+static_assert(test05());
--
2.34.1
smime.p7s
Description: S/MIME Cryptographic Signature
