#882

Committed 31 Aug 2023 07:44PM UTC coverage: 41.798% (-44.7%) from 86.546%

Build # #882

Build Type

push

Committed by

Commit Message

Run Details

19442 of 46514 relevant lines covered (41.8%)

126375.38 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

48.78

/libs/core/algorithms/include/hpx/parallel/algorithms/sort.hpp

//  Copyright (c) 2015 John Biddiscombe
//  Copyright (c) 2015-2024 Hartmut Kaiser
//  Copyright (c) 2015-2019 Francisco Jose Tapia
//  Copyright (c) 2018 Taeguk Kwon
//  Copyright (c) 2021 Akhil J Nair
//
//  SPDX-License-Identifier: BSL-1.0
//  Distributed under the Boost Software License, Version 1.0. (See accompanying
//  file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)

/// \page hpx::sort
/// \headerfile hpx/algorithm.hpp

#pragma once

#if defined(DOXYGEN)

namespace hpx {
    // clang-format off

    ///////////////////////////////////////////////////////////////////////////
    /// Sorts the elements in the range [first, last) in ascending order. The
    /// order of equal elements is not guaranteed to be preserved. The function
    /// uses the given comparison function object comp (defaults to using
    /// operator<()).
    ///
    /// \note   Complexity: O(N log(N)), where N = std::distance(first, last)
    ///                     comparisons.
    ///
    /// A sequence is sorted with respect to a comparator \a comp and a
    /// projection \a proj if for every iterator i pointing to the sequence and
    /// every non-negative integer n such that i + n is a valid iterator
    /// pointing to an element of the sequence, and
    /// INVOKE(comp, INVOKE(proj, *(i + n)), INVOKE(proj, *i)) == false.
    ///
    /// \tparam RandomIt    The type of the source iterators used (deduced).
    ///                     This iterator type must meet the requirements of a
    ///                     random access iterator.
    /// \tparam Comp        The type of the function/function object to use
    ///                     (deduced).
    /// \tparam Proj        The type of an optional projection function. This
    ///                     defaults to
    ///                     \a hpx::identity.
    ///
    /// \param first        Refers to the beginning of the sequence of elements
    ///                     the algorithm will be applied to.
    /// \param last         Refers to the end of the sequence of elements the
    ///                     algorithm will be applied to.
    /// \param comp         comp is a callable object. The return value of the
    ///                     INVOKE operation applied to an object of type \a Comp,
    ///                     when contextually converted to bool, yields true if
    ///                     the first argument of the call is less than the
    ///                     second, and false otherwise. It is assumed that comp
    ///                     will not apply any non-constant function through the
    ///                     dereferenced iterator.
    /// \param proj         Specifies the function (or function object) which
    ///                     will be invoked for each pair of elements as a
    ///                     projection operation before the actual predicate
    ///                     \a comp is invoked.
    ///
    /// \a comp has to induce a strict weak ordering on the values.
    ///
    /// The assignments in the parallel \a sort algorithm invoked without
    /// an execution policy object execute in sequential order in the
    /// calling thread.
    ///
    /// \returns  The \a sort algorithm returns \a void.
    ///
    template <typename RandomIt,
        typename Comp = hpx::parallel::detail::less,
        typename Proj = hpx::identity>
    void sort(RandomIt first, RandomIt last, Comp&& comp, Proj&& proj = Proj());

