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
25namespace TestUtils
26{
27
28typedef double float64_t;
29typedef float float32_t;
30
31template <class T, std::size_t N>
32constexpr size_t
33const_size(const T (&)[N]) noexcept
34{
35 return N;
36}
37
38template <typename T>
39class 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.
54inline void
55issue_error_message(std::stringstream& outstr)
56{
57 outstr << std::endl;
58 std::cerr << outstr.str();
59 std::exit(EXIT_FAILURE);
60}
61
62inline void
63expect(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.
75template <typename T>
76void
77expect_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
88template <typename T>
89void
90expect_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
116template <typename Iterator1, typename Iterator2, typename Size>
117void
118expect_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 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.
138template <typename Iterator, typename IteratorTag>
139class 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
187template <typename Iterator, typename IteratorTag>
188class 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
223template <typename Iterator, typename F>
224void
225fill_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
234struct MemoryChecker {
235 // static counters and state tags
236 static std::atomic<std::int64_t> alive_object_counter; // initialized outside
237 static constexpr std::int64_t alive_state = 0xAAAAAAAAAAAAAAAA;
238 static constexpr std::int32_t dead_state = 0; // only used as a set value to cancel alive_state
239
240 std::int32_t _value; // object value used for algorithms
241 std::int64_t _state; // state tag used for checks
242
243 // ctors, dtors, assign ops
244 explicit MemoryChecker(std::int32_t value = 0) : _value(value) {
245 // check for EXPECT_TRUE(state() != alive_state, ...) has not been done since we cannot guarantee that
246 // raw memory for object being constructed does not have a bit sequence being equal to alive_state
247
248 // set constructed state and increment counter for living object
249 inc_alive_objects();
250 _state = alive_state;
251 }
252 MemoryChecker(MemoryChecker&& other) : _value(other.value()) {
253 // check for EXPECT_TRUE(state() != alive_state, ...) has not been done since
254 // compiler can optimize out the move ctor call that results in false positive failure
255 EXPECT_TRUE(other.state() == alive_state, "wrong effect from MemoryChecker(MemoryChecker&&): attemp to construct an object from non-existing object");
256 // set constructed state and increment counter for living object
257 inc_alive_objects();
258 _state = alive_state;
259 }
260 MemoryChecker(const MemoryChecker& other) : _value(other.value()) {
261 // check for EXPECT_TRUE(state() != alive_state, ...) has not been done since
262 // compiler can optimize out the copy ctor call that results in false positive failure
263 EXPECT_TRUE(other.state() == alive_state, "wrong effect from MemoryChecker(const MemoryChecker&): attemp to construct an object from non-existing object");
264 // set constructed state and increment counter for living object
265 inc_alive_objects();
266 _state = alive_state;
267 }
268 MemoryChecker& operator=(MemoryChecker&& other) {
269 // check if we do not assign over uninitialized memory
270 EXPECT_TRUE(state() == alive_state, "wrong effect from MemoryChecker::operator=(MemoryChecker&& other): attemp to assign to non-existing object");
271 EXPECT_TRUE(other.state() == alive_state, "wrong effect from MemoryChecker::operator=(MemoryChecker&& other): attemp to assign from non-existing object");
272 // just assign new value, counter is the same, state is the same
273 _value = other.value();
274
275 return *this;
276 }
277 MemoryChecker& operator=(const MemoryChecker& other) {
278 // check if we do not assign over uninitialized memory
279 EXPECT_TRUE(state() == alive_state, "wrong effect from MemoryChecker::operator=(const MemoryChecker& other): attemp to assign to non-existing object");
280 EXPECT_TRUE(other.state() == alive_state, "wrong effect from MemoryChecker::operator=(const MemoryChecker& other): attemp to assign from non-existing object");
281 // just assign new value, counter is the same, state is the same
282 _value = other.value();
283
284 return *this;
285 }
286 ~MemoryChecker() {
287 // check if we do not double destruct the object
288 EXPECT_TRUE(state() == alive_state, "wrong effect from ~MemoryChecker(): attemp to destroy non-existing object");
289 // set destructed state and decrement counter for living object
290 static_cast<volatile std::int64_t&>(_state) = dead_state;
291 dec_alive_objects();
292 }
293
294 // getters
295 std::int32_t value() const { return _value; }
296 std::int64_t state() const { return _state; }
297 static std::int32_t alive_objects() { return alive_object_counter.load(); }
298private:
299 // setters
300 void inc_alive_objects() { alive_object_counter.fetch_add(i: 1); }
301 void dec_alive_objects() { alive_object_counter.fetch_sub(i: 1); }
302};
303
304std::atomic<std::int64_t> MemoryChecker::alive_object_counter{0};
305
306std::ostream& operator<<(std::ostream& os, const MemoryChecker& val) { return (os << val.value()); }
307bool operator==(const MemoryChecker& v1, const MemoryChecker& v2) { return v1.value() == v2.value(); }
308bool operator<(const MemoryChecker& v1, const MemoryChecker& v2) { return v1.value() < v2.value(); }
309
310// Sequence<T> is a container of a sequence of T with lots of kinds of iterators.
311// Prefixes on begin/end mean:
312// c = "const"
313// f = "forward"
314// No prefix indicates non-const random-access iterator.
315template <typename T>
316class Sequence
317{
318 std::vector<T> m_storage;
319
320 public:
321 typedef typename std::vector<T>::iterator iterator;
322 typedef typename std::vector<T>::const_iterator const_iterator;
323 typedef ForwardIterator<iterator, std::forward_iterator_tag> forward_iterator;
324 typedef ForwardIterator<const_iterator, std::forward_iterator_tag> const_forward_iterator;
325
326 typedef BidirectionalIterator<iterator, std::bidirectional_iterator_tag> bidirectional_iterator;
327 typedef BidirectionalIterator<const_iterator, std::bidirectional_iterator_tag> const_bidirectional_iterator;
328
329 typedef T value_type;
330 explicit Sequence(size_t size) : m_storage(size) {}
331
332 // Construct sequence [f(0), f(1), ... f(size-1)]
333 // f can rely on its invocations being sequential from 0 to size-1.
334 template <typename Func>
335 Sequence(size_t size, Func f)
336 {
337 m_storage.reserve(size);
338 // Use push_back because T might not have a default constructor
339 for (size_t k = 0; k < size; ++k)
340 m_storage.push_back(T(f(k)));
341 }
342 Sequence(const std::initializer_list<T>& data) : m_storage(data) {}
343
344 const_iterator
345 begin() const
346 {
347 return m_storage.begin();
348 }
349 const_iterator
350 end() const
351 {
352 return m_storage.end();
353 }
354 iterator
355 begin()
356 {
357 return m_storage.begin();
358 }
359 iterator
360 end()
361 {
362 return m_storage.end();
363 }
364 const_iterator
365 cbegin() const
366 {
367 return m_storage.cbegin();
368 }
369 const_iterator
370 cend() const
371 {
372 return m_storage.cend();
373 }
374 forward_iterator
375 fbegin()
376 {
377 return forward_iterator(m_storage.begin());
378 }
379 forward_iterator
380 fend()
381 {
382 return forward_iterator(m_storage.end());
383 }
384 const_forward_iterator
385 cfbegin() const
386 {
387 return const_forward_iterator(m_storage.cbegin());
388 }
389 const_forward_iterator
390 cfend() const
391 {
392 return const_forward_iterator(m_storage.cend());
393 }
394 const_forward_iterator
395 fbegin() const
396 {
397 return const_forward_iterator(m_storage.cbegin());
398 }
399 const_forward_iterator
400 fend() const
401 {
402 return const_forward_iterator(m_storage.cend());
403 }
404
405 const_bidirectional_iterator
406 cbibegin() const
407 {
408 return const_bidirectional_iterator(m_storage.cbegin());
409 }
410 const_bidirectional_iterator
411 cbiend() const
412 {
413 return const_bidirectional_iterator(m_storage.cend());
414 }
415
416 bidirectional_iterator
417 bibegin()
418 {
419 return bidirectional_iterator(m_storage.begin());
420 }
421 bidirectional_iterator
422 biend()
423 {
424 return bidirectional_iterator(m_storage.end());
425 }
426
427 std::size_t
428 size() const
429 {
430 return m_storage.size();
431 }
432 const T*
433 data() const
434 {
435 return m_storage.data();
436 }
437 typename std::vector<T>::reference operator[](size_t j) { return m_storage[j]; }
438 const T& operator[](size_t j) const { return m_storage[j]; }
439
440 // Fill with given value
441 void
442 fill(const T& value)
443 {
444 for (size_t i = 0; i < m_storage.size(); i++)
445 m_storage[i] = value;
446 }
447
448 void
449 print() const;
450
451 template <typename Func>
452 void
453 fill(Func f)
454 {
455 fill_data(m_storage.begin(), m_storage.end(), f);
456 }
457};
458
459template <typename T>
460void
461Sequence<T>::print() const
462{
463 std::cout << "size = " << size() << ": { ";
464 std::copy(begin(), end(), std::ostream_iterator<T>(std::cout, " "));
465 std::cout << " } " << std::endl;
466}
467
468// Predicates for algorithms
469template <typename DataType>
470struct is_equal_to
471{
472 is_equal_to(const DataType& expected) : m_expected(expected) {}
473 bool
474 operator()(const DataType& actual) const
475 {
476 return actual == m_expected;
477 }
478
479 private:
480 DataType m_expected;
481};
482
483// Low-quality hash function, returns value between 0 and (1<<bits)-1
484// Warning: low-order bits are quite predictable.
485inline size_t
486HashBits(size_t i, size_t bits)
487{
488 size_t mask = bits >= 8 * sizeof(size_t) ? ~size_t(0) : (size_t(1) << bits) - 1;
489 return (424157 * i ^ 0x24aFa) & mask;
490}
491
492// Stateful unary op
493template <typename T, typename U>
494class Complement
495{
496 int32_t val;
497
498 public:
499 Complement(T v) : val(v) {}
500 U
501 operator()(const T& x) const
502 {
503 return U(val - x);
504 }
505};
506
507// Tag used to prevent accidental use of converting constructor, even if use is explicit.
508struct OddTag
509{
510};
511
512class Sum;
513
514// Type with limited set of operations. Not default-constructible.
515// Only available operator is "==".
516// Typically used as value type in tests.
517class Number
518{
519 int32_t value;
520 friend class Add;
521 friend class Sum;
522 friend class IsMultiple;
523 friend class Congruent;
524 friend Sum
525 operator+(const Sum& x, const Sum& y);
526
527 public:
528 Number(int32_t val, OddTag) : value(val) {}
529 friend bool
530 operator==(const Number& x, const Number& y)
531 {
532 return x.value == y.value;
533 }
534 friend std::ostream&
535 operator<<(std::ostream& o, const Number& d)
536 {
537 return o << d.value;
538 }
539};
540
541// Stateful predicate for Number. Not default-constructible.
542class IsMultiple
543{
544 long modulus;
545
546 public:
547 // True if x is multiple of modulus
548 bool
549 operator()(Number x) const
550 {
551 return x.value % modulus == 0;
552 }
553 IsMultiple(long modulus_, OddTag) : modulus(modulus_) {}
554};
555
556// Stateful equivalence-class predicate for Number. Not default-constructible.
557class Congruent
558{
559 long modulus;
560
561 public:
562 // True if x and y have same remainder for the given modulus.
563 // Note: this is not quite the same as "equivalent modulo modulus" when x and y have different
564 // sign, but nonetheless AreCongruent is still an equivalence relationship, which is all
565 // we need for testing.
566 bool
567 operator()(Number x, Number y) const
568 {
569 return x.value % modulus == y.value % modulus;
570 }
571 Congruent(long modulus_, OddTag) : modulus(modulus_) {}
572};
573
574// Stateful reduction operation for Number
575class Add
576{
577 long bias;
578
579 public:
580 explicit Add(OddTag) : bias(1) {}
581 Number
582 operator()(Number x, const Number& y)
583 {
584 return Number(x.value + y.value + (bias - 1), OddTag());
585 }
586};
587
588// Class similar to Number, but has default constructor and +.
589class Sum : public Number
590{
591 public:
592 Sum() : Number(0, OddTag()) {}
593 Sum(long x, OddTag) : Number(x, OddTag()) {}
594 friend Sum
595 operator+(const Sum& x, const Sum& y)
596 {
597 return Sum(x.value + y.value, OddTag());
598 }
599};
600
601// Type with limited set of operations, which includes an associative but not commutative operation.
602// Not default-constructible.
603// Typically used as value type in tests involving "GENERALIZED_NONCOMMUTATIVE_SUM".
604class MonoidElement
605{
606 size_t a, b;
607
608 public:
609 MonoidElement(size_t a_, size_t b_, OddTag) : a(a_), b(b_) {}
610 friend bool
611 operator==(const MonoidElement& x, const MonoidElement& y)
612 {
613 return x.a == y.a && x.b == y.b;
614 }
615 friend std::ostream&
616 operator<<(std::ostream& o, const MonoidElement& x)
617 {
618 return o << "[" << x.a << ".." << x.b << ")";
619 }
620 friend class AssocOp;
621};
622
623// Stateful associative op for MonoidElement
624// It's not really a monoid since the operation is not allowed for any two elements.
625// But it's good enough for testing.
626class AssocOp
627{
628 unsigned c;
629
630 public:
631 explicit AssocOp(OddTag) : c(5) {}
632 MonoidElement
633 operator()(const MonoidElement& x, const MonoidElement& y)
634 {
635 unsigned d = 5;
636 EXPECT_EQ(d, c, "state lost");
637 EXPECT_EQ(x.b, y.a, "commuted?");
638
639 return MonoidElement(x.a, y.b, OddTag());
640 }
641};
642
643// Multiplication of matrix is an associative but not commutative operation
644// Typically used as value type in tests involving "GENERALIZED_NONCOMMUTATIVE_SUM".
645template <typename T>
646struct Matrix2x2
647{
648 T a[2][2];
649 Matrix2x2() : a{{1, 0}, {0, 1}} {}
650 Matrix2x2(T x, T y) : a{{0, x}, {x, y}} {}
651#if !defined(_PSTL_ICL_19_VC14_VC141_TEST_SCAN_RELEASE_BROKEN)
652 Matrix2x2(const Matrix2x2& m) : a{{m.a[0][0], m.a[0][1]}, {m.a[1][0], m.a[1][1]}} {}
653 Matrix2x2&
654 operator=(const Matrix2x2& m)
655 {
656 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];
657 return *this;
658 }
659#endif
660};
661
662template <typename T>
663bool
664operator==(const Matrix2x2<T>& left, const Matrix2x2<T>& right)
665{
666 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] &&
667 left.a[1][1] == right.a[1][1];
668}
669
670template <typename T>
671Matrix2x2<T>
672multiply_matrix(const Matrix2x2<T>& left, const Matrix2x2<T>& right)
673{
674 Matrix2x2<T> result;
675 for (int32_t i = 0; i < 2; ++i)
676 {
677 for (int32_t j = 0; j < 2; ++j)
678 {
679 result.a[i][j] = left.a[i][0] * right.a[0][j] + left.a[i][1] * right.a[1][j];
680 }
681 }
682 return result;
683}
684
685//============================================================================
686// Adapters for creating different types of iterators.
687//
688// In this block we implemented some adapters for creating differnet types of iterators.
689// It's needed for extending the unit testing of Parallel STL algorithms.
690// We have adapters for iterators with different tags (forward_iterator_tag, bidirectional_iterator_tag), reverse iterators.
691// The input iterator should be const or non-const, non-reverse random access iterator.
692// Iterator creates in "MakeIterator":
693// firstly, iterator is "packed" by "IteratorTypeAdapter" (creating forward or bidirectional iterator)
694// then iterator is "packed" by "ReverseAdapter" (if it's possible)
695// So, from input iterator we may create, for example, reverse bidirectional iterator.
696// "Main" functor for testing iterators is named "invoke_on_all_iterator_types".
697
698// Base adapter
699template <typename Iterator>
700struct BaseAdapter
701{
702 typedef Iterator iterator_type;
703 iterator_type
704 operator()(Iterator it)
705 {
706 return it;
707 }
708};
709
710// Check if the iterator is reverse iterator
711// Note: it works only for iterators that created by std::reverse_iterator
712template <typename NotReverseIterator>
713struct isReverse : std::false_type
714{
715};
716
717template <typename Iterator>
718struct isReverse<std::reverse_iterator<Iterator>> : std::true_type
719{
720};
721
722// Reverse adapter
723template <typename Iterator, typename IsReverse>
724struct ReverseAdapter
725{
726 typedef std::reverse_iterator<Iterator> iterator_type;
727 iterator_type
728 operator()(Iterator it)
729 {
730#if defined(_PSTL_CPP14_MAKE_REVERSE_ITERATOR_PRESENT)
731 return std::make_reverse_iterator(it);
732#else
733 return iterator_type(it);
734#endif
735 }
736};
737
738// Non-reverse adapter
739template <typename Iterator>
740struct ReverseAdapter<Iterator, std::false_type> : BaseAdapter<Iterator>
741{
742};
743
744// Iterator adapter by type (by default std::random_access_iterator_tag)
745template <typename Iterator, typename IteratorTag>
746struct IteratorTypeAdapter : BaseAdapter<Iterator>
747{
748};
749
750// Iterator adapter for forward iterator
751template <typename Iterator>
752struct IteratorTypeAdapter<Iterator, std::forward_iterator_tag>
753{
754 typedef ForwardIterator<Iterator, std::forward_iterator_tag> iterator_type;
755 iterator_type
756 operator()(Iterator it)
757 {
758 return iterator_type(it);
759 }
760};
761
762// Iterator adapter for bidirectional iterator
763template <typename Iterator>
764struct IteratorTypeAdapter<Iterator, std::bidirectional_iterator_tag>
765{
766 typedef BidirectionalIterator<Iterator, std::bidirectional_iterator_tag> iterator_type;
767 iterator_type
768 operator()(Iterator it)
769 {
770 return iterator_type(it);
771 }
772};
773
774//For creating iterator with new type
775template <typename InputIterator, typename IteratorTag, typename IsReverse>
776struct MakeIterator
777{
778 typedef IteratorTypeAdapter<InputIterator, IteratorTag> IterByType;
779 typedef ReverseAdapter<typename IterByType::iterator_type, IsReverse> ReverseIter;
780
781 typename ReverseIter::iterator_type
782 operator()(InputIterator it)
783 {
784 return ReverseIter()(IterByType()(it));
785 }
786};
787
788// Useful constant variables
789constexpr std::size_t GuardSize = 5;
790constexpr std::ptrdiff_t sizeLimit = 1000;
791
792template <typename Iter, typename Void = void> // local iterator_traits for non-iterators
793struct iterator_traits_
794{
795};
796
797template <typename Iter> // For iterators
798struct iterator_traits_<Iter,
799 typename std::enable_if<!std::is_void<typename Iter::iterator_category>::value, void>::type>
800{
801 typedef typename Iter::iterator_category iterator_category;
802};
803
804template <typename T> // For pointers
805struct iterator_traits_<T*>
806{
807 typedef std::random_access_iterator_tag iterator_category;
808};
809
810// is iterator Iter has tag Tag
811template <typename Iter, typename Tag>
812using is_same_iterator_category = std::is_same<typename iterator_traits_<Iter>::iterator_category, Tag>;
813
814// if we run with reverse or const iterators we shouldn't test the large range
815template <typename IsReverse, typename IsConst>
816struct invoke_if_
817{
818 template <typename Op, typename... Rest>
819 void
820 operator()(bool is_allow, Op op, Rest&&... rest)
821 {
822 if (is_allow)
823 op(std::forward<Rest>(rest)...);
824 }
825};
826template <>
827struct invoke_if_<std::false_type, std::false_type>
828{
829 template <typename Op, typename... Rest>
830 void
831 operator()(bool, Op op, Rest&&... rest)
832 {
833 op(std::forward<Rest>(rest)...);
834 }
835};
836
837// Base non_const_wrapper struct. It is used to distinguish non_const testcases
838// from a regular one. For non_const testcases only compilation is checked.
839struct non_const_wrapper
840{
841};
842
843// Generic wrapper to specify iterator type to execute callable Op on.
844// The condition can be either positive(Op is executed only with IteratorTag)
845// or negative(Op is executed with every type of iterators except IteratorTag)
846template <typename Op, typename IteratorTag, bool IsPositiveCondition = true>
847struct non_const_wrapper_tagged : non_const_wrapper
848{
849 template <typename Policy, typename Iterator>
850 typename std::enable_if<IsPositiveCondition == is_same_iterator_category<Iterator, IteratorTag>::value, void>::type
851 operator()(Policy&& exec, Iterator iter)
852 {
853 Op()(exec, iter);
854 }
855
856 template <typename Policy, typename InputIterator, typename OutputIterator>
857 typename std::enable_if<IsPositiveCondition == is_same_iterator_category<OutputIterator, IteratorTag>::value,
858 void>::type
859 operator()(Policy&& exec, InputIterator input_iter, OutputIterator out_iter)
860 {
861 Op()(exec, input_iter, out_iter);
862 }
863
864 template <typename Policy, typename Iterator>
865 typename std::enable_if<IsPositiveCondition != is_same_iterator_category<Iterator, IteratorTag>::value, void>::type
866 operator()(Policy&&, Iterator)
867 {
868 }
869
870 template <typename Policy, typename InputIterator, typename OutputIterator>
871 typename std::enable_if<IsPositiveCondition != is_same_iterator_category<OutputIterator, IteratorTag>::value,
872 void>::type
873 operator()(Policy&&, InputIterator, OutputIterator)
874 {
875 }
876};
877
878// These run_for_* structures specify with which types of iterators callable object Op
879// should be executed.
880template <typename Op>
881struct run_for_rnd : non_const_wrapper_tagged<Op, std::random_access_iterator_tag>
882{
883};
884
885template <typename Op>
886struct run_for_rnd_bi : non_const_wrapper_tagged<Op, std::forward_iterator_tag, false>
887{
888};
889
890template <typename Op>
891struct run_for_rnd_fw : non_const_wrapper_tagged<Op, std::bidirectional_iterator_tag, false>
892{
893};
894
895// Invoker for different types of iterators.
896template <typename IteratorTag, typename IsReverse>
897struct iterator_invoker
898{
899 template <typename Iterator>
900 using make_iterator = MakeIterator<Iterator, IteratorTag, IsReverse>;
901 template <typename Iterator>
902 using IsConst = typename std::is_const<
903 typename std::remove_pointer<typename std::iterator_traits<Iterator>::pointer>::type>::type;
904 template <typename Iterator>
905 using invoke_if = invoke_if_<IsReverse, IsConst<Iterator>>;
906
907 // A single iterator version which is used for non_const testcases
908 template <typename Policy, typename Op, typename Iterator>
909 typename std::enable_if<is_same_iterator_category<Iterator, std::random_access_iterator_tag>::value &&
910 std::is_base_of<non_const_wrapper, Op>::value,
911 void>::type
912 operator()(Policy&& exec, Op op, Iterator iter)
913 {
914 op(std::forward<Policy>(exec), make_iterator<Iterator>()(iter));
915 }
916
917 // A version with 2 iterators which is used for non_const testcases
918 template <typename Policy, typename Op, typename InputIterator, typename OutputIterator>
919 typename std::enable_if<is_same_iterator_category<OutputIterator, std::random_access_iterator_tag>::value &&
920 std::is_base_of<non_const_wrapper, Op>::value,
921 void>::type
922 operator()(Policy&& exec, Op op, InputIterator input_iter, OutputIterator out_iter)
923 {
924 op(std::forward<Policy>(exec), make_iterator<InputIterator>()(input_iter),
925 make_iterator<OutputIterator>()(out_iter));
926 }
927
928 template <typename Policy, typename Op, typename Iterator, typename Size, typename... Rest>
929 typename std::enable_if<is_same_iterator_category<Iterator, std::random_access_iterator_tag>::value, void>::type
930 operator()(Policy&& exec, Op op, Iterator begin, Size n, Rest&&... rest)
931 {
932 invoke_if<Iterator>()(n <= sizeLimit, op, exec, make_iterator<Iterator>()(begin), n,
933 std::forward<Rest>(rest)...);
934 }
935
936 template <typename Policy, typename Op, typename Iterator, typename... Rest>
937 typename std::enable_if<is_same_iterator_category<Iterator, std::random_access_iterator_tag>::value &&
938 !std::is_base_of<non_const_wrapper, Op>::value,
939 void>::type
940 operator()(Policy&& exec, Op op, Iterator inputBegin, Iterator inputEnd, Rest&&... rest)
941 {
942 invoke_if<Iterator>()(std::distance(inputBegin, inputEnd) <= sizeLimit, op, exec,
943 make_iterator<Iterator>()(inputBegin), make_iterator<Iterator>()(inputEnd),
944 std::forward<Rest>(rest)...);
945 }
946
947 template <typename Policy, typename Op, typename InputIterator, typename OutputIterator, typename... Rest>
948 typename std::enable_if<is_same_iterator_category<OutputIterator, std::random_access_iterator_tag>::value,
949 void>::type
950 operator()(Policy&& exec, Op op, InputIterator inputBegin, InputIterator inputEnd, OutputIterator outputBegin,
951 Rest&&... rest)
952 {
953 invoke_if<InputIterator>()(std::distance(inputBegin, inputEnd) <= sizeLimit, op, exec,
954 make_iterator<InputIterator>()(inputBegin), make_iterator<InputIterator>()(inputEnd),
955 make_iterator<OutputIterator>()(outputBegin), 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 OutputIterator outputEnd, Rest&&... rest)
963 {
964 invoke_if<InputIterator>()(std::distance(inputBegin, inputEnd) <= sizeLimit, op, exec,
965 make_iterator<InputIterator>()(inputBegin), make_iterator<InputIterator>()(inputEnd),
966 make_iterator<OutputIterator>()(outputBegin),
967 make_iterator<OutputIterator>()(outputEnd), std::forward<Rest>(rest)...);
968 }
969
970 template <typename Policy, typename Op, typename InputIterator1, typename InputIterator2, typename OutputIterator,
971 typename... Rest>
972 typename std::enable_if<is_same_iterator_category<OutputIterator, std::random_access_iterator_tag>::value,
973 void>::type
974 operator()(Policy&& exec, Op op, InputIterator1 inputBegin1, InputIterator1 inputEnd1, InputIterator2 inputBegin2,
975 InputIterator2 inputEnd2, OutputIterator outputBegin, OutputIterator outputEnd, Rest&&... rest)
976 {
977 invoke_if<InputIterator1>()(
978 std::distance(inputBegin1, inputEnd1) <= sizeLimit, op, exec, make_iterator<InputIterator1>()(inputBegin1),
979 make_iterator<InputIterator1>()(inputEnd1), make_iterator<InputIterator2>()(inputBegin2),
980 make_iterator<InputIterator2>()(inputEnd2), make_iterator<OutputIterator>()(outputBegin),
981 make_iterator<OutputIterator>()(outputEnd), std::forward<Rest>(rest)...);
982 }
983};
984
985// Invoker for reverse iterators only
986// Note: if we run with reverse iterators we shouldn't test the large range
987template <typename IteratorTag>
988struct iterator_invoker<IteratorTag, /* IsReverse = */ std::true_type>
989{
990
991 template <typename Iterator>
992 using make_iterator = MakeIterator<Iterator, IteratorTag, std::true_type>;
993
994 // A single iterator version which is used for non_const testcases
995 template <typename Policy, typename Op, typename Iterator>
996 typename std::enable_if<is_same_iterator_category<Iterator, std::random_access_iterator_tag>::value &&
997 std::is_base_of<non_const_wrapper, Op>::value,
998 void>::type
999 operator()(Policy&& exec, Op op, Iterator iter)
1000 {
1001 op(std::forward<Policy>(exec), make_iterator<Iterator>()(iter));
1002 }
1003
1004 // A version with 2 iterators which is used for non_const testcases
1005 template <typename Policy, typename Op, typename InputIterator, typename OutputIterator>
1006 typename std::enable_if<is_same_iterator_category<OutputIterator, std::random_access_iterator_tag>::value &&
1007 std::is_base_of<non_const_wrapper, Op>::value,
1008 void>::type
1009 operator()(Policy&& exec, Op op, InputIterator input_iter, OutputIterator out_iter)
1010 {
1011 op(std::forward<Policy>(exec), make_iterator<InputIterator>()(input_iter),
1012 make_iterator<OutputIterator>()(out_iter));
1013 }
1014
1015 template <typename Policy, typename Op, typename Iterator, typename Size, typename... Rest>
1016 typename std::enable_if<is_same_iterator_category<Iterator, std::random_access_iterator_tag>::value, void>::type
1017 operator()(Policy&& exec, Op op, Iterator begin, Size n, Rest&&... rest)
1018 {
1019 if (n <= sizeLimit)
1020 op(exec, make_iterator<Iterator>()(begin + n), n, std::forward<Rest>(rest)...);
1021 }
1022
1023 template <typename Policy, typename Op, typename Iterator, typename... Rest>
1024 typename std::enable_if<is_same_iterator_category<Iterator, std::random_access_iterator_tag>::value &&
1025 !std::is_base_of<non_const_wrapper, Op>::value,
1026 void>::type
1027 operator()(Policy&& exec, Op op, Iterator inputBegin, Iterator inputEnd, Rest&&... rest)
1028 {
1029 if (std::distance(inputBegin, inputEnd) <= sizeLimit)
1030 op(exec, make_iterator<Iterator>()(inputEnd), make_iterator<Iterator>()(inputBegin),
1031 std::forward<Rest>(rest)...);
1032 }
1033
1034 template <typename Policy, typename Op, typename InputIterator, typename OutputIterator, typename... Rest>
1035 typename std::enable_if<is_same_iterator_category<OutputIterator, std::random_access_iterator_tag>::value,
1036 void>::type
1037 operator()(Policy&& exec, Op op, InputIterator inputBegin, InputIterator inputEnd, OutputIterator outputBegin,
1038 Rest&&... rest)
1039 {
1040 if (std::distance(inputBegin, inputEnd) <= sizeLimit)
1041 op(exec, make_iterator<InputIterator>()(inputEnd), make_iterator<InputIterator>()(inputBegin),
1042 make_iterator<OutputIterator>()(outputBegin + (inputEnd - inputBegin)), std::forward<Rest>(rest)...);
1043 }
1044
1045 template <typename Policy, typename Op, typename InputIterator, typename OutputIterator, typename... Rest>
1046 typename std::enable_if<is_same_iterator_category<OutputIterator, std::random_access_iterator_tag>::value,
1047 void>::type
1048 operator()(Policy&& exec, Op op, InputIterator inputBegin, InputIterator inputEnd, OutputIterator outputBegin,
1049 OutputIterator outputEnd, Rest&&... rest)
1050 {
1051 if (std::distance(inputBegin, inputEnd) <= sizeLimit)
1052 op(exec, make_iterator<InputIterator>()(inputEnd), make_iterator<InputIterator>()(inputBegin),
1053 make_iterator<OutputIterator>()(outputEnd), make_iterator<OutputIterator>()(outputBegin),
1054 std::forward<Rest>(rest)...);
1055 }
1056
1057 template <typename Policy, typename Op, typename InputIterator1, typename InputIterator2, typename OutputIterator,
1058 typename... Rest>
1059 typename std::enable_if<is_same_iterator_category<OutputIterator, std::random_access_iterator_tag>::value,
1060 void>::type
1061 operator()(Policy&& exec, Op op, InputIterator1 inputBegin1, InputIterator1 inputEnd1, InputIterator2 inputBegin2,
1062 InputIterator2 inputEnd2, OutputIterator outputBegin, OutputIterator outputEnd, Rest&&... rest)
1063 {
1064 if (std::distance(inputBegin1, inputEnd1) <= sizeLimit)
1065 op(exec, make_iterator<InputIterator1>()(inputEnd1), make_iterator<InputIterator1>()(inputBegin1),
1066 make_iterator<InputIterator2>()(inputEnd2), make_iterator<InputIterator2>()(inputBegin2),
1067 make_iterator<OutputIterator>()(outputEnd), make_iterator<OutputIterator>()(outputBegin),
1068 std::forward<Rest>(rest)...);
1069 }
1070};
1071
1072// We can't create reverse iterator from forward iterator
1073template <>
1074struct iterator_invoker<std::forward_iterator_tag, /*isReverse=*/std::true_type>
1075{
1076 template <typename... Rest>
1077 void
1078 operator()(Rest&&...)
1079 {
1080 }
1081};
1082
1083template <typename IsReverse>
1084struct reverse_invoker
1085{
1086 template <typename... Rest>
1087 void
1088 operator()(Rest&&... rest)
1089 {
1090 // Random-access iterator
1091 iterator_invoker<std::random_access_iterator_tag, IsReverse>()(std::forward<Rest>(rest)...);
1092
1093 // Forward iterator
1094 iterator_invoker<std::forward_iterator_tag, IsReverse>()(std::forward<Rest>(rest)...);
1095
1096 // Bidirectional iterator
1097 iterator_invoker<std::bidirectional_iterator_tag, IsReverse>()(std::forward<Rest>(rest)...);
1098 }
1099};
1100
1101struct invoke_on_all_iterator_types
1102{
1103 template <typename... Rest>
1104 void
1105 operator()(Rest&&... rest)
1106 {
1107 reverse_invoker</* IsReverse = */ std::false_type>()(std::forward<Rest>(rest)...);
1108 reverse_invoker</* IsReverse = */ std::true_type>()(std::forward<Rest>(rest)...);
1109 }
1110};
1111//============================================================================
1112
1113// Invoke op(policy,rest...) for each possible policy.
1114template <typename Op, typename... T>
1115void
1116invoke_on_all_policies(Op op, T&&... rest)
1117{
1118 using namespace __pstl::execution;
1119
1120 // Try static execution policies
1121 invoke_on_all_iterator_types()(seq, op, std::forward<T>(rest)...);
1122 invoke_on_all_iterator_types()(unseq, op, std::forward<T>(rest)...);
1123 invoke_on_all_iterator_types()(par, op, std::forward<T>(rest)...);
1124 invoke_on_all_iterator_types()(par_unseq, op, std::forward<T>(rest)...);
1125}
1126
1127template <typename F>
1128struct NonConstAdapter
1129{
1130 F my_f;
1131 NonConstAdapter(const F& f) : my_f(f) {}
1132
1133 template <typename... Types>
1134 auto
1135 operator()(Types&&... args) -> decltype(std::declval<F>().
1136 operator()(std::forward<Types>(args)...))
1137 {
1138 return my_f(std::forward<Types>(args)...);
1139 }
1140};
1141
1142template <typename F>
1143NonConstAdapter<F>
1144non_const(const F& f)
1145{
1146 return NonConstAdapter<F>(f);
1147}
1148
1149// Wrapper for types. It's need for counting of constructing and destructing objects
1150template <typename T>
1151class Wrapper
1152{
1153 public:
1154 Wrapper()
1155 {
1156 my_field = std::shared_ptr<T>(new T());
1157 ++my_count;
1158 }
1159 Wrapper(const T& input)
1160 {
1161 my_field = std::shared_ptr<T>(new T(input));
1162 ++my_count;
1163 }
1164 Wrapper(const Wrapper& input)
1165 {
1166 my_field = input.my_field;
1167 ++my_count;
1168 }
1169 Wrapper(Wrapper&& input)
1170 {
1171 my_field = input.my_field;
1172 input.my_field = nullptr;
1173 ++move_count;
1174 }
1175 Wrapper&
1176 operator=(const Wrapper& input)
1177 {
1178 my_field = input.my_field;
1179 return *this;
1180 }
1181 Wrapper&
1182 operator=(Wrapper&& input)
1183 {
1184 my_field = input.my_field;
1185 input.my_field = nullptr;
1186 ++move_count;
1187 return *this;
1188 }
1189 bool
1190 operator==(const Wrapper& input) const
1191 {
1192 return my_field == input.my_field;
1193 }
1194 bool
1195 operator<(const Wrapper& input) const
1196 {
1197 return *my_field < *input.my_field;
1198 }
1199 bool
1200 operator>(const Wrapper& input) const
1201 {
1202 return *my_field > *input.my_field;
1203 }
1204 friend std::ostream&
1205 operator<<(std::ostream& stream, const Wrapper& input)
1206 {
1207 return stream << *(input.my_field);
1208 }
1209 ~Wrapper()
1210 {
1211 --my_count;
1212 if (move_count > 0)
1213 {
1214 --move_count;
1215 }
1216 }
1217 T*
1218 get_my_field() const
1219 {
1220 return my_field.get();
1221 };
1222 static size_t
1223 Count()
1224 {
1225 return my_count;
1226 }
1227 static size_t
1228 MoveCount()
1229 {
1230 return move_count;
1231 }
1232 static void
1233 SetCount(const size_t& n)
1234 {
1235 my_count = n;
1236 }
1237 static void
1238 SetMoveCount(const size_t& n)
1239 {
1240 move_count = n;
1241 }
1242
1243 private:
1244 static std::atomic<size_t> my_count;
1245 static std::atomic<size_t> move_count;
1246 std::shared_ptr<T> my_field;
1247};
1248
1249template <typename T>
1250std::atomic<size_t> Wrapper<T>::my_count = {0};
1251
1252template <typename T>
1253std::atomic<size_t> Wrapper<T>::move_count = {0};
1254
1255template <typename InputIterator, typename T, typename BinaryOperation, typename UnaryOperation>
1256T
1257transform_reduce_serial(InputIterator first, InputIterator last, T init, BinaryOperation binary_op,
1258 UnaryOperation unary_op) noexcept
1259{
1260 for (; first != last; ++first)
1261 {
1262 init = binary_op(init, unary_op(*first));
1263 }
1264 return init;
1265}
1266
1267static const char*
1268done()
1269{
1270#if defined(_PSTL_TEST_SUCCESSFUL_KEYWORD)
1271 return "done";
1272#else
1273 return "passed";
1274#endif
1275}
1276
1277// test_algo_basic_* functions are used to execute
1278// f on a very basic sequence of elements of type T.
1279
1280// Should be used with unary predicate
1281template <typename T, typename F>
1282static void
1283test_algo_basic_single(F&& f)
1284{
1285 size_t N = 10;
1286 Sequence<T> in(N, [](size_t v) -> T { return T(v); });
1287
1288 invoke_on_all_policies(f, in.begin());
1289}
1290
1291// Should be used with binary predicate
1292template <typename T, typename F>
1293static void
1294test_algo_basic_double(F&& f)
1295{
1296 size_t N = 10;
1297 Sequence<T> in(N, [](size_t v) -> T { return T(v); });
1298 Sequence<T> out(N, [](size_t v) -> T { return T(v); });
1299
1300 invoke_on_all_policies(f, in.begin(), out.begin());
1301}
1302
1303template <typename Policy, typename F>
1304static void
1305invoke_if(Policy&&, F f)
1306{
1307#if defined(_PSTL_ICC_16_VC14_TEST_SIMD_LAMBDA_DEBUG_32_BROKEN) || defined(_PSTL_ICC_17_VC141_TEST_SIMD_LAMBDA_DEBUG_32_BROKEN)
1308 using decay_policy = typename std::decay<Policy>::type;
1309 using allow_unsequenced =
1310 std::integral_constant<bool, (std::is_same<decay_policy, std::execution::unsequenced_policy>::value ||
1311 std::is_same<decay_policy, std::execution::parallel_unsequenced_policy>::value)>;
1312 __pstl::__internal::__invoke_if_not(allow_unsequenced{}, f);
1313#else
1314 f();
1315#endif
1316}
1317
1318} /* namespace TestUtils */
1319

source code of pstl/test/support/utils.h