#867

Committed 15 Jan 2023 08:00PM CUT coverage: 86.487% (+0.5%) from 85.951%

Build # #867

Build Type

push

Committed by StellarBot

Commit Message

Merge #6135

6135: Fixing warnings reported by MSVC analysis r=hkaiser a=hkaiser

- adding MSVC specific #pragma's to suppress the benign warnings


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

Run Details

120 of 120 new or added lines in 33 files covered. (100.0%)

174599 of 201880 relevant lines covered (86.49%)

1945607.64 hits per line

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

93.94

/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,	410✔
186	Sent2 last2, F&& f, Proj1&& proj1, Proj2&& proj2, CancelToken& tok)
187	{
188	while (first2 != last2)	62,672✔
189	{
190	if (tok.was_cancelled())	62,581✔
191	{
192	return false;	5✔
193	}
194
195	if (first1 == last1)	62,390✔
196	{
197	return false;	1✔
198	}
199
200	auto&& value1 = HPX_INVOKE(proj1, *first1);	62,420✔
201	auto&& value2 = HPX_INVOKE(proj2, *first2);	62,420✔
202
203	if (HPX_INVOKE(f, value2, value1))	62,420✔
204	{
205	return false;	22✔
206	}
207
208	if (!HPX_INVOKE(f, value1, value2))	62,360✔
209	{
210	++first2;	62,239✔
211	}	62,239✔
212
213	++first1;	62,160✔
214	}
215	return true;	382✔
216	}	410✔
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)	336,436✔
224	{
225	if (first1 == last1)	336,412✔
226	{
227	return false;	×
228	}
229
230	auto&& value1 = HPX_INVOKE(proj1, *first1);	336,388✔
231	auto&& value2 = HPX_INVOKE(proj2, *first2);	336,388✔
232
233	if (HPX_INVOKE(f, value2, value1))	336,388✔
234	{
235	return false;	24✔
236	}
237
238	if (!HPX_INVOKE(f, value1, value2))	336,364✔
239	{
240	++first2;	74,850✔
241	}	74,850✔
242
243	++first1;	336,364✔
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,005✔
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);	737✔
293
294	auto value = HPX_INVOKE(proj2, *part_begin);	737✔
295	if (first2 != part_begin && part_count > 1)	737✔
296	{
297	part_begin = detail::upper_bound(	488✔
298	part_begin, part_end, value, f, proj2, tok);	488✔
299	if (tok.was_cancelled())	488✔
300	{
301	return false;	102✔
302	}
303	if (part_begin == part_end)	386✔
304	{
305	return true;	×
306	}
307	value = HPX_INVOKE(proj2, *part_begin);	386✔
308	}	386✔
309
310	Iter1 low = detail::lower_bound(	434✔
311	first1, last1, value, f, proj1, tok);	434✔
312	if (tok.was_cancelled())	434✔
313	{
314	return false;	18✔
315	}
316
317	if (low == last1 \|\|	416✔
318	HPX_INVOKE(f, value, HPX_INVOKE(proj1, *low)))	416✔
319	{
320	tok.cancel();	1✔
321	return false;	1✔
322	}
323
324	Iter1 high = last1;	415✔
325	if (part_end != last2)	415✔
326	{
327	auto&& value1 = HPX_INVOKE(proj2, *part_end);	384✔
328
329	high = detail::upper_bound(	384✔
330	low, last1, value1, f, proj1, tok);	384✔
331	part_end = detail::upper_bound(	384✔
332	part_end, last2, value1, f, proj2, tok);	384✔
333
334	if (tok.was_cancelled())	384✔
335	{
336	return false;	5✔
337	}
338	}	379✔
339
340	if (!sequential_includes(low, high, part_begin, part_end, f,	820✔
341	proj1, proj2, tok))	410✔
342	{
343	tok.cancel();	27✔
344	}	27✔
345	return !tok.was_cancelled();	409✔
346	};	535✔
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(); });	343✔
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 / #867

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