    ///////////////////////////////////////////////////////////////////////////
    /// Sorts the elements in the range [first, last) in ascending order. The
    /// order of equal elements is not guaranteed to be preserved. The function
    /// uses the given comparison function object comp (defaults to using
    /// operator<()). Executed according to the policy.
    ///
    /// \note   Complexity: O(N log(N)), where N = std::distance(first, last)
    ///                     comparisons.
    ///
    /// A sequence is sorted with respect to a comparator \a comp and a
    /// projection \a proj if for every iterator i pointing to the sequence and
    /// every non-negative integer n such that i + n is a valid iterator
    /// pointing to an element of the sequence, and
    /// INVOKE(comp, INVOKE(proj, *(i + n)), INVOKE(proj, *i)) == false.
    ///
    /// \tparam ExPolicy    The type of the execution policy to use (deduced).
    ///                     It describes the manner in which the execution
    ///                     of the algorithm may be parallelized and the manner
    ///                     in which it applies user-provided function objects.
    /// \tparam RandomIt    The type of the source iterators used (deduced).
    ///                     This iterator type must meet the requirements of a
    ///                     random access iterator.
    /// \tparam Comp        The type of the function/function object to use
    ///                     (deduced).
    /// \tparam Proj        The type of an optional projection function. This
    ///                     defaults to
    ///                     \a hpx::identity.
    ///
    /// \param policy       The execution policy to use for the scheduling of
    ///                     the iterations.
    /// \param first        Refers to the beginning of the sequence of elements
    ///                     the algorithm will be applied to.
    /// \param last         Refers to the end of the sequence of elements the
    ///                     algorithm will be applied to.
    /// \param comp         comp is a callable object. The return value of the
    ///                     INVOKE operation applied to an object of type \a Comp,
    ///                     when contextually converted to bool, yields true if
    ///                     the first argument of the call is less than the
    ///                     second, and false otherwise. It is assumed that comp
    ///                     will not apply any non-constant function through the
    ///                     dereferenced iterator.
    /// \param proj         Specifies the function (or function object) which
    ///                     will be invoked for each pair of elements as a
    ///                     projection operation before the actual predicate
    ///                     \a comp is invoked.
    ///
    /// \a comp has to induce a strict weak ordering on the values.
    ///
    /// The application of function objects in parallel algorithm
    /// invoked with an execution policy object of type
    /// \a sequenced_policy execute in sequential order in the
    /// calling thread.
    ///
    /// The application of function objects in parallel algorithm
    /// invoked with an execution policy object of type
    /// \a parallel_policy or \a parallel_task_policy are
    /// permitted to execute in an unordered fashion in unspecified
    /// threads, and indeterminately sequenced within each thread.
    ///
    /// \returns  The \a sort algorithm returns a
    ///           \a hpx::future<void> if the execution policy is of
    ///           type
    ///           \a sequenced_task_policy or
    ///           \a parallel_task_policy and returns \a void
    ///           otherwise.
    ///
    template <typename ExPolicy, typename RandomIt,
        typename Comp = hpx::parallel::detail::less,
        typename Proj = hpx::identity>
    hpx::parallel::util::detail::algorithm_result_t<ExPolicy>
    sort(ExPolicy&& policy, RandomIt first, RandomIt last, Comp&& comp,
        Proj&& proj);

    // clang-format on
}    // namespace hpx

#else    // DOXYGEN

#include <hpx/config.hpp>
#include <hpx/algorithms/traits/projected.hpp>
#include <hpx/assert.hpp>
#include <hpx/modules/async_local.hpp>
#include <hpx/modules/concepts.hpp>
#include <hpx/modules/execution.hpp>
#include <hpx/modules/executors.hpp>
#include <hpx/modules/iterator_support.hpp>
#include <hpx/modules/type_support.hpp>
#include <hpx/parallel/algorithms/detail/advance_to_sentinel.hpp>
#include <hpx/parallel/algorithms/detail/dispatch.hpp>
#include <hpx/parallel/algorithms/detail/is_sorted.hpp>
#include <hpx/parallel/algorithms/detail/pivot.hpp>
#include <hpx/parallel/util/compare_projected.hpp>
#include <hpx/parallel/util/detail/algorithm_result.hpp>
#include <hpx/parallel/util/detail/chunk_size.hpp>
#include <hpx/parallel/util/detail/sender_util.hpp>

#include <algorithm>
#include <cstddef>
#include <exception>
#include <iterator>
#include <list>
#include <type_traits>
#include <utility>

namespace hpx::parallel {

    ///////////////////////////////////////////////////////////////////////////
    // sort
    namespace detail {

        /// \cond NOINTERNAL
        HPX_CXX_EXPORT inline constexpr std::size_t sort_limit_per_task =
            65536ul;

