1/*
2 Copyright (c) 2005-2019 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 "tbb/blocked_range.h"
18#include "harness_assert.h"
19
20// First test as much as we can without including other headers.
21// Doing so should catch problems arising from failing to include headers.
22
23class AbstractValueType {
24 AbstractValueType() {}
25 int value;
26public:
27 friend AbstractValueType MakeAbstractValueType( int i );
28 friend int GetValueOf( const AbstractValueType& v ) {return v.value;}
29};
30
31AbstractValueType MakeAbstractValueType( int i ) {
32 AbstractValueType x;
33 x.value = i;
34 return x;
35}
36
37std::size_t operator-( const AbstractValueType& u, const AbstractValueType& v ) {
38 return GetValueOf(u) - GetValueOf(v);
39}
40
41bool operator<( const AbstractValueType& u, const AbstractValueType& v ) {
42 return GetValueOf(u) < GetValueOf(v);
43}
44
45AbstractValueType operator+( const AbstractValueType& u, std::size_t offset ) {
46 return MakeAbstractValueType(GetValueOf(u) + int(offset));
47}
48
49static void SerialTest() {
50 for( int x=-10; x<10; ++x )
51 for( int y=-10; y<10; ++y ) {
52 AbstractValueType i = MakeAbstractValueType(x);
53 AbstractValueType j = MakeAbstractValueType(y);
54 for( std::size_t k=1; k<10; ++k ) {
55 typedef tbb::blocked_range<AbstractValueType> range_type;
56 range_type r( i, j, k );
57 AssertSameType( r.empty(), true );
58 AssertSameType( range_type::size_type(), std::size_t() );
59 AssertSameType( static_cast<range_type::const_iterator*>(0), static_cast<AbstractValueType*>(0) );
60 AssertSameType( r.begin(), MakeAbstractValueType(0) );
61 AssertSameType( r.end(), MakeAbstractValueType(0) );
62 ASSERT( r.empty()==(y<=x), NULL );
63 ASSERT( r.grainsize()==k, NULL );
64 if( x<=y ) {
65 AssertSameType( r.is_divisible(), true );
66 ASSERT( r.is_divisible()==(std::size_t(y-x)>k), NULL );
67 ASSERT( r.size()==std::size_t(y-x), NULL );
68 if( r.is_divisible() ) {
69 tbb::blocked_range<AbstractValueType> r2(r,tbb::split());
70 ASSERT( GetValueOf(r.begin())==x, NULL );
71 ASSERT( GetValueOf(r.end())==GetValueOf(r2.begin()), NULL );
72 ASSERT( GetValueOf(r2.end())==y, NULL );
73 ASSERT( r.grainsize()==k, NULL );
74 ASSERT( r2.grainsize()==k, NULL );
75 }
76 }
77 }
78 }
79}
80
81#include "tbb/parallel_for.h"
82#include "harness.h"
83
84const int N = 1<<22;
85
86unsigned char Array[N];
87
88struct Striker {
89 // Note: we use <int> here instead of <long> in order to test for Quad 407676
90 void operator()( const tbb::blocked_range<int>& r ) const {
91 for( tbb::blocked_range<int>::const_iterator i=r.begin(); i!=r.end(); ++i )
92 ++Array[i];
93 }
94};
95
96void ParallelTest() {
97 for( int i=0; i<N; i=i<3 ? i+1 : i*3 ) {
98 const tbb::blocked_range<int> r( 0, i, 10 );
99 tbb::parallel_for( r, Striker() );
100 for( int k=0; k<N; ++k ) {
101 ASSERT( Array[k]==(k<i), NULL );
102 Array[k] = 0;
103 }
104 }
105}
106
107#if __TBB_RANGE_BASED_FOR_PRESENT
108#include "test_range_based_for.h"
109#include <functional>
110void TestRangeBasedFor() {
111 using namespace range_based_for_support_tests;
112 REMARK("testing range based for loop compatibility \n");
113
114 size_t int_array[100] = {0};
115 const size_t sequence_length = Harness::array_length(int_array);
116
117 for (size_t i = 0; i < sequence_length; ++i) {
118 int_array[i] = i + 1;
119 }
120
121 const tbb::blocked_range<size_t*> r(int_array, Harness::end(int_array), 1);
122
123 ASSERT(range_based_for_accumulate<size_t>(r, std::plus<size_t>(), size_t(0)) == gauss_summ_of_int_sequence(sequence_length), "incorrect accumulated value generated via range based for ?");
124}
125#endif //if __TBB_RANGE_BASED_FOR_PRESENT
126
127#if __TBB_USE_PROPORTIONAL_SPLIT_IN_BLOCKED_RANGES
128
129void TestProportionalSplitOverflow()
130{
131 REMARK("Testing overflow during proportional split - ");
132 using tbb::blocked_range;
133 using tbb::proportional_split;
134
135 blocked_range<size_t> r1(0, size_t(-1) / 2);
136 size_t size = r1.size();
137 size_t begin = r1.begin();
138 size_t end = r1.end();
139
140 proportional_split p(1, 3);
141 blocked_range<size_t> r2(r1, p);
142
143 // overflow-free computation
144 size_t parts = p.left() + p.right();
145 size_t int_part = size / parts;
146 size_t fraction = size - int_part * parts; // fraction < parts
147 size_t right_idx = int_part * p.right() + fraction * p.right() / parts + 1;
148 size_t newRangeBegin = end - right_idx;
149
150 // Division in 'right_idx' very likely is inexact also.
151 size_t tolerance = 1;
152 size_t diff = (r2.begin() < newRangeBegin) ? (newRangeBegin - r2.begin()) : (r2.begin() - newRangeBegin);
153 bool is_split_correct = diff <= tolerance;
154 bool test_passed = (r1.begin() == begin && r1.end() == r2.begin() && is_split_correct &&
155 r2.end() == end);
156 if (!test_passed) {
157 REPORT("Incorrect split of blocked range[%lu, %lu) into r1[%lu, %lu) and r2[%lu, %lu), "
158 "must be r1[%lu, %lu) and r2[%lu, %lu)\n", begin, end, r1.begin(), r1.end(), r2.begin(), r2.end(), begin, newRangeBegin, newRangeBegin, end);
159 ASSERT(test_passed, NULL);
160 }
161 REMARK("OK\n");
162}
163#endif /* __TBB_USE_PROPORTIONAL_SPLIT_IN_BLOCKED_RANGES */
164
165#if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
166void TestDeductionGuides() {
167 std::vector<const int *> v;
168
169 // check blocked_range(Value, Value, size_t)
170 tbb::blocked_range r1(v.begin(), v.end());
171 static_assert(std::is_same<decltype(r1), tbb::blocked_range<decltype(v)::iterator>>::value);
172
173 // check blocked_range(blocked_range &)
174 tbb::blocked_range r2(r1);
175 static_assert(std::is_same<decltype(r2), decltype(r1)>::value);
176
177 // check blocked_range(blocked_range &&)
178 tbb::blocked_range r3(std::move(r1));
179 static_assert(std::is_same<decltype(r3), decltype(r1)>::value);
180}
181#endif
182
183//------------------------------------------------------------------------
184// Test driver
185#include "tbb/task_scheduler_init.h"
186
187int TestMain () {
188 SerialTest();
189 for( int p=MinThread; p<=MaxThread; ++p ) {
190 tbb::task_scheduler_init init(p);
191 ParallelTest();
192 }
193
194 #if __TBB_RANGE_BASED_FOR_PRESENT
195 TestRangeBasedFor();
196 #endif //if __TBB_RANGE_BASED_FOR_PRESENT
197
198 #if __TBB_USE_PROPORTIONAL_SPLIT_IN_BLOCKED_RANGES
199 TestProportionalSplitOverflow();
200 #endif
201
202 #if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
203 TestDeductionGuides();
204 #endif
205 return Harness::Done;
206}
207