1 // -*- C++ -*-
2 // { dg-options "-ltbb" }
3 // { dg-do run { target c++17 } }
4 // { dg-timeout-factor 3 }
5 // { dg-require-effective-target tbb-backend }
6
7 //===-- find.pass.cpp -----------------------------------------------------===//
8 //
9 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
10 // See https://llvm.org/LICENSE.txt for license information.
11 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
12 //
13 //===----------------------------------------------------------------------===//
14
15 // Tests for find
16 #include "pstl/pstl_test_config.h"
17
18 #ifdef PSTL_STANDALONE_TESTS
19 #include "pstl/execution"
20 #include "pstl/algorithm"
21 #else
22 #include <execution>
23 #include <algorithm>
24 #endif // PSTL_STANDALONE_TESTS
25
26 #include "pstl/test_utils.h"
27
28 using namespace TestUtils;
29
30 struct test_find
31 {
32 #if _PSTL_ICC_17_VC141_TEST_SIMD_LAMBDA_DEBUG_32_BROKEN || \
33 _PSTL_ICC_16_VC14_TEST_SIMD_LAMBDA_DEBUG_32_BROKEN //dummy specialization by policy type, in case of broken configuration
34 template <typename Iterator, typename Value>
35 void
operator ()test_find36 operator()(pstl::execution::unsequenced_policy, Iterator first, Iterator last, Value value)
37 {
38 }
39 template <typename Iterator, typename Value>
40 void
operator ()test_find41 operator()(pstl::execution::parallel_unsequenced_policy, Iterator first, Iterator last, Value value)
42 {
43 }
44 #endif
45
46 template <typename Policy, typename Iterator, typename Value>
47 void
operator ()test_find48 operator()(Policy&& exec, Iterator first, Iterator last, Value value)
49 {
50 auto i = std::find(first, last, value);
51 auto j = find(exec, first, last, value);
52 EXPECT_TRUE(i == j, "wrong return value from find");
53 }
54 };
55
56 template <typename T, typename Value, typename Hit, typename Miss>
57 void
test(Value value,Hit hit,Miss miss)58 test(Value value, Hit hit, Miss miss)
59 {
60 // Try sequences of various lengths.
61 for (size_t n = 0; n <= 100000; n = n <= 16 ? n + 1 : size_t(3.1415 * n))
62 {
63 Sequence<T> in(n, [&](size_t k) -> T { return miss(n ^ k); });
64 // Try different find positions, including not found.
65 // By going backwards, we can add extra matches that are *not* supposed to be found.
66 // The decreasing exponential gives us O(n) total work for the loop since each find takes O(m) time.
67 for (size_t m = n; m > 0; m *= 0.6)
68 {
69 if (m < n)
70 in[m] = hit(n ^ m);
71 invoke_on_all_policies(test_find(), in.begin(), in.end(), value);
72 invoke_on_all_policies(test_find(), in.cbegin(), in.cend(), value);
73 }
74 }
75 }
76
77 // Type defined for sake of checking that std::find works with asymmetric ==.
78 class Weird
79 {
80 Number value;
81
82 public:
83 friend bool
operator ==(Number x,Weird y)84 operator==(Number x, Weird y)
85 {
86 return x == y.value;
87 }
Weird(int32_t val,OddTag)88 Weird(int32_t val, OddTag) : value(val, OddTag()) {}
89 };
90
91 int32_t
main()92 main()
93 {
94 // Note that the "hit" and "miss" functions here avoid overflow issues.
95 test<Number>(Weird(42, OddTag()), [](int32_t j) { return Number(42, OddTag()); }, // hit
96 [](int32_t j) { return Number(j == 42 ? 0 : j, OddTag()); }); // miss
97
98 // Test with value that is equal to two different bit patterns (-0.0 and 0.0)
99 test<float32_t>(-0.0, [](int32_t j) { return j & 1 ? 0.0 : -0.0; }, // hit
100 [](int32_t j) { return j == 0 ? ~j : j; }); // miss
101
102 std::cout << done() << std::endl;
103 return 0;
104 }
105