        // \brief this function is the work assigned to each thread in the
        //        parallel process
        HPX_CXX_EXPORT template <typename ExPolicy, typename RandomIt,
            typename Comp>
        hpx::future<RandomIt> sort_thread(ExPolicy&& policy, RandomIt first,
            RandomIt last, Comp comp, std::size_t chunk_size)
        {
            std::ptrdiff_t const N = last - first;
            if (static_cast<std::size_t>(N) <= chunk_size)
            {
                return execution::async_execute(policy.executor(),
                    [first, last, comp = HPX_MOVE(comp)]() -> RandomIt {
                        std::sort(first, last, comp);
                        return last;
                    });
            }

            // check if sorted
            if (detail::is_sorted_sequential(first, last, comp))
            {
                return hpx::make_ready_future(last);
            }

            // pivot selections
            pivot9(first, last, comp);

            using reference =
                typename std::iterator_traits<RandomIt>::reference;

            reference val = *first;
            RandomIt c_first = first + 1, c_last = last - 1;

            while (comp(*c_first, val))
            {
                ++c_first;
            }
            while (comp(val, *c_last))
            {
                --c_last;
            }
            while (c_first < c_last)
            {
#if defined(HPX_HAVE_CXX20_STD_RANGES_ITER_SWAP)
                std::ranges::iter_swap(c_first++, c_last--);
#else
                std::iter_swap(c_first++, c_last--);
#endif
                while (comp(*c_first, val))
                {
                    ++c_first;
                }
                while (comp(val, *c_last))
                {
                    --c_last;
                }
            }

#if defined(HPX_HAVE_CXX20_STD_RANGES_ITER_SWAP)
            std::ranges::iter_swap(first, c_last);
#else
            std::iter_swap(first, c_last);
#endif

            // spawn tasks for each sub section
            hpx::future<RandomIt> left = execution::async_execute(
                policy.executor(), &sort_thread<ExPolicy, RandomIt, Comp>,
                policy, first, c_last, comp, chunk_size);

            hpx::future<RandomIt> right = execution::async_execute(
                policy.executor(), &sort_thread<ExPolicy, RandomIt, Comp>,
                policy, c_first, last, comp, chunk_size);

            return hpx::dataflow(
                [last](hpx::future<RandomIt>&& leftf,
                    hpx::future<RandomIt>&& rightf) -> RandomIt {
                    if (leftf.has_exception() || rightf.has_exception())
                    {
                        std::list<std::exception_ptr> errors;
                        if (leftf.has_exception())
                            errors.push_back(leftf.get_exception_ptr());
                        if (rightf.has_exception())
                            errors.push_back(rightf.get_exception_ptr());

                        throw exception_list(HPX_MOVE(errors));
                    }
                    return last;
                },
                HPX_MOVE(left), HPX_MOVE(right));
        }

        // policy : execution policy
        // [in] first   iterator to the first element to sort
        // [in] last    iterator to the next element after the last
        // [in] comp    object for to Comp
        HPX_CXX_EXPORT template <typename ExPolicy, typename RandomIt,
            typename Comp>
        hpx::future<RandomIt> parallel_sort_async(
            ExPolicy&& policy, RandomIt first, RandomIt last, Comp&& comp)
        {
            // number of elements to sort
            std::size_t count = last - first;
            if (count == 0)
            {
                return hpx::make_ready_future(last);
            }

            // figure out the chunk size to use
            std::size_t const cores =
                hpx::execution::experimental::processing_units_count(
                    policy.parameters(), policy.executor(),
                    hpx::chrono::null_duration, count);

            std::size_t max_chunks =
                hpx::execution::experimental::maximal_number_of_chunks(
                    policy.parameters(), policy.executor(), cores, count);

            std::size_t chunk_size =
                hpx::execution::experimental::get_chunk_size(
                    policy.parameters(), policy.executor(),
                    hpx::chrono::null_duration, cores, count);

            util::detail::adjust_chunk_size_and_max_chunks(
                cores, count, max_chunks, chunk_size);

            // we should not get smaller than our sort_limit_per_task
            chunk_size = (std::max) (chunk_size, sort_limit_per_task);

            if (count < chunk_size)
            {
                std::sort(first, last, comp);
                return hpx::make_ready_future(last);
            }

            // check if already sorted
            if (detail::is_sorted_sequential(first, last, comp))
            {
                return hpx::make_ready_future(last);
            }

            return execution::async_execute(policy.executor(),
                &sort_thread<std::decay_t<ExPolicy>, RandomIt, Comp>,
                HPX_FORWARD(ExPolicy, policy), first, last,
                HPX_FORWARD(Comp, comp), chunk_size);
        }

