algorithms/alg.sorting/sort.pass.cpp

// -*- C++ -*-
//===-- sort.pass.cpp -----------------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

// UNSUPPORTED: c++03, c++11, c++14

#include "support/pstl_test_config.h"

#include <execution>
#include <algorithm>

#include "support/utils.h"

using namespace TestUtils;
#define _CRT_SECURE_NO_WARNINGS

#include <atomic>

static bool Stable;

//! Number of extant keys
static std::atomic<int32_t> KeyCount;

//! One more than highest index in array to be sorted.
static uint32_t LastIndex;

//! Keeping Equal() static and a friend of ParanoidKey class (C++, paragraphs 3.5/7.1.1)
class ParanoidKey;
static bool
Equal(const ParanoidKey& x, const ParanoidKey& y);

//! A key to be sorted, with lots of checking.
class ParanoidKey
{
    //! Value used by comparator
    int32_t value;
    //! Original position or special value (Empty or Dead)
    int32_t index;
    //! Special value used to mark object without a comparable value, e.g. after being moved from.
    static const int32_t Empty = -1;
    //! Special value used to mark destroyed objects.
    static const int32_t Dead = -2;
    // True if key object has comparable value
    bool
    isLive() const
    {
        return (uint32_t)(index) < LastIndex;
    }
    // True if key object has been constructed.
    bool
    isConstructed() const
    {
        return isLive() || index == Empty;
    }

  public:
    ParanoidKey()
    {
        ++KeyCount;
        index = Empty;
        value = Empty;
    }
    ParanoidKey(const ParanoidKey& k) : value(k.value), index(k.index)
    {
        EXPECT_TRUE(k.isLive(), "source for copy-constructor is dead");
        ++KeyCount;
    }
    ~ParanoidKey()
    {
        EXPECT_TRUE(isConstructed(), "double destruction");
        index = Dead;
        --KeyCount;
    }
    ParanoidKey&
    operator=(const ParanoidKey& k)
    {
        EXPECT_TRUE(k.isLive(), "source for copy-assignment is dead");
        EXPECT_TRUE(isConstructed(), "destination for copy-assignment is dead");
        value = k.value;
        index = k.index;
        return *this;
    }
    ParanoidKey(int32_t index, int32_t value, OddTag) : value(value), index(index) {}
    ParanoidKey(ParanoidKey&& k) : value(k.value), index(k.index)
    {
        EXPECT_TRUE(k.isConstructed(), "source for move-construction is dead");
// std::stable_sort() fails in move semantics on paranoid test before VS2015
#if !defined(_MSC_VER) || _MSC_VER >= 1900
        k.index = Empty;
#endif
        ++KeyCount;
    }
    ParanoidKey&
    operator=(ParanoidKey&& k)
    {
        EXPECT_TRUE(k.isConstructed(), "source for move-assignment is dead");
        EXPECT_TRUE(isConstructed(), "destination for move-assignment is dead");
        value = k.value;
        index = k.index;
// std::stable_sort() fails in move semantics on paranoid test before VS2015
#if !defined(_MSC_VER) || _MSC_VER >= 1900
        k.index = Empty;
#endif
        return *this;
    }
    friend class KeyCompare;
    friend bool
    Equal(const ParanoidKey& x, const ParanoidKey& y);
};

class KeyCompare
{
    enum statusType
    {
        //! Special value used to mark defined object.
        Live = 0xabcd,
        //! Special value used to mark destroyed objects.
        Dead = -1
    } status;

  public:
    KeyCompare(OddTag) : status(Live) {}
    ~KeyCompare() { status = Dead; }
    bool
    operator()(const ParanoidKey& j, const ParanoidKey& k) const
    {
        EXPECT_TRUE(status == Live, "key comparison object not defined");
        EXPECT_TRUE(j.isLive(), "first key to operator() is not live");
        EXPECT_TRUE(k.isLive(), "second key to operator() is not live");
        return j.value < k.value;
    }
};

