xref: /oneTBB/test/tbb/test_blocked_range.cpp (revision 478de5b1) 
1 /*
2     Copyright (c) 2005-2021 Intel Corporation
3 
4     Licensed under the Apache License, Version 2.0 (the "License");
5     you may not use this file except in compliance with the License.
6     You may obtain a copy of the License at
7 
8         http://www.apache.org/licenses/LICENSE-2.0
9 
10     Unless required by applicable law or agreed to in writing, software
11     distributed under the License is distributed on an "AS IS" BASIS,
12     WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13     See the License for the specific language governing permissions and
14     limitations under the License.
15 */
16 
17 #include "common/test.h"
18 #include "common/utils.h"
19 #include "common/utils_report.h"
20 #include "common/range_based_for_support.h"
21 #include "common/config.h"
22 #include "common/concepts_common.h"
23 
24 #include "tbb/blocked_range.h"
25 #include "tbb/blocked_range2d.h"
26 #include "tbb/blocked_range3d.h"
27 #define TBB_PREVIEW_BLOCKED_RANGE_ND 1
28 #include "tbb/blocked_rangeNd.h"
29 
30 //! \file test_blocked_range.cpp
31 //! \brief Test for [algorithms.blocked_range] specification
32 
33 #include <utility> //for std::pair
34 #include <functional>
35 #include <vector>
36 
37 //! Testing blocked_range with range based for
38 //! \brief \ref interface
39 TEST_CASE("Range based for") {
40     using namespace range_based_for_support_tests;
41 
42     const std::size_t sequence_length = 100;
43     std::size_t int_array[sequence_length] = {0};
44 
45     for (std::size_t i = 0; i < sequence_length; ++i) {
46         int_array[i] = i + 1;
47     }
48     const tbb::blocked_range<std::size_t*> r(int_array, int_array + sequence_length, 1);
49 
50     CHECK_MESSAGE(range_based_for_accumulate<std::size_t>(r, std::plus<std::size_t>(), std::size_t(0))
51             == gauss_summ_of_int_sequence(sequence_length), "incorrect accumulated value generated via range based for ?");
52 }
53 
54 //! Proportional split does not overflow with blocked range
55 //! \brief \ref error_guessing \ref boundary
56 TEST_CASE("Proportional split overflow") {
57     using tbb::blocked_range;
58     using tbb::proportional_split;
59 
60     blocked_range<std::size_t> r1(0, std::size_t(-1) / 2);
61     std::size_t size = r1.size();
62     std::size_t begin = r1.begin();
63     std::size_t end = r1.end();
64 
65     proportional_split p(1, 3);
66     blocked_range<std::size_t> r2(r1, p);
67 
68     // overflow-free computation
69     std::size_t parts = p.left() + p.right();
70     std::size_t int_part = size / parts;
71     std::size_t fraction = size - int_part * parts; // fraction < parts
72     std::size_t right_idx = int_part * p.right() + fraction * p.right() / parts + 1;
73     std::size_t newRangeBegin = end - right_idx;
74 
75     // Division in 'right_idx' very likely is inexact also.
76     std::size_t tolerance = 1;
77     std::size_t diff = (r2.begin() < newRangeBegin) ? (newRangeBegin - r2.begin()) : (r2.begin() - newRangeBegin);
78     bool is_split_correct = diff <= tolerance;
79     bool test_passed = (r1.begin() == begin && r1.end() == r2.begin() && is_split_correct &&
80                         r2.end() == end);
81     if (!test_passed) {
82         REPORT("Incorrect split of blocked range[%lu, %lu) into r1[%lu, %lu) and r2[%lu, %lu), "
83                "must be r1[%lu, %lu) and r2[%lu, %lu)\n", begin, end, r1.begin(), r1.end(), r2.begin(), r2.end(), begin, newRangeBegin, newRangeBegin, end);
84         CHECK(test_passed);
85     }
86 }
87 
88 #if __TBB_CPP20_CONCEPTS_PRESENT
89 
90 template <bool ExpectSatisfies, typename... Types>
91     requires (... && (utils::well_formed_instantiation<tbb::blocked_range, Types> == ExpectSatisfies))
test_blocked_range_constraint()92 void test_blocked_range_constraint() {}
93 
94 template <bool ExpectSatisfies, typename... Types>
95     requires (... && (utils::well_formed_instantiation<tbb::blocked_range2d, Types, Types> == ExpectSatisfies))
test_blocked_range2d_constraint()96 void test_blocked_range2d_constraint() {}
97 
98 template <typename... Types>
99     requires (... && (utils::well_formed_instantiation<tbb::blocked_range2d, Types, test_concepts::Dummy> == false))
test_blocked_range2d_col_invalid_constraint()100 void test_blocked_range2d_col_invalid_constraint() {}
101 
102 template <typename... Types>
103     requires (... && (utils::well_formed_instantiation<tbb::blocked_range2d, test_concepts::Dummy, Types> == false))
test_blocked_range2d_row_invalid_constraint()104 void test_blocked_range2d_row_invalid_constraint() {}
105 
106 template <bool ExpectSatisfies, typename... Types>
107     requires (... && (utils::well_formed_instantiation<tbb::blocked_range3d, Types, Types, Types> == ExpectSatisfies))
test_blocked_range3d_constraint()108 void test_blocked_range3d_constraint() {}
109 
110 template <typename... Types>
111     requires (... && (utils::well_formed_instantiation<tbb::blocked_range3d, test_concepts::Dummy, Types, Types> == false))
test_blocked_range3d_page_invalid_constraint()112 void test_blocked_range3d_page_invalid_constraint() {}
113 
114 template <typename... Types>
115     requires (... && (utils::well_formed_instantiation<tbb::blocked_range3d, Types, test_concepts::Dummy, Types> == false))
test_blocked_range3d_row_invalid_constraint()116 void test_blocked_range3d_row_invalid_constraint() {}
117 
118 template <typename... Types>
119     requires (... && (utils::well_formed_instantiation<tbb::blocked_range3d, Types, Types, test_concepts::Dummy> == false))
test_blocked_range3d_col_invalid_constraint()120 void test_blocked_range3d_col_invalid_constraint() {}
121 
122 template <typename T>
123 concept well_formed_blocked_range_Nd_instantiation_basic = requires {
124     typename tbb::blocked_rangeNd<T, 1>;
125 };
126 
127 template <typename... Types>
128 concept well_formed_blocked_range_Nd_instantiation = ( ... && well_formed_blocked_range_Nd_instantiation_basic<Types> );
129 
130 //! \brief \ref error_guessing
131 TEST_CASE("constraints for blocked_range value") {
132     using namespace test_concepts::blocked_range_value;
133     using const_iterator = typename std::vector<int>::const_iterator;
134 
135     test_blocked_range_constraint</*Expected = */true,
136                                   Correct, char, int, std::size_t, const_iterator>();
137 
138     test_blocked_range_constraint</*Expected = */false,
139                                   NonCopyable, NonCopyAssignable, NonDestructible,
140                                   NoOperatorLess, OperatorLessNonConst, WrongReturnOperatorLess,
141                                   NoOperatorMinus, OperatorMinusNonConst, WrongReturnOperatorMinus,
142                                   NoOperatorPlus, OperatorPlusNonConst, WrongReturnOperatorPlus>();
143 }
144 
145 //! \brief \ref error_guessing
146 TEST_CASE("constraints for blocked_range2d value") {
147     using namespace test_concepts::blocked_range_value;
148     using const_iterator = typename std::vector<int>::const_iterator;
149 
150     test_blocked_range2d_constraint</*Expected = */true,
151                                     Correct, char, int, std::size_t, const_iterator>();
152 
153     test_blocked_range2d_constraint</*Expected = */false,
154                                     NonCopyable, NonCopyAssignable, NonDestructible,
155                                     NoOperatorLess, OperatorLessNonConst, WrongReturnOperatorLess,
156                                     NoOperatorMinus, OperatorMinusNonConst, WrongReturnOperatorMinus,
157                                     NoOperatorPlus, OperatorPlusNonConst, WrongReturnOperatorPlus>();
158 
159     test_blocked_range2d_row_invalid_constraint<Correct, char, int, std::size_t, const_iterator>();
160     test_blocked_range2d_col_invalid_constraint<Correct, char, int, std::size_t, const_iterator>();
161 }
162 
163 //! \brief \ref error_guessing
164 TEST_CASE("constraints for blocked_range3d value") {
165     using namespace test_concepts::blocked_range_value;
166     using const_iterator = typename std::vector<int>::const_iterator;
167 
168     test_blocked_range3d_constraint</*Expected = */true,
169                                     Correct, char, int, std::size_t, const_iterator>();
170 
171     test_blocked_range3d_constraint</*Expected = */false,
172                                     NonCopyable, NonCopyAssignable, NonDestructible,
173                                     NoOperatorLess, OperatorLessNonConst, WrongReturnOperatorLess,
174                                     NoOperatorMinus, OperatorMinusNonConst, WrongReturnOperatorMinus,
175                                     NoOperatorPlus, OperatorPlusNonConst, WrongReturnOperatorPlus>();
176 
177     test_blocked_range3d_page_invalid_constraint<Correct, char, int, std::size_t, const_iterator>();
178     test_blocked_range3d_row_invalid_constraint<Correct, char, int, std::size_t, const_iterator>();
179     test_blocked_range3d_col_invalid_constraint<Correct, char, int, std::size_t, const_iterator>();
180 }
181 
182 //! \brief \ref error_guessing
183 TEST_CASE("constraints for blocked_rangeNd value") {
184     using namespace test_concepts::blocked_range_value;
185     using const_iterator = typename std::vector<int>::const_iterator;
186 
187     static_assert(well_formed_blocked_range_Nd_instantiation<Correct, char, int, std::size_t, const_iterator>);
188 
189     static_assert(!well_formed_blocked_range_Nd_instantiation<NonCopyable, NonCopyAssignable, NonDestructible,
190                                                               NoOperatorLess, OperatorLessNonConst, WrongReturnOperatorLess,
191                                                               NoOperatorMinus, OperatorMinusNonConst, WrongReturnOperatorMinus,
192                                                               NoOperatorPlus, OperatorPlusNonConst, WrongReturnOperatorPlus>);
193 }
194 
195 #endif // __TBB_CPP20_CONCEPTS_PRESENT
196