        ///////////////////////////////////////////////////////////////////////
        // sort
        HPX_CXX_EXPORT template <typename RandomIt>
        struct sort : public algorithm<sort<RandomIt>, RandomIt>
        {
            constexpr sort() noexcept
              : algorithm<sort, RandomIt>("sort")
            {
            }

            template <typename ExPolicy, typename Sent, typename Comp,
                typename Proj>
            static constexpr RandomIt sequential(
                ExPolicy, RandomIt first, Sent last, Comp&& comp, Proj&& proj)
            {
                auto last_iter = detail::advance_to_sentinel(first, last);
                std::sort(first, last_iter,
                    util::compare_projected<Comp&, Proj&>(comp, proj));
                return last_iter;
            }

            template <typename ExPolicy, typename Sent, typename Comp,
                typename Proj>
            static util::detail::algorithm_result_t<ExPolicy, RandomIt>
            parallel(ExPolicy&& policy, RandomIt first, Sent last_s,
                Comp&& comp, Proj&& proj)
            {
                auto last = detail::advance_to_sentinel(first, last_s);
                typedef util::detail::algorithm_result<ExPolicy, RandomIt>
                    algorithm_result;

                try
                {
                    // call the sort routine and return the right type,
                    // depending on execution policy
                    return algorithm_result::get(parallel_sort_async(
                        HPX_FORWARD(ExPolicy, policy), first, last,
                        util::compare_projected<Comp&, Proj&>(comp, proj)));
                }
                catch (...)
                {
                    return algorithm_result::get(
                        detail::handle_exception<ExPolicy, RandomIt>::call(
                            std::current_exception()));
                }
            }
        };
        /// \endcond
    }    // namespace detail
}    // namespace hpx::parallel

namespace hpx {

    ///////////////////////////////////////////////////////////////////////////
    // CPO for hpx::sort
    HPX_CXX_EXPORT inline constexpr struct sort_t final
      : hpx::detail::tag_parallel_algorithm<sort_t>
    {
        template <typename RandomIt,
            typename Comp = hpx::parallel::detail::less>
        // clang-format off
            requires (
                hpx::traits::is_iterator_v<RandomIt> &&
                hpx::is_invocable_v<Comp,
                    hpx::traits::iter_value_t<RandomIt>,
                    hpx::traits::iter_value_t<RandomIt>
                >
            )
        // clang-format on
        friend void tag_fallback_invoke(
            hpx::sort_t, RandomIt first, RandomIt last, Comp comp = Comp())
        {
            static_assert(hpx::traits::is_random_access_iterator_v<RandomIt>,
                "Requires a random access iterator.");

            hpx::parallel::detail::sort<RandomIt>().call(hpx::execution::seq,
                first, last, HPX_MOVE(comp), hpx::identity_v);
        }

        template <typename ExPolicy, typename RandomIt,
            typename Comp = hpx::parallel::detail::less>
        // clang-format off
            requires (
                hpx::is_execution_policy_v<ExPolicy> &&
                hpx::traits::is_iterator_v<RandomIt> &&
                hpx::is_invocable_v<Comp,
                    hpx::traits::iter_value_t<RandomIt>,
                    hpx::traits::iter_value_t<RandomIt>
                >
            )
        // clang-format on
        friend parallel::util::detail::algorithm_result_t<ExPolicy>
        tag_fallback_invoke(hpx::sort_t, ExPolicy&& policy, RandomIt first,
            RandomIt last, Comp comp = Comp())
        {
            static_assert(hpx::traits::is_random_access_iterator_v<RandomIt>,
                "Requires a random access iterator.");

            using result_type =
                typename hpx::parallel::util::detail::algorithm_result<
                    ExPolicy>::type;

            return hpx::util::void_guard<result_type>(),
                   hpx::parallel::detail::sort<RandomIt>().call(
                       HPX_FORWARD(ExPolicy, policy), first, last,
                       HPX_MOVE(comp), hpx::identity_v);
        }
    } sort{};
}    // namespace hpx

#endif    // DOXYGEN

