142 lines · c
1//===----------------------------------------------------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef LIBCXX_TEST_BENCHMARKS_ALGORITHMS_SORTING_COMMON_H10#define LIBCXX_TEST_BENCHMARKS_ALGORITHMS_SORTING_COMMON_H11 12#include <algorithm>13#include <cstddef>14#include <numeric>15#include <random>16#include <type_traits>17#include <vector>18 19namespace support {20 21// This function creates a vector with N int-like values.22//23// These values are arranged in such a way that they would invoke O(N^2)24// behavior on any quick sort implementation that satisifies certain conditions.25// Details are available in the following paper:26//27// "A Killer Adversary for Quicksort", M. D. McIlroy, Software-Practice &28// Experience Volume 29 Issue 4 April 10, 1999 pp 341-344.29// https://dl.acm.org/doi/10.5555/311868.311871.30template <class T>31std::vector<T> quicksort_adversarial_data(std::size_t n) {32 static_assert(std::is_integral_v<T>);33 assert(n > 0);34 35 // If an element is equal to gas, it indicates that the value of the element36 // is still to be decided and may change over the course of time.37 T gas = n - 1;38 39 std::vector<T> v;40 v.resize(n);41 for (unsigned int i = 0; i < n; ++i) {42 v[i] = gas;43 }44 // Candidate for the pivot position.45 int candidate = 0;46 int nsolid = 0;47 // Populate all positions in the generated input to gas.48 std::vector<int> ascending_values(v.size());49 50 // Fill up with ascending values from 0 to v.size()-1. These will act as51 // indices into v.52 std::iota(ascending_values.begin(), ascending_values.end(), 0);53 std::sort(ascending_values.begin(), ascending_values.end(), [&](int x, int y) {54 if (v[x] == gas && v[y] == gas) {55 // We are comparing two inputs whose value is still to be decided.56 if (x == candidate) {57 v[x] = nsolid++;58 } else {59 v[y] = nsolid++;60 }61 }62 if (v[x] == gas) {63 candidate = x;64 } else if (v[y] == gas) {65 candidate = y;66 }67 return v[x] < v[y];68 });69 return v;70}71 72// ascending sorted values73template <class T>74std::vector<T> ascending_sorted_data(std::size_t n) {75 std::vector<T> v(n);76 std::iota(v.begin(), v.end(), 0);77 return v;78}79 80// descending sorted values81template <class T>82std::vector<T> descending_sorted_data(std::size_t n) {83 std::vector<T> v(n);84 std::iota(v.begin(), v.end(), 0);85 std::reverse(v.begin(), v.end());86 return v;87}88 89// pipe-organ pattern90template <class T>91std::vector<T> pipe_organ_data(std::size_t n) {92 std::vector<T> v(n);93 std::iota(v.begin(), v.end(), 0);94 auto half = v.begin() + v.size() / 2;95 std::reverse(half, v.end());96 return v;97}98 99// heap pattern100template <class T>101std::vector<T> heap_data(std::size_t n) {102 std::vector<T> v(n);103 std::iota(v.begin(), v.end(), 0);104 std::make_heap(v.begin(), v.end());105 return v;106}107 108// shuffled randomly109template <class T>110std::vector<T> shuffled_data(std::size_t n) {111 std::vector<T> v(n);112 std::iota(v.begin(), v.end(), 0);113 std::mt19937 rng;114 std::shuffle(v.begin(), v.end(), rng);115 return v;116}117 118// single element in the whole sequence119template <class T>120std::vector<T> single_element_data(std::size_t n) {121 std::vector<T> v(n);122 return v;123}124 125struct NonIntegral {126 NonIntegral() : value_(0) {}127 NonIntegral(int i) : value_(i) {}128 friend auto operator<(NonIntegral const& a, NonIntegral const& b) { return a.value_ < b.value_; }129 friend auto operator>(NonIntegral const& a, NonIntegral const& b) { return a.value_ > b.value_; }130 friend auto operator<=(NonIntegral const& a, NonIntegral const& b) { return a.value_ <= b.value_; }131 friend auto operator>=(NonIntegral const& a, NonIntegral const& b) { return a.value_ >= b.value_; }132 friend auto operator==(NonIntegral const& a, NonIntegral const& b) { return a.value_ == b.value_; }133 friend auto operator!=(NonIntegral const& a, NonIntegral const& b) { return a.value_ != b.value_; }134 135private:136 int value_;137};138 139} // namespace support140 141#endif // LIBCXX_TEST_BENCHMARKS_ALGORITHMS_SORTING_COMMON_H142