1 // -*- C++ -*-
2 //===-- utils.h -----------------------------------------------------------===//
3 //
4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5 // See https://llvm.org/LICENSE.txt for license information.
6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //
8 //===----------------------------------------------------------------------===//
9
10 // File contains common utilities that tests rely on
11
12 // Do not #include <algorithm>, because if we do we will not detect accidental dependencies.
13 #include <sstream>
14 #include <iostream>
15 #include <cstring>
16 #include <iterator>
17 #include <vector>
18 #include <atomic>
19 #include <memory>
20 #include <cstdint>
21
22 #include "pstl_test_config.h"
23
24 namespace TestUtils
25 {
26
27 typedef double float64_t;
28 typedef float float32_t;
29
30 template <class T, std::size_t N>
31 constexpr size_t
const_size(const T (& array)[N])32 const_size(const T (&array)[N]) noexcept
33 {
34 return N;
35 }
36
37 template <typename T>
38 class Sequence;
39
40 // Handy macros for error reporting
41 #define EXPECT_TRUE(condition, message) TestUtils::expect<true>(condition, __FILE__, __LINE__, message)
42 #define EXPECT_FALSE(condition, message) TestUtils::expect<false>(condition, __FILE__, __LINE__, message)
43
44 // Check that expected and actual are equal and have the same type.
45 #define EXPECT_EQ(expected, actual, message) TestUtils::expect_equal(expected, actual, __FILE__, __LINE__, message)
46
47 // Check that sequences started with expected and actual and have had size n are equal and have the same type.
48 #define EXPECT_EQ_N(expected, actual, n, message) \
49 TestUtils::expect_equal(expected, actual, n, __FILE__, __LINE__, message)
50
51 // Issue error message from outstr, adding a newline.
52 // Real purpose of this routine is to have a place to hang a breakpoint.
53 static void
issue_error_message(std::stringstream & outstr)54 issue_error_message(std::stringstream& outstr)
55 {
56 outstr << std::endl;
57 std::cerr << outstr.str();
58 }
59
60 template <bool B>
61 void
expect(bool condition,const char * file,int32_t line,const char * message)62 expect(bool condition, const char* file, int32_t line, const char* message)
63 {
64 // Templating this function is somewhat silly, but avoids the need to declare it static
65 // or have a separate translation unit.
66 if (condition != B)
67 {
68 std::stringstream outstr;
69 outstr << "error at " << file << ":" << line << " - " << message;
70 issue_error_message(outstr);
71 }
72 }
73
74 // Do not change signature to const T&.
75 // Function must be able to detect const differences between expected and actual.
76 template <typename T>
77 void
expect_equal(T & expected,T & actual,const char * file,int32_t line,const char * message)78 expect_equal(T& expected, T& actual, const char* file, int32_t line, const char* message)
79 {
80 if (!(expected == actual))
81 {
82 std::stringstream outstr;
83 outstr << "error at " << file << ":" << line << " - " << message << ", expected " << expected << " got "
84 << actual;
85 issue_error_message(outstr);
86 }
87 }
88
89 template <typename T>
90 void
expect_equal(Sequence<T> & expected,Sequence<T> & actual,const char * file,int32_t line,const char * message)91 expect_equal(Sequence<T>& expected, Sequence<T>& actual, const char* file, int32_t line, const char* message)
92 {
93 size_t n = expected.size();
94 size_t m = actual.size();
95 if (n != m)
96 {
97 std::stringstream outstr;
98 outstr << "error at " << file << ":" << line << " - " << message << ", expected sequence of size " << n
99 << " got sequence of size " << m;
100 issue_error_message(outstr);
101 return;
102 }
103 size_t error_count = 0;
104 for (size_t k = 0; k < n && error_count < 10; ++k)
105 {
106 if (!(expected[k] == actual[k]))
107 {
108 std::stringstream outstr;
109 outstr << "error at " << file << ":" << line << " - " << message << ", at index " << k << " expected "
110 << expected[k] << " got " << actual[k];
111 issue_error_message(outstr);
112 ++error_count;
113 }
114 }
115 }
116
117 template <typename Iterator1, typename Iterator2, typename Size>
118 void
expect_equal(Iterator1 expected_first,Iterator2 actual_first,Size n,const char * file,int32_t line,const char * message)119 expect_equal(Iterator1 expected_first, Iterator2 actual_first, Size n, const char* file, int32_t line,
120 const char* message)
121 {
122 size_t error_count = 0;
123 for (size_t k = 0; k < n && error_count < 10; ++k, ++expected_first, ++actual_first)
124 {
125 if (!(*expected_first == *actual_first))
126 {
127 std::stringstream outstr;
128 outstr << "error at " << file << ":" << line << " - " << message << ", at index " << k;
129 issue_error_message(outstr);
130 ++error_count;
131 }
132 }
133 }
134
135 // ForwardIterator is like type Iterator, but restricted to be a forward iterator.
136 // Only the forward iterator signatures that are necessary for tests are present.
137 // Post-increment in particular is deliberatly omitted since our templates should avoid using it
138 // because of efficiency considerations.
139 template <typename Iterator, typename IteratorTag>
140 class ForwardIterator
141 {
142 public:
143 typedef IteratorTag iterator_category;
144 typedef typename std::iterator_traits<Iterator>::value_type value_type;
145 typedef typename std::iterator_traits<Iterator>::difference_type difference_type;
146 typedef typename std::iterator_traits<Iterator>::pointer pointer;
147 typedef typename std::iterator_traits<Iterator>::reference reference;
148
149 protected:
150 Iterator my_iterator;
151 typedef value_type element_type;
152
153 public:
154 ForwardIterator() = default;
ForwardIterator(Iterator i)155 explicit ForwardIterator(Iterator i) : my_iterator(i) {}
156 reference operator*() const { return *my_iterator; }
157 Iterator operator->() const { return my_iterator; }
158 ForwardIterator
159 operator++()
160 {
161 ++my_iterator;
162 return *this;
163 }
164 ForwardIterator operator++(int32_t)
165 {
166 auto retval = *this;
167 my_iterator++;
168 return retval;
169 }
170 friend bool
171 operator==(const ForwardIterator& i, const ForwardIterator& j)
172 {
173 return i.my_iterator == j.my_iterator;
174 }
175 friend bool
176 operator!=(const ForwardIterator& i, const ForwardIterator& j)
177 {
178 return i.my_iterator != j.my_iterator;
179 }
180
181 Iterator
iterator()182 iterator() const
183 {
184 return my_iterator;
185 }
186 };
187
188 template <typename Iterator, typename IteratorTag>
189 class BidirectionalIterator : public ForwardIterator<Iterator, IteratorTag>
190 {
191 typedef ForwardIterator<Iterator, IteratorTag> base_type;
192
193 public:
194 BidirectionalIterator() = default;
BidirectionalIterator(Iterator i)195 explicit BidirectionalIterator(Iterator i) : base_type(i) {}
BidirectionalIterator(const base_type & i)196 BidirectionalIterator(const base_type& i) : base_type(i.iterator()) {}
197
198 BidirectionalIterator
199 operator++()
200 {
201 ++base_type::my_iterator;
202 return *this;
203 }
204 BidirectionalIterator
205 operator--()
206 {
207 --base_type::my_iterator;
208 return *this;
209 }
210 BidirectionalIterator operator++(int32_t)
211 {
212 auto retval = *this;
213 base_type::my_iterator++;
214 return retval;
215 }
216 BidirectionalIterator operator--(int32_t)
217 {
218 auto retval = *this;
219 base_type::my_iterator--;
220 return retval;
221 }
222 };
223
224 template <typename Iterator, typename F>
225 void
fill_data(Iterator first,Iterator last,F f)226 fill_data(Iterator first, Iterator last, F f)
227 {
228 typedef typename std::iterator_traits<Iterator>::value_type T;
229 for (std::size_t i = 0; first != last; ++first, ++i)
230 {
231 *first = T(f(i));
232 }
233 }
234
235 // Sequence<T> is a container of a sequence of T with lots of kinds of iterators.
236 // Prefixes on begin/end mean:
237 // c = "const"
238 // f = "forward"
239 // No prefix indicates non-const random-access iterator.
240 template <typename T>
241 class Sequence
242 {
243 std::vector<T> m_storage;
244
245 public:
246 typedef typename std::vector<T>::iterator iterator;
247 typedef typename std::vector<T>::const_iterator const_iterator;
248 typedef ForwardIterator<iterator, std::forward_iterator_tag> forward_iterator;
249 typedef ForwardIterator<const_iterator, std::forward_iterator_tag> const_forward_iterator;
250
251 typedef BidirectionalIterator<iterator, std::bidirectional_iterator_tag> bidirectional_iterator;
252 typedef BidirectionalIterator<const_iterator, std::bidirectional_iterator_tag> const_bidirectional_iterator;
253
254 typedef T value_type;
Sequence(size_t size)255 explicit Sequence(size_t size) : m_storage(size) {}
256
257 // Construct sequence [f(0), f(1), ... f(size-1)]
258 // f can rely on its invocations being sequential from 0 to size-1.
259 template <typename Func>
Sequence(size_t size,Func f)260 Sequence(size_t size, Func f)
261 {
262 m_storage.reserve(size);
263 // Use push_back because T might not have a default constructor
264 for (size_t k = 0; k < size; ++k)
265 m_storage.push_back(T(f(k)));
266 }
Sequence(const std::initializer_list<T> & data)267 Sequence(const std::initializer_list<T>& data) : m_storage(data) {}
268
269 const_iterator
begin()270 begin() const
271 {
272 return m_storage.begin();
273 }
274 const_iterator
end()275 end() const
276 {
277 return m_storage.end();
278 }
279 iterator
begin()280 begin()
281 {
282 return m_storage.begin();
283 }
284 iterator
end()285 end()
286 {
287 return m_storage.end();
288 }
289 const_iterator
cbegin()290 cbegin() const
291 {
292 return m_storage.cbegin();
293 }
294 const_iterator
cend()295 cend() const
296 {
297 return m_storage.cend();
298 }
299 forward_iterator
fbegin()300 fbegin()
301 {
302 return forward_iterator(m_storage.begin());
303 }
304 forward_iterator
fend()305 fend()
306 {
307 return forward_iterator(m_storage.end());
308 }
309 const_forward_iterator
cfbegin()310 cfbegin() const
311 {
312 return const_forward_iterator(m_storage.cbegin());
313 }
314 const_forward_iterator
cfend()315 cfend() const
316 {
317 return const_forward_iterator(m_storage.cend());
318 }
319 const_forward_iterator
fbegin()320 fbegin() const
321 {
322 return const_forward_iterator(m_storage.cbegin());
323 }
324 const_forward_iterator
fend()325 fend() const
326 {
327 return const_forward_iterator(m_storage.cend());
328 }
329
330 const_bidirectional_iterator
cbibegin()331 cbibegin() const
332 {
333 return const_bidirectional_iterator(m_storage.cbegin());
334 }
335 const_bidirectional_iterator
cbiend()336 cbiend() const
337 {
338 return const_bidirectional_iterator(m_storage.cend());
339 }
340
341 bidirectional_iterator
bibegin()342 bibegin()
343 {
344 return bidirectional_iterator(m_storage.begin());
345 }
346 bidirectional_iterator
biend()347 biend()
348 {
349 return bidirectional_iterator(m_storage.end());
350 }
351
352 std::size_t
size()353 size() const
354 {
355 return m_storage.size();
356 }
357 const T*
data()358 data() const
359 {
360 return m_storage.data();
361 }
362 typename std::vector<T>::reference operator[](size_t j) { return m_storage[j]; }
363 const T& operator[](size_t j) const { return m_storage[j]; }
364
365 // Fill with given value
366 void
fill(const T & value)367 fill(const T& value)
368 {
369 for (size_t i = 0; i < m_storage.size(); i++)
370 m_storage[i] = value;
371 }
372
373 void
374 print() const;
375
376 template <typename Func>
377 void
fill(Func f)378 fill(Func f)
379 {
380 fill_data(m_storage.begin(), m_storage.end(), f);
381 }
382 };
383
384 template <typename T>
385 void
print()386 Sequence<T>::print() const
387 {
388 std::cout << "size = " << size() << ": { ";
389 std::copy(begin(), end(), std::ostream_iterator<T>(std::cout, " "));
390 std::cout << " } " << std::endl;
391 }
392
393 // Predicates for algorithms
394 template <typename DataType>
395 struct is_equal_to
396 {
is_equal_tois_equal_to397 is_equal_to(const DataType& expected) : m_expected(expected) {}
398 bool
operatoris_equal_to399 operator()(const DataType& actual) const
400 {
401 return actual == m_expected;
402 }
403
404 private:
405 DataType m_expected;
406 };
407
408 // Low-quality hash function, returns value between 0 and (1<<bits)-1
409 // Warning: low-order bits are quite predictable.
410 inline size_t
HashBits(size_t i,size_t bits)411 HashBits(size_t i, size_t bits)
412 {
413 size_t mask = bits >= 8 * sizeof(size_t) ? ~size_t(0) : (size_t(1) << bits) - 1;
414 return (424157 * i ^ 0x24aFa) & mask;
415 }
416
417 // Stateful unary op
418 template <typename T, typename U>
419 class Complement
420 {
421 int32_t val;
422
423 public:
Complement(T v)424 Complement(T v) : val(v) {}
425 U
operator()426 operator()(const T& x) const
427 {
428 return U(val - x);
429 }
430 };
431
432 // Tag used to prevent accidental use of converting constructor, even if use is explicit.
433 struct OddTag
434 {
435 };
436
437 class Sum;
438
439 // Type with limited set of operations. Not default-constructible.
440 // Only available operator is "==".
441 // Typically used as value type in tests.
442 class Number
443 {
444 int32_t value;
445 friend class Add;
446 friend class Sum;
447 friend class IsMultiple;
448 friend class Congruent;
449 friend Sum
450 operator+(const Sum& x, const Sum& y);
451
452 public:
Number(int32_t val,OddTag)453 Number(int32_t val, OddTag) : value(val) {}
454 friend bool
455 operator==(const Number& x, const Number& y)
456 {
457 return x.value == y.value;
458 }
459 friend std::ostream&
460 operator<<(std::ostream& o, const Number& d)
461 {
462 return o << d.value;
463 }
464 };
465
466 // Stateful predicate for Number. Not default-constructible.
467 class IsMultiple
468 {
469 long modulus;
470
471 public:
472 // True if x is multiple of modulus
473 bool
operator()474 operator()(Number x) const
475 {
476 return x.value % modulus == 0;
477 }
IsMultiple(long modulus_,OddTag)478 IsMultiple(long modulus_, OddTag) : modulus(modulus_) {}
479 };
480
481 // Stateful equivalence-class predicate for Number. Not default-constructible.
482 class Congruent
483 {
484 long modulus;
485
486 public:
487 // True if x and y have same remainder for the given modulus.
488 // Note: this is not quite the same as "equivalent modulo modulus" when x and y have different
489 // sign, but nonetheless AreCongruent is still an equivalence relationship, which is all
490 // we need for testing.
491 bool
operator()492 operator()(Number x, Number y) const
493 {
494 return x.value % modulus == y.value % modulus;
495 }
Congruent(long modulus_,OddTag)496 Congruent(long modulus_, OddTag) : modulus(modulus_) {}
497 };
498
499 // Stateful reduction operation for Number
500 class Add
501 {
502 long bias;
503
504 public:
Add(OddTag)505 explicit Add(OddTag) : bias(1) {}
506 Number
operator()507 operator()(Number x, const Number& y)
508 {
509 return Number(x.value + y.value + (bias - 1), OddTag());
510 }
511 };
512
513 // Class similar to Number, but has default constructor and +.
514 class Sum : public Number
515 {
516 public:
Sum()517 Sum() : Number(0, OddTag()) {}
Sum(long x,OddTag)518 Sum(long x, OddTag) : Number(x, OddTag()) {}
519 friend Sum
520 operator+(const Sum& x, const Sum& y)
521 {
522 return Sum(x.value + y.value, OddTag());
523 }
524 };
525
526 // Type with limited set of operations, which includes an associative but not commutative operation.
527 // Not default-constructible.
528 // Typically used as value type in tests involving "GENERALIZED_NONCOMMUTATIVE_SUM".
529 class MonoidElement
530 {
531 size_t a, b;
532
533 public:
MonoidElement(size_t a_,size_t b_,OddTag)534 MonoidElement(size_t a_, size_t b_, OddTag) : a(a_), b(b_) {}
535 friend bool
536 operator==(const MonoidElement& x, const MonoidElement& y)
537 {
538 return x.a == y.a && x.b == y.b;
539 }
540 friend std::ostream&
541 operator<<(std::ostream& o, const MonoidElement& x)
542 {
543 return o << "[" << x.a << ".." << x.b << ")";
544 }
545 friend class AssocOp;
546 };
547
548 // Stateful associative op for MonoidElement
549 // It's not really a monoid since the operation is not allowed for any two elements.
550 // But it's good enough for testing.
551 class AssocOp
552 {
553 unsigned c;
554
555 public:
AssocOp(OddTag)556 explicit AssocOp(OddTag) : c(5) {}
557 MonoidElement
operator()558 operator()(const MonoidElement& x, const MonoidElement& y)
559 {
560 unsigned d = 5;
561 EXPECT_EQ(d, c, "state lost");
562 EXPECT_EQ(x.b, y.a, "commuted?");
563
564 return MonoidElement(x.a, y.b, OddTag());
565 }
566 };
567
568 // Multiplication of matrix is an associative but not commutative operation
569 // Typically used as value type in tests involving "GENERALIZED_NONCOMMUTATIVE_SUM".
570 template <typename T>
571 struct Matrix2x2
572 {
573 T a[2][2];
Matrix2x2Matrix2x2574 Matrix2x2() : a{{1, 0}, {0, 1}} {}
Matrix2x2Matrix2x2575 Matrix2x2(T x, T y) : a{{0, x}, {x, y}} {}
576 #if !__PSTL_ICL_19_VC14_VC141_TEST_SCAN_RELEASE_BROKEN
Matrix2x2Matrix2x2577 Matrix2x2(const Matrix2x2& m) : a{{m.a[0][0], m.a[0][1]}, {m.a[1][0], m.a[1][1]}} {}
578 Matrix2x2&
579 operator=(const Matrix2x2& m)
580 {
581 a[0][0] = m.a[0][0], a[0][1] = m.a[0][1], a[1][0] = m.a[1][0], a[1][1] = m.a[1][1];
582 return *this;
583 }
584 #endif
585 };
586
587 template <typename T>
588 bool
589 operator==(const Matrix2x2<T>& left, const Matrix2x2<T>& right)
590 {
591 return left.a[0][0] == right.a[0][0] && left.a[0][1] == right.a[0][1] && left.a[1][0] == right.a[1][0] &&
592 left.a[1][1] == right.a[1][1];
593 }
594
595 template <typename T>
596 Matrix2x2<T>
multiply_matrix(const Matrix2x2<T> & left,const Matrix2x2<T> & right)597 multiply_matrix(const Matrix2x2<T>& left, const Matrix2x2<T>& right)
598 {
599 Matrix2x2<T> result;
600 for (int32_t i = 0; i < 2; ++i)
601 {
602 for (int32_t j = 0; j < 2; ++j)
603 {
604 result.a[i][j] = left.a[i][0] * right.a[0][j] + left.a[i][1] * right.a[1][j];
605 }
606 }
607 return result;
608 }
609
610 // Check that Intel(R) Threading Building Blocks header files are not used when parallel policies are off
611 #if !__PSTL_USE_PAR_POLICIES
612 #if defined(TBB_INTERFACE_VERSION)
613 #error The parallel backend is used while it should not (__PSTL_USE_PAR_POLICIES==0)
614 #endif
615 #endif
616
617 //============================================================================
618 // Adapters for creating different types of iterators.
619 //
620 // In this block we implemented some adapters for creating differnet types of iterators.
621 // It's needed for extending the unit testing of Parallel STL algorithms.
622 // We have adapters for iterators with different tags (forward_iterator_tag, bidirectional_iterator_tag), reverse iterators.
623 // The input iterator should be const or non-const, non-reverse random access iterator.
624 // Iterator creates in "MakeIterator":
625 // firstly, iterator is "packed" by "IteratorTypeAdapter" (creating forward or bidirectional iterator)
626 // then iterator is "packed" by "ReverseAdapter" (if it's possible)
627 // So, from input iterator we may create, for example, reverse bidirectional iterator.
628 // "Main" functor for testing iterators is named "invoke_on_all_iterator_types".
629
630 // Base adapter
631 template <typename Iterator>
632 struct BaseAdapter
633 {
634 typedef Iterator iterator_type;
635 iterator_type
operatorBaseAdapter636 operator()(Iterator it)
637 {
638 return it;
639 }
640 };
641
642 // Check if the iterator is reverse iterator
643 // Note: it works only for iterators that created by std::reverse_iterator
644 template <typename NotReverseIterator>
645 struct isReverse : std::false_type
646 {
647 };
648
649 template <typename Iterator>
650 struct isReverse<std::reverse_iterator<Iterator>> : std::true_type
651 {
652 };
653
654 // Reverse adapter
655 template <typename Iterator, typename IsReverse>
656 struct ReverseAdapter
657 {
658 typedef std::reverse_iterator<Iterator> iterator_type;
659 iterator_type
660 operator()(Iterator it)
661 {
662 #if __PSTL_CPP14_MAKE_REVERSE_ITERATOR_PRESENT
663 return std::make_reverse_iterator(it);
664 #else
665 return iterator_type(it);
666 #endif
667 }
668 };
669
670 // Non-reverse adapter
671 template <typename Iterator>
672 struct ReverseAdapter<Iterator, std::false_type> : BaseAdapter<Iterator>
673 {
674 };
675
676 // Iterator adapter by type (by default std::random_access_iterator_tag)
677 template <typename Iterator, typename IteratorTag>
678 struct IteratorTypeAdapter : BaseAdapter<Iterator>
679 {
680 };
681
682 // Iterator adapter for forward iterator
683 template <typename Iterator>
684 struct IteratorTypeAdapter<Iterator, std::forward_iterator_tag>
685 {
686 typedef ForwardIterator<Iterator, std::forward_iterator_tag> iterator_type;
687 iterator_type
688 operator()(Iterator it)
689 {
690 return iterator_type(it);
691 }
692 };
693
694 // Iterator adapter for bidirectional iterator
695 template <typename Iterator>
696 struct IteratorTypeAdapter<Iterator, std::bidirectional_iterator_tag>
697 {
698 typedef BidirectionalIterator<Iterator, std::bidirectional_iterator_tag> iterator_type;
699 iterator_type
700 operator()(Iterator it)
701 {
702 return iterator_type(it);
703 }
704 };
705
706 //For creating iterator with new type
707 template <typename InputIterator, typename IteratorTag, typename IsReverse>
708 struct MakeIterator
709 {
710 typedef IteratorTypeAdapter<InputIterator, IteratorTag> IterByType;
711 typedef ReverseAdapter<typename IterByType::iterator_type, IsReverse> ReverseIter;
712
713 typename ReverseIter::iterator_type
714 operator()(InputIterator it)
715 {
716 return ReverseIter()(IterByType()(it));
717 }
718 };
719
720 // Useful constant variables
721 constexpr std::size_t GuardSize = 5;
722 constexpr std::ptrdiff_t sizeLimit = 1000;
723
724 template <typename Iter, typename Void = void> // local iterator_traits for non-iterators
725 struct iterator_traits_
726 {
727 };
728
729 template <typename Iter> // For iterators
730 struct iterator_traits_<Iter,
731 typename std::enable_if<!std::is_void<typename Iter::iterator_category>::value, void>::type>
732 {
733 typedef typename Iter::iterator_category iterator_category;
734 };
735
736 template <typename T> // For pointers
737 struct iterator_traits_<T*>
738 {
739 typedef std::random_access_iterator_tag iterator_category;
740 };
741
742 // is iterator Iter has tag Tag
743 template <typename Iter, typename Tag>
744 using is_same_iterator_category = std::is_same<typename iterator_traits_<Iter>::iterator_category, Tag>;
745
746 // if we run with reverse or const iterators we shouldn't test the large range
747 template <typename IsReverse, typename IsConst>
748 struct invoke_if_
749 {
750 template <typename Op, typename... Rest>
751 void
752 operator()(bool is_allow, Op op, Rest&&... rest)
753 {
754 if (is_allow)
755 op(std::forward<Rest>(rest)...);
756 }
757 };
758 template <>
759 struct invoke_if_<std::false_type, std::false_type>
760 {
761 template <typename Op, typename... Rest>
762 void
763 operator()(bool is_allow, Op op, Rest&&... rest)
764 {
765 op(std::forward<Rest>(rest)...);
766 }
767 };
768
769 // Base non_const_wrapper struct. It is used to distinguish non_const testcases
770 // from a regular one. For non_const testcases only compilation is checked.
771 struct non_const_wrapper
772 {
773 };
774
775 // Generic wrapper to specify iterator type to execute callable Op on.
776 // The condition can be either positive(Op is executed only with IteratorTag)
777 // or negative(Op is executed with every type of iterators except IteratorTag)
778 template <typename Op, typename IteratorTag, bool IsPositiveCondition = true>
779 struct non_const_wrapper_tagged : non_const_wrapper
780 {
781 template <typename Policy, typename Iterator>
782 typename std::enable_if<IsPositiveCondition == is_same_iterator_category<Iterator, IteratorTag>::value, void>::type
783 operator()(Policy&& exec, Iterator iter)
784 {
785 Op()(exec, iter);
786 }
787
788 template <typename Policy, typename InputIterator, typename OutputIterator>
789 typename std::enable_if<IsPositiveCondition == is_same_iterator_category<OutputIterator, IteratorTag>::value,
790 void>::type
791 operator()(Policy&& exec, InputIterator input_iter, OutputIterator out_iter)
792 {
793 Op()(exec, input_iter, out_iter);
794 }
795
796 template <typename Policy, typename Iterator>
797 typename std::enable_if<IsPositiveCondition != is_same_iterator_category<Iterator, IteratorTag>::value, void>::type
798 operator()(Policy&& exec, Iterator iter)
799 {
800 }
801
802 template <typename Policy, typename InputIterator, typename OutputIterator>
803 typename std::enable_if<IsPositiveCondition != is_same_iterator_category<OutputIterator, IteratorTag>::value,
804 void>::type
805 operator()(Policy&& exec, InputIterator input_iter, OutputIterator out_iter)
806 {
807 }
808 };
809
810 // These run_for_* structures specify with which types of iterators callable object Op
811 // should be executed.
812 template <typename Op>
813 struct run_for_rnd : non_const_wrapper_tagged<Op, std::random_access_iterator_tag>
814 {
815 };
816
817 template <typename Op>
818 struct run_for_rnd_bi : non_const_wrapper_tagged<Op, std::forward_iterator_tag, false>
819 {
820 };
821
822 template <typename Op>
823 struct run_for_rnd_fw : non_const_wrapper_tagged<Op, std::bidirectional_iterator_tag, false>
824 {
825 };
826
827 // Invoker for different types of iterators.
828 template <typename IteratorTag, typename IsReverse>
829 struct iterator_invoker
830 {
831 template <typename Iterator>
832 using make_iterator = MakeIterator<Iterator, IteratorTag, IsReverse>;
833 template <typename Iterator>
834 using IsConst = typename std::is_const<
835 typename std::remove_pointer<typename std::iterator_traits<Iterator>::pointer>::type>::type;
836 template <typename Iterator>
837 using invoke_if = invoke_if_<IsReverse, IsConst<Iterator>>;
838
839 // A single iterator version which is used for non_const testcases
840 template <typename Policy, typename Op, typename Iterator>
841 typename std::enable_if<is_same_iterator_category<Iterator, std::random_access_iterator_tag>::value &&
842 std::is_base_of<non_const_wrapper, Op>::value,
843 void>::type
844 operator()(Policy&& exec, Op op, Iterator iter)
845 {
846 op(std::forward<Policy>(exec), make_iterator<Iterator>()(iter));
847 }
848
849 // A version with 2 iterators which is used for non_const testcases
850 template <typename Policy, typename Op, typename InputIterator, typename OutputIterator>
851 typename std::enable_if<is_same_iterator_category<OutputIterator, std::random_access_iterator_tag>::value &&
852 std::is_base_of<non_const_wrapper, Op>::value,
853 void>::type
854 operator()(Policy&& exec, Op op, InputIterator input_iter, OutputIterator out_iter)
855 {
856 op(std::forward<Policy>(exec), make_iterator<InputIterator>()(input_iter),
857 make_iterator<OutputIterator>()(out_iter));
858 }
859
860 template <typename Policy, typename Op, typename Iterator, typename Size, typename... Rest>
861 typename std::enable_if<is_same_iterator_category<Iterator, std::random_access_iterator_tag>::value, void>::type
862 operator()(Policy&& exec, Op op, Iterator begin, Size n, Rest&&... rest)
863 {
864 invoke_if<Iterator>()(n <= sizeLimit, op, exec, make_iterator<Iterator>()(begin), n,
865 std::forward<Rest>(rest)...);
866 }
867
868 template <typename Policy, typename Op, typename Iterator, typename... Rest>
869 typename std::enable_if<is_same_iterator_category<Iterator, std::random_access_iterator_tag>::value &&
870 !std::is_base_of<non_const_wrapper, Op>::value,
871 void>::type
872 operator()(Policy&& exec, Op op, Iterator inputBegin, Iterator inputEnd, Rest&&... rest)
873 {
874 invoke_if<Iterator>()(std::distance(inputBegin, inputEnd) <= sizeLimit, op, exec,
875 make_iterator<Iterator>()(inputBegin), make_iterator<Iterator>()(inputEnd),
876 std::forward<Rest>(rest)...);
877 }
878
879 template <typename Policy, typename Op, typename InputIterator, typename OutputIterator, typename... Rest>
880 typename std::enable_if<is_same_iterator_category<OutputIterator, std::random_access_iterator_tag>::value,
881 void>::type
882 operator()(Policy&& exec, Op op, InputIterator inputBegin, InputIterator inputEnd, OutputIterator outputBegin,
883 Rest&&... rest)
884 {
885 invoke_if<InputIterator>()(std::distance(inputBegin, inputEnd) <= sizeLimit, op, exec,
886 make_iterator<InputIterator>()(inputBegin), make_iterator<InputIterator>()(inputEnd),
887 make_iterator<OutputIterator>()(outputBegin), std::forward<Rest>(rest)...);
888 }
889
890 template <typename Policy, typename Op, typename InputIterator, typename OutputIterator, typename... Rest>
891 typename std::enable_if<is_same_iterator_category<OutputIterator, std::random_access_iterator_tag>::value,
892 void>::type
893 operator()(Policy&& exec, Op op, InputIterator inputBegin, InputIterator inputEnd, OutputIterator outputBegin,
894 OutputIterator outputEnd, Rest&&... rest)
895 {
896 invoke_if<InputIterator>()(std::distance(inputBegin, inputEnd) <= sizeLimit, op, exec,
897 make_iterator<InputIterator>()(inputBegin), make_iterator<InputIterator>()(inputEnd),
898 make_iterator<OutputIterator>()(outputBegin),
899 make_iterator<OutputIterator>()(outputEnd), std::forward<Rest>(rest)...);
900 }
901
902 template <typename Policy, typename Op, typename InputIterator1, typename InputIterator2, typename OutputIterator,
903 typename... Rest>
904 typename std::enable_if<is_same_iterator_category<OutputIterator, std::random_access_iterator_tag>::value,
905 void>::type
906 operator()(Policy&& exec, Op op, InputIterator1 inputBegin1, InputIterator1 inputEnd1, InputIterator2 inputBegin2,
907 InputIterator2 inputEnd2, OutputIterator outputBegin, OutputIterator outputEnd, Rest&&... rest)
908 {
909 invoke_if<InputIterator1>()(
910 std::distance(inputBegin1, inputEnd1) <= sizeLimit, op, exec, make_iterator<InputIterator1>()(inputBegin1),
911 make_iterator<InputIterator1>()(inputEnd1), make_iterator<InputIterator2>()(inputBegin2),
912 make_iterator<InputIterator2>()(inputEnd2), make_iterator<OutputIterator>()(outputBegin),
913 make_iterator<OutputIterator>()(outputEnd), std::forward<Rest>(rest)...);
914 }
915 };
916
917 // Invoker for reverse iterators only
918 // Note: if we run with reverse iterators we shouldn't test the large range
919 template <typename IteratorTag>
920 struct iterator_invoker<IteratorTag, /* IsReverse = */ std::true_type>
921 {
922
923 template <typename Iterator>
924 using make_iterator = MakeIterator<Iterator, IteratorTag, std::true_type>;
925
926 // A single iterator version which is used for non_const testcases
927 template <typename Policy, typename Op, typename Iterator>
928 typename std::enable_if<is_same_iterator_category<Iterator, std::random_access_iterator_tag>::value &&
929 std::is_base_of<non_const_wrapper, Op>::value,
930 void>::type
931 operator()(Policy&& exec, Op op, Iterator iter)
932 {
933 op(std::forward<Policy>(exec), make_iterator<Iterator>()(iter));
934 }
935
936 // A version with 2 iterators which is used for non_const testcases
937 template <typename Policy, typename Op, typename InputIterator, typename OutputIterator>
938 typename std::enable_if<is_same_iterator_category<OutputIterator, std::random_access_iterator_tag>::value &&
939 std::is_base_of<non_const_wrapper, Op>::value,
940 void>::type
941 operator()(Policy&& exec, Op op, InputIterator input_iter, OutputIterator out_iter)
942 {
943 op(std::forward<Policy>(exec), make_iterator<InputIterator>()(input_iter),
944 make_iterator<OutputIterator>()(out_iter));
945 }
946
947 template <typename Policy, typename Op, typename Iterator, typename Size, typename... Rest>
948 typename std::enable_if<is_same_iterator_category<Iterator, std::random_access_iterator_tag>::value, void>::type
949 operator()(Policy&& exec, Op op, Iterator begin, Size n, Rest&&... rest)
950 {
951 if (n <= sizeLimit)
952 op(exec, make_iterator<Iterator>()(begin + n), n, std::forward<Rest>(rest)...);
953 }
954
955 template <typename Policy, typename Op, typename Iterator, typename... Rest>
956 typename std::enable_if<is_same_iterator_category<Iterator, std::random_access_iterator_tag>::value &&
957 !std::is_base_of<non_const_wrapper, Op>::value,
958 void>::type
959 operator()(Policy&& exec, Op op, Iterator inputBegin, Iterator inputEnd, Rest&&... rest)
960 {
961 if (std::distance(inputBegin, inputEnd) <= sizeLimit)
962 op(exec, make_iterator<Iterator>()(inputEnd), make_iterator<Iterator>()(inputBegin),
963 std::forward<Rest>(rest)...);
964 }
965
966 template <typename Policy, typename Op, typename InputIterator, typename OutputIterator, typename... Rest>
967 typename std::enable_if<is_same_iterator_category<OutputIterator, std::random_access_iterator_tag>::value,
968 void>::type
969 operator()(Policy&& exec, Op op, InputIterator inputBegin, InputIterator inputEnd, OutputIterator outputBegin,
970 Rest&&... rest)
971 {
972 if (std::distance(inputBegin, inputEnd) <= sizeLimit)
973 op(exec, make_iterator<InputIterator>()(inputEnd), make_iterator<InputIterator>()(inputBegin),
974 make_iterator<OutputIterator>()(outputBegin + (inputEnd - inputBegin)), std::forward<Rest>(rest)...);
975 }
976
977 template <typename Policy, typename Op, typename InputIterator, typename OutputIterator, typename... Rest>
978 typename std::enable_if<is_same_iterator_category<OutputIterator, std::random_access_iterator_tag>::value,
979 void>::type
980 operator()(Policy&& exec, Op op, InputIterator inputBegin, InputIterator inputEnd, OutputIterator outputBegin,
981 OutputIterator outputEnd, Rest&&... rest)
982 {
983 if (std::distance(inputBegin, inputEnd) <= sizeLimit)
984 op(exec, make_iterator<InputIterator>()(inputEnd), make_iterator<InputIterator>()(inputBegin),
985 make_iterator<OutputIterator>()(outputEnd), make_iterator<OutputIterator>()(outputBegin),
986 std::forward<Rest>(rest)...);
987 }
988
989 template <typename Policy, typename Op, typename InputIterator1, typename InputIterator2, typename OutputIterator,
990 typename... Rest>
991 typename std::enable_if<is_same_iterator_category<OutputIterator, std::random_access_iterator_tag>::value,
992 void>::type
993 operator()(Policy&& exec, Op op, InputIterator1 inputBegin1, InputIterator1 inputEnd1, InputIterator2 inputBegin2,
994 InputIterator2 inputEnd2, OutputIterator outputBegin, OutputIterator outputEnd, Rest&&... rest)
995 {
996 if (std::distance(inputBegin1, inputEnd1) <= sizeLimit)
997 op(exec, make_iterator<InputIterator1>()(inputEnd1), make_iterator<InputIterator1>()(inputBegin1),
998 make_iterator<InputIterator2>()(inputEnd2), make_iterator<InputIterator2>()(inputBegin2),
999 make_iterator<OutputIterator>()(outputEnd), make_iterator<OutputIterator>()(outputBegin),
1000 std::forward<Rest>(rest)...);
1001 }
1002 };
1003
1004 // We can't create reverse iterator from forward iterator
1005 template <>
1006 struct iterator_invoker<std::forward_iterator_tag, /*isReverse=*/std::true_type>
1007 {
1008 template <typename... Rest>
1009 void
1010 operator()(Rest&&... rest)
1011 {
1012 }
1013 };
1014
1015 template <typename IsReverse>
1016 struct reverse_invoker
1017 {
1018 template <typename... Rest>
1019 void
1020 operator()(Rest&&... rest)
1021 {
1022 // Random-access iterator
1023 iterator_invoker<std::random_access_iterator_tag, IsReverse>()(std::forward<Rest>(rest)...);
1024
1025 // Forward iterator
1026 iterator_invoker<std::forward_iterator_tag, IsReverse>()(std::forward<Rest>(rest)...);
1027
1028 // Bidirectional iterator
1029 iterator_invoker<std::bidirectional_iterator_tag, IsReverse>()(std::forward<Rest>(rest)...);
1030 }
1031 };
1032
1033 struct invoke_on_all_iterator_types
1034 {
1035 template <typename... Rest>
1036 void
1037 operator()(Rest&&... rest)
1038 {
1039 reverse_invoker</* IsReverse = */ std::false_type>()(std::forward<Rest>(rest)...);
1040 reverse_invoker</* IsReverse = */ std::true_type>()(std::forward<Rest>(rest)...);
1041 }
1042 };
1043 //============================================================================
1044
1045 // Invoke op(policy,rest...) for each possible policy.
1046 template <typename Op, typename... T>
1047 void
1048 invoke_on_all_policies(Op op, T&&... rest)
1049 {
1050 using namespace __pstl::execution;
1051
1052 // Try static execution policies
1053 invoke_on_all_iterator_types()(seq, op, std::forward<T>(rest)...);
1054 invoke_on_all_iterator_types()(unseq, op, std::forward<T>(rest)...);
1055 #if __PSTL_USE_PAR_POLICIES
1056 invoke_on_all_iterator_types()(par, op, std::forward<T>(rest)...);
1057 invoke_on_all_iterator_types()(par_unseq, op, std::forward<T>(rest)...);
1058 #endif
1059 }
1060
1061 template <typename F>
1062 struct NonConstAdapter
1063 {
1064 F my_f;
1065 NonConstAdapter(const F& f) : my_f(f) {}
1066
1067 template <typename... Types>
1068 auto
1069 operator()(Types&&... args) -> decltype(std::declval<F>().
1070 operator()(std::forward<Types>(args)...))
1071 {
1072 return my_f(std::forward<Types>(args)...);
1073 }
1074 };
1075
1076 template <typename F>
1077 NonConstAdapter<F>
1078 non_const(const F& f)
1079 {
1080 return NonConstAdapter<F>(f);
1081 }
1082
1083 // Wrapper for types. It's need for counting of constructing and destructing objects
1084 template <typename T>
1085 class Wrapper
1086 {
1087 public:
1088 Wrapper()
1089 {
1090 my_field = std::shared_ptr<T>(new T());
1091 ++my_count;
1092 }
1093 Wrapper(const T& input)
1094 {
1095 my_field = std::shared_ptr<T>(new T(input));
1096 ++my_count;
1097 }
1098 Wrapper(const Wrapper& input)
1099 {
1100 my_field = input.my_field;
1101 ++my_count;
1102 }
1103 Wrapper(Wrapper&& input)
1104 {
1105 my_field = input.my_field;
1106 input.my_field = nullptr;
1107 ++move_count;
1108 }
1109 Wrapper&
1110 operator=(const Wrapper& input)
1111 {
1112 my_field = input.my_field;
1113 return *this;
1114 }
1115 Wrapper&
1116 operator=(Wrapper&& input)
1117 {
1118 my_field = input.my_field;
1119 input.my_field = nullptr;
1120 ++move_count;
1121 return *this;
1122 }
1123 bool
1124 operator==(const Wrapper& input) const
1125 {
1126 return my_field == input.my_field;
1127 }
1128 bool
1129 operator<(const Wrapper& input) const
1130 {
1131 return *my_field < *input.my_field;
1132 }
1133 bool
1134 operator>(const Wrapper& input) const
1135 {
1136 return *my_field > *input.my_field;
1137 }
1138 friend std::ostream&
1139 operator<<(std::ostream& stream, const Wrapper& input)
1140 {
1141 return stream << *(input.my_field);
1142 }
1143 ~Wrapper()
1144 {
1145 --my_count;
1146 if (move_count > 0)
1147 {
1148 --move_count;
1149 }
1150 }
1151 T*
1152 get_my_field() const
1153 {
1154 return my_field.get();
1155 };
1156 static size_t
1157 Count()
1158 {
1159 return my_count;
1160 }
1161 static size_t
1162 MoveCount()
1163 {
1164 return move_count;
1165 }
1166 static void
1167 SetCount(const size_t& n)
1168 {
1169 my_count = n;
1170 }
1171 static void
1172 SetMoveCount(const size_t& n)
1173 {
1174 move_count = n;
1175 }
1176
1177 private:
1178 static std::atomic<size_t> my_count;
1179 static std::atomic<size_t> move_count;
1180 std::shared_ptr<T> my_field;
1181 };
1182
1183 template <typename T>
1184 std::atomic<size_t> Wrapper<T>::my_count = {0};
1185
1186 template <typename T>
1187 std::atomic<size_t> Wrapper<T>::move_count = {0};
1188
1189 template <typename InputIterator, typename T, typename BinaryOperation, typename UnaryOperation>
1190 T
1191 transform_reduce_serial(InputIterator first, InputIterator last, T init, BinaryOperation binary_op,
1192 UnaryOperation unary_op) noexcept
1193 {
1194 for (; first != last; ++first)
1195 {
1196 init = binary_op(init, unary_op(*first));
1197 }
1198 return init;
1199 }
1200
1201 static const char*
1202 done()
1203 {
1204 #if __PSTL_TEST_SUCCESSFUL_KEYWORD
1205 return "done";
1206 #else
1207 return "passed";
1208 #endif
1209 }
1210
1211 // test_algo_basic_* functions are used to execute
1212 // f on a very basic sequence of elements of type T.
1213
1214 // Should be used with unary predicate
1215 template <typename T, typename F>
1216 static void
1217 test_algo_basic_single(F&& f)
1218 {
1219 size_t N = 10;
1220 Sequence<T> in(N, [](size_t v) -> T { return T(v); });
1221
1222 invoke_on_all_policies(f, in.begin());
1223 }
1224
1225 // Should be used with binary predicate
1226 template <typename T, typename F>
1227 static void
1228 test_algo_basic_double(F&& f)
1229 {
1230 size_t N = 10;
1231 Sequence<T> in(N, [](size_t v) -> T { return T(v); });
1232 Sequence<T> out(N, [](size_t v) -> T { return T(v); });
1233
1234 invoke_on_all_policies(f, in.begin(), out.begin());
1235 }
1236
1237 template <typename Policy, typename F>
1238 static void
1239 invoke_if(Policy&& p, F f)
1240 {
1241 #if __PSTL_ICC_16_VC14_TEST_SIMD_LAMBDA_DEBUG_32_BROKEN || __PSTL_ICC_17_VC141_TEST_SIMD_LAMBDA_DEBUG_32_BROKEN
1242 __pstl::__internal::invoke_if_not(__pstl::__internal::allow_unsequenced<Policy>(), f);
1243 #else
1244 f();
1245 #endif
1246 }
1247
1248 } /* namespace TestUtils */
1249