https://gcc.gnu.org/g:ff43f9853d3b10e0d2694cd607da1056cb80f38a
commit r15-7708-gff43f9853d3b10e0d2694cd607da1056cb80f38a
Author: Giuseppe D'Angelo <giuseppe.dang...@kdab.com>
Date: Tue Feb 25 18:23:55 2025 +0000
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 (stable_sort): Add constexpr.
* 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): Add constexpr.
(__inplace_stable_sort): Likewise.
(__merge_without_buffer): Likewise.
* include/bits/version.def (constexpr_algorithms): Bump value
for C++26.
* include/bits/version.h: Regnerate.
* 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>
Diff:
---
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 ++-
.../testsuite/25_algorithms/cpp_lib_constexpr.cc | 4 ++
.../25_algorithms/headers/algorithm/synopsis.cc | 2 +
.../25_algorithms/stable_sort/constexpr.cc | 62 ++++++++++++++++++++++
8 files changed, 93 insertions(+), 1 deletion(-)
diff --git a/libstdc++-v3/include/bits/algorithmfwd.h
b/libstdc++-v3/include/bits/algorithmfwd.h
index 0b72895796a2..3e81bca0348a 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 a72eab582be0..d3644a83f802 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 39795e946c91..41b4d0853b71 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 e75befe7f4b1..665b92acae5a 100644
--- a/libstdc++-v3/include/bits/version.def
+++ b/libstdc++-v3/include/bits/version.def
@@ -1110,6 +1110,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 cd713ee54ea3..b47b75a1ca97 100644
--- a/libstdc++-v3/include/bits/version.h
+++ b/libstdc++-v3/include/bits/version.h
@@ -1251,7 +1251,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 4906c4524613..3f60e9961158 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 0765e27ad8bd..5000b18fc42b 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 000000000000..f850278bda5c
--- /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());
