[libc++][PSTL] Implement std::equal

[philnik]

Update exception handling

[ldionne]

libcxx/include/__algorithm/pstl_equal.h

1

Missing documentation comment for the backend.

15

__utility/move.h

113

libcxx/test/std/algorithms/alg.nonmodifying/alg.equal/pstl.equal.pass.cpp

48

We need to test combinations of empty ranges (empty/non-empty, non-empty/empty, empty/empty)

60–62

Why don't you just do this:

[](int lhs, int rhs) { return lhs % 2 == rhs % 2; };

Then you need to call that with two ranges that are not equal, but where all the elements have the same odd-ness.

libcxx/test/std/algorithms/alg.nonmodifying/alg.equal/pstl.exception_handling.pass.cpp

25

boilerplate

[philnik]

Abandoning in favour of https://github.com/llvm/llvm-project/pull/72448

libcxx/include/CMakeLists.txt

set(files
   __algorithm/pstl_backends/cpu_backends/merge.h
   __algorithm/pstl_backends/cpu_backends/serial.h
   __algorithm/pstl_backends/cpu_backends/stable_sort.h
   __algorithm/pstl_backends/cpu_backends/thread.h
   __algorithm/pstl_backends/cpu_backends/transform.h
   __algorithm/pstl_backends/cpu_backends/transform_reduce.h
   __algorithm/pstl_copy.h
   __algorithm/pstl_count.h
+  __algorithm/pstl_equal.h
   __algorithm/pstl_fill.h
   __algorithm/pstl_find.h
   __algorithm/pstl_for_each.h
   __algorithm/pstl_frontend_dispatch.h
   __algorithm/pstl_generate.h
   __algorithm/pstl_is_partitioned.h
   __algorithm/pstl_merge.h
   __algorithm/pstl_replace.h

libcxx/include/__algorithm/pstl_equal.h

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP___ALGORITHM_PSTL_EQUAL_H
+#define _LIBCPP___ALGORITHM_PSTL_EQUAL_H
+
+#include <__algorithm/pstl_frontend_dispatch.h>
+#include <__config>
+#include <__functional/operations.h>
+#include <__numeric/pstl_transform_reduce.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+#if !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+template <class>
+void __pstl_equal();
+
+template <class _ExecutionPolicy,
+          class _ForwardIterator1,
+          class _ForwardIterator2,
+          class _Pred,
+          class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
+          enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
+[[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool>
+__equal(_ExecutionPolicy&& __policy,
+        _ForwardIterator1&& __first1,
+        _ForwardIterator1&& __last1,
+        _ForwardIterator2&& __first2,
+        _Pred&& __pred) noexcept {
+  return std::__pstl_frontend_dispatch(
+      _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_equal),
+      [&__policy](
+          _ForwardIterator1 __g_first1, _ForwardIterator1 __g_last1, _ForwardIterator2 __g_first2, _Pred __g_pred) {
+        return std::__transform_reduce(
+            __policy,
+            std::move(__g_first1),
+            std::move(__g_last1),
+            std::move(__g_first2),
+            true,
+            std::logical_and{},
+            std::move(__g_pred));
+      },
+      std::move(__first1),
+      std::move(__last1),
+      std::move(__first2),
+      std::move(__pred));
+}
+
+template <class _ExecutionPolicy,
+          class _ForwardIterator1,
+          class _ForwardIterator2,
+          class _Pred,
+          class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
+          enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
+_LIBCPP_HIDE_FROM_ABI bool
+equal(_ExecutionPolicy&& __policy,
+      _ForwardIterator1 __first1,
+      _ForwardIterator1 __last1,
+      _ForwardIterator2 __first2,
+      _Pred __pred) {
+  auto __res = std::__equal(__policy, std::move(__first1), std::move(__last1), std::move(__first2), std::move(__pred));
+  if (!__res)
+    std::__throw_bad_alloc();
+  return *__res;
+}
+
+template <class _ExecutionPolicy,
+          class _ForwardIterator1,
+          class _ForwardIterator2,
+          enable_if_t<is_execution_policy_v<__remove_cvref_t<_ExecutionPolicy>>, int> = 0>
+_LIBCPP_HIDE_FROM_ABI bool
+equal(_ExecutionPolicy&& __policy, _ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2) {
+  return std::equal(__policy, std::move(__first1), std::move(__last1), std::move(__first2), std::equal_to{});
+}
+
+template <class _ExecutionPolicy,
+          class _ForwardIterator1,
+          class _ForwardIterator2,
+          class _Pred,
+          class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
+          enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
+[[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool>
+__equal(_ExecutionPolicy&& __policy,
+        _ForwardIterator1&& __first1,
+        _ForwardIterator1&& __last1,
+        _ForwardIterator2&& __first2,
+        _ForwardIterator2&& __last2,
+        _Pred&& __pred) noexcept {
+  return std::__pstl_frontend_dispatch(
+      _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_equal),
+      [&__policy](_ForwardIterator1 __g_first1,
+                  _ForwardIterator1 __g_last1,
+                  _ForwardIterator2 __g_first2,
+                  _ForwardIterator2 __g_last2,
+                  _Pred __g_pred) -> optional<bool> {
+        if constexpr (__has_random_access_iterator_category<_ForwardIterator1>::value &&
+                      __has_random_access_iterator_category<_ForwardIterator2>::value) {
+          if (__g_last1 - __g_first1 != __g_last2 - __g_first2)
+            return false;
+          return std::__equal(
+              __policy, std::move(__g_first1), std::move(__g_last1), std::move(__g_first2), std::move(__g_pred));
+        } else {
+          (void)__policy; // Avoid unused lambda captue warning
+          return std::equal(
+              std::move(__g_first1),
+              std::move(__g_last1),
+              std::move(__g_first2),
+              std::move(__g_last2),
+              std::move(__g_pred));
+        }
+      },
+      std::move(__first1),
+      std::move(__last1),
+      std::move(__first2),
+      std::move(__last2),
+      std::move(__pred));
+}
+
+template <class _ExecutionPolicy,
+          class _ForwardIterator1,
+          class _ForwardIterator2,
+          class _Pred,
+          class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
+          enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
+_LIBCPP_HIDE_FROM_ABI bool
+equal(_ExecutionPolicy&& __policy,
+      _ForwardIterator1 __first1,
+      _ForwardIterator1 __last1,
+      _ForwardIterator2 __first2,
+      _ForwardIterator2 __last2,
+      _Pred __pred) {
+  auto __res = std::__equal(
+      __policy, std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2), std::move(__pred));
+  if (!__res)
+    std::__throw_bad_alloc();
+  return *__res;
+}
+
+template <class _ExecutionPolicy,
+          class _ForwardIterator1,
+          class _ForwardIterator2,
+          enable_if_t<is_execution_policy_v<__remove_cvref_t<_ExecutionPolicy>>, int> = 0>
+_LIBCPP_HIDE_FROM_ABI bool
+equal(_ExecutionPolicy&& __policy,
+      _ForwardIterator1 __first1,
+      _ForwardIterator1 __last1,
+      _ForwardIterator2 __first2,
+      _ForwardIterator2 __last2) {
+  return std::equal(
+      __policy, std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2), std::equal_to{});
+}
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
+
+#endif // _LIBCPP___ALGORITHM_PSTL_EQUAL_H

libcxx/include/algorithm

 #include <__algorithm/partition.h>
 #include <__algorithm/partition_copy.h>
 #include <__algorithm/partition_point.h>
 #include <__algorithm/pop_heap.h>
 #include <__algorithm/prev_permutation.h>
 #include <__algorithm/pstl_any_all_none_of.h>
 #include <__algorithm/pstl_copy.h>
 #include <__algorithm/pstl_count.h>
+#include <__algorithm/pstl_equal.h>
 #include <__algorithm/pstl_fill.h>
 #include <__algorithm/pstl_find.h>
 #include <__algorithm/pstl_for_each.h>
 #include <__algorithm/pstl_generate.h>
 #include <__algorithm/pstl_is_partitioned.h>
 #include <__algorithm/pstl_merge.h>
 #include <__algorithm/pstl_replace.h>
 #include <__algorithm/pstl_sort.h>

libcxx/include/module.modulemap.in

 module std_private_algorithm_pstl_backends_cpu_backends_thread           [system] { textual header "__algorithm/pstl_backends/cpu_backends/thread.h" }
 module std_private_algorithm_pstl_backends_cpu_backends_transform        [system] {
   header "__algorithm/pstl_backends/cpu_backends/transform.h"
   export std_private_algorithm_transform
 }
 module std_private_algorithm_pstl_backends_cpu_backends_transform_reduce [system] { header "__algorithm/pstl_backends/cpu_backends/transform_reduce.h" }
 module std_private_algorithm_pstl_copy                                   [system] { header "__algorithm/pstl_copy.h" }
 module std_private_algorithm_pstl_count                                  [system] { header "__algorithm/pstl_count.h" }
+module std_private_algorithm_pstl_equal                                  [system] { header "__algorithm/pstl_equal.h" }
 module std_private_algorithm_pstl_fill                                   [system] { header "__algorithm/pstl_fill.h" }
 module std_private_algorithm_pstl_find                                   [system] {
   header "__algorithm/pstl_find.h"
   export *
 }
 module std_private_algorithm_pstl_for_each                               [system] {
   header "__algorithm/pstl_for_each.h"
   export *

libcxx/test/std/algorithms/alg.nonmodifying/alg.equal/pstl.equal.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14
+
+// UNSUPPORETD: libcpp-has-no-incomplete-pstl
+
+// <algorithm>
+
+// template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
+//   bool equal(ExecutionPolicy&& exec,
+//              ForwardIterator1 first1, ForwardIterator1 last1,
+//              ForwardIterator2 first2);
+//
+// template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
+//          class BinaryPredicate>
+//   bool equal(ExecutionPolicy&& exec,
+//              ForwardIterator1 first1, ForwardIterator1 last1,
+//              ForwardIterator2 first2, BinaryPredicate pred);
+//
+// template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
+//   bool equal(ExecutionPolicy&& exec,
+//              ForwardIterator1 first1, ForwardIterator1 last1,
+//              ForwardIterator2 first2, ForwardIterator2 last2);
+//
+// template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
+//          class BinaryPredicate>
+//   bool equal(ExecutionPolicy&& exec,
+//              ForwardIterator1 first1, ForwardIterator1 last1,
+//              ForwardIterator2 first2, ForwardIterator2 last2,
+//              BinaryPredicate pred);
+
+#include <algorithm>
+#include <cassert>
+
+#include "test_execution_policies.h"
+#include "test_iterators.h"
+#include "test_macros.h"
+
+template <class Iter1, class Iter2>
+struct Test {
+  template <class Policy>
+  void operator()(Policy&& policy) {
+    { // 3 iter overloads
+      int a[] = {1, 2, 3, 4, 5, 6, 7, 8};
+      int b[] = {1, 2, 3, 5, 6, 7, 8, 9};
+
+      // simple test
+      assert(std::equal(policy, Iter1(std::begin(a)), Iter1(std::end(a)), Iter2(std::begin(a))));
+
+      // check that false is returned on different ranges
+      assert(!std::equal(policy, Iter1(std::begin(a)), Iter1(std::end(a)), Iter2(std::begin(b))));
+
+      // check that the predicate is used
+      assert(std::equal(policy, Iter1(std::begin(a)), Iter1(std::end(a)), Iter2(std::begin(b)), [](int lhs, int rhs) {
+        return lhs == rhs || lhs + 1 == rhs || rhs + 1 == lhs;
+      }));
+    }
+
+    { // 4 iter overloads
+      int a[] = {1, 2, 3, 4, 5, 6, 7, 8};
+      int b[] = {1, 2, 3, 5, 6, 7, 8, 9};
+
+      // simple test
+      assert(std::equal(policy, Iter1(std::begin(a)), Iter1(std::end(a)), Iter2(std::begin(a)), Iter2(std::end(a))));
+
+      // check that false is returned on different ranges
+      assert(!std::equal(policy, Iter1(std::begin(a)), Iter1(std::end(a)), Iter2(std::begin(b)), Iter2(std::end(b))));
+
+      // check that false is returned on different sized ranges
+      assert(
+          !std::equal(policy, Iter1(std::begin(a)), Iter1(std::end(a)), Iter2(std::begin(a)), Iter2(std::end(a) - 1)));
+
+      // check that the predicate is used
+      assert(std::equal(
+          policy,
+          Iter1(std::begin(a)),
+          Iter1(std::end(a)),
+          Iter2(std::begin(b)),
+          Iter2(std::end(b)),
+          [](int lhs, int rhs) { return lhs == rhs || lhs + 1 == rhs || rhs + 1 == lhs; }));
+    }
+  }
+};
+
+int main(int, char**) {
+  types::for_each(types::forward_iterator_list<int*>{}, types::apply_type_identity{[](auto v) {
+                    using Iter1 = typename decltype(v)::type;
+                    types::for_each(
+                        types::forward_iterator_list<int*>{},
+                        TestIteratorWithPolicies<types::partial_instantiation<Test, Iter1>::template apply>{});
+                  }});
+}

libcxx/test/std/algorithms/alg.nonmodifying/alg.equal/pstl.exception_handling.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14
+// UNSUPPORTED: no-exceptions
+
+// UNSUPPORTED: libcpp-has-no-incomplete-pstl
+
+// check that std::equal(ExecutionPolicy) terminates on user-thrown exceptions
+
+#include <algorithm>
+
+#include "check_assertion.h"
+#include "test_execution_policies.h"
+#include "test_iterators.h"
+
+struct ThrowOnCompare {};
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+bool operator==(ThrowOnCompare, ThrowOnCompare) { throw int{}; }
+#endif
+
+int main(int, char**) {
+  test_execution_policies([](auto&& policy) {
+    EXPECT_STD_TERMINATE([&] {
+      try {
+        int a[] = {1, 2};
+        int b[] = {1, 2};
+        (void)std::equal(policy,
+                         util::throw_on_move_iterator(std::begin(a), 1),
+                         util::throw_on_move_iterator(std::end(a), 1),
+                         util::throw_on_move_iterator(std::begin(b), 1));
+      } catch (const util::iterator_error&) {
+        assert(false);
+      }
+      std::terminate(); // make the test pass in case the algorithm didn't move the iterator
+    });
+    EXPECT_STD_TERMINATE([&] {
+      try {
+        int a[] = {1, 2};
+        int b[] = {1, 2};
+        (void)std::equal(
+            policy,
+            util::throw_on_move_iterator(std::begin(a), 1),
+            util::throw_on_move_iterator(std::end(a), 1),
+            util::throw_on_move_iterator(std::begin(b), 1),
+            util::throw_on_move_iterator(std::end(b), 1));
+      } catch (const util::iterator_error&) {
+        assert(false);
+      }
+      std::terminate(); // make the test pass in case the algorithm didn't move the iterator
+    });
+  });
+}