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

14 files changed, 1719 insertions, 0 deletions

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 <execution>
+#include <algorithm>
+#endif // PSTL_STANDALONE_TESTS
+
+#include "support/utils.h"
+
+using namespace TestUtils;
+
+struct test_adjacent_find
+{
+    template <typename Policy, typename Iterator, typename Pred>
+    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 <typename T>
+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<T> 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<T>());
+            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<T>());
+            invoke_on_all_policies(test_adjacent_find(), in.cbegin(), in.cend(), std::equal_to<T>());
+        }
+    }
+
+    //special cases: size=0, size=1;
+    for (int32_t expect = 0; expect < 1; ++expect)
+    {
+        Sequence<T> in(expect, [](int32_t v) -> T { return T(v); }); //fill 0...n
+        auto i = std::adjacent_find(in.cbegin(), in.cend(), std::equal_to<T>());
+        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<T>());
+        invoke_on_all_policies(test_adjacent_find(), in.cbegin(), in.cend(), std::equal_to<T>());
+    }
+
+    //special cases:
+    Sequence<T> a1 = {5, 5, 5, 6, 7, 8, 9};
+    invoke_on_all_policies(test_adjacent_find(), a1.begin(), a1.end(), std::equal_to<T>());
+    invoke_on_all_policies(test_adjacent_find(), a1.begin() + 1, a1.end(), std::equal_to<T>());
+
+    invoke_on_all_policies(test_adjacent_find(), a1.cbegin(), a1.cend(), std::equal_to<T>());
+    invoke_on_all_policies(test_adjacent_find(), a1.cbegin() + 1, a1.cend(), std::equal_to<T>());
+
+    Sequence<T> a2 = {5, 6, 7, 8, 9, 9};
+    invoke_on_all_policies(test_adjacent_find(), a2.begin(), a2.end(), std::equal_to<T>());
+    invoke_on_all_policies(test_adjacent_find(), a2.begin(), a2.end() - 1, std::equal_to<T>());
+
+    invoke_on_all_policies(test_adjacent_find(), a2.cbegin(), a2.cend(), std::equal_to<T>());
+    invoke_on_all_policies(test_adjacent_find(), a2.cbegin(), a2.cend() - 1, std::equal_to<T>());
+
+    Sequence<T> a3 = {5, 6, 6, 6, 7, 9, 9, 9, 9};
+    invoke_on_all_policies(test_adjacent_find(), a3.begin(), a3.end(), std::equal_to<T>());
+
+    invoke_on_all_policies(test_adjacent_find(), a3.cbegin(), a3.cend(), std::equal_to<T>());
+}
+
+template <typename T>
+struct test_non_const
+{
+    template <typename Policy, typename Iterator>
+    void
+    operator()(Policy&& exec, Iterator iter)
+    {
+        adjacent_find(exec, iter, iter, non_const(std::equal_to<T>()));
+    }
+};
+
+int32_t
+main()
+{
+
+    test_adjacent_find_by_type<int32_t>();
+    test_adjacent_find_by_type<float64_t>();
+
+    test_algo_basic_single<int32_t>(run_for_rnd_bi<test_non_const<int32_t>>());
+
+    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 <execution>
+#include <algorithm>
+#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 <typename ExecutionPolicy, typename Iterator, typename Predicate>
+    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 <typename T>
+struct Parity
+{
+    bool parity;
+
+  public:
+    Parity(bool parity_) : parity(parity_) {}
+    bool
+    operator()(T value) const
+    {
+        return (size_t(value) ^ parity) % 2 == 0;
+    }
+};
+
+template <typename T>
+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<T> 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<T> inCopy(in);
+
+        invoke_on_all_policies(test_all_of(), in.begin(), in.end(), Parity<T>(1), true);
+        invoke_on_all_policies(test_all_of(), in.cbegin(), in.cend(), Parity<T>(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<T>(1), false);
+            invoke_on_all_policies(test_all_of(), in.cbegin(), in.cend(), Parity<T>(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<T>(1), false);
+            invoke_on_all_policies(test_all_of(), in.cbegin(), in.cend(), Parity<T>(1), false);
+        }
+    }
+}
+
+struct test_non_const
+{
+    template <typename Policy, typename Iterator>
+    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<int32_t>(8 * sizeof(int32_t));
+    test<uint16_t>(8 * sizeof(uint16_t));
+    test<float64_t>(53);
+#if !__PSTL_ICC_16_17_TEST_REDUCTION_BOOL_TYPE_RELEASE_64_BROKEN
+    test<bool>(1);
+#endif
+
+    test_algo_basic_single<int32_t>(run_for_rnd_fw<test_non_const>());
+
+    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 <execution>
+#include <algorithm>
+#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 <typename ExecutionPolicy, typename Iterator, typename Predicate>
+    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 <typename T>
+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<T> 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<T> inCopy(in);
+
+        invoke_on_all_policies(test_any_of(), in.begin(), in.end(), is_equal_to<T>(spike), false);
+        invoke_on_all_policies(test_any_of(), in.cbegin(), in.cend(), is_equal_to<T>(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<T>(spike), true);
+            invoke_on_all_policies(test_any_of(), in.cbegin(), in.cend(), is_equal_to<T>(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<T>(spike), true);
+            invoke_on_all_policies(test_any_of(), in.cbegin(), in.cend(), is_equal_to<T>(spike), true);
+        }
+    }
+}
+
+struct test_non_const
+{
+    template <typename Policy, typename Iterator>
+    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<int32_t>(8 * sizeof(int32_t));
+    test<uint16_t>(8 * sizeof(uint16_t));
+    test<float64_t>(53);
+#if !__PSTL_ICC_16_17_TEST_REDUCTION_BOOL_TYPE_RELEASE_64_BROKEN
+    test<bool>(1);
+#endif
+
+    test_algo_basic_single<int32_t>(run_for_rnd_fw<test_non_const>());
+
+    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 <execution>
+#include <algorithm>
+#endif // PSTL_STANDALONE_TESTS
+
+#include "support/utils.h"
+
+using namespace TestUtils;
+
+struct test_count
+{
+    template <typename Policy, typename Iterator, typename T>
+    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 <typename Policy, typename Iterator, typename Predicate>
+    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 <typename T>
+class IsEqual
+{
+    T value;
+
+  public:
+    IsEqual(T value_, OddTag) : value(value_) {}
+    bool
+    operator()(const T& x) const
+    {
+        return x == value;
+    }
+};
+
+template <typename In, typename T, typename Predicate, typename Convert>
+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> 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 <typename Policy, typename Iterator>
+    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<int32_t>(42, IsEqual<int32_t>(50, OddTag()), [](int32_t j) { return j; });
+#if !__PSTL_ICC_16_17_TEST_REDUCTION_RELEASE_BROKEN
+    test<int32_t>(42, [](const int32_t& x) { return true; }, [](int32_t j) { return j; });
+#endif
+    test<float64_t>(42, IsEqual<float64_t>(50, OddTag()), [](int32_t j) { return float64_t(j); });
+    test<Number>(Number(42, OddTag()), IsEqual<Number>(Number(50, OddTag()), OddTag()),
+                 [](int32_t j) { return Number(j, OddTag()); });
+
+    test_algo_basic_single<int32_t>(run_for_rnd_fw<test_non_const>());
+
+    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 <execution>
+#include <algorithm>
+#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 <typename ExecutionPolicy, typename Iterator1, typename Iterator2>
+    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 <typename T>
+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<T> in(n, [bits](size_t k) { return T(2 * HashBits(k, bits - 1) ^ 1); });
+        Sequence<T> 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 <typename T>
+struct test_non_const
+{
+    template <typename Policy, typename FirstIterator, typename SecondInterator>
+    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<T>()));
+    }
+};
+
+int32_t
+main()
+{
+
+    test<int32_t>(8 * sizeof(int32_t));
+    test<uint16_t>(8 * sizeof(uint16_t));
+    test<float64_t>(53);
+#if !__PSTL_ICC_16_17_TEST_REDUCTION_BOOL_TYPE_RELEASE_64_BROKEN
+    test<bool>(1);
+#endif
+    test<UserType>(256);
+
+    test_algo_basic_double<int32_t>(run_for_rnd_fw<test_non_const<int32_t>>());
+
+    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 <execution>
+#include <algorithm>
+#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 <typename Iterator, typename Value>
+    void
+    operator()(pstl::execution::unsequenced_policy, Iterator first, Iterator last, Value value)
+    {
+    }
+    template <typename Iterator, typename Value>
+    void
+    operator()(pstl::execution::parallel_unsequenced_policy, Iterator first, Iterator last, Value value)
+    {
+    }
+#endif
+
+    template <typename Policy, typename Iterator, typename Value>
+    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 <typename T, typename Value, typename Hit, typename Miss>
+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<T> 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<Number>(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<float32_t>(-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 <execution>
+#include <algorithm>
+#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 <typename Iterator1, typename Iterator2, typename Predicate>
+    void
+    operator()(pstl::execution::unsequenced_policy, Iterator1 b, Iterator1 e, Iterator2 bsub, Iterator2 esub,
+               Predicate pred)
+    {
+    }
+    template <typename Iterator1, typename Iterator2, typename Predicate>
+    void
+    operator()(pstl::execution::parallel_unsequenced_policy, Iterator1 b, Iterator1 e, Iterator2 bsub, Iterator2 esub,
+               Predicate pred)
+    {
+    }
+#endif
+
+    template <typename ExecutionPolicy, typename Iterator1, typename Iterator2, typename Predicate>
+    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 <typename T>
+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<T> in(max_n1, [max_n1, bits](std::size_t k) { return T(2 * HashBits(max_n1, bits - 1) ^ 1); });
+    Sequence<T> 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<T>());
+                invoke_on_all_policies(test_one_policy(), in.cbegin(), in.cbegin() + n1, sub.cbegin(),
+                                       sub.cbegin() + n2, std::equal_to<T>());
+            }
+        }
+    }
+}
+
+template <typename T>
+struct test_non_const
+{
+    template <typename Policy, typename FirstIterator, typename SecondInterator>
+    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<T>()));
+            search(exec, first_iter, first_iter, second_iter, second_iter, non_const(std::equal_to<T>()));
+        });
+    }
+};
+
+int32_t
+main()
+{
+    test<int32_t>(8 * sizeof(int32_t));
+    test<uint16_t>(8 * sizeof(uint16_t));
+    test<float64_t>(53);
+#if !__PSTL_ICC_16_17_TEST_REDUCTION_BOOL_TYPE_RELEASE_64_BROKEN
+    test<bool>(1);
+#endif
+
+    test_algo_basic_double<int32_t>(run_for_rnd_fw<test_non_const<int32_t>>());
+
+    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 <execution>
+#include <algorithm>
+#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 <typename Iterator1, typename Iterator2, typename Predicate>
+    void
+    operator()(pstl::execution::unsequenced_policy, Iterator1 b, Iterator1 e, Iterator2 bsub, Iterator2 esub,
+               Predicate pred)
+    {
+    }
+    template <typename Iterator1, typename Iterator2, typename Predicate>
+    void
+    operator()(pstl::execution::parallel_unsequenced_policy, Iterator1 b, Iterator1 e, Iterator2 bsub, Iterator2 esub,
+               Predicate pred)
+    {
+    }
+#endif
+
+    template <typename ExecutionPolicy, typename Iterator1, typename Iterator2, typename Predicate>
+    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 <typename T, typename Predicate>
+void
+test(Predicate pred)
+{
+
+    const std::size_t max_n1 = 1000;
+    const std::size_t max_n2 = (max_n1 * 10) / 8;
+    Sequence<T> in1(max_n1, [](std::size_t k) { return T(1); });
+    Sequence<T> 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 <typename T>
+struct test_non_const
+{
+    template <typename Policy, typename FirstIterator, typename SecondInterator>
+    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<T>()));
+        });
+    }
+};
+
+int32_t
+main()
+{
+    test<int32_t>(std::equal_to<int32_t>());
+    test<uint16_t>(std::not_equal_to<uint16_t>());
+    test<float64_t>([](const float64_t x, const float64_t y) { return x * x == y * y; });
+
+    test_algo_basic_double<int32_t>(run_for_rnd_fw<test_non_const<int32_t>>());
+
+    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 <execution>
+#include <algorithm>
+#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 <typename Iterator, typename Predicate, typename NotPredicate>
+    void
+    operator()(pstl::execution::unsequenced_policy, Iterator first, Iterator last, Predicate pred,
+               NotPredicate not_pred)
+    {
+    }
+    template <typename Iterator, typename Predicate, typename NotPredicate>
+    void
+    operator()(pstl::execution::parallel_unsequenced_policy, Iterator first, Iterator last, Predicate pred,
+               NotPredicate not_pred)
+    {
+    }
+#endif
+
+    template <typename Policy, typename Iterator, typename Predicate, typename NotPredicate>
+    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 <typename T, typename Predicate, typename Hit, typename Miss>
+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<T> 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 <typename Policy, typename Iterator>
+    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<Number>(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>([](float32_t x) { return x >= 0; }, [](float32_t j) { return j * j; },
+                    [](float32_t j) { return -1 - j * j; });
+
+    test_algo_basic_single<int32_t>(run_for_rnd_fw<test_non_const>());
+
+    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 <execution>
+#include <algorithm>
+#endif // PSTL_STANDALONE_TESTS
+
+#include "support/utils.h"
+
+using namespace TestUtils;
+
+template <typename Type>
+struct Gen
+{
+    Type
+    operator()(std::size_t k)
+    {
+        return Type(k % 5 != 1 ? 3 * k - 7 : 0);
+    };
+};
+
+template <typename T>
+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 <typename Policy, typename Iterator, typename Size>
+    void
+    operator()(Policy&& exec, Iterator first, Iterator last, Iterator expected_first, Iterator expected_last, Size n)
+    {
+        typedef typename std::iterator_traits<Iterator>::value_type T;
+
+        // Try for_each
+        std::for_each(expected_first, expected_last, Flip<T>(1));
+        for_each(exec, first, last, Flip<T>(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<T>(1));
+        for_each_n(exec, first, n, Flip<T>(1));
+        EXPECT_EQ_N(expected_first, first, n, "wrong effect from for_each_n");
+    }
+};
+
+template <typename T>
+void
+test()
+{
+    for (size_t n = 0; n <= 100000; n = n <= 16 ? n + 1 : size_t(3.1415 * n))
+    {
+        Sequence<T> inout(n, Gen<T>());
+        Sequence<T> expected(n, Gen<T>());
+        invoke_on_all_policies(test_one_policy(), inout.begin(), inout.end(), expected.begin(), expected.end(),
+                               inout.size());
+    }
+}
+
+struct test_non_const
+{
+    template <typename Policy, typename Iterator>
+    void
+    operator()(Policy&& exec, Iterator iter)
+    {
+        invoke_if(exec, [&]() {
+            auto f = [](typename std::iterator_traits<Iterator>::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<int32_t>();
+    test<uint16_t>();
+    test<float64_t>();
+
+    test_algo_basic_single<int32_t>(run_for_rnd_fw<test_non_const>());
+
+    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 <execution>
+#include <algorithm>
+#endif // PSTL_STANDALONE_TESTS
+
+#include "support/utils.h"
+
+using namespace TestUtils;
+
+struct test_mismatch
+{
+    template <typename Policy, typename Iterator1, typename Iterator2>
+    void
+    operator()(Policy&& exec, Iterator1 first1, Iterator1 last1, Iterator2 first2)
+    {
+        using namespace std;
+        typedef typename iterator_traits<Iterator1>::value_type T;
+        {
+            const auto expected = std::mismatch(first1, last1, first2, std::equal_to<T>());
+            const auto res3 = mismatch(exec, first1, last1, first2, std::equal_to<T>());
+            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 <typename Policy, typename Iterator1, typename Iterator2>
+    void
+    operator()(Policy&& exec, Iterator1 first1, Iterator1 last1, Iterator2 first2, Iterator2 last2)
+    {
+        using namespace std;
+        typedef typename iterator_traits<Iterator1>::value_type T;
+        {
+            const auto expected = mismatch(pstl::execution::seq, first1, last1, first2, last2, std::equal_to<T>());
+            const auto res1 = mismatch(exec, first1, last1, first2, last2, std::equal_to<T>());
+            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 <typename T>
+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<T> in(size, [](size_t v) -> T { return T(v % 100); });
+        {
+            Sequence<T> 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<T> 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<T> 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 <typename T>
+struct test_non_const
+{
+    template <typename Policy, typename FirstIterator, typename SecondInterator>
+    void
+    operator()(Policy&& exec, FirstIterator first_iter, SecondInterator second_iter)
+    {
+        mismatch(exec, first_iter, first_iter, second_iter, second_iter, non_const(std::less<T>()));
+    }
+};
+
+int32_t
+main()
+{
+
+    test_mismatch_by_type<int32_t>();
+    test_mismatch_by_type<float64_t>();
+    test_mismatch_by_type<Wrapper<int32_t>>();
+
+    test_algo_basic_double<int32_t>(run_for_rnd_fw<test_non_const<int32_t>>());
+
+    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 <execution>
+#include <algorithm>
+#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 <typename ExecutionPolicy, typename Iterator, typename Predicate>
+    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 <typename T>
+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<T> 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<T>(spike), true);
+        invoke_on_all_policies(test_none_of(), in.cbegin(), in.cend(), is_equal_to<T>(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<T>(spike), false);
+            invoke_on_all_policies(test_none_of(), in.cbegin(), in.cend(), is_equal_to<T>(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<T>(spike), false);
+            invoke_on_all_policies(test_none_of(), in.cbegin(), in.cend(), is_equal_to<T>(spike), false);
+        }
+    }
+}
+
+struct test_non_const
+{
+    template <typename Policy, typename Iterator>
+    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<int32_t>(8 * sizeof(int32_t));
+    test<uint16_t>(8 * sizeof(uint16_t));
+    test<float64_t>(53);
+#if !__PSTL_ICC_16_17_TEST_REDUCTION_BOOL_TYPE_RELEASE_64_BROKEN
+    test<bool>(1);
+#endif
+
+    test_algo_basic_single<int32_t>(run_for_rnd_fw<test_non_const>());
+
+    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 <algorithm>
+#include <iostream>
+#include "pstl/execution"
+#include "pstl/algorithm"
+
+#else
+#include <execution>
+#include <algorithm>
+#endif // PSTL_STANDALONE_TESTS
+
+#include "support/utils.h"
+
+using namespace TestUtils;
+
+// User defined type with minimal requirements
+template <typename T>
+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<T>& input)
+    {
+        return stream << input.my_val;
+    }
+
+  private:
+    T my_val;
+};
+
+template <typename T>
+bool
+is_equal(const DataType<T>& x, const DataType<T>& y)
+{
+    return x.get_val() == y.get_val();
+}
+
+template <typename T>
+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 Iterator1, typename Size, typename Generator1, typename Generator2, typename Compare>
+    typename std::enable_if<is_same_iterator_category<Iterator1, std::random_access_iterator_tag>::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 Iterator1, typename Size, typename Generator1, typename Generator2, typename Compare>
+    typename std::enable_if<is_same_iterator_category<Iterator1, std::random_access_iterator_tag>::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 Policy, typename Iterator1, typename Size, typename Generator1, typename Generator2,
+              typename Compare>
+    typename std::enable_if<is_same_iterator_category<Iterator1, std::random_access_iterator_tag>::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<Iterator1>::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 Policy, typename Iterator1, typename Size, typename Generator1, typename Generator2,
+              typename Compare>
+    typename std::enable_if<!is_same_iterator_category<Iterator1, std::random_access_iterator_tag>::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 <typename T, typename Generator1, typename Generator2, typename Compare>
+void
+test_by_type(Generator1 generator1, Generator2 generator2, Compare comp)
+{
+    using namespace std;
+    size_t max_size = 10000;
+    Sequence<T> in1(max_size, [](size_t v) { return T(v); });
+    Sequence<T> 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 <typename T>
+struct test_non_const
+{
+    template <typename Policy, typename Iterator>
+    void
+    operator()(Policy&& exec, Iterator iter)
+    {
+        invoke_if(exec, [&]() { nth_element(exec, iter, iter, iter, non_const(std::less<T>())); });
+    }
+};
+
+int32_t
+main()
+{
+    test_by_type<int32_t>([](int32_t i) { return 10 * i; }, [](int32_t i) { return i + 1; }, std::less<int32_t>());
+    test_by_type<int32_t>([](int32_t) { return 0; }, [](int32_t) { return 0; }, std::less<int32_t>());
+
+    test_by_type<float64_t>([](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<DataType<float32_t>>(
+        [](int32_t i) { return DataType<float32_t>(2 * i + 1); }, [](int32_t i) { return DataType<float32_t>(2 * i); },
+        [](const DataType<float32_t>& x, const DataType<float32_t>& y) { return x.get_val() < y.get_val(); });
+
+    test_algo_basic_single<int32_t>(run_for_rnd<test_non_const<int32_t>>());
+
+    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 <execution>
+#include <algorithm>
+#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 <typename Iterator, typename Size, typename T, typename Predicate>
+    void
+    operator()(pstl::execution::unsequenced_policy, Iterator b, Iterator e, Size count, const T& value, Predicate pred)
+    {
+    }
+    template <typename Iterator, typename Size, typename T, typename Predicate>
+    void
+    operator()(pstl::execution::parallel_unsequenced_policy, Iterator b, Iterator e, Size count, const T& value,
+               Predicate pred)
+    {
+    }
+#endif
+
+    template <typename ExecutionPolicy, typename Iterator, typename Size, typename T, typename Predicate>
+    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 <typename T>
+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<T> 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<T>());
+                invoke_on_all_policies(test_one_policy(), in.cbegin(), in.cbegin() + n1, n2, value, std::equal_to<T>());
+            }
+        }
+    }
+}
+
+template <typename T>
+struct test_non_const
+{
+    template <typename Policy, typename Iterator>
+    void
+    operator()(Policy&& exec, Iterator iter)
+    {
+        invoke_if(exec, [&]() { search_n(exec, iter, iter, 0, T(0), non_const(std::equal_to<T>())); });
+    }
+};
+
+int32_t
+main()
+{
+    test<int32_t>();
+    test<uint16_t>();
+    test<float64_t>();
+#if !__PSTL_ICC_16_17_TEST_REDUCTION_BOOL_TYPE_RELEASE_64_BROKEN
+    test<bool>();
+#endif
+
+    test_algo_basic_single<int32_t>(run_for_rnd_fw<test_non_const<int32_t>>());
+
+    std::cout << done() << std::endl;
+    return 0;
+}