From 3b62047b8b2209bed57d239f581bdbfc91a10b94 Mon Sep 17 00:00:00 2001 From: Louis Dionne Date: Wed, 27 Mar 2019 21:28:24 +0000 Subject: Restructure test suite to follow libc++ standard layout Summary: Subsumes changes requested in https://reviews.llvm.org/D59110 Reviewers: EricWF, ldionne Subscribers: mgorny, krytarowski, jfb, jdoerfert, libcxx-commits Differential Revision: https://reviews.llvm.org/D59856 llvm-svn: 357124 --- .../alg.nonmodifying/adjacent_find.pass.cpp | 118 ++++++++++++++ .../algorithms/alg.nonmodifying/all_of.pass.cpp | 120 ++++++++++++++ .../algorithms/alg.nonmodifying/any_of.pass.cpp | 106 ++++++++++++ .../std/algorithms/alg.nonmodifying/count.pass.cpp | 111 +++++++++++++ .../std/algorithms/alg.nonmodifying/equal.pass.cpp | 171 +++++++++++++++++++ .../std/algorithms/alg.nonmodifying/find.pass.cpp | 99 +++++++++++ .../algorithms/alg.nonmodifying/find_end.pass.cpp | 126 ++++++++++++++ .../alg.nonmodifying/find_first_of.pass.cpp | 115 +++++++++++++ .../algorithms/alg.nonmodifying/find_if.pass.cpp | 112 +++++++++++++ .../algorithms/alg.nonmodifying/for_each.pass.cpp | 105 ++++++++++++ .../algorithms/alg.nonmodifying/mismatch.pass.cpp | 139 ++++++++++++++++ .../algorithms/alg.nonmodifying/none_of.pass.cpp | 104 ++++++++++++ .../alg.nonmodifying/nth_element.pass.cpp | 181 +++++++++++++++++++++ .../algorithms/alg.nonmodifying/search_n.pass.cpp | 112 +++++++++++++ 14 files changed, 1719 insertions(+) create mode 100644 pstl/test/std/algorithms/alg.nonmodifying/adjacent_find.pass.cpp create mode 100644 pstl/test/std/algorithms/alg.nonmodifying/all_of.pass.cpp create mode 100644 pstl/test/std/algorithms/alg.nonmodifying/any_of.pass.cpp create mode 100644 pstl/test/std/algorithms/alg.nonmodifying/count.pass.cpp create mode 100644 pstl/test/std/algorithms/alg.nonmodifying/equal.pass.cpp create mode 100644 pstl/test/std/algorithms/alg.nonmodifying/find.pass.cpp create mode 100644 pstl/test/std/algorithms/alg.nonmodifying/find_end.pass.cpp create mode 100644 pstl/test/std/algorithms/alg.nonmodifying/find_first_of.pass.cpp create mode 100644 pstl/test/std/algorithms/alg.nonmodifying/find_if.pass.cpp create mode 100644 pstl/test/std/algorithms/alg.nonmodifying/for_each.pass.cpp create mode 100644 pstl/test/std/algorithms/alg.nonmodifying/mismatch.pass.cpp create mode 100644 pstl/test/std/algorithms/alg.nonmodifying/none_of.pass.cpp create mode 100644 pstl/test/std/algorithms/alg.nonmodifying/nth_element.pass.cpp create mode 100644 pstl/test/std/algorithms/alg.nonmodifying/search_n.pass.cpp (limited to 'pstl/test/std/algorithms/alg.nonmodifying') diff --git a/pstl/test/std/algorithms/alg.nonmodifying/adjacent_find.pass.cpp b/pstl/test/std/algorithms/alg.nonmodifying/adjacent_find.pass.cpp new file mode 100644 index 00000000000..50b01e38bc1 --- /dev/null +++ b/pstl/test/std/algorithms/alg.nonmodifying/adjacent_find.pass.cpp @@ -0,0 +1,118 @@ +// -*- C++ -*- +//===-- adjacent_find.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 +// +//===----------------------------------------------------------------------===// + +#include "support/pstl_test_config.h" + +#ifdef PSTL_STANDALONE_TESTS + +#include "pstl/execution" +#include "pstl/algorithm" +#else +#include +#include +#endif // PSTL_STANDALONE_TESTS + +#include "support/utils.h" + +using namespace TestUtils; + +struct test_adjacent_find +{ + template + void + operator()(Policy&& exec, Iterator first, Iterator last, Pred pred) + { + using namespace std; + + auto k = std::adjacent_find(first, last, pred); + auto i = adjacent_find(exec, first, last, pred); + EXPECT_TRUE(i == k, "wrong return value from adjacent_find with predicate"); + + i = adjacent_find(exec, first, last); + EXPECT_TRUE(i == k, "wrong return value from adjacent_find without predicate"); + } +}; + +template +void +test_adjacent_find_by_type() +{ + + size_t counts[] = {2, 3, 500}; + for (int32_t c = 0; c < const_size(counts); ++c) + { + + for (int32_t e = 0; e < (counts[c] >= 64 ? 64 : (counts[c] == 2 ? 1 : 2)); ++e) + { + Sequence in(counts[c], [](int32_t v) -> T { return T(v); }); //fill 0...n + in[e] = in[e + 1] = -1; //make an adjacent pair + + auto i = std::adjacent_find(in.cbegin(), in.cend(), std::equal_to()); + EXPECT_TRUE(i == in.cbegin() + e, "std::adjacent_find returned wrong result"); + + invoke_on_all_policies(test_adjacent_find(), in.begin(), in.end(), std::equal_to()); + invoke_on_all_policies(test_adjacent_find(), in.cbegin(), in.cend(), std::equal_to()); + } + } + + //special cases: size=0, size=1; + for (int32_t expect = 0; expect < 1; ++expect) + { + Sequence in(expect, [](int32_t v) -> T { return T(v); }); //fill 0...n + auto i = std::adjacent_find(in.cbegin(), in.cend(), std::equal_to()); + EXPECT_TRUE(i == in.cbegin() + expect, "std::adjacent_find returned wrong result"); + + invoke_on_all_policies(test_adjacent_find(), in.begin(), in.end(), std::equal_to()); + invoke_on_all_policies(test_adjacent_find(), in.cbegin(), in.cend(), std::equal_to()); + } + + //special cases: + Sequence a1 = {5, 5, 5, 6, 7, 8, 9}; + invoke_on_all_policies(test_adjacent_find(), a1.begin(), a1.end(), std::equal_to()); + invoke_on_all_policies(test_adjacent_find(), a1.begin() + 1, a1.end(), std::equal_to()); + + invoke_on_all_policies(test_adjacent_find(), a1.cbegin(), a1.cend(), std::equal_to()); + invoke_on_all_policies(test_adjacent_find(), a1.cbegin() + 1, a1.cend(), std::equal_to()); + + Sequence a2 = {5, 6, 7, 8, 9, 9}; + invoke_on_all_policies(test_adjacent_find(), a2.begin(), a2.end(), std::equal_to()); + invoke_on_all_policies(test_adjacent_find(), a2.begin(), a2.end() - 1, std::equal_to()); + + invoke_on_all_policies(test_adjacent_find(), a2.cbegin(), a2.cend(), std::equal_to()); + invoke_on_all_policies(test_adjacent_find(), a2.cbegin(), a2.cend() - 1, std::equal_to()); + + Sequence a3 = {5, 6, 6, 6, 7, 9, 9, 9, 9}; + invoke_on_all_policies(test_adjacent_find(), a3.begin(), a3.end(), std::equal_to()); + + invoke_on_all_policies(test_adjacent_find(), a3.cbegin(), a3.cend(), std::equal_to()); +} + +template +struct test_non_const +{ + template + void + operator()(Policy&& exec, Iterator iter) + { + adjacent_find(exec, iter, iter, non_const(std::equal_to())); + } +}; + +int32_t +main() +{ + + test_adjacent_find_by_type(); + test_adjacent_find_by_type(); + + test_algo_basic_single(run_for_rnd_bi>()); + + std::cout << done() << std::endl; + return 0; +} diff --git a/pstl/test/std/algorithms/alg.nonmodifying/all_of.pass.cpp b/pstl/test/std/algorithms/alg.nonmodifying/all_of.pass.cpp new file mode 100644 index 00000000000..f6372c44bd5 --- /dev/null +++ b/pstl/test/std/algorithms/alg.nonmodifying/all_of.pass.cpp @@ -0,0 +1,120 @@ +// -*- C++ -*- +//===-- all_of.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 +// +//===----------------------------------------------------------------------===// + +#include "support/pstl_test_config.h" + +#ifdef PSTL_STANDALONE_TESTS +#include "pstl/execution" +#include "pstl/algorithm" +#else +#include +#include +#endif // PSTL_STANDALONE_TESTS + +#include "support/utils.h" + +/* + TODO: consider implementing the following tests for a better code coverage + - correctness + - bad input argument (if applicable) + - data corruption around/of input and output + - correctly work with nested parallelism + - check that algorithm does not require anything more than is described in its requirements section +*/ + +using namespace TestUtils; + +struct test_all_of +{ + template + void + operator()(ExecutionPolicy&& exec, Iterator begin, Iterator end, Predicate pred, bool expected) + { + + auto actualr = std::all_of(exec, begin, end, pred); + EXPECT_EQ(expected, actualr, "result for all_of"); + } +}; + +template +struct Parity +{ + bool parity; + + public: + Parity(bool parity_) : parity(parity_) {} + bool + operator()(T value) const + { + return (size_t(value) ^ parity) % 2 == 0; + } +}; + +template +void +test(size_t bits) +{ + for (size_t n = 0; n <= 100000; n = n <= 16 ? n + 1 : size_t(3.1415 * n)) + { + + // Sequence of odd values + Sequence in(n, [n, bits](size_t k) { return T(2 * HashBits(n, bits - 1) ^ 1); }); + + // Even value, or false when T is bool. + T spike(2 * HashBits(n, bits - 1)); + Sequence inCopy(in); + + invoke_on_all_policies(test_all_of(), in.begin(), in.end(), Parity(1), true); + invoke_on_all_policies(test_all_of(), in.cbegin(), in.cend(), Parity(1), true); + EXPECT_EQ(in, inCopy, "all_of modified input sequence"); + if (n > 0) + { + // Sprinkle in a miss + in[2 * n / 3] = spike; + invoke_on_all_policies(test_all_of(), in.begin(), in.end(), Parity(1), false); + invoke_on_all_policies(test_all_of(), in.cbegin(), in.cend(), Parity(1), false); + + // Sprinkle in a few more misses + in[n / 2] = spike; + in[n / 3] = spike; + invoke_on_all_policies(test_all_of(), in.begin(), in.end(), Parity(1), false); + invoke_on_all_policies(test_all_of(), in.cbegin(), in.cend(), Parity(1), false); + } + } +} + +struct test_non_const +{ + template + void + operator()(Policy&& exec, Iterator iter) + { + auto is_even = [&](float64_t v) { + uint32_t i = (uint32_t)v; + return i % 2 == 0; + }; + all_of(exec, iter, iter, non_const(is_even)); + } +}; + +int32_t +main() +{ + test(8 * sizeof(int32_t)); + test(8 * sizeof(uint16_t)); + test(53); +#if !__PSTL_ICC_16_17_TEST_REDUCTION_BOOL_TYPE_RELEASE_64_BROKEN + test(1); +#endif + + test_algo_basic_single(run_for_rnd_fw()); + + std::cout << done() << std::endl; + return 0; +} diff --git a/pstl/test/std/algorithms/alg.nonmodifying/any_of.pass.cpp b/pstl/test/std/algorithms/alg.nonmodifying/any_of.pass.cpp new file mode 100644 index 00000000000..70bd4b2fb3b --- /dev/null +++ b/pstl/test/std/algorithms/alg.nonmodifying/any_of.pass.cpp @@ -0,0 +1,106 @@ +// -*- C++ -*- +//===-- any_of.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 +// +//===----------------------------------------------------------------------===// + +#include "support/pstl_test_config.h" + +#ifdef PSTL_STANDALONE_TESTS +#include "pstl/execution" +#include "pstl/algorithm" +#else +#include +#include +#endif // PSTL_STANDALONE_TESTS + +#include "support/utils.h" + +/* + TODO: consider implementing the following tests for a better code coverage + - correctness + - bad input argument (if applicable) + - data corruption around/of input and output + - correctly work with nested parallelism + - check that algorithm does not require anything more than is described in its requirements section +*/ + +using namespace TestUtils; + +struct test_any_of +{ + template + void + operator()(ExecutionPolicy&& exec, Iterator begin, Iterator end, Predicate pred, bool expected) + { + + auto actualr = std::any_of(exec, begin, end, pred); + EXPECT_EQ(expected, actualr, "result for any_of"); + } +}; + +template +void +test(size_t bits) +{ + for (size_t n = 0; n <= 100000; n = n <= 16 ? n + 1 : size_t(3.1415 * n)) + { + + // Sequence of odd values + Sequence in(n, [n, bits](size_t k) { return T(2 * HashBits(n, bits - 1) ^ 1); }); + + // Even value, or false when T is bool. + T spike(2 * HashBits(n, bits - 1)); + Sequence inCopy(in); + + invoke_on_all_policies(test_any_of(), in.begin(), in.end(), is_equal_to(spike), false); + invoke_on_all_policies(test_any_of(), in.cbegin(), in.cend(), is_equal_to(spike), false); + EXPECT_EQ(in, inCopy, "any_of modified input sequence"); + if (n > 0) + { + // Sprinkle in a hit + in[2 * n / 3] = spike; + invoke_on_all_policies(test_any_of(), in.begin(), in.end(), is_equal_to(spike), true); + invoke_on_all_policies(test_any_of(), in.cbegin(), in.cend(), is_equal_to(spike), true); + + // Sprinkle in a few more hits + in[n / 2] = spike; + in[n / 3] = spike; + invoke_on_all_policies(test_any_of(), in.begin(), in.end(), is_equal_to(spike), true); + invoke_on_all_policies(test_any_of(), in.cbegin(), in.cend(), is_equal_to(spike), true); + } + } +} + +struct test_non_const +{ + template + void + operator()(Policy&& exec, Iterator iter) + { + auto is_even = [&](float64_t v) { + uint32_t i = (uint32_t)v; + return i % 2 == 0; + }; + any_of(exec, iter, iter, non_const(is_even)); + } +}; + +int32_t +main() +{ + test(8 * sizeof(int32_t)); + test(8 * sizeof(uint16_t)); + test(53); +#if !__PSTL_ICC_16_17_TEST_REDUCTION_BOOL_TYPE_RELEASE_64_BROKEN + test(1); +#endif + + test_algo_basic_single(run_for_rnd_fw()); + + std::cout << done() << std::endl; + return 0; +} diff --git a/pstl/test/std/algorithms/alg.nonmodifying/count.pass.cpp b/pstl/test/std/algorithms/alg.nonmodifying/count.pass.cpp new file mode 100644 index 00000000000..38c553762f3 --- /dev/null +++ b/pstl/test/std/algorithms/alg.nonmodifying/count.pass.cpp @@ -0,0 +1,111 @@ +// -*- C++ -*- +//===-- count.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 +// +//===----------------------------------------------------------------------===// + +// Tests for count and count_if +#include "support/pstl_test_config.h" + +#ifdef PSTL_STANDALONE_TESTS +#include "pstl/execution" +#include "pstl/algorithm" +#else +#include +#include +#endif // PSTL_STANDALONE_TESTS + +#include "support/utils.h" + +using namespace TestUtils; + +struct test_count +{ + template + void + operator()(Policy&& exec, Iterator first, Iterator last, T needle) + { + auto expected = std::count(first, last, needle); + auto result = std::count(exec, first, last, needle); + EXPECT_EQ(expected, result, "wrong count result"); + } +}; + +struct test_count_if +{ + template + void + operator()(Policy&& exec, Iterator first, Iterator last, Predicate pred) + { + auto expected = std::count_if(first, last, pred); + auto result = std::count_if(exec, first, last, pred); + EXPECT_EQ(expected, result, "wrong count_if result"); + } +}; + +template +class IsEqual +{ + T value; + + public: + IsEqual(T value_, OddTag) : value(value_) {} + bool + operator()(const T& x) const + { + return x == value; + } +}; + +template +void +test(T needle, Predicate pred, Convert convert) +{ + // Try sequences of various lengths. + for (size_t n = 0; n <= 100000; n = n <= 16 ? n + 1 : size_t(3.1415 * n)) + { + Sequence in(n, [=](size_t k) -> In { + // Sprinkle "42" and "50" early, so that short sequences have non-zero count. + return convert((n - k - 1) % 3 == 0 ? 42 : (n - k - 2) % 5 == 0 ? 50 : 3 * (int(k) % 1000 - 500)); + }); + invoke_on_all_policies(test_count(), in.begin(), in.end(), needle); + invoke_on_all_policies(test_count_if(), in.begin(), in.end(), pred); + + invoke_on_all_policies(test_count(), in.cbegin(), in.cend(), needle); + invoke_on_all_policies(test_count_if(), in.cbegin(), in.cend(), pred); + } +} + +struct test_non_const +{ + template + void + operator()(Policy&& exec, Iterator iter) + { + auto is_even = [&](float64_t v) { + uint32_t i = (uint32_t)v; + return i % 2 == 0; + }; + count_if(exec, iter, iter, non_const(is_even)); + } +}; + +int32_t +main() +{ + test(42, IsEqual(50, OddTag()), [](int32_t j) { return j; }); +#if !__PSTL_ICC_16_17_TEST_REDUCTION_RELEASE_BROKEN + test(42, [](const int32_t& x) { return true; }, [](int32_t j) { return j; }); +#endif + test(42, IsEqual(50, OddTag()), [](int32_t j) { return float64_t(j); }); + test(Number(42, OddTag()), IsEqual(Number(50, OddTag()), OddTag()), + [](int32_t j) { return Number(j, OddTag()); }); + + test_algo_basic_single(run_for_rnd_fw()); + + std::cout << done() << std::endl; + return 0; +} diff --git a/pstl/test/std/algorithms/alg.nonmodifying/equal.pass.cpp b/pstl/test/std/algorithms/alg.nonmodifying/equal.pass.cpp new file mode 100644 index 00000000000..0e4f38c2eb7 --- /dev/null +++ b/pstl/test/std/algorithms/alg.nonmodifying/equal.pass.cpp @@ -0,0 +1,171 @@ +// -*- C++ -*- +//===-- 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 +// +//===----------------------------------------------------------------------===// + +#include "support/pstl_test_config.h" + +#ifdef PSTL_STANDALONE_TESTS +#include "pstl/execution" +#include "pstl/algorithm" +#else +#include +#include +#endif // PSTL_STANDALONE_TESTS + +#include "support/utils.h" + +using namespace TestUtils; + +#define CPP14_ENABLED 0 + +struct UserType +{ + float32_t f; + float64_t d; + int32_t i; + size_t key; + + bool + operator()(UserType a, UserType b) + { + return a.key < b.key; + } + bool + operator<(UserType a) + { + return a.key < key; + } + bool + operator>=(UserType a) + { + return a.key <= key; + } + bool + operator<=(UserType a) + { + return a.key >= key; + } + bool + operator==(UserType a) + { + return a.key == key; + } + bool + operator==(UserType a) const + { + return a.key == key; + } + bool + operator!=(UserType a) + { + return a.key != key; + } + UserType operator!() + { + UserType tmp; + tmp.key = !key; + return tmp; + } + friend std::ostream& + operator<<(std::ostream& stream, const UserType a) + { + stream << a.key; + return stream; + } + + UserType() : key(-1), f(0.0f), d(0.0), i(0) {} + UserType(size_t Number) : key(Number), f(0.0f), d(0.0), i(0) {} + UserType& + operator=(const UserType& other) + { + key = other.key; + return *this; + } + UserType(const UserType& other) : key(other.key), f(other.f), d(other.d), i(other.i) {} + UserType(UserType&& other) : key(other.key), f(other.f), d(other.d), i(other.i) + { + other.key = -1; + other.f = 0.0f; + other.d = 0.0; + other.i = 0; + } +}; + +struct test_one_policy +{ + template + void + operator()(ExecutionPolicy&& exec, Iterator1 first1, Iterator1 last1, Iterator2 first2, bool is_true_equal) + { + using namespace std; + + auto expected = equal(first1, last1, first2); + auto actual = equal(exec, first1, last1, first2); + EXPECT_EQ(expected, actual, "result for equal for random-access iterator, checking against std::equal()"); + + // testing bool + EXPECT_TRUE(is_true_equal == actual, "result for equal for random-access iterator, bool"); + +//add C++14 equal symantics tests +//add more cases for inCopy size less than in +#if CPP14_ENABLED + auto actualr14 = std::equal(in.cbegin(), in.cend(), inCopy.cbegin(), inCopy.cend()); + EXPECT_EQ(expected, actualr14, "result for equal for random-access iterator"); +#endif + } +}; + +template +void +test(size_t bits) +{ + for (size_t n = 1; n <= 100000; n = n <= 16 ? n + 1 : size_t(3.1415 * n)) + { + + // Sequence of odd values + Sequence in(n, [bits](size_t k) { return T(2 * HashBits(k, bits - 1) ^ 1); }); + Sequence inCopy(in); + + invoke_on_all_policies(test_one_policy(), in.begin(), in.end(), inCopy.begin(), true); + invoke_on_all_policies(test_one_policy(), in.cbegin(), in.cend(), inCopy.cbegin(), true); + + // testing bool !equal() + inCopy[0] = !inCopy[0]; + invoke_on_all_policies(test_one_policy(), in.begin(), in.end(), inCopy.begin(), false); + invoke_on_all_policies(test_one_policy(), in.cbegin(), in.cend(), inCopy.cbegin(), false); + } +} + +template +struct test_non_const +{ + template + void + operator()(Policy&& exec, FirstIterator first_iter, SecondInterator second_iter) + { + equal(exec, first_iter, first_iter, second_iter, second_iter, non_const(std::equal_to())); + } +}; + +int32_t +main() +{ + + test(8 * sizeof(int32_t)); + test(8 * sizeof(uint16_t)); + test(53); +#if !__PSTL_ICC_16_17_TEST_REDUCTION_BOOL_TYPE_RELEASE_64_BROKEN + test(1); +#endif + test(256); + + test_algo_basic_double(run_for_rnd_fw>()); + + std::cout << done() << std::endl; + return 0; +} diff --git a/pstl/test/std/algorithms/alg.nonmodifying/find.pass.cpp b/pstl/test/std/algorithms/alg.nonmodifying/find.pass.cpp new file mode 100644 index 00000000000..60e56ae4628 --- /dev/null +++ b/pstl/test/std/algorithms/alg.nonmodifying/find.pass.cpp @@ -0,0 +1,99 @@ +// -*- C++ -*- +//===-- find.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 +// +//===----------------------------------------------------------------------===// + +// Tests for find +#include "support/pstl_test_config.h" + +#ifdef PSTL_STANDALONE_TESTS +#include "pstl/execution" +#include "pstl/algorithm" +#else +#include +#include +#endif // PSTL_STANDALONE_TESTS + +#include "support/utils.h" + +using namespace TestUtils; + +struct test_find +{ +#if __PSTL_ICC_17_VC141_TEST_SIMD_LAMBDA_DEBUG_32_BROKEN || \ + __PSTL_ICC_16_VC14_TEST_SIMD_LAMBDA_DEBUG_32_BROKEN //dummy specialization by policy type, in case of broken configuration + template + void + operator()(pstl::execution::unsequenced_policy, Iterator first, Iterator last, Value value) + { + } + template + void + operator()(pstl::execution::parallel_unsequenced_policy, Iterator first, Iterator last, Value value) + { + } +#endif + + template + void + operator()(Policy&& exec, Iterator first, Iterator last, Value value) + { + auto i = std::find(first, last, value); + auto j = find(exec, first, last, value); + EXPECT_TRUE(i == j, "wrong return value from find"); + } +}; + +template +void +test(Value value, Hit hit, Miss miss) +{ + // Try sequences of various lengths. + for (size_t n = 0; n <= 100000; n = n <= 16 ? n + 1 : size_t(3.1415 * n)) + { + Sequence in(n, [&](size_t k) -> T { return miss(n ^ k); }); + // Try different find positions, including not found. + // By going backwards, we can add extra matches that are *not* supposed to be found. + // The decreasing exponential gives us O(n) total work for the loop since each find takes O(m) time. + for (size_t m = n; m > 0; m *= 0.6) + { + if (m < n) + in[m] = hit(n ^ m); + invoke_on_all_policies(test_find(), in.begin(), in.end(), value); + invoke_on_all_policies(test_find(), in.cbegin(), in.cend(), value); + } + } +} + +// Type defined for sake of checking that std::find works with asymmetric ==. +class Weird +{ + Number value; + + public: + friend bool + operator==(Number x, Weird y) + { + return x == y.value; + } + Weird(int32_t val, OddTag) : value(val, OddTag()) {} +}; + +int32_t +main() +{ + // Note that the "hit" and "miss" functions here avoid overflow issues. + test(Weird(42, OddTag()), [](int32_t j) { return Number(42, OddTag()); }, // hit + [](int32_t j) { return Number(j == 42 ? 0 : j, OddTag()); }); // miss + + // Test with value that is equal to two different bit patterns (-0.0 and 0.0) + test(-0.0, [](int32_t j) { return j & 1 ? 0.0 : -0.0; }, // hit + [](int32_t j) { return j == 0 ? ~j : j; }); // miss + + std::cout << done() << std::endl; + return 0; +} diff --git a/pstl/test/std/algorithms/alg.nonmodifying/find_end.pass.cpp b/pstl/test/std/algorithms/alg.nonmodifying/find_end.pass.cpp new file mode 100644 index 00000000000..4059630b3d1 --- /dev/null +++ b/pstl/test/std/algorithms/alg.nonmodifying/find_end.pass.cpp @@ -0,0 +1,126 @@ +// -*- C++ -*- +//===-- find_end.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 +// +//===----------------------------------------------------------------------===// + +#include "support/pstl_test_config.h" + +#ifdef PSTL_STANDALONE_TESTS +#include "pstl/execution" +#include "pstl/algorithm" +#else +#include +#include +#endif // PSTL_STANDALONE_TESTS + +#include "support/utils.h" + +using namespace TestUtils; + +struct test_one_policy +{ +#if __PSTL_ICC_17_VC141_TEST_SIMD_LAMBDA_DEBUG_32_BROKEN || \ + __PSTL_ICC_16_VC14_TEST_SIMD_LAMBDA_DEBUG_32_BROKEN //dummy specialization by policy type, in case of broken configuration + template + void + operator()(pstl::execution::unsequenced_policy, Iterator1 b, Iterator1 e, Iterator2 bsub, Iterator2 esub, + Predicate pred) + { + } + template + void + operator()(pstl::execution::parallel_unsequenced_policy, Iterator1 b, Iterator1 e, Iterator2 bsub, Iterator2 esub, + Predicate pred) + { + } +#endif + + template + void + operator()(ExecutionPolicy&& exec, Iterator1 b, Iterator1 e, Iterator2 bsub, Iterator2 esub, Predicate pred) + { + using namespace std; + // For find_end + { + auto expected = find_end(b, e, bsub, esub, pred); + auto actual = find_end(exec, b, e, bsub, esub); + EXPECT_TRUE(actual == expected, "wrong return result from find_end"); + + actual = find_end(exec, b, e, bsub, esub, pred); + EXPECT_TRUE(actual == expected, "wrong return result from find_end with a predicate"); + } + + // For search + { + auto expected = search(b, e, bsub, esub, pred); + auto actual = search(exec, b, e, bsub, esub); + EXPECT_TRUE(actual == expected, "wrong return result from search"); + + actual = search(exec, b, e, bsub, esub, pred); + EXPECT_TRUE(actual == expected, "wrong return result from search with a predicate"); + } + } +}; + +template +void +test(const std::size_t bits) +{ + + const std::size_t max_n1 = 1000; + const std::size_t max_n2 = (max_n1 * 10) / 8; + Sequence in(max_n1, [max_n1, bits](std::size_t k) { return T(2 * HashBits(max_n1, bits - 1) ^ 1); }); + Sequence sub(max_n2, [max_n1, bits](std::size_t k) { return T(2 * HashBits(max_n1, bits - 1)); }); + for (std::size_t n1 = 0; n1 <= max_n1; n1 = n1 <= 16 ? n1 + 1 : size_t(3.1415 * n1)) + { + std::size_t sub_n[] = {0, 1, 3, n1, (n1 * 10) / 8}; + std::size_t res[] = {0, 1, n1 / 2, n1}; + for (auto n2 : sub_n) + { + for (auto r : res) + { + std::size_t i = r, isub = 0; + for (; i < n1 & isub < n2; ++i, ++isub) + in[i] = sub[isub]; + invoke_on_all_policies(test_one_policy(), in.begin(), in.begin() + n1, sub.begin(), sub.begin() + n2, + std::equal_to()); + invoke_on_all_policies(test_one_policy(), in.cbegin(), in.cbegin() + n1, sub.cbegin(), + sub.cbegin() + n2, std::equal_to()); + } + } + } +} + +template +struct test_non_const +{ + template + void + operator()(Policy&& exec, FirstIterator first_iter, SecondInterator second_iter) + { + invoke_if(exec, [&]() { + find_end(exec, first_iter, first_iter, second_iter, second_iter, non_const(std::equal_to())); + search(exec, first_iter, first_iter, second_iter, second_iter, non_const(std::equal_to())); + }); + } +}; + +int32_t +main() +{ + test(8 * sizeof(int32_t)); + test(8 * sizeof(uint16_t)); + test(53); +#if !__PSTL_ICC_16_17_TEST_REDUCTION_BOOL_TYPE_RELEASE_64_BROKEN + test(1); +#endif + + test_algo_basic_double(run_for_rnd_fw>()); + + std::cout << done() << std::endl; + return 0; +} diff --git a/pstl/test/std/algorithms/alg.nonmodifying/find_first_of.pass.cpp b/pstl/test/std/algorithms/alg.nonmodifying/find_first_of.pass.cpp new file mode 100644 index 00000000000..ee62e84fd16 --- /dev/null +++ b/pstl/test/std/algorithms/alg.nonmodifying/find_first_of.pass.cpp @@ -0,0 +1,115 @@ +// -*- C++ -*- +//===-- find_first_of.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 +// +//===----------------------------------------------------------------------===// + +#include "support/pstl_test_config.h" + +#ifdef PSTL_STANDALONE_TESTS +#include "pstl/execution" +#include "pstl/algorithm" +#else +#include +#include +#endif // PSTL_STANDALONE_TESTS + +#include "support/utils.h" + +using namespace TestUtils; + +struct test_one_policy +{ +#if __PSTL_ICC_17_VC141_TEST_SIMD_LAMBDA_DEBUG_32_BROKEN || \ + __PSTL_ICC_16_VC14_TEST_SIMD_LAMBDA_DEBUG_32_BROKEN //dummy specialization by policy type, in case of broken configuration + template + void + operator()(pstl::execution::unsequenced_policy, Iterator1 b, Iterator1 e, Iterator2 bsub, Iterator2 esub, + Predicate pred) + { + } + template + void + operator()(pstl::execution::parallel_unsequenced_policy, Iterator1 b, Iterator1 e, Iterator2 bsub, Iterator2 esub, + Predicate pred) + { + } +#endif + + template + void + operator()(ExecutionPolicy&& exec, Iterator1 b, Iterator1 e, Iterator2 bsub, Iterator2 esub, Predicate pred) + { + using namespace std; + Iterator1 expected = find_first_of(b, e, bsub, esub, pred); + Iterator1 actual = find_first_of(exec, b, e, bsub, esub, pred); + EXPECT_TRUE(actual == expected, "wrong return result from find_first_of with a predicate"); + + expected = find_first_of(b, e, bsub, esub); + actual = find_first_of(exec, b, e, bsub, esub); + EXPECT_TRUE(actual == expected, "wrong return result from find_first_of"); + } +}; + +template +void +test(Predicate pred) +{ + + const std::size_t max_n1 = 1000; + const std::size_t max_n2 = (max_n1 * 10) / 8; + Sequence in1(max_n1, [](std::size_t k) { return T(1); }); + Sequence in2(max_n2, [](std::size_t k) { return T(0); }); + for (std::size_t n1 = 0; n1 <= max_n1; n1 = n1 <= 16 ? n1 + 1 : size_t(3.1415 * n1)) + { + std::size_t sub_n[] = {0, 1, n1 / 3, n1, (n1 * 10) / 8}; + for (const auto n2 : sub_n) + { + invoke_on_all_policies(test_one_policy(), in1.begin(), in1.begin() + n1, in2.data(), in2.data() + n2, pred); + + in2[n2 / 2] = T(1); + invoke_on_all_policies(test_one_policy(), in1.cbegin(), in1.cbegin() + n1, in2.data(), in2.data() + n2, + pred); + + if (n2 >= 3) + { + in2[2 * n2 / 3] = T(1); + invoke_on_all_policies(test_one_policy(), in1.cbegin(), in1.cbegin() + n1, in2.begin(), + in2.begin() + n2, pred); + in2[2 * n2 / 3] = T(0); + } + in2[n2 / 2] = T(0); + } + } + invoke_on_all_policies(test_one_policy(), in1.begin(), in1.begin() + max_n1 / 10, in1.data(), + in1.data() + max_n1 / 10, pred); +} + +template +struct test_non_const +{ + template + void + operator()(Policy&& exec, FirstIterator first_iter, SecondInterator second_iter) + { + invoke_if(exec, [&]() { + find_first_of(exec, first_iter, first_iter, second_iter, second_iter, non_const(std::equal_to())); + }); + } +}; + +int32_t +main() +{ + test(std::equal_to()); + test(std::not_equal_to()); + test([](const float64_t x, const float64_t y) { return x * x == y * y; }); + + test_algo_basic_double(run_for_rnd_fw>()); + + std::cout << done() << std::endl; + return 0; +} diff --git a/pstl/test/std/algorithms/alg.nonmodifying/find_if.pass.cpp b/pstl/test/std/algorithms/alg.nonmodifying/find_if.pass.cpp new file mode 100644 index 00000000000..2ea8765077f --- /dev/null +++ b/pstl/test/std/algorithms/alg.nonmodifying/find_if.pass.cpp @@ -0,0 +1,112 @@ +// -*- C++ -*- +//===-- find_if.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 +// +//===----------------------------------------------------------------------===// + +// Tests for find_if and find_if_not +#include "support/pstl_test_config.h" + +#ifdef PSTL_STANDALONE_TESTS +#include "pstl/execution" +#include "pstl/algorithm" +#else +#include +#include +#endif // PSTL_STANDALONE_TESTS + +#include "support/utils.h" + +using namespace TestUtils; + +struct test_find_if +{ +#if __PSTL_ICC_17_VC141_TEST_SIMD_LAMBDA_DEBUG_32_BROKEN || \ + __PSTL_ICC_16_VC14_TEST_SIMD_LAMBDA_DEBUG_32_BROKEN //dummy specialization by policy type, in case of broken configuration + template + void + operator()(pstl::execution::unsequenced_policy, Iterator first, Iterator last, Predicate pred, + NotPredicate not_pred) + { + } + template + void + operator()(pstl::execution::parallel_unsequenced_policy, Iterator first, Iterator last, Predicate pred, + NotPredicate not_pred) + { + } +#endif + + template + void + operator()(Policy&& exec, Iterator first, Iterator last, Predicate pred, NotPredicate not_pred) + { + auto i = std::find_if(first, last, pred); + auto j = find_if(exec, first, last, pred); + EXPECT_TRUE(i == j, "wrong return value from find_if"); + auto i_not = find_if_not(exec, first, last, not_pred); + EXPECT_TRUE(i_not == i, "wrong return value from find_if_not"); + } +}; + +template +void +test(Predicate pred, Hit hit, Miss miss) +{ + auto not_pred = [pred](T x) { return !pred(x); }; + // Try sequences of various lengths. + for (size_t n = 0; n <= 100000; n = n <= 16 ? n + 1 : size_t(3.1415 * n)) + { + Sequence in(n, [&](size_t k) -> T { return miss(n ^ k); }); + // Try different find positions, including not found. + // By going backwards, we can add extra matches that are *not* supposed to be found. + // The decreasing exponential gives us O(n) total work for the loop since each find takes O(m) time. + for (size_t m = n; m > 0; m *= 0.6) + { + if (m < n) + in[m] = hit(n ^ m); + invoke_on_all_policies(test_find_if(), in.begin(), in.end(), pred, not_pred); + invoke_on_all_policies(test_find_if(), in.cbegin(), in.cend(), pred, not_pred); + } + } +} + +struct test_non_const +{ + template + void + operator()(Policy&& exec, Iterator iter) + { + auto is_even = [&](float64_t v) { + uint32_t i = (uint32_t)v; + return i % 2 == 0; + }; + + invoke_if(exec, [&]() { + find_if(exec, iter, iter, non_const(is_even)); + find_if_not(exec, iter, iter, non_const(is_even)); + }); + } +}; + +int32_t +main() +{ +#if !__PSTL_ICC_17_TEST_MAC_RELEASE_32_BROKEN + // Note that the "hit" and "miss" functions here avoid overflow issues. + test(IsMultiple(5, OddTag()), [](int32_t j) { return Number(j - j % 5, OddTag()); }, // hit + [](int32_t j) { return Number(j % 5 == 0 ? j ^ 1 : j, OddTag()); }); // miss +#endif + + // Try type for which algorithm can really be vectorized. + test([](float32_t x) { return x >= 0; }, [](float32_t j) { return j * j; }, + [](float32_t j) { return -1 - j * j; }); + + test_algo_basic_single(run_for_rnd_fw()); + + std::cout << done() << std::endl; + return 0; +} diff --git a/pstl/test/std/algorithms/alg.nonmodifying/for_each.pass.cpp b/pstl/test/std/algorithms/alg.nonmodifying/for_each.pass.cpp new file mode 100644 index 00000000000..cb0fa06dcda --- /dev/null +++ b/pstl/test/std/algorithms/alg.nonmodifying/for_each.pass.cpp @@ -0,0 +1,105 @@ +// -*- C++ -*- +//===-- for_each.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 +// +//===----------------------------------------------------------------------===// + +#include "support/pstl_test_config.h" + +#ifdef PSTL_STANDALONE_TESTS +#include "pstl/execution" +#include "pstl/algorithm" +#else +#include +#include +#endif // PSTL_STANDALONE_TESTS + +#include "support/utils.h" + +using namespace TestUtils; + +template +struct Gen +{ + Type + operator()(std::size_t k) + { + return Type(k % 5 != 1 ? 3 * k - 7 : 0); + }; +}; + +template +struct Flip +{ + int32_t val; + Flip(int32_t y) : val(y) {} + T + operator()(T& x) const + { + return x = val - x; + } +}; + +struct test_one_policy +{ + template + void + operator()(Policy&& exec, Iterator first, Iterator last, Iterator expected_first, Iterator expected_last, Size n) + { + typedef typename std::iterator_traits::value_type T; + + // Try for_each + std::for_each(expected_first, expected_last, Flip(1)); + for_each(exec, first, last, Flip(1)); + EXPECT_EQ_N(expected_first, first, n, "wrong effect from for_each"); + + // Try for_each_n + std::for_each_n(pstl::execution::seq, expected_first, n, Flip(1)); + for_each_n(exec, first, n, Flip(1)); + EXPECT_EQ_N(expected_first, first, n, "wrong effect from for_each_n"); + } +}; + +template +void +test() +{ + for (size_t n = 0; n <= 100000; n = n <= 16 ? n + 1 : size_t(3.1415 * n)) + { + Sequence inout(n, Gen()); + Sequence expected(n, Gen()); + invoke_on_all_policies(test_one_policy(), inout.begin(), inout.end(), expected.begin(), expected.end(), + inout.size()); + } +} + +struct test_non_const +{ + template + void + operator()(Policy&& exec, Iterator iter) + { + invoke_if(exec, [&]() { + auto f = [](typename std::iterator_traits::reference x) { x = x + 1; }; + + for_each(exec, iter, iter, non_const(f)); + for_each_n(exec, iter, 0, non_const(f)); + }); + } +}; + +int32_t +main() +{ + test(); + test(); + test(); + + test_algo_basic_single(run_for_rnd_fw()); + + std::cout << done() << std::endl; + return 0; +} diff --git a/pstl/test/std/algorithms/alg.nonmodifying/mismatch.pass.cpp b/pstl/test/std/algorithms/alg.nonmodifying/mismatch.pass.cpp new file mode 100644 index 00000000000..ec34af08fb0 --- /dev/null +++ b/pstl/test/std/algorithms/alg.nonmodifying/mismatch.pass.cpp @@ -0,0 +1,139 @@ +// -*- C++ -*- +//===-- mismatch.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 +// +//===----------------------------------------------------------------------===// + +#include "support/pstl_test_config.h" + +#ifdef PSTL_STANDALONE_TESTS + +#include "pstl/execution" +#include "pstl/algorithm" +#include "pstl/numeric" +#include "pstl/memory" + +#else +#include +#include +#endif // PSTL_STANDALONE_TESTS + +#include "support/utils.h" + +using namespace TestUtils; + +struct test_mismatch +{ + template + void + operator()(Policy&& exec, Iterator1 first1, Iterator1 last1, Iterator2 first2) + { + using namespace std; + typedef typename iterator_traits::value_type T; + { + const auto expected = std::mismatch(first1, last1, first2, std::equal_to()); + const auto res3 = mismatch(exec, first1, last1, first2, std::equal_to()); + EXPECT_TRUE(expected == res3, "wrong return result from mismatch"); + const auto res4 = mismatch(exec, first1, last1, first2); + EXPECT_TRUE(expected == res4, "wrong return result from mismatch"); + } + } + template + void + operator()(Policy&& exec, Iterator1 first1, Iterator1 last1, Iterator2 first2, Iterator2 last2) + { + using namespace std; + typedef typename iterator_traits::value_type T; + { + const auto expected = mismatch(pstl::execution::seq, first1, last1, first2, last2, std::equal_to()); + const auto res1 = mismatch(exec, first1, last1, first2, last2, std::equal_to()); + EXPECT_TRUE(expected == res1, "wrong return result from mismatch"); + const auto res2 = mismatch(exec, first1, last1, first2, last2); + EXPECT_TRUE(expected == res2, "wrong return result from mismatch"); + } + } +}; + +template +void +test_mismatch_by_type() +{ + using namespace std; + for (size_t size = 0; size <= 100000; size = size <= 16 ? size + 1 : size_t(3.1415 * size)) + { + const T val = T(-1); + Sequence in(size, [](size_t v) -> T { return T(v % 100); }); + { + Sequence in2(in); + invoke_on_all_policies(test_mismatch(), in.begin(), in.end(), in2.begin(), in2.end()); + invoke_on_all_policies(test_mismatch(), in.begin(), in.end(), in2.begin()); + + const size_t min_size = 3; + if (size > min_size) + { + const size_t idx_for_1 = size / min_size; + in[idx_for_1] = val, in[idx_for_1 + 1] = val, in[idx_for_1 + 2] = val; + invoke_on_all_policies(test_mismatch(), in.begin(), in.end(), in2.begin(), in2.end()); + invoke_on_all_policies(test_mismatch(), in.begin(), in.end(), in2.begin()); + } + + const size_t idx_for_2 = 500; + if (size >= idx_for_2 - 1) + { + in2[size / idx_for_2] = val; + invoke_on_all_policies(test_mismatch(), in.cbegin(), in.cend(), in2.cbegin(), in2.cend()); + invoke_on_all_policies(test_mismatch(), in.cbegin(), in.cend(), in2.cbegin()); + } + } + { + Sequence in2(100, [](size_t v) -> T { return T(v); }); + invoke_on_all_policies(test_mismatch(), in2.begin(), in2.end(), in.begin(), in.end()); + // We can't call std::mismatch with semantic below when size of second sequence less than size of first sequence + if (in2.size() <= in.size()) + invoke_on_all_policies(test_mismatch(), in2.begin(), in2.end(), in.begin()); + + const size_t idx = 97; + in2[idx] = val; + in2[idx + 1] = val; + invoke_on_all_policies(test_mismatch(), in.cbegin(), in.cend(), in2.cbegin(), in2.cend()); + if (in.size() <= in2.size()) + invoke_on_all_policies(test_mismatch(), in.cbegin(), in.cend(), in2.cbegin()); + } + { + Sequence in2({}); + invoke_on_all_policies(test_mismatch(), in2.begin(), in2.end(), in.begin(), in.end()); + + invoke_on_all_policies(test_mismatch(), in.cbegin(), in.cend(), in2.cbegin(), in2.cend()); + if (in.size() == 0) + invoke_on_all_policies(test_mismatch(), in.cbegin(), in.cend(), in2.cbegin()); + } + } +} + +template +struct test_non_const +{ + template + void + operator()(Policy&& exec, FirstIterator first_iter, SecondInterator second_iter) + { + mismatch(exec, first_iter, first_iter, second_iter, second_iter, non_const(std::less())); + } +}; + +int32_t +main() +{ + + test_mismatch_by_type(); + test_mismatch_by_type(); + test_mismatch_by_type>(); + + test_algo_basic_double(run_for_rnd_fw>()); + + std::cout << done() << std::endl; + return 0; +} diff --git a/pstl/test/std/algorithms/alg.nonmodifying/none_of.pass.cpp b/pstl/test/std/algorithms/alg.nonmodifying/none_of.pass.cpp new file mode 100644 index 00000000000..47a01a15027 --- /dev/null +++ b/pstl/test/std/algorithms/alg.nonmodifying/none_of.pass.cpp @@ -0,0 +1,104 @@ +// -*- C++ -*- +//===-- none_of.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 +// +//===----------------------------------------------------------------------===// + +#include "support/pstl_test_config.h" + +#ifdef PSTL_STANDALONE_TESTS +#include "pstl/execution" +#include "pstl/algorithm" +#else +#include +#include +#endif // PSTL_STANDALONE_TESTS + +#include "support/utils.h" + +/* + TODO: consider implementing the following tests for a better code coverage + - correctness + - bad input argument (if applicable) + - data corruption around/of input and output + - correctly work with nested parallelism + - check that algorithm does not require anything more than is described in its requirements section +*/ + +using namespace TestUtils; + +struct test_none_of +{ + template + void + operator()(ExecutionPolicy&& exec, Iterator begin, Iterator end, Predicate pred, bool expected) + { + + auto actualr = std::none_of(exec, begin, end, pred); + EXPECT_EQ(expected, actualr, "result for none_of"); + } +}; + +template +void +test(size_t bits) +{ + for (size_t n = 0; n <= 100000; n = n <= 16 ? n + 1 : size_t(3.1415 * n)) + { + + // Sequence of odd values + Sequence in(n, [n, bits](size_t k) { return T(2 * HashBits(n, bits - 1) ^ 1); }); + + // Even value, or false when T is bool. + T spike(2 * HashBits(n, bits - 1)); + + invoke_on_all_policies(test_none_of(), in.begin(), in.end(), is_equal_to(spike), true); + invoke_on_all_policies(test_none_of(), in.cbegin(), in.cend(), is_equal_to(spike), true); + if (n > 0) + { + // Sprinkle in a hit + in[2 * n / 3] = spike; + invoke_on_all_policies(test_none_of(), in.begin(), in.end(), is_equal_to(spike), false); + invoke_on_all_policies(test_none_of(), in.cbegin(), in.cend(), is_equal_to(spike), false); + + // Sprinkle in a few more hits + in[n / 3] = spike; + in[n / 2] = spike; + invoke_on_all_policies(test_none_of(), in.begin(), in.end(), is_equal_to(spike), false); + invoke_on_all_policies(test_none_of(), in.cbegin(), in.cend(), is_equal_to(spike), false); + } + } +} + +struct test_non_const +{ + template + void + operator()(Policy&& exec, Iterator iter) + { + auto is_even = [&](float64_t v) { + uint32_t i = (uint32_t)v; + return i % 2 == 0; + }; + none_of(exec, iter, iter, non_const(is_even)); + } +}; + +int32_t +main() +{ + test(8 * sizeof(int32_t)); + test(8 * sizeof(uint16_t)); + test(53); +#if !__PSTL_ICC_16_17_TEST_REDUCTION_BOOL_TYPE_RELEASE_64_BROKEN + test(1); +#endif + + test_algo_basic_single(run_for_rnd_fw()); + + std::cout << done() << std::endl; + return 0; +} diff --git a/pstl/test/std/algorithms/alg.nonmodifying/nth_element.pass.cpp b/pstl/test/std/algorithms/alg.nonmodifying/nth_element.pass.cpp new file mode 100644 index 00000000000..f8154d2426d --- /dev/null +++ b/pstl/test/std/algorithms/alg.nonmodifying/nth_element.pass.cpp @@ -0,0 +1,181 @@ +// -*- C++ -*- +//===-- nth_element.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 +// +//===----------------------------------------------------------------------===// + +#include "support/pstl_test_config.h" + +#ifdef PSTL_STANDALONE_TESTS +#include +#include +#include "pstl/execution" +#include "pstl/algorithm" + +#else +#include +#include +#endif // PSTL_STANDALONE_TESTS + +#include "support/utils.h" + +using namespace TestUtils; + +// User defined type with minimal requirements +template +struct DataType +{ + explicit DataType(int32_t k) : my_val(k) {} + DataType(DataType&& input) + { + my_val = std::move(input.my_val); + input.my_val = T(0); + } + DataType& + operator=(DataType&& input) + { + my_val = std::move(input.my_val); + input.my_val = T(0); + return *this; + } + T + get_val() const + { + return my_val; + } + + friend std::ostream& + operator<<(std::ostream& stream, const DataType& input) + { + return stream << input.my_val; + } + + private: + T my_val; +}; + +template +bool +is_equal(const DataType& x, const DataType& y) +{ + return x.get_val() == y.get_val(); +} + +template +bool +is_equal(const T& x, const T& y) +{ + return x == y; +} + +struct test_one_policy +{ +#if __PSTL_ICC_17_VC141_TEST_SIMD_LAMBDA_DEBUG_32_BROKEN || \ + __PSTL_ICC_16_VC14_TEST_SIMD_LAMBDA_DEBUG_32_BROKEN // dummy specialization by policy type, in case of broken configuration + template + typename std::enable_if::value, void>::type + operator()(pstl::execution::unsequenced_policy, Iterator1 first1, Iterator1 last1, Iterator1 first2, + Iterator1 last2, Size n, Size m, Generator1 generator1, Generator2 generator2, Compare comp) + { + } + template + typename std::enable_if::value, void>::type + operator()(pstl::execution::parallel_unsequenced_policy, Iterator1 first1, Iterator1 last1, Iterator1 first2, + Iterator1 last2, Size n, Size m, Generator1 generator1, Generator2 generator2, Compare comp) + { + } +#endif + + // nth_element works only with random access iterators + template + typename std::enable_if::value, void>::type + operator()(Policy&& exec, Iterator1 first1, Iterator1 last1, Iterator1 first2, Iterator1 last2, Size n, Size m, + Generator1 generator1, Generator2 generator2, Compare comp) + { + + using T = typename std::iterator_traits::value_type; + const Iterator1 mid1 = std::next(first1, m); + const Iterator1 mid2 = std::next(first2, m); + + fill_data(first1, mid1, generator1); + fill_data(mid1, last1, generator2); + fill_data(first2, mid2, generator1); + fill_data(mid2, last2, generator2); + std::nth_element(first1, mid1, last1, comp); + std::nth_element(exec, first2, mid2, last2, comp); + if (m > 0 && m < n) + { + EXPECT_TRUE(is_equal(*mid1, *mid2), "wrong result from nth_element with predicate"); + } + EXPECT_TRUE(std::find_first_of(first2, mid2, mid2, last2, [comp](T& x, T& y) { return comp(y, x); }) == mid2, + "wrong effect from nth_element with predicate"); + } + + template + typename std::enable_if::value, void>::type + operator()(Policy&& exec, Iterator1 first1, Iterator1 last1, Iterator1 first2, Iterator1 last2, Size n, Size m, + Generator1 generator1, Generator2 generator2, Compare comp) + { + } +}; + +template +void +test_by_type(Generator1 generator1, Generator2 generator2, Compare comp) +{ + using namespace std; + size_t max_size = 10000; + Sequence in1(max_size, [](size_t v) { return T(v); }); + Sequence exp(max_size, [](size_t v) { return T(v); }); + size_t m; + + for (size_t n = 0; n <= max_size; n = n <= 16 ? n + 1 : size_t(3.1415 * n)) + { + m = 0; + invoke_on_all_policies(test_one_policy(), exp.begin(), exp.begin() + n, in1.begin(), in1.begin() + n, n, m, + generator1, generator2, comp); + m = n / 7; + invoke_on_all_policies(test_one_policy(), exp.begin(), exp.begin() + n, in1.begin(), in1.begin() + n, n, m, + generator1, generator2, comp); + m = 3 * n / 5; + invoke_on_all_policies(test_one_policy(), exp.begin(), exp.begin() + n, in1.begin(), in1.begin() + n, n, m, + generator1, generator2, comp); + } + invoke_on_all_policies(test_one_policy(), exp.begin(), exp.begin() + max_size, in1.begin(), in1.begin() + max_size, + max_size, max_size, generator1, generator2, comp); +} + +template +struct test_non_const +{ + template + void + operator()(Policy&& exec, Iterator iter) + { + invoke_if(exec, [&]() { nth_element(exec, iter, iter, iter, non_const(std::less())); }); + } +}; + +int32_t +main() +{ + test_by_type([](int32_t i) { return 10 * i; }, [](int32_t i) { return i + 1; }, std::less()); + test_by_type([](int32_t) { return 0; }, [](int32_t) { return 0; }, std::less()); + + test_by_type([](int32_t i) { return -2 * i; }, [](int32_t i) { return -(2 * i + 1); }, + [](const float64_t x, const float64_t y) { return x > y; }); + + test_by_type>( + [](int32_t i) { return DataType(2 * i + 1); }, [](int32_t i) { return DataType(2 * i); }, + [](const DataType& x, const DataType& y) { return x.get_val() < y.get_val(); }); + + test_algo_basic_single(run_for_rnd>()); + + std::cout << done() << std::endl; + return 0; +} diff --git a/pstl/test/std/algorithms/alg.nonmodifying/search_n.pass.cpp b/pstl/test/std/algorithms/alg.nonmodifying/search_n.pass.cpp new file mode 100644 index 00000000000..c0c6040e176 --- /dev/null +++ b/pstl/test/std/algorithms/alg.nonmodifying/search_n.pass.cpp @@ -0,0 +1,112 @@ +// -*- C++ -*- +//===-- search_n.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 +// +//===----------------------------------------------------------------------===// + +#include "support/pstl_test_config.h" + +#ifdef PSTL_STANDALONE_TESTS +#include "pstl/execution" +#include "pstl/algorithm" +#else +#include +#include +#endif // PSTL_STANDALONE_TESTS + +#include "support/utils.h" + +using namespace TestUtils; + +struct test_one_policy +{ +#if __PSTL_ICC_17_VC141_TEST_SIMD_LAMBDA_DEBUG_32_BROKEN || \ + __PSTL_ICC_16_VC14_TEST_SIMD_LAMBDA_DEBUG_32_BROKEN //dummy specialization by policy type, in case of broken configuration + template + void + operator()(pstl::execution::unsequenced_policy, Iterator b, Iterator e, Size count, const T& value, Predicate pred) + { + } + template + void + operator()(pstl::execution::parallel_unsequenced_policy, Iterator b, Iterator e, Size count, const T& value, + Predicate pred) + { + } +#endif + + template + void + operator()(ExecutionPolicy&& exec, Iterator b, Iterator e, Size count, const T& value, Predicate pred) + { + using namespace std; + auto expected = search_n(b, e, count, value, pred); + auto actual = search_n(exec, b, e, count, value); + EXPECT_TRUE(actual == expected, "wrong return result from search_n"); + + actual = search_n(exec, b, e, count, value, pred); + EXPECT_TRUE(actual == expected, "wrong return result from search_n with a predicate"); + } +}; + +template +void +test() +{ + + const std::size_t max_n1 = 100000; + const T value = T(1); + for (std::size_t n1 = 0; n1 <= max_n1; n1 = n1 <= 16 ? n1 + 1 : size_t(3.1415 * n1)) + { + std::size_t sub_n[] = {0, 1, 3, n1, (n1 * 10) / 8}; + std::size_t res[] = {0, 1, n1 / 2, n1}; + for (auto n2 : sub_n) + { + // Some of standard libraries return "first" in this case. We return "last" according to the standard + if (n2 == 0) + { + continue; + } + for (auto r : res) + { + Sequence in(n1, [n1](std::size_t k) { return T(0); }); + std::size_t i = r, isub = 0; + for (; i < n1 & isub < n2; ++i, ++isub) + in[i] = value; + + invoke_on_all_policies(test_one_policy(), in.begin(), in.begin() + n1, n2, value, std::equal_to()); + invoke_on_all_policies(test_one_policy(), in.cbegin(), in.cbegin() + n1, n2, value, std::equal_to()); + } + } + } +} + +template +struct test_non_const +{ + template + void + operator()(Policy&& exec, Iterator iter) + { + invoke_if(exec, [&]() { search_n(exec, iter, iter, 0, T(0), non_const(std::equal_to())); }); + } +}; + +int32_t +main() +{ + test(); + test(); + test(); +#if !__PSTL_ICC_16_17_TEST_REDUCTION_BOOL_TYPE_RELEASE_64_BROKEN + test(); +#endif + + test_algo_basic_single(run_for_rnd_fw>()); + + std::cout << done() << std::endl; + return 0; +} -- cgit v1.2.3