PR libstdc++/100795
PR libstdc++/118209
libstdc++-v3/ChangeLog:
* include/bits/max_size_type.h (__bit_width): New explicit
specializatino for __max_size_type.
* include/bits/ranges_algo.h (__detail::__move_median_to_first):
New, based on the stl_algo.h implementation.
(__detail::__unguarded_liner_insert): Likewise.
(__detail::__insertion_sort): Likewise.
(__detail::__sort_threshold): Likewise.
(__detail::__unguarded_insertion_sort): Likewise.
(__detail::__final_insertion_sort): Likewise.
(__detail::__unguarded_partition): Likewise.
(__detail::__unguarded_partition_pivot): Likewise.
(__detail::__heap_select): Likewise.
(__detail::__partial_sort): Likewise.
(__detail::__introsort_loop): Likewise.
(__sort_fn::operator()): Reimplement in terms of the above.
* libstdc++-v3/testsuite/25_algorithms/sort/118209.cc: New test.
* libstdc++-v3/testsuite/25_algorithms/sort/constrained.cc
(test03): New test.
Reviewed-by: Tomasz Kamiński <tkami...@redhat.com>
---
libstdc++-v3/include/bits/max_size_type.h | 11 ++
libstdc++-v3/include/bits/ranges_algo.h | 168 +++++++++++++++++-
.../testsuite/25_algorithms/sort/118209.cc | 23 +++
.../25_algorithms/sort/constrained.cc | 31 ++++
4 files changed, 229 insertions(+), 4 deletions(-)
create mode 100644 libstdc++-v3/testsuite/25_algorithms/sort/118209.cc
diff --git a/libstdc++-v3/include/bits/max_size_type.h
b/libstdc++-v3/include/bits/max_size_type.h
index e602b1b4bee5..73a6d141d5bc 100644
--- a/libstdc++-v3/include/bits/max_size_type.h
+++ b/libstdc++-v3/include/bits/max_size_type.h
@@ -36,6 +36,7 @@
#if __cplusplus > 201703L && __cpp_lib_concepts
#include <ext/numeric_traits.h>
+#include <bit> // __bit_width
#include <numbers>
// This header implements unsigned and signed integer-class types (as per
@@ -818,6 +819,16 @@ namespace ranges
{ return min(); }
};
+ template<>
+ inline constexpr int
+ __bit_width(ranges::__detail::__max_size_type __x) noexcept
+ {
+ if (__x._M_msb)
+ return numeric_limits<ranges::__detail::__max_size_type>::digits;
+ else
+ return std::__bit_width(__x._M_val);
+ }
+
_GLIBCXX_END_NAMESPACE_VERSION
} // namespace
diff --git a/libstdc++-v3/include/bits/ranges_algo.h
b/libstdc++-v3/include/bits/ranges_algo.h
index d13729a83f72..de935dde4f70 100644
--- a/libstdc++-v3/include/bits/ranges_algo.h
+++ b/libstdc++-v3/include/bits/ranges_algo.h
@@ -32,6 +32,7 @@
#if __cplusplus > 201703L
+#include <bit> // __bit_width
#if __cplusplus > 202002L
#include <optional>
#endif
@@ -2200,6 +2201,154 @@ namespace ranges
inline constexpr __is_heap_fn is_heap{};
+ namespace __detail
+ {
+ template<typename _Iter, typename _Comp>
+ constexpr void
+ __move_median_to_first(_Iter __result, _Iter __a, _Iter __b, _Iter __c,
+ _Comp __comp)
+ {
+ if (__comp(*__a, *__b))
+ {
+ if (__comp(*__b, *__c))
+ ranges::iter_swap(__result, __b);
+ else if (__comp(*__a, *__c))
+ ranges::iter_swap(__result, __c);
+ else
+ ranges::iter_swap(__result, __a);
+ }
+ else if (__comp(*__a, *__c))
+ ranges::iter_swap(__result, __a);
+ else if (__comp(*__b, *__c))
+ ranges::iter_swap(__result, __c);
+ else
+ ranges::iter_swap(__result, __b);
+ }
+
+ template<typename _Iter, typename _Comp>
+ constexpr void
+ __unguarded_linear_insert(_Iter __last, _Comp __comp)
+ {
+ iter_value_t<_Iter> __val = ranges::iter_move(__last);
+ _Iter __next = __last;
+ --__next;
+ while (__comp(__val, *__next))
+ {
+ *__last = ranges::iter_move(__next);
+ __last = __next;
+ --__next;
+ }
+ *__last = std::move(__val);
+ }
+
+ template<typename _Iter, typename _Comp>
+ constexpr void
+ __insertion_sort(_Iter __first, _Iter __last, _Comp __comp)
+ {
+ if (__first == __last)
+ return;
+
+ for (_Iter __i = __first + 1; __i != __last; ++__i)
+ {
+ if (__comp(*__i, *__first))
+ {
+ iter_value_t<_Iter> __val = ranges::iter_move(__i);
+ ranges::move_backward(__first, __i, __i + 1);
+ *__first = std::move(__val);
+ }
+ else
+ __detail::__unguarded_linear_insert(__i, __comp);
+ }
+ }
+
+ template<typename _Iter, typename _Comp>
+ constexpr void
+ __unguarded_insertion_sort(_Iter __first, _Iter __last, _Comp __comp)
+ {
+ for (_Iter __i = __first; __i != __last; ++__i)
+ __detail::__unguarded_linear_insert(__i, __comp);
+ }
+
+ inline constexpr int __sort_threshold = 16;
+
+ template<typename _Iter, typename _Comp>
+ constexpr void
+ __final_insertion_sort(_Iter __first, _Iter __last, _Comp __comp)
+ {
+ if (__last - __first > __sort_threshold)
+ {
+ __detail::__insertion_sort(__first, __first + __sort_threshold,
__comp);
+ __detail::__unguarded_insertion_sort(__first + __sort_threshold,
__last,
+ __comp);
+ }
+ else
+ __detail::__insertion_sort(__first, __last, __comp);
+ }
+
+ template<typename _Iter, typename _Comp>
+ constexpr _Iter
+ __unguarded_partition(_Iter __first, _Iter __last, _Iter __pivot, _Comp
__comp)
+ {
+ while (true)
+ {
+ while (__comp(*__first, *__pivot))
+ ++__first;
+ --__last;
+ while (__comp(*__pivot, *__last))
+ --__last;
+ if (!(__first < __last))
+ return __first;
+ ranges::iter_swap(__first, __last);
+ ++__first;
+ }
+ }
+
+ template<typename _Iter, typename _Comp>
+ constexpr _Iter
+ __unguarded_partition_pivot(_Iter __first, _Iter __last, _Comp __comp)
+ {
+ _Iter __mid = __first + (__last - __first) / 2;
+ __detail::__move_median_to_first(__first, __first + 1, __mid, __last -
1, __comp);
+ return __detail::__unguarded_partition(__first + 1, __last, __first,
__comp);
+ }
+
+ template<typename _Iter, typename _Comp>
+ constexpr void
+ __heap_select(_Iter __first, _Iter __middle, _Iter __last, _Comp __comp)
+ {
+ ranges::make_heap(__first, __middle, __comp);
+ for (_Iter __i = __middle; __i < __last; ++__i)
+ if (__comp(*__i, *__first))
+ __detail::__pop_heap(__first, __middle, __i, __comp);
+ }
+
+ template<typename _Iter, typename _Comp>
+ constexpr void
+ __partial_sort(_Iter __first, _Iter __middle, _Iter __last, _Comp __comp)
+ {
+ __detail::__heap_select(__first, __middle, __last, __comp);
+ ranges::sort_heap(__first, __middle, __comp);
+ }
+
+ template<typename _Iter, typename _Comp>
+ constexpr void
+ __introsort_loop(_Iter __first, _Iter __last, unsigned __depth_limit,
_Comp __comp)
+ {
+ while (__last - __first > __sort_threshold)
+ {
+ if (__depth_limit == 0)
+ {
+ __detail::__partial_sort(__first, __last, __last, __comp);
+ return;
+ }
+ --__depth_limit;
+ _Iter __cut = __detail::__unguarded_partition_pivot(__first,
__last, __comp);
+ __detail::__introsort_loop(__cut, __last, __depth_limit, __comp);
+ __last = __cut;
+ }
+ }
+ } // namespace __detail
+
struct __sort_fn
{
template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
@@ -2209,10 +2358,21 @@ namespace ranges
operator()(_Iter __first, _Sent __last,
_Comp __comp = {}, _Proj __proj = {}) const
{
- auto __lasti = ranges::next(__first, __last);
- _GLIBCXX_STD_A::sort(std::move(__first), __lasti,
- __detail::__make_comp_proj(__comp, __proj));
- return __lasti;
+ if constexpr (!same_as<_Iter, _Sent>)
+ return (*this)(__first, ranges::next(__first, __last),
+ std::move(__comp), std::move(__proj));
+ else
+ {
+ if (__first != __last)
+ {
+ auto __comp_proj = __detail::__make_comp_proj(__comp, __proj);
+ auto __n = __detail::__to_unsigned_like(__last - __first);
+ unsigned __depth_limit = (std::__bit_width(__n) - 1) * 2;
+ __detail::__introsort_loop(__first, __last, __depth_limit,
__comp_proj);
+ __detail::__final_insertion_sort(__first, __last, __comp_proj);
+ }
+ return __last;
+ }
}
template<random_access_range _Range,
diff --git a/libstdc++-v3/testsuite/25_algorithms/sort/118209.cc
b/libstdc++-v3/testsuite/25_algorithms/sort/118209.cc
new file mode 100644
index 000000000000..6dedbde75173
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/sort/118209.cc
@@ -0,0 +1,23 @@
+// PR libstdc++ - ranges::sort doesn't use iter_move, cannot sort zip of
move-only type
+// { dg-do compile { target c++23 } }
+
+#include <algorithm>
+#include <ranges>
+#include <vector>
+
+struct F {
+ int a = -1;
+ explicit F(int d) : a(d) { }
+ F(const F&) = delete;
+ F(F&& o) : a(o.a) { }
+ void operator=(const F&) = delete;
+ F& operator=(F&& o) { return *this; }
+ auto operator<=>(const F&) const = default;
+};
+
+int main () {
+ int a[] = {3,2,1};
+ std::vector<F> v(a, a+3);
+ std::ranges::sort(v); // OK
+ std::ranges::sort(std::views::zip(v)); // didn't compile
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/sort/constrained.cc
b/libstdc++-v3/testsuite/25_algorithms/sort/constrained.cc
index 82754af96430..930dbd77a376 100644
--- a/libstdc++-v3/testsuite/25_algorithms/sort/constrained.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/sort/constrained.cc
@@ -20,6 +20,7 @@
#include <algorithm>
#include <random>
+#include <ranges>
#include <vector>
#include <testsuite_hooks.h>
#include <testsuite_iterators.h>
@@ -72,9 +73,39 @@ test02()
&& ranges::equal(x, y, {}, &X::i, &X::i));
}
+constexpr bool
+test03()
+{
+ // PR libstdc++/100795 - ranges::sort should not use std::sort directly
+#if __SIZEOF_INT128__
+ auto v = std::views::iota(__int128(0), __int128(20));
+#else
+ auto v = std::views::iota(0ll, 20ll);
+#endif
+
+ int storage[20] = {2,5,4,3,1,6,7,9,10,8,11,14,12,13,15,16,18,0,19,17};
+ auto w = v | std::views::transform([&](auto i) -> int& { return storage[i];
});
+ using type = decltype(w);
+ using cat =
std::iterator_traits<std::ranges::iterator_t<type>>::iterator_category;
+ static_assert( std::same_as<cat, std::output_iterator_tag> );
+ static_assert( std::ranges::random_access_range<type> );
+
+ ranges::sort(w);
+ VERIFY( ranges::equal(w, v) );
+
+ ranges::sort(w, std::ranges::greater{});
+ VERIFY( ranges::equal(w, v | std::views::reverse) );
+
+ ranges::sort(w, std::ranges::greater{}, std::negate{});
+ VERIFY( ranges::equal(w, v) );
+
+ return true;
+}
+
int
main()
{
test01();
static_assert(test02());
+ static_assert(test03());
}
--
2.50.0.131.gcf6f63ea6b