// Equal is equality comparison used for checking result of sort against expected result.
static bool
Equal(const ParanoidKey& x, const ParanoidKey& y)
{
    return (x.value == y.value && !Stable) || (x.index == y.index);
}

static bool
Equal(float32_t x, float32_t y)
{
    return x == y;
}

static bool
Equal(int32_t x, int32_t y)
{
    return x == y;
}

struct test_sort_with_compare
{
    template <typename Policy, typename InputIterator, typename OutputIterator, typename OutputIterator2, typename Size,
              typename Compare>
    typename std::enable_if<is_same_iterator_category<InputIterator, std::random_access_iterator_tag>::value,
                            void>::type
    operator()(Policy&& exec, OutputIterator tmp_first, OutputIterator tmp_last, OutputIterator2 expected_first,
               OutputIterator2 expected_last, InputIterator first, InputIterator, Size n, Compare compare)
    {
        using namespace std;
        copy_n(first, n, expected_first);
        copy_n(first, n, tmp_first);
        if (Stable)
            std::stable_sort(expected_first + 1, expected_last - 1, compare);
        else
            std::sort(expected_first + 1, expected_last - 1, compare);
        int32_t count0 = KeyCount;
        if (Stable)
            stable_sort(exec, tmp_first + 1, tmp_last - 1, compare);
        else
            sort(exec, tmp_first + 1, tmp_last - 1, compare);

        for (size_t i = 0; i < n; ++i, ++expected_first, ++tmp_first)
        {
            // Check that expected[i] is equal to tmp[i]
            EXPECT_TRUE(Equal(*expected_first, *tmp_first), "bad sort");
        }
        int32_t count1 = KeyCount;
        EXPECT_EQ(count0, count1, "key cleanup error");
    }
    template <typename Policy, typename InputIterator, typename OutputIterator, typename OutputIterator2, typename Size,
              typename Compare>
    typename std::enable_if<!is_same_iterator_category<InputIterator, std::random_access_iterator_tag>::value,
                            void>::type
    operator()(Policy&&, OutputIterator, OutputIterator, OutputIterator2, OutputIterator2, InputIterator, InputIterator,
               Size, Compare)
    {
    }
};

template <typename T, typename Compare, typename Convert>
void
test_sort(Compare compare, Convert convert)
{
    for (size_t n = 0; n < 100000; n = n <= 16 ? n + 1 : size_t(3.1415 * n))
    {
        LastIndex = n + 2;
        // The rand()%(2*n+1) encourages generation of some duplicates.
        // Sequence is padded with an extra element at front and back, to detect overwrite bugs.
        Sequence<T> in(n + 2, [=](size_t k) { return convert(k, rand() % (2 * n + 1)); });
        Sequence<T> expected(in);
        Sequence<T> tmp(in);
        invoke_on_all_policies(test_sort_with_compare(), tmp.begin(), tmp.end(), expected.begin(), expected.end(),
                               in.begin(), in.end(), in.size(), compare);
    }
}

template <typename T>
struct test_non_const
{
    template <typename Policy, typename Iterator>
    void
    operator()(Policy&& exec, Iterator iter)
    {
        sort(exec, iter, iter, non_const(std::less<T>()));
        stable_sort(exec, iter, iter, non_const(std::less<T>()));
    }
};

int
main()
{
    std::srand(42);
    for (int32_t kind = 0; kind < 2; ++kind)
    {
        Stable = kind != 0;
        test_sort<ParanoidKey>(KeyCompare(OddTag()),
                               [](size_t k, size_t val) { return ParanoidKey(k, val, OddTag()); });
        test_sort<float32_t>([](float32_t x, float32_t y) { return x < y; },
                             [](size_t, size_t val) { return float32_t(val); });
        test_sort<int32_t>(
            [](int32_t x, int32_t y) { return x > y; }, // Reversed so accidental use of < will be detected.
            [](size_t, size_t val) { return int32_t(val); });
    }

    test_algo_basic_single<int32_t>(run_for_rnd<test_non_const<int32_t>>());

    std::cout << done() << std::endl;
    return 0;
}