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