1	// Copyright (c) 2015 John Biddiscombe
2	// Copyright (c) 2015-2024 Hartmut Kaiser
3	// Copyright (c) 2015-2019 Francisco Jose Tapia
4	// Copyright (c) 2018 Taeguk Kwon
5	// Copyright (c) 2021 Akhil J Nair
6	//
7	// SPDX-License-Identifier: BSL-1.0
8	// Distributed under the Boost Software License, Version 1.0. (See accompanying
9	// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
10
11	/// \page hpx::sort
12	/// \headerfile hpx/algorithm.hpp
13
14	#pragma once
15
16	#if defined(DOXYGEN)
17
18	namespace hpx {
19	// clang-format off
20
21	///////////////////////////////////////////////////////////////////////////
22	/// Sorts the elements in the range [first, last) in ascending order. The
23	/// order of equal elements is not guaranteed to be preserved. The function
24	/// uses the given comparison function object comp (defaults to using
25	/// operator<()).
26	///
27	/// \note Complexity: O(N log(N)), where N = std::distance(first, last)
28	/// comparisons.
29	///
30	/// A sequence is sorted with respect to a comparator \a comp and a
31	/// projection \a proj if for every iterator i pointing to the sequence and
32	/// every non-negative integer n such that i + n is a valid iterator
33	/// pointing to an element of the sequence, and
34	/// INVOKE(comp, INVOKE(proj, (i + n)), INVOKE(proj, i)) == false.
35	///
36	/// \tparam RandomIt The type of the source iterators used (deduced).
37	/// This iterator type must meet the requirements of a
38	/// random access iterator.
39	/// \tparam Comp The type of the function/function object to use
40	/// (deduced).
41	/// \tparam Proj The type of an optional projection function. This
42	/// defaults to
43	/// \a hpx::identity.
44	///
45	/// \param first Refers to the beginning of the sequence of elements
46	/// the algorithm will be applied to.
47	/// \param last Refers to the end of the sequence of elements the
48	/// algorithm will be applied to.
49	/// \param comp comp is a callable object. The return value of the
50	/// INVOKE operation applied to an object of type \a Comp,
51	/// when contextually converted to bool, yields true if
52	/// the first argument of the call is less than the
53	/// second, and false otherwise. It is assumed that comp
54	/// will not apply any non-constant function through the
55	/// dereferenced iterator.
56	/// \param proj Specifies the function (or function object) which
57	/// will be invoked for each pair of elements as a
58	/// projection operation before the actual predicate
59	/// \a comp is invoked.
60	///
61	/// \a comp has to induce a strict weak ordering on the values.
62	///
63	/// The assignments in the parallel \a sort algorithm invoked without
64	/// an execution policy object execute in sequential order in the
65	/// calling thread.
66	///
67	/// \returns The \a sort algorithm returns \a void.
68	///
69	template <typename RandomIt,
70	typename Comp = hpx::parallel::detail::less,
71	typename Proj = hpx::identity>
72	void sort(RandomIt first, RandomIt last, Comp&& comp, Proj&& proj = Proj());
73
74	///////////////////////////////////////////////////////////////////////////
75	/// Sorts the elements in the range [first, last) in ascending order. The
76	/// order of equal elements is not guaranteed to be preserved. The function
77	/// uses the given comparison function object comp (defaults to using
78	/// operator<()). Executed according to the policy.
79	///
80	/// \note Complexity: O(N log(N)), where N = std::distance(first, last)
81	/// comparisons.
82	///
83	/// A sequence is sorted with respect to a comparator \a comp and a
84	/// projection \a proj if for every iterator i pointing to the sequence and
85	/// every non-negative integer n such that i + n is a valid iterator
86	/// pointing to an element of the sequence, and
87	/// INVOKE(comp, INVOKE(proj, (i + n)), INVOKE(proj, i)) == false.
88	///
89	/// \tparam ExPolicy The type of the execution policy to use (deduced).
90	/// It describes the manner in which the execution
91	/// of the algorithm may be parallelized and the manner
92	/// in which it applies user-provided function objects.
93	/// \tparam RandomIt The type of the source iterators used (deduced).
94	/// This iterator type must meet the requirements of a
95	/// random access iterator.
96	/// \tparam Comp The type of the function/function object to use
97	/// (deduced).
98	/// \tparam Proj The type of an optional projection function. This
99	/// defaults to
100	/// \a hpx::identity.
101	///
102	/// \param policy The execution policy to use for the scheduling of
103	/// the iterations.
104	/// \param first Refers to the beginning of the sequence of elements
105	/// the algorithm will be applied to.
106	/// \param last Refers to the end of the sequence of elements the
107	/// algorithm will be applied to.
108	/// \param comp comp is a callable object. The return value of the
109	/// INVOKE operation applied to an object of type \a Comp,
110	/// when contextually converted to bool, yields true if
111	/// the first argument of the call is less than the
112	/// second, and false otherwise. It is assumed that comp
113	/// will not apply any non-constant function through the
114	/// dereferenced iterator.
115	/// \param proj Specifies the function (or function object) which
116	/// will be invoked for each pair of elements as a
117	/// projection operation before the actual predicate
118	/// \a comp is invoked.
119	///
120	/// \a comp has to induce a strict weak ordering on the values.
121	///
122	/// The application of function objects in parallel algorithm
123	/// invoked with an execution policy object of type
124	/// \a sequenced_policy execute in sequential order in the
125	/// calling thread.
126	///
127	/// The application of function objects in parallel algorithm
128	/// invoked with an execution policy object of type
129	/// \a parallel_policy or \a parallel_task_policy are
130	/// permitted to execute in an unordered fashion in unspecified
131	/// threads, and indeterminately sequenced within each thread.
132	///
133	/// \returns The \a sort algorithm returns a
134	/// \a hpx::future<void> if the execution policy is of
135	/// type
136	/// \a sequenced_task_policy or
137	/// \a parallel_task_policy and returns \a void
138	/// otherwise.
139	///
140	template <typename ExPolicy, typename RandomIt,
141	typename Comp = hpx::parallel::detail::less,
142	typename Proj = hpx::identity>
143	hpx::parallel::util::detail::algorithm_result_t<ExPolicy>
144	sort(ExPolicy&& policy, RandomIt first, RandomIt last, Comp&& comp,
145	Proj&& proj);
146
147	// clang-format on
148	} // namespace hpx
149
150	#else // DOXYGEN
151
152	#include <hpx/config.hpp>
153	#include <hpx/algorithms/traits/projected.hpp>
154	#include <hpx/assert.hpp>
155	#include <hpx/modules/async_local.hpp>
156	#include <hpx/modules/concepts.hpp>
157	#include <hpx/modules/execution.hpp>
158	#include <hpx/modules/executors.hpp>
159	#include <hpx/modules/iterator_support.hpp>
160	#include <hpx/modules/type_support.hpp>
161	#include <hpx/parallel/algorithms/detail/advance_to_sentinel.hpp>
162	#include <hpx/parallel/algorithms/detail/dispatch.hpp>
163	#include <hpx/parallel/algorithms/detail/is_sorted.hpp>
164	#include <hpx/parallel/algorithms/detail/pivot.hpp>
165	#include <hpx/parallel/util/compare_projected.hpp>
166	#include <hpx/parallel/util/detail/algorithm_result.hpp>
167	#include <hpx/parallel/util/detail/chunk_size.hpp>
168	#include <hpx/parallel/util/detail/sender_util.hpp>
169
170	#include <algorithm>
171	#include <cstddef>
172	#include <exception>
173	#include <iterator>
174	#include <list>
175	#include <type_traits>
176	#include <utility>
177
178	namespace hpx::parallel {
179
180	///////////////////////////////////////////////////////////////////////////
181	// sort
182	namespace detail {
183
184	/// \cond NOINTERNAL
185	HPX_CXX_EXPORT inline constexpr std::size_t sort_limit_per_task =
186	65536ul;
187
188	// \brief this function is the work assigned to each thread in the
189	// parallel process
190	HPX_CXX_EXPORT template <typename ExPolicy, typename RandomIt,	1✔
191	typename Comp>
192	hpx::future<RandomIt> sort_thread(ExPolicy&& policy, RandomIt first,
193	RandomIt last, Comp comp, std::size_t chunk_size)
194	{	1✔
195	std::ptrdiff_t const N = last - first;
196	if (static_cast<std::size_t>(N) <= chunk_size)
197	{	2✔
198	return execution::async_execute(policy.executor(),	1✔
199	[first, last, comp = HPX_MOVE(comp)]() -> RandomIt {	1✔
200	std::sort(first, last, comp);
201	return last;
202	});
203	}
204		×
205	// check if sorted
206	if (detail::is_sorted_sequential(first, last, comp))
207	{
208	return hpx::make_ready_future(last);
209	}
210		×
211	// pivot selections
212	pivot9(first, last, comp);
213
214	using reference =
215	typename std::iterator_traits<RandomIt>::reference;	×
216		×
217	reference val = *first;
218	RandomIt c_first = first + 1, c_last = last - 1;	×
219
220	while (comp(*c_first, val))
221	{
222	++c_first;	×
223	}
224	while (comp(val, *c_last))
225	{
226	--c_last;	×
227	}
228	while (c_first < c_last)
229	{	×
230	#if defined(HPX_HAVE_CXX20_STD_RANGES_ITER_SWAP)
231	std::ranges::iter_swap(c_first++, c_last--);
232	#else
233	std::iter_swap(c_first++, c_last--);	×
234	#endif
235	while (comp(*c_first, val))
236	{
237	++c_first;	×
238	}
239	while (comp(val, *c_last))
240	{
241	--c_last;
242	}
243	}
244		×
245	#if defined(HPX_HAVE_CXX20_STD_RANGES_ITER_SWAP)
246	std::ranges::iter_swap(first, c_last);
247	#else
248	std::iter_swap(first, c_last);
249	#endif
250		×
251	// spawn tasks for each sub section
252	hpx::future<RandomIt> left = execution::async_execute(
253	policy.executor(), &sort_thread<ExPolicy, RandomIt, Comp>,
254	policy, first, c_last, comp, chunk_size);	×
255
256	hpx::future<RandomIt> right = execution::async_execute(
257	policy.executor(), &sort_thread<ExPolicy, RandomIt, Comp>,
258	policy, c_first, last, comp, chunk_size);
259		×
260	return hpx::dataflow(
261	[last](hpx::future<RandomIt>&& leftf,
262	hpx::future<RandomIt>&& rightf) -> RandomIt {
263	if (leftf.has_exception() \|\| rightf.has_exception())
264	{
265	std::list<std::exception_ptr> errors;	×
266	if (leftf.has_exception())
267	errors.push_back(leftf.get_exception_ptr());	×
268	if (rightf.has_exception())
269	errors.push_back(rightf.get_exception_ptr());	×
270
271	throw exception_list(HPX_MOVE(errors));	×
272	}
273	return last;
274	},
275	HPX_MOVE(left), HPX_MOVE(right));
276	}
277
278	// policy : execution policy
279	// [in] first iterator to the first element to sort
280	// [in] last iterator to the next element after the last
281	// [in] comp object for to Comp	2✔
282	HPX_CXX_EXPORT template <typename ExPolicy, typename RandomIt,
283	typename Comp>
284	hpx::future<RandomIt> parallel_sort_async(
285	ExPolicy&& policy, RandomIt first, RandomIt last, Comp&& comp)	2✔
286	{
287	// number of elements to sort
288	std::size_t count = last - first;
289	if (count == 0)
290	{
291	return hpx::make_ready_future(last);
292	}	2✔
293
294	// figure out the chunk size to use
295	std::size_t const cores =	2✔
296	hpx::execution::experimental::processing_units_count(
297	policy.parameters(), policy.executor(),
298	hpx::chrono::null_duration, count);
299		2✔
300	std::size_t max_chunks =
301	hpx::execution::experimental::maximal_number_of_chunks(
302	policy.parameters(), policy.executor(), cores, count);
303		2✔
304	std::size_t chunk_size =
305	hpx::execution::experimental::get_chunk_size(
306	policy.parameters(), policy.executor(),
307	hpx::chrono::null_duration, cores, count);
308		2✔
309	util::detail::adjust_chunk_size_and_max_chunks(
310	cores, count, max_chunks, chunk_size);	1✔
311
312	// we should not get smaller than our sort_limit_per_task
313	chunk_size = (std::max) (chunk_size, sort_limit_per_task);
314
315	if (count < chunk_size)	1✔
316	{
317	std::sort(first, last, comp);
318	return hpx::make_ready_future(last);
319	}
320
321	// check if already sorted
322	if (detail::is_sorted_sequential(first, last, comp))
323	{	2✔
324	return hpx::make_ready_future(last);
325	}
326
327	return execution::async_execute(policy.executor(),
328	&sort_thread<std::decay_t<ExPolicy>, RandomIt, Comp>,
329	HPX_FORWARD(ExPolicy, policy), first, last,
330	HPX_FORWARD(Comp, comp), chunk_size);
331	}
332
333	///////////////////////////////////////////////////////////////////////
334	// sort
335	HPX_CXX_EXPORT template <typename RandomIt>
336	struct sort : public algorithm<sort<RandomIt>, RandomIt>
337	{
338	constexpr sort() noexcept
339	: algorithm<sort, RandomIt>("sort")
340	{
341	}
342
343	template <typename ExPolicy, typename Sent, typename Comp,
344	typename Proj>
345	static constexpr RandomIt sequential(
346	ExPolicy, RandomIt first, Sent last, Comp&& comp, Proj&& proj)
347	{
348	auto last_iter = detail::advance_to_sentinel(first, last);
349	std::sort(first, last_iter,
350	util::compare_projected<Comp&, Proj&>(comp, proj));	2✔
351	return last_iter;
352	}
353
354	template <typename ExPolicy, typename Sent, typename Comp,
355	typename Proj>
356	static util::detail::algorithm_result_t<ExPolicy, RandomIt>
357	parallel(ExPolicy&& policy, RandomIt first, Sent last_s,
358	Comp&& comp, Proj&& proj)
359	{
360	auto last = detail::advance_to_sentinel(first, last_s);
361	typedef util::detail::algorithm_result<ExPolicy, RandomIt>	1✔
362	algorithm_result;
363		3✔
364	try
365	{	×
366	// call the sort routine and return the right type,
367	// depending on execution policy
368	return algorithm_result::get(parallel_sort_async(	×
369	HPX_FORWARD(ExPolicy, policy), first, last,	×
370	util::compare_projected<Comp&, Proj&>(comp, proj)));
371	}
372	catch (...)
373	{
374	return algorithm_result::get(
375	detail::handle_exception<ExPolicy, RandomIt>::call(
376	std::current_exception()));
377	}
378	}
379	};
380	/// \endcond
381	} // namespace detail
382	} // namespace hpx::parallel
383
384	namespace hpx {
385
386	///////////////////////////////////////////////////////////////////////////
387	// CPO for hpx::sort
388	HPX_CXX_EXPORT inline constexpr struct sort_t final
389	: hpx::detail::tag_parallel_algorithm<sort_t>
390	{
391	template <typename RandomIt,
392	typename Comp = hpx::parallel::detail::less>
393	// clang-format off
394	requires (
395	hpx::traits::is_iterator_v<RandomIt> &&
396	hpx::is_invocable_v<Comp,
397	hpx::traits::iter_value_t<RandomIt>,
398	hpx::traits::iter_value_t<RandomIt>
399	>
400	)
401	// clang-format on
402	friend void tag_fallback_invoke(
403	hpx::sort_t, RandomIt first, RandomIt last, Comp comp = Comp())
404	{
405	static_assert(hpx::traits::is_random_access_iterator_v<RandomIt>,
406	"Requires a random access iterator.");
407
408	hpx::parallel::detail::sort<RandomIt>().call(hpx::execution::seq,
409	first, last, HPX_MOVE(comp), hpx::identity_v);
410	}
411
412	template <typename ExPolicy, typename RandomIt,
413	typename Comp = hpx::parallel::detail::less>
414	// clang-format off
415	requires (
416	hpx::is_execution_policy_v<ExPolicy> &&
417	hpx::traits::is_iterator_v<RandomIt> &&
418	hpx::is_invocable_v<Comp,
419	hpx::traits::iter_value_t<RandomIt>,
420	hpx::traits::iter_value_t<RandomIt>
421	>
422	)
423	// clang-format on
424	friend parallel::util::detail::algorithm_result_t<ExPolicy>
425	tag_fallback_invoke(hpx::sort_t, ExPolicy&& policy, RandomIt first,
426	RandomIt last, Comp comp = Comp())
427	{
428	static_assert(hpx::traits::is_random_access_iterator_v<RandomIt>,
429	"Requires a random access iterator.");
430
431	using result_type =
432	typename hpx::parallel::util::detail::algorithm_result<
433	ExPolicy>::type;
434
435	return hpx::util::void_guard<result_type>(),
436	hpx::parallel::detail::sort<RandomIt>().call(
437	HPX_FORWARD(ExPolicy, policy), first, last,
438	HPX_MOVE(comp), hpx::identity_v);
439	}
440	} sort{};
441	} // namespace hpx
442
443	#endif // DOXYGEN

STEllAR-GROUP / hpx / #882

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous