#868

Committed 16 Jan 2023 08:21PM UTC coverage: 86.487%. Remained the same

Build # #868

Build Type

push

Committed by StellarBot

Commit Message

Merge #6137

6137: Adding example of a simple master/slave distributed application r=hkaiser a=hkaiser

The purpose of this example is to demonstrate how HPX actions can be used to build a simple master-slave application. The master (locality 0) assigns work to the slaves (all other localities). Note that if this application is run on one locality only it uses the same locality for the master and the slave functionalities.

The slaves receive a message that encodes how many sub-tasks of a certain type they should spawn locally.


Co-authored-by: Hartmut Kaiser <hartmut.kaiser@gmail.com>

Run Details

72 of 72 new or added lines in 1 file covered. (100.0%)

174663 of 201952 relevant lines covered (86.49%)

1849169.69 hits per line

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

91.92

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

//  Copyright (c) 2007-2022 Hartmut Kaiser
//
//  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)

/// \file parallel/algorithms/includes.hpp

#pragma once

#if defined(DOXYGEN)
namespace hpx {
    // clang-format off

    /// Returns true if every element from the sorted range [\a first2, \a last2) is
    /// found within the sorted range [\a first1, \a last1). Also returns true if
    /// [\a first2, \a last2) is empty. The version expects both ranges to be sorted
    /// with the user supplied binary predicate \a f. Executed according to the
    /// policy.
    ///
    /// \note   At most 2*(N1+N2-1) comparisons, where
    ///         N1 = std::distance(first1, last1) and
    ///         N2 = std::distance(first2, last2).
    ///
    /// \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 executes the assignments.
    /// \tparam FwdIter1    The type of the source iterators used for the
    ///                     first range (deduced).
    ///                     This iterator type must meet the requirements of an
    ///                     forward iterator.
    /// \tparam FwdIter2    The type of the source iterators used for the
    ///                     second range (deduced).
    ///                     This iterator type must meet the requirements of an
    ///                     forward iterator.
    /// \tparam Pred        The type of an optional function/function object to use.
    ///                     Unlike its sequential form, the parallel
    ///                     overload of \a includes requires \a Pred to meet the
    ///                     requirements of \a CopyConstructible. This defaults
    ///                     to std::less<>
    ///
    /// \param policy       The execution policy to use for the scheduling of
    ///                     the iterations.
    /// \param first1       Refers to the beginning of the sequence of elements
    ///                     of the first range the algorithm will be applied to.
    /// \param last1        Refers to the end of the sequence of elements of
    ///                     the first range the algorithm will be applied to.
    /// \param first2       Refers to the beginning of the sequence of elements
    ///                     of the second range the algorithm will be applied to.
    /// \param last2        Refers to the end of the sequence of elements of
    ///                     the second range the algorithm will be applied to.
    /// \param op           The binary predicate which returns true if the
    ///                     elements should be treated as includes. The signature
    ///                     of the predicate function should be equivalent to
    ///                     the following:
    ///                     \code
    ///                     bool pred(const Type1 &a, const Type2 &b);
    ///                     \endcode \n
    ///                     The signature does not need to have const &, but
    ///                     the function must not modify the objects passed to
    ///                     it. The types \a Type1 and \a Type2 must be such
    ///                     that objects of types \a FwdIter1 and \a FwdIter2 can
    ///                     be dereferenced and then implicitly converted to
    ///                     \a Type1 and \a Type2 respectively
    ///
    /// The comparison operations in the parallel \a includes algorithm invoked
    /// with an execution policy object of type \a sequenced_policy
    /// execute in sequential order in the calling thread.
    ///
    /// The comparison operations in the parallel \a includes 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 includes algorithm returns a \a hpx::future<bool> if the
    ///           execution policy is of type
    ///           \a sequenced_task_policy or
    ///           \a parallel_task_policy and
    ///           returns \a bool otherwise.
    ///           The \a includes algorithm returns true every element from the
    ///           sorted range [\a first2, \a last2) is found within the sorted range
    ///           [\a first1, \a last1).
    ///           Also returns true if [\a first2, \a last2) is empty.
    ///
    template <typename ExPolicy, typename FwdIter1, typename FwdIter2,
        typename Pred = hpx::parallel::v1::detail::less>
    typename hpx::parallel::util::detail::algorithm_result<ExPolicy, bool>::type>::type
    includes(ExPolicy&& policy, FwdIter1 first1, FwdIter1 last1,
            FwdIter2 first2, FwdIter2 last2, Pred&& op = Pred());

    /// Returns true if every element from the sorted range [\a first2, \a last2) is
    /// found within the sorted range [\a first1, \a last1). Also returns true if
    /// [\a first2, \a last2) is empty. The version expects both ranges to be sorted
    /// with the user supplied binary predicate \a f.
    ///
    /// \note   At most 2*(N1+N2-1) comparisons, where
    ///         N1 = std::distance(first1, last1) and
    ///         N2 = std::distance(first2, last2).
    ///
    /// \tparam FwdIter1    The type of the source iterators used for the
    ///                     first range (deduced).
    ///                     This iterator type must meet the requirements of an
    ///                     forward iterator.
    /// \tparam FwdIter2    The type of the source iterators used for the
    ///                     second range (deduced).
    ///                     This iterator type must meet the requirements of an
    ///                     forward iterator.
    /// \tparam Pred        The type of an optional function/function object to use.
    ///                     Unlike its sequential form, the parallel
    ///                     overload of \a includes requires \a Pred to meet the
    ///                     requirements of \a CopyConstructible. This defaults
    ///                     to std::less<>
    ///
    /// \param first1       Refers to the beginning of the sequence of elements
    ///                     of the first range the algorithm will be applied to.
    /// \param last1        Refers to the end of the sequence of elements of
    ///                     the first range the algorithm will be applied to.
    /// \param first2       Refers to the beginning of the sequence of elements
    ///                     of the second range the algorithm will be applied to.
    /// \param last2        Refers to the end of the sequence of elements of
    ///                     the second range the algorithm will be applied to.
    /// \param op           The binary predicate which returns true if the
    ///                     elements should be treated as includes. The signature
    ///                     of the predicate function should be equivalent to
    ///                     the following:
    ///                     \code
    ///                     bool pred(const Type1 &a, const Type2 &b);
    ///                     \endcode \n
    ///                     The signature does not need to have const &, but
    ///                     the function must not modify the objects passed to
    ///                     it. The types \a Type1 and \a Type2 must be such
    ///                     that objects of types \a FwdIter1 and \a FwdIter2 can
    ///                     be dereferenced and then implicitly converted to
    ///                     \a Type1 and \a Type2 respectively
    ///
    /// \returns  The \a includes algorithm returns a \a bool.
    ///           The \a includes algorithm returns true every element from the
    ///           sorted range [\a first2, \a last2) is found within the sorted range
    ///           [\a first1, \a last1).
    ///           Also returns true if [\a first2, \a last2) is empty.
    ///
    template <typename FwdIter1, typename FwdIter2,
        typename Pred = hpx::parallel::v1::detail::less>
    bool includes(FwdIter1 first1, FwdIter1 last1,
            FwdIter2 first2, FwdIter2 last2, Pred&& op = Pred());

    // clang-format on
}    // namespace hpx

#else    // DOXYGEN

#include <hpx/config.hpp>
#include <hpx/concepts/concepts.hpp>
#include <hpx/functional/invoke.hpp>
#include <hpx/iterator_support/traits/is_iterator.hpp>
#include <hpx/parallel/util/detail/sender_util.hpp>

#include <hpx/execution/algorithms/detail/predicates.hpp>
#include <hpx/executors/execution_policy.hpp>
#include <hpx/parallel/algorithms/detail/dispatch.hpp>
#include <hpx/parallel/algorithms/detail/upper_lower_bound.hpp>
#include <hpx/parallel/util/cancellation_token.hpp>
#include <hpx/parallel/util/detail/algorithm_result.hpp>
#include <hpx/parallel/util/partitioner.hpp>
#include <hpx/parallel/util/projection_identity.hpp>
#include <hpx/parallel/util/result_types.hpp>

#include <algorithm>
#include <cstddef>
#include <iterator>
#include <type_traits>
#include <utility>
#include <vector>

namespace hpx { namespace parallel { inline namespace v1 {
    ///////////////////////////////////////////////////////////////////////////
    // includes
    namespace detail {

        template <typename Iter1, typename Sent1, typename Iter2,
            typename Sent2, typename F, typename Proj1, typename Proj2,
            typename CancelToken>
        bool sequential_includes(Iter1 first1, Sent1 last1, Iter2 first2,
            Sent2 last2, F&& f, Proj1&& proj1, Proj2&& proj2, CancelToken& tok)
        {
            while (first2 != last2)
            {
                if (tok.was_cancelled())
                {
                    return false;
                }

                if (first1 == last1)
                {
                    return false;
                }

                auto&& value1 = HPX_INVOKE(proj1, *first1);
                auto&& value2 = HPX_INVOKE(proj2, *first2);

                if (HPX_INVOKE(f, value2, value1))
                {
                    return false;
                }

                if (!HPX_INVOKE(f, value1, value2))
                {
                    ++first2;
                }

                ++first1;
            }
            return true;
        }

        template <typename Iter1, typename Sent1, typename Iter2,
            typename Sent2, typename F, typename Proj1, typename Proj2>
        constexpr bool sequential_includes(Iter1 first1, Sent1 last1,
            Iter2 first2, Sent2 last2, F&& f, Proj1&& proj1, Proj2&& proj2)
        {
            while (first2 != last2)
            {
                if (first1 == last1)
                {
                    return false;
                }

                auto&& value1 = HPX_INVOKE(proj1, *first1);
                auto&& value2 = HPX_INVOKE(proj2, *first2);

                if (HPX_INVOKE(f, value2, value1))
                {
                    return false;
                }

                if (!HPX_INVOKE(f, value1, value2))
                {
                    ++first2;
                }

                ++first1;
            }
            return true;
        }

        ///////////////////////////////////////////////////////////////////////
        struct includes : public detail::algorithm<includes, bool>
        {
            includes()
              : includes::algorithm("includes")
            {
            }

            template <typename ExPolicy, typename Iter1, typename Sent1,
                typename Iter2, typename Sent2, typename F, typename Proj1,
                typename Proj2>
            static bool sequential(ExPolicy, Iter1 first1, Sent1 last1,
                Iter2 first2, Sent2 last2, F&& f, Proj1&& proj1, Proj2&& proj2)
            {
                return sequential_includes(first1, last1, first2, last2,
                    HPX_FORWARD(F, f), HPX_FORWARD(Proj1, proj1),
                    HPX_FORWARD(Proj2, proj2));
            }

            template <typename ExPolicy, typename Iter1, typename Sent1,
                typename Iter2, typename Sent2, typename F, typename Proj1,
                typename Proj2>
            static typename util::detail::algorithm_result<ExPolicy, bool>::type
            parallel(ExPolicy&& policy, Iter1 first1, Sent1 last1, Iter2 first2,
                Sent2 last2, F&& f, Proj1&& proj1, Proj2&& proj2)
            {
                if (first1 == last1)
                {
                    return util::detail::algorithm_result<ExPolicy, bool>::get(
                        false);
                }
                if (first2 == last2)
                {
                    return util::detail::algorithm_result<ExPolicy, bool>::get(
                        true);
                }

                util::cancellation_token<> tok;

                auto f1 =
                    [first1, last1, first2, last2, tok, f = HPX_FORWARD(F, f),
                        proj1 = HPX_FORWARD(Proj1, proj1),
                        proj2 = HPX_FORWARD(Proj2, proj2)](Iter2 part_begin,
                        std::size_t part_count) mutable -> bool {
                    Iter2 part_end = detail::next(part_begin, part_count);

                    auto value = HPX_INVOKE(proj2, *part_begin);
                    if (first2 != part_begin && part_count > 1)
                    {
                        part_begin = detail::upper_bound(
                            part_begin, part_end, value, f, proj2, tok);
                        if (tok.was_cancelled())
                        {
                            return false;
                        }
                        if (part_begin == part_end)
                        {
                            return true;
                        }
                        value = HPX_INVOKE(proj2, *part_begin);
                    }

                    Iter1 low = detail::lower_bound(
                        first1, last1, value, f, proj1, tok);
                    if (tok.was_cancelled())
                    {
                        return false;
                    }

                    if (low == last1 ||
                        HPX_INVOKE(f, value, HPX_INVOKE(proj1, *low)))
                    {
                        tok.cancel();
                        return false;
                    }

                    Iter1 high = last1;
                    if (part_end != last2)
                    {
                        auto&& value1 = HPX_INVOKE(proj2, *part_end);

                        high = detail::upper_bound(
                            low, last1, value1, f, proj1, tok);
                        part_end = detail::upper_bound(
                            part_end, last2, value1, f, proj2, tok);

                        if (tok.was_cancelled())
                        {
                            return false;
                        }
                    }

                    if (!sequential_includes(low, high, part_begin, part_end, f,
                            proj1, proj2, tok))
                    {
                        tok.cancel();
                    }
                    return !tok.was_cancelled();
                };

                auto f2 = [](auto&& results) {
                    return std::all_of(hpx::util::begin(results),
                        hpx::util::end(results),
                        [](hpx::future<bool>& val) { return val.get(); });
                };

                return util::partitioner<ExPolicy, bool>::call(
                    HPX_FORWARD(ExPolicy, policy), first2,
                    detail::distance(first2, last2), HPX_MOVE(f1),
                    HPX_MOVE(f2));
            }
        };
    }    // namespace detail
}}}      // namespace hpx::parallel::v1

namespace hpx {

    ///////////////////////////////////////////////////////////////////////////
    // CPO for hpx::includes
    inline constexpr struct includes_t final
      : hpx::detail::tag_parallel_algorithm<includes_t>
    {
    private:
        // clang-format off
        template <typename ExPolicy, typename FwdIter1, typename FwdIter2,
            typename Pred = hpx::parallel::v1::detail::less,
            HPX_CONCEPT_REQUIRES_(
                hpx::is_execution_policy<ExPolicy>::value &&
                hpx::traits::is_iterator<FwdIter1>::value &&
                hpx::traits::is_iterator<FwdIter2>::value &&
                hpx::is_invocable_v<Pred,
                    typename std::iterator_traits<FwdIter1>::value_type,
                    typename std::iterator_traits<FwdIter2>::value_type
                >
            )>
        // clang-format on
        friend typename hpx::parallel::util::detail::algorithm_result<ExPolicy,
            bool>::type
        tag_fallback_invoke(includes_t, ExPolicy&& policy, FwdIter1 first1,
            FwdIter1 last1, FwdIter2 first2, FwdIter2 last2, Pred&& op = Pred())
        {
            static_assert((hpx::traits::is_forward_iterator<FwdIter1>::value),
                "Requires at least forward iterator.");
            static_assert((hpx::traits::is_forward_iterator<FwdIter2>::value),
                "Requires at least forward iterator.");

            return hpx::parallel::v1::detail::includes().call(
                HPX_FORWARD(ExPolicy, policy), first1, last1, first2, last2,
                HPX_FORWARD(Pred, op),
                hpx::parallel::util::projection_identity(),
                hpx::parallel::util::projection_identity());
        }

        // clang-format off
        template <typename FwdIter1, typename FwdIter2,
            typename Pred = hpx::parallel::v1::detail::less,
            HPX_CONCEPT_REQUIRES_(
                hpx::traits::is_iterator<FwdIter1>::value &&
                hpx::traits::is_iterator<FwdIter2>::value &&
                hpx::is_invocable_v<Pred,
                    typename std::iterator_traits<FwdIter1>::value_type,
                    typename std::iterator_traits<FwdIter2>::value_type
                >
            )>
        // clang-format on
        friend bool tag_fallback_invoke(includes_t, FwdIter1 first1,
            FwdIter1 last1, FwdIter2 first2, FwdIter2 last2, Pred&& op = Pred())
        {
            static_assert((hpx::traits::is_forward_iterator<FwdIter1>::value),
                "Requires at least forward iterator.");
            static_assert((hpx::traits::is_forward_iterator<FwdIter2>::value),
                "Requires at least forward iterator.");

            return hpx::parallel::v1::detail::includes().call(
                hpx::execution::seq, first1, last1, first2, last2,
                HPX_FORWARD(Pred, op),
                hpx::parallel::util::projection_identity(),
                hpx::parallel::util::projection_identity());
        }
    } includes{};
}    // namespace hpx

#endif    // DOXYGEN

1	// Copyright (c) 2007-2022 Hartmut Kaiser
2	//
3	// SPDX-License-Identifier: BSL-1.0
4	// Distributed under the Boost Software License, Version 1.0. (See accompanying
5	// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6
7	/// \file parallel/algorithms/includes.hpp
8
9	#pragma once
10
11	#if defined(DOXYGEN)
12	namespace hpx {
13	// clang-format off
14
15	/// Returns true if every element from the sorted range [\a first2, \a last2) is
16	/// found within the sorted range [\a first1, \a last1). Also returns true if
17	/// [\a first2, \a last2) is empty. The version expects both ranges to be sorted
18	/// with the user supplied binary predicate \a f. Executed according to the
19	/// policy.
20	///
21	/// \note At most 2*(N1+N2-1) comparisons, where
22	/// N1 = std::distance(first1, last1) and
23	/// N2 = std::distance(first2, last2).
24	///
25	/// \tparam ExPolicy The type of the execution policy to use (deduced).
26	/// It describes the manner in which the execution
27	/// of the algorithm may be parallelized and the manner
28	/// in which it executes the assignments.
29	/// \tparam FwdIter1 The type of the source iterators used for the
30	/// first range (deduced).
31	/// This iterator type must meet the requirements of an
32	/// forward iterator.
33	/// \tparam FwdIter2 The type of the source iterators used for the
34	/// second range (deduced).
35	/// This iterator type must meet the requirements of an
36	/// forward iterator.
37	/// \tparam Pred The type of an optional function/function object to use.
38	/// Unlike its sequential form, the parallel
39	/// overload of \a includes requires \a Pred to meet the
40	/// requirements of \a CopyConstructible. This defaults
41	/// to std::less<>
42	///
43	/// \param policy The execution policy to use for the scheduling of
44	/// the iterations.
45	/// \param first1 Refers to the beginning of the sequence of elements
46	/// of the first range the algorithm will be applied to.
47	/// \param last1 Refers to the end of the sequence of elements of
48	/// the first range the algorithm will be applied to.
49	/// \param first2 Refers to the beginning of the sequence of elements
50	/// of the second range the algorithm will be applied to.
51	/// \param last2 Refers to the end of the sequence of elements of
52	/// the second range the algorithm will be applied to.
53	/// \param op The binary predicate which returns true if the
54	/// elements should be treated as includes. The signature
55	/// of the predicate function should be equivalent to
56	/// the following:
57	/// \code
58	/// bool pred(const Type1 &a, const Type2 &b);
59	/// \endcode \n
60	/// The signature does not need to have const &, but
61	/// the function must not modify the objects passed to
62	/// it. The types \a Type1 and \a Type2 must be such
63	/// that objects of types \a FwdIter1 and \a FwdIter2 can
64	/// be dereferenced and then implicitly converted to
65	/// \a Type1 and \a Type2 respectively
66	///
67	/// The comparison operations in the parallel \a includes algorithm invoked
68	/// with an execution policy object of type \a sequenced_policy
69	/// execute in sequential order in the calling thread.
70	///
71	/// The comparison operations in the parallel \a includes algorithm invoked
72	/// with an execution policy object of type \a parallel_policy
73	/// or \a parallel_task_policy are permitted to execute in an unordered
74	/// fashion in unspecified threads, and indeterminately sequenced
75	/// within each thread.
76	///
77	/// \returns The \a includes algorithm returns a \a hpx::future<bool> if the
78	/// execution policy is of type
79	/// \a sequenced_task_policy or
80	/// \a parallel_task_policy and
81	/// returns \a bool otherwise.
82	/// The \a includes algorithm returns true every element from the
83	/// sorted range [\a first2, \a last2) is found within the sorted range
84	/// [\a first1, \a last1).
85	/// Also returns true if [\a first2, \a last2) is empty.
86	///
87	template <typename ExPolicy, typename FwdIter1, typename FwdIter2,
88	typename Pred = hpx::parallel::v1::detail::less>
89	typename hpx::parallel::util::detail::algorithm_result<ExPolicy, bool>::type>::type
90	includes(ExPolicy&& policy, FwdIter1 first1, FwdIter1 last1,
91	FwdIter2 first2, FwdIter2 last2, Pred&& op = Pred());
92
93	/// Returns true if every element from the sorted range [\a first2, \a last2) is
94	/// found within the sorted range [\a first1, \a last1). Also returns true if
95	/// [\a first2, \a last2) is empty. The version expects both ranges to be sorted
96	/// with the user supplied binary predicate \a f.
97	///
98	/// \note At most 2*(N1+N2-1) comparisons, where
99	/// N1 = std::distance(first1, last1) and
100	/// N2 = std::distance(first2, last2).
101	///
102	/// \tparam FwdIter1 The type of the source iterators used for the
103	/// first range (deduced).
104	/// This iterator type must meet the requirements of an
105	/// forward iterator.
106	/// \tparam FwdIter2 The type of the source iterators used for the
107	/// second range (deduced).
108	/// This iterator type must meet the requirements of an
109	/// forward iterator.
110	/// \tparam Pred The type of an optional function/function object to use.
111	/// Unlike its sequential form, the parallel
112	/// overload of \a includes requires \a Pred to meet the
113	/// requirements of \a CopyConstructible. This defaults
114	/// to std::less<>
115	///
116	/// \param first1 Refers to the beginning of the sequence of elements
117	/// of the first range the algorithm will be applied to.
118	/// \param last1 Refers to the end of the sequence of elements of
119	/// the first range the algorithm will be applied to.
120	/// \param first2 Refers to the beginning of the sequence of elements
121	/// of the second range the algorithm will be applied to.
122	/// \param last2 Refers to the end of the sequence of elements of
123	/// the second range the algorithm will be applied to.
124	/// \param op The binary predicate which returns true if the
125	/// elements should be treated as includes. The signature
126	/// of the predicate function should be equivalent to
127	/// the following:
128	/// \code
129	/// bool pred(const Type1 &a, const Type2 &b);
130	/// \endcode \n
131	/// The signature does not need to have const &, but
132	/// the function must not modify the objects passed to
133	/// it. The types \a Type1 and \a Type2 must be such
134	/// that objects of types \a FwdIter1 and \a FwdIter2 can
135	/// be dereferenced and then implicitly converted to
136	/// \a Type1 and \a Type2 respectively
137	///
138	/// \returns The \a includes algorithm returns a \a bool.
139	/// The \a includes algorithm returns true every element from the
140	/// sorted range [\a first2, \a last2) is found within the sorted range
141	/// [\a first1, \a last1).
142	/// Also returns true if [\a first2, \a last2) is empty.
143	///
144	template <typename FwdIter1, typename FwdIter2,
145	typename Pred = hpx::parallel::v1::detail::less>
146	bool includes(FwdIter1 first1, FwdIter1 last1,
147	FwdIter2 first2, FwdIter2 last2, Pred&& op = Pred());
148
149	// clang-format on
150	} // namespace hpx
151
152	#else // DOXYGEN
153
154	#include <hpx/config.hpp>
155	#include <hpx/concepts/concepts.hpp>
156	#include <hpx/functional/invoke.hpp>
157	#include <hpx/iterator_support/traits/is_iterator.hpp>
158	#include <hpx/parallel/util/detail/sender_util.hpp>
159
160	#include <hpx/execution/algorithms/detail/predicates.hpp>
161	#include <hpx/executors/execution_policy.hpp>
162	#include <hpx/parallel/algorithms/detail/dispatch.hpp>
163	#include <hpx/parallel/algorithms/detail/upper_lower_bound.hpp>
164	#include <hpx/parallel/util/cancellation_token.hpp>
165	#include <hpx/parallel/util/detail/algorithm_result.hpp>
166	#include <hpx/parallel/util/partitioner.hpp>
167	#include <hpx/parallel/util/projection_identity.hpp>
168	#include <hpx/parallel/util/result_types.hpp>
169
170	#include <algorithm>
171	#include <cstddef>
172	#include <iterator>
173	#include <type_traits>
174	#include <utility>
175	#include <vector>
176
177	namespace hpx { namespace parallel { inline namespace v1 {
178	///////////////////////////////////////////////////////////////////////////
179	// includes
180	namespace detail {
181
182	template <typename Iter1, typename Sent1, typename Iter2,
183	typename Sent2, typename F, typename Proj1, typename Proj2,
184	typename CancelToken>
185	bool sequential_includes(Iter1 first1, Sent1 last1, Iter2 first2,	453✔
186	Sent2 last2, F&& f, Proj1&& proj1, Proj2&& proj2, CancelToken& tok)
187	{
188	while (first2 != last2)	91,674✔
189	{
190	if (tok.was_cancelled())	92,073✔
191	{
192	return false;	4✔
193	}
194
195	if (first1 == last1)	91,373✔
196	{
197	return false;	2✔
198	}
199
200	auto&& value1 = HPX_INVOKE(proj1, *first1);	91,573✔
201	auto&& value2 = HPX_INVOKE(proj2, *first2);	91,573✔
202
203	if (HPX_INVOKE(f, value2, value1))	91,573✔
204	{
205	return false;	22✔
206	}
207
208	if (!HPX_INVOKE(f, value1, value2))	91,457✔
209	{
210	++first2;	91,197✔
211	}	91,197✔
212
213	++first1;	90,769✔
214	}
215	return true;	423✔
216	}	451✔
217
218	template <typename Iter1, typename Sent1, typename Iter2,
219	typename Sent2, typename F, typename Proj1, typename Proj2>
220	constexpr bool sequential_includes(Iter1 first1, Sent1 last1,	72✔
221	Iter2 first2, Sent2 last2, F&& f, Proj1&& proj1, Proj2&& proj2)
222	{
223	while (first2 != last2)	303,383✔
224	{
225	if (first1 == last1)	303,359✔
226	{
227	return false;	×
228	}
229
230	auto&& value1 = HPX_INVOKE(proj1, *first1);	303,335✔
231	auto&& value2 = HPX_INVOKE(proj2, *first2);	303,335✔
232
233	if (HPX_INVOKE(f, value2, value1))	303,335✔
234	{
235	return false;	24✔
236	}
237
238	if (!HPX_INVOKE(f, value1, value2))	303,311✔
239	{
240	++first2;	100,267✔
241	}	100,267✔
242
243	++first1;	303,311✔
244	}
245	return true;	24✔
246	}	48✔
247
248	///////////////////////////////////////////////////////////////////////
249	struct includes : public detail::algorithm<includes, bool>
250	{
251	includes()	136✔
252	: includes::algorithm("includes")	136✔
253	{	136✔
254	}	136✔
255
256	template <typename ExPolicy, typename Iter1, typename Sent1,
257	typename Iter2, typename Sent2, typename F, typename Proj1,
258	typename Proj2>
259	static bool sequential(ExPolicy, Iter1 first1, Sent1 last1,	72✔
260	Iter2 first2, Sent2 last2, F&& f, Proj1&& proj1, Proj2&& proj2)
261	{
262	return sequential_includes(first1, last1, first2, last2,	144✔
263	HPX_FORWARD(F, f), HPX_FORWARD(Proj1, proj1),	72✔
264	HPX_FORWARD(Proj2, proj2));	72✔
265	}
266
267	template <typename ExPolicy, typename Iter1, typename Sent1,
268	typename Iter2, typename Sent2, typename F, typename Proj1,
269	typename Proj2>
270	static typename util::detail::algorithm_result<ExPolicy, bool>::type
271	parallel(ExPolicy&& policy, Iter1 first1, Sent1 last1, Iter2 first2,	64✔
272	Sent2 last2, F&& f, Proj1&& proj1, Proj2&& proj2)
273	{
274	if (first1 == last1)	64✔
275	{
276	return util::detail::algorithm_result<ExPolicy, bool>::get(	×
277	false);	×
278	}
279	if (first2 == last2)	64✔
280	{
281	return util::detail::algorithm_result<ExPolicy, bool>::get(	×
282	true);	×
283	}
284
285	util::cancellation_token<> tok;	64✔
286
287	auto f1 =
288	[first1, last1, first2, last2, tok, f = HPX_FORWARD(F, f),	4,260✔
289	proj1 = HPX_FORWARD(Proj1, proj1),	64✔
290	proj2 = HPX_FORWARD(Proj2, proj2)](Iter2 part_begin,	64✔
291	std::size_t part_count) mutable -> bool {
292	Iter2 part_end = detail::next(part_begin, part_count);	788✔
293
294	auto value = HPX_INVOKE(proj2, *part_begin);	788✔
295	if (first2 != part_begin && part_count > 1)	788✔
296	{
297	part_begin = detail::upper_bound(	550✔
298	part_begin, part_end, value, f, proj2, tok);	550✔
299	if (tok.was_cancelled())	550✔
300	{
301	return false;	118✔
302	}
303	if (part_begin == part_end)	432✔
304	{
305	return true;	×
306	}
307	value = HPX_INVOKE(proj2, *part_begin);	432✔
308	}	432✔
309
310	Iter1 low = detail::lower_bound(	480✔
311	first1, last1, value, f, proj1, tok);	480✔
312	if (tok.was_cancelled())	480✔
313	{
314	return false;	19✔
315	}
316
317	if (low == last1 \|\|	461✔
318	HPX_INVOKE(f, value, HPX_INVOKE(proj1, *low)))	461✔
319	{
320	tok.cancel();	×
321	return false;	×
322	}
323
324	Iter1 high = last1;	461✔
325	if (part_end != last2)	461✔
326	{
327	auto&& value1 = HPX_INVOKE(proj2, *part_end);	433✔
328
329	high = detail::upper_bound(	433✔
330	low, last1, value1, f, proj1, tok);	433✔
331	part_end = detail::upper_bound(	433✔
332	part_end, last2, value1, f, proj2, tok);	433✔
333
334	if (tok.was_cancelled())	433✔
335	{
336	return false;	8✔
337	}
338	}	425✔
339
340	if (!sequential_includes(low, high, part_begin, part_end, f,	906✔
341	proj1, proj2, tok))	451✔
342	{
343	tok.cancel();	28✔
344	}	28✔
345	return !tok.was_cancelled();	451✔
346	};	596✔
347
348	auto f2 = [](auto&& results) {	48✔
349	return std::all_of(hpx::util::begin(results),	96✔
350	hpx::util::end(results),	48✔
351	[](hpx::future<bool>& val) { return val.get(); });	376✔
352	};
353
354	return util::partitioner<ExPolicy, bool>::call(	64✔
355	HPX_FORWARD(ExPolicy, policy), first2,	64✔
356	detail::distance(first2, last2), HPX_MOVE(f1),	64✔
357	HPX_MOVE(f2));
358	}	64✔
359	};
360	} // namespace detail
361	}}} // namespace hpx::parallel::v1
362
363	namespace hpx {
364
365	///////////////////////////////////////////////////////////////////////////
366	// CPO for hpx::includes
367	inline constexpr struct includes_t final
368	: hpx::detail::tag_parallel_algorithm<includes_t>
369	{
370	private:
371	// clang-format off
372	template <typename ExPolicy, typename FwdIter1, typename FwdIter2,
373	typename Pred = hpx::parallel::v1::detail::less,
374	HPX_CONCEPT_REQUIRES_(
375	hpx::is_execution_policy<ExPolicy>::value &&
376	hpx::traits::is_iterator<FwdIter1>::value &&
377	hpx::traits::is_iterator<FwdIter2>::value &&
378	hpx::is_invocable_v<Pred,
379	typename std::iterator_traits<FwdIter1>::value_type,
380	typename std::iterator_traits<FwdIter2>::value_type
381	>
382	)>
383	// clang-format on
384	friend typename hpx::parallel::util::detail::algorithm_result<ExPolicy,
385	bool>::type
386	tag_fallback_invoke(includes_t, ExPolicy&& policy, FwdIter1 first1,	56✔
387	FwdIter1 last1, FwdIter2 first2, FwdIter2 last2, Pred&& op = Pred())
388	{
389	static_assert((hpx::traits::is_forward_iterator<FwdIter1>::value),
390	"Requires at least forward iterator.");
391	static_assert((hpx::traits::is_forward_iterator<FwdIter2>::value),
392	"Requires at least forward iterator.");
393
394	return hpx::parallel::v1::detail::includes().call(	112✔
395	HPX_FORWARD(ExPolicy, policy), first1, last1, first2, last2,	56✔
396	HPX_FORWARD(Pred, op),	56✔
397	hpx::parallel::util::projection_identity(),
398	hpx::parallel::util::projection_identity());
399	}
400
401	// clang-format off
402	template <typename FwdIter1, typename FwdIter2,
403	typename Pred = hpx::parallel::v1::detail::less,
404	HPX_CONCEPT_REQUIRES_(
405	hpx::traits::is_iterator<FwdIter1>::value &&
406	hpx::traits::is_iterator<FwdIter2>::value &&
407	hpx::is_invocable_v<Pred,
408	typename std::iterator_traits<FwdIter1>::value_type,
409	typename std::iterator_traits<FwdIter2>::value_type
410	>
411	)>
412	// clang-format on
413	friend bool tag_fallback_invoke(includes_t, FwdIter1 first1,	12✔
414	FwdIter1 last1, FwdIter2 first2, FwdIter2 last2, Pred&& op = Pred())
415	{
416	static_assert((hpx::traits::is_forward_iterator<FwdIter1>::value),
417	"Requires at least forward iterator.");
418	static_assert((hpx::traits::is_forward_iterator<FwdIter2>::value),
419	"Requires at least forward iterator.");
420
421	return hpx::parallel::v1::detail::includes().call(	24✔
422	hpx::execution::seq, first1, last1, first2, last2,
423	HPX_FORWARD(Pred, op),	12✔
424	hpx::parallel::util::projection_identity(),
425	hpx::parallel::util::projection_identity());
426	}
427	} includes{};
428	} // namespace hpx
429
430	#endif // DOXYGEN

STEllAR-GROUP / hpx / #868

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