1/*
2 Copyright (c) 2017-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#define TBB_PREVIEW_BLOCKED_RANGE_ND 1
18#include "tbb/blocked_rangeNd.h"
19
20#include "tbb/tbb_config.h"
21
22#if __TBB_CPP11_PRESENT && __TBB_CPP11_ARRAY_PRESENT && __TBB_CPP11_TEMPLATE_ALIASES_PRESENT
23// AbstractValueType class represents Value concept's requirements in the most abstract way
24class AbstractValueType {
25 int value;
26 AbstractValueType() {}
27public:
28 friend AbstractValueType MakeAbstractValue(int i);
29 friend int GetValueOf(const AbstractValueType& v);
30};
31
32int GetValueOf(const AbstractValueType& v) { return v.value; }
33
34AbstractValueType MakeAbstractValue(int i) {
35 AbstractValueType x;
36 x.value = i;
37 return x;
38}
39
40// operator- returns amount of elements of AbstractValueType between u and v
41std::size_t operator-(const AbstractValueType& u, const AbstractValueType& v) {
42 return GetValueOf(u) - GetValueOf(v);
43}
44
45bool operator<(const AbstractValueType& u, const AbstractValueType& v) {
46 return GetValueOf(u) < GetValueOf(v);
47}
48
49AbstractValueType operator+(const AbstractValueType& u, std::size_t offset) {
50 return MakeAbstractValue(GetValueOf(u) + int(offset));
51}
52
53#include "harness_assert.h"
54#include <algorithm> // std::for_each
55#include <array>
56
57namespace internal {
58 template<typename range_t, unsigned int N>
59 struct utils {
60 using val_t = typename range_t::value_type;
61
62 template<typename EntityType, std::size_t DimSize>
63 using data_type = std::array<typename utils<range_t, N - 1>::template data_type<EntityType, DimSize>, DimSize>;
64
65 template<typename EntityType, std::size_t DimSize>
66 static void init_data(data_type<EntityType, DimSize>& data) {
67 std::for_each(data.begin(), data.end(), utils<range_t, N - 1>::template init_data<EntityType, DimSize>);
68 }
69
70 template<typename EntityType, std::size_t DimSize>
71 static void increment_data(const range_t& range, data_type<EntityType, DimSize>& data) {
72 auto begin = data.begin() + range.dim(N - 1).begin();
73 // same as "auto end = out.begin() + range.dim(N - 1).end();"
74 auto end = begin + range.dim(N - 1).size();
75 for (auto i = begin; i != end; ++i) {
76 utils<range_t, N - 1>::template increment_data<EntityType, DimSize>(range, *i);
77 }
78 }
79
80 template<typename EntityType, std::size_t DimSize>
81 static void check_data(const range_t& range, data_type<EntityType, DimSize>& data) {
82 auto begin = data.begin() + range.dim(N - 1).begin();
83 // same as "auto end = out.begin() + range.dim(N - 1).end();"
84 auto end = begin + range.dim(N - 1).size();
85 for (auto i = begin; i != end; ++i) {
86 utils<range_t, N - 1>::template check_data<EntityType, DimSize>(range, *i);
87 }
88 }
89
90 template<typename input_t, std::size_t... Is>
91 static range_t make_range(std::size_t shift, bool negative, val_t(*gen)(input_t), tbb::internal::index_sequence<Is...>) {
92 return range_t( { {
93 /* begin =*/gen(negative ? -input_t(Is + shift) : 0),
94 /* end =*/gen(input_t(Is + shift)),
95 /*grainsize =*/Is + 1}
96 /*pack expansion*/... } );
97 }
98
99 static bool is_empty(const range_t& range) {
100 if (range.dim(N - 1).empty()) { return true; }
101 return utils<range_t, N - 1>::is_empty(range);
102 }
103
104 static bool is_divisible(const range_t& range) {
105 if (range.dim(N - 1).is_divisible()) { return true; }
106 return utils<range_t, N - 1>::is_divisible(range);
107 }
108
109 static void check_splitting(const range_t& range_split, const range_t& range_new, int(*get)(const val_t&), bool split_checker = false) {
110 if (get(range_split.dim(N - 1).begin()) == get(range_new.dim(N - 1).begin())) {
111 ASSERT(get(range_split.dim(N - 1).end()) == get(range_new.dim(N - 1).end()), NULL);
112 }
113 else {
114 ASSERT(get(range_split.dim(N - 1).end()) == get(range_new.dim(N - 1).begin()) && !split_checker, NULL);
115 split_checker = true;
116 }
117 utils<range_t, N - 1>::check_splitting(range_split, range_new, get, split_checker);
118 }
119
120 };
121
122 template<typename range_t>
123 struct utils<range_t, 0> {
124 using val_t = typename range_t::value_type;
125
126 template<typename EntityType, std::size_t DimSize>
127 using data_type = EntityType;
128
129 template<typename EntityType, std::size_t DimSize>
130 static void init_data(data_type<EntityType, DimSize>& data) { data = 0; }
131
132 template<typename EntityType, std::size_t DimSize>
133 static void increment_data(const range_t&, data_type<EntityType, DimSize>& data) { ++data; }
134
135 template<typename EntityType, std::size_t DimSize>
136 static void check_data(const range_t&, data_type<EntityType, DimSize>& data) {
137 ASSERT(data == 1, NULL);
138 }
139
140 static bool is_empty(const range_t&) { return false; }
141
142 static bool is_divisible(const range_t&) { return false; }
143
144 static void check_splitting(const range_t&, const range_t&, int(*)(const val_t&), bool) {}
145 };
146
147 // We need MakeInt function to pass it into make_range as factory function
148 // because of matching make_range with AbstractValueType and other types too
149 int MakeInt(int i) { return i; }
150}
151
152template<unsigned int DimAmount>
153void SerialTest() {
154 __TBB_STATIC_ASSERT((tbb::blocked_rangeNd<int, DimAmount>::ndims()
155 == tbb::blocked_rangeNd<AbstractValueType, DimAmount>::ndims()),
156 "different amount of dimensions");
157
158 using range_t = tbb::blocked_rangeNd<AbstractValueType, DimAmount>;
159 // 'typedef' instead of 'using' because of GCC 4.7.2 bug on Debian 7.0
160 typedef internal::utils<range_t, DimAmount> utils;
161
162 // Generate empty range
163 range_t r = utils::make_range(0, true, &MakeAbstractValue, tbb::internal::make_index_sequence<DimAmount>());
164
165 AssertSameType(r.is_divisible(), bool());
166 AssertSameType(r.empty(), bool());
167 AssertSameType(range_t::ndims(), 0U);
168
169 ASSERT(r.empty() == utils::is_empty(r) && r.empty(), NULL);
170 ASSERT(r.is_divisible() == utils::is_divisible(r), NULL);
171
172 // Generate not-empty range divisible range
173 r = utils::make_range(1, true, &MakeAbstractValue, tbb::internal::make_index_sequence<DimAmount>());
174 ASSERT(r.empty() == utils::is_empty(r) && !r.empty(), NULL);
175 ASSERT(r.is_divisible() == utils::is_divisible(r) && r.is_divisible(), NULL);
176
177 range_t r_new(r, tbb::split());
178 utils::check_splitting(r, r_new, &GetValueOf);
179
180 SerialTest<DimAmount - 1>();
181}
182template<> void SerialTest<0>() {}
183
184#include "tbb/parallel_for.h"
185
186template<unsigned int DimAmount>
187void ParallelTest() {
188 using range_t = tbb::blocked_rangeNd<int, DimAmount>;
189 // 'typedef' instead of 'using' because of GCC 4.7.2 bug on Debian 7.0
190 typedef internal::utils<range_t, DimAmount> utils;
191
192 // Max size is 1 << 20 - 1 bytes
193 // Thus size of one dimension's elements is 1 << (20 / DimAmount - 1) bytes
194 typename utils::template data_type<unsigned char, 1 << (20 / DimAmount - 1)> data;
195 utils::init_data(data);
196
197 range_t r = utils::make_range((1 << (20 / DimAmount - 1)) - DimAmount, false, &internal::MakeInt, tbb::internal::make_index_sequence<DimAmount>());
198
199 tbb::parallel_for(r, [&data](const range_t& range) {
200 utils::increment_data(range, data);
201 });
202
203 utils::check_data(r, data);
204
205 ParallelTest<DimAmount - 1>();
206}
207template<> void ParallelTest<0>() {}
208
209void TestCtors() {
210 tbb::blocked_rangeNd<int, 1>{ { 0,13,3 } };
211
212 tbb::blocked_rangeNd<int, 1>{ tbb::blocked_range<int>{ 0,13,3 } };
213
214 tbb::blocked_rangeNd<int, 2>(tbb::blocked_range<int>(-8923, 8884, 13), tbb::blocked_range<int>(-8923, 5, 13));
215
216 tbb::blocked_rangeNd<int, 2>({ -8923, 8884, 13 }, { -8923, 8884, 13 });
217
218 tbb::blocked_range<int> r1(0, 13);
219
220 tbb::blocked_range<int> r2(-12, 23);
221
222 tbb::blocked_rangeNd<int, 2>({ { -8923, 8884, 13 }, r1});
223
224 tbb::blocked_rangeNd<int, 2>({ r2, r1 });
225
226 tbb::blocked_rangeNd<int, 2>(r1, r2);
227
228 tbb::blocked_rangeNd<AbstractValueType, 4>({ MakeAbstractValue(-3), MakeAbstractValue(13), 8 },
229 { MakeAbstractValue(-53), MakeAbstractValue(23), 2 },
230 { MakeAbstractValue(-23), MakeAbstractValue(33), 1 },
231 { MakeAbstractValue(-13), MakeAbstractValue(43), 7 });
232}
233
234static const std::size_t N = 4;
235
236#include "harness.h"
237#include "tbb/task_scheduler_init.h"
238
239int TestMain() {
240 TestCtors();
241 SerialTest<N>();
242 for( int p=MinThread; p<= MaxThread; ++p ) {
243 tbb::task_scheduler_init init(p);
244 ParallelTest<N>();
245 }
246 return Harness::Done;
247}
248
249#else
250
251// tbb::blocked_rangeNd requires C++11 support
252#define HARNESS_SKIP_TEST 1
253#include "harness.h"
254
255#endif /* __TBB_CPP11_PRESENT && __TBB_CPP11_ARRAY_PRESENT && __TBB_CPP11_TEMPLATE_ALIASES_PRESENT */
256