pstl/test/std/algorithms/alg.sorting/sort.pass.cpp

   1 // -*- C++ -*-
   2 //===-- sort.pass.cpp -----------------------------------------------------===//
   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 // UNSUPPORTED: c++03, c++11, c++14
  11
  12 #include "support/pstl_test_config.h"
  13
  14 #include <execution>
  15 #include <algorithm>
  16
  17 #include "support/utils.h"
  18
  19 using namespace TestUtils;
  20 #define _CRT_SECURE_NO_WARNINGS
  21
  22 #include <atomic>
  23
  24 static bool Stable;
  25
  26 //! Number of extant keys
  27 static std::atomic<int32_t> KeyCount;
  28
  29 //! One more than highest index in array to be sorted.
  30 static uint32_t LastIndex;
  31
  32 //! Keeping Equal() static and a friend of ParanoidKey class (C++, paragraphs 3.5/7.1.1)
  33 class ParanoidKey;
  34 static bool
  35 Equal(const ParanoidKey& x, const ParanoidKey& y);
  36
  37 //! A key to be sorted, with lots of checking.
  38 class ParanoidKey
  39 {
  40     //! Value used by comparator
  41     int32_t value;
  42     //! Original position or special value (Empty or Dead)
  43     int32_t index;
  44     //! Special value used to mark object without a comparable value, e.g. after being moved from.
  45     static const int32_t Empty = -1;
  46     //! Special value used to mark destroyed objects.
  47     static const int32_t Dead = -2;
  48     // True if key object has comparable value
  49     bool
  50     isLive() const
  51     {
  52         return (uint32_t)(index) < LastIndex;
  53     }
  54     // True if key object has been constructed.
  55     bool
  56     isConstructed() const
  57     {
  58         return isLive() || index == Empty;
  59     }
  60
  61   public:
  62     ParanoidKey()
  63     {
  64         ++KeyCount;
  65         index = Empty;
  66         value = Empty;
  67     }
  68     ParanoidKey(const ParanoidKey& k) : value(k.value), index(k.index)
  69     {
  70         EXPECT_TRUE(k.isLive(), "source for copy-constructor is dead");
  71         ++KeyCount;
  72     }
  73     ~ParanoidKey()
  74     {
  75         EXPECT_TRUE(isConstructed(), "double destruction");
  76         index = Dead;
  77         --KeyCount;
  78     }
  79     ParanoidKey&
  80     operator=(const ParanoidKey& k)
  81     {
  82         EXPECT_TRUE(k.isLive(), "source for copy-assignment is dead");
  83         EXPECT_TRUE(isConstructed(), "destination for copy-assignment is dead");
  84         value = k.value;
  85         index = k.index;
  86         return *this;
  87     }
  88     ParanoidKey(int32_t index, int32_t value, OddTag) : value(value), index(index) {}
  89     ParanoidKey(ParanoidKey&& k) : value(k.value), index(k.index)
  90     {
  91         EXPECT_TRUE(k.isConstructed(), "source for move-construction is dead");
  92 // std::stable_sort() fails in move semantics on paranoid test before VS2015
  93 #if !defined(_MSC_VER) || _MSC_VER >= 1900
  94         k.index = Empty;
  95 #endif
  96         ++KeyCount;
  97     }
  98     ParanoidKey&
  99     operator=(ParanoidKey&& k)
 100     {
 101         EXPECT_TRUE(k.isConstructed(), "source for move-assignment is dead");
 102         EXPECT_TRUE(isConstructed(), "destination for move-assignment is dead");
 103         value = k.value;
 104         index = k.index;
 105 // std::stable_sort() fails in move semantics on paranoid test before VS2015
 106 #if !defined(_MSC_VER) || _MSC_VER >= 1900
 107         k.index = Empty;
 108 #endif
 109         return *this;
 110     }
 111     friend class KeyCompare;
 112     friend bool
 113     Equal(const ParanoidKey& x, const ParanoidKey& y);
 114 };
 115
 116 class KeyCompare
 117 {
 118     enum statusType
 119     {
 120         //! Special value used to mark defined object.
 121         Live = 0xabcd,
 122         //! Special value used to mark destroyed objects.
 123         Dead = -1
 124     } status;
 125
 126   public:
 127     KeyCompare(OddTag) : status(Live) {}
 128     ~KeyCompare() { status = Dead; }
 129     bool
 130     operator()(const ParanoidKey& j, const ParanoidKey& k) const
 131     {
 132         EXPECT_TRUE(status == Live, "key comparison object not defined");
 133         EXPECT_TRUE(j.isLive(), "first key to operator() is not live");
 134         EXPECT_TRUE(k.isLive(), "second key to operator() is not live");
 135         return j.value < k.value;
 136     }
 137 };
 138
 139 // Equal is equality comparison used for checking result of sort against expected result.
 140 static bool
 141 Equal(const ParanoidKey& x, const ParanoidKey& y)
 142 {
 143     return (x.value == y.value && !Stable) || (x.index == y.index);
 144 }
 145
 146 static bool
 147 Equal(float32_t x, float32_t y)
 148 {
 149     return x == y;
 150 }
 151
 152 static bool
 153 Equal(int32_t x, int32_t y)
 154 {
 155     return x == y;
 156 }
 157
 158 struct test_sort_with_compare
 159 {
 160     template <typename Policy, typename InputIterator, typename OutputIterator, typename OutputIterator2, typename Size,
 161               typename Compare>
 162     typename std::enable_if<is_same_iterator_category<InputIterator, std::random_access_iterator_tag>::value,
 163                             void>::type
 164     operator()(Policy&& exec, OutputIterator tmp_first, OutputIterator tmp_last, OutputIterator2 expected_first,
 165                OutputIterator2 expected_last, InputIterator first, InputIterator, Size n, Compare compare)
 166     {
 167         using namespace std;
 168         copy_n(first, n, expected_first);
 169         copy_n(first, n, tmp_first);
 170         if (Stable)
 171             std::stable_sort(expected_first + 1, expected_last - 1, compare);
 172         else
 173             std::sort(expected_first + 1, expected_last - 1, compare);
 174         int32_t count0 = KeyCount;
 175         if (Stable)
 176             stable_sort(exec, tmp_first + 1, tmp_last - 1, compare);
 177         else
 178             sort(exec, tmp_first + 1, tmp_last - 1, compare);
 179
 180         for (size_t i = 0; i < n; ++i, ++expected_first, ++tmp_first)
 181         {
 182             // Check that expected[i] is equal to tmp[i]
 183             EXPECT_TRUE(Equal(*expected_first, *tmp_first), "bad sort");
 184         }
 185         int32_t count1 = KeyCount;
 186         EXPECT_EQ(count0, count1, "key cleanup error");
 187     }
 188     template <typename Policy, typename InputIterator, typename OutputIterator, typename OutputIterator2, typename Size,
 189               typename Compare>
 190     typename std::enable_if<!is_same_iterator_category<InputIterator, std::random_access_iterator_tag>::value,
 191                             void>::type
 192     operator()(Policy&&, OutputIterator, OutputIterator, OutputIterator2, OutputIterator2, InputIterator, InputIterator,
 193                Size, Compare)
 194     {
 195     }
 196 };
 197
 198 template <typename T, typename Compare, typename Convert>
 199 void
 200 test_sort(Compare compare, Convert convert)
 201 {
 202     for (size_t n = 0; n < 100000; n = n <= 16 ? n + 1 : size_t(3.1415 * n))
 203     {
 204         LastIndex = n + 2;
 205         // The rand()%(2*n+1) encourages generation of some duplicates.
 206         // Sequence is padded with an extra element at front and back, to detect overwrite bugs.
 207         Sequence<T> in(n + 2, [=](size_t k) { return convert(k, rand() % (2 * n + 1)); });
 208         Sequence<T> expected(in);
 209         Sequence<T> tmp(in);
 210         invoke_on_all_policies(test_sort_with_compare(), tmp.begin(), tmp.end(), expected.begin(), expected.end(),
 211                                in.begin(), in.end(), in.size(), compare);
 212     }
 213 }
 214
 215 template <typename T>
 216 struct test_non_const
 217 {
 218     template <typename Policy, typename Iterator>
 219     void
 220     operator()(Policy&& exec, Iterator iter)
 221     {
 222         sort(exec, iter, iter, non_const(std::less<T>()));
 223         stable_sort(exec, iter, iter, non_const(std::less<T>()));
 224     }
 225 };
 226
 227 int
 228 main()
 229 {
 230     std::srand(42);
 231     for (int32_t kind = 0; kind < 2; ++kind)
 232     {
 233         Stable = kind != 0;
 234         test_sort<ParanoidKey>(KeyCompare(OddTag()),
 235                                [](size_t k, size_t val) { return ParanoidKey(k, val, OddTag()); });
 236         test_sort<float32_t>([](float32_t x, float32_t y) { return x < y; },
 237                              [](size_t, size_t val) { return float32_t(val); });
 238         test_sort<int32_t>(
 239             [](int32_t x, int32_t y) { return x > y; }, // Reversed so accidental use of < will be detected.
 240             [](size_t, size_t val) { return int32_t(val); });
 241     }
 242
 243     test_algo_basic_single<int32_t>(run_for_rnd<test_non_const<int32_t>>());
 244
 245     std::cout << done() << std::endl;
 246     return 0;
 247 }