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-exception
6//
7//===----------------------------------------------------------------------===//
8
9#ifndef LIBCXX_TEST_BENCHMARKS_ALGORITHMS_SORTING_COMMON_H
10#define LIBCXX_TEST_BENCHMARKS_ALGORITHMS_SORTING_COMMON_H
11
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 element
36 // 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 as
51 // indices into v.
52 std::iota(first: ascending_values.begin(), last: ascending_values.end(), value: 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 values
73template <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 values
81template <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 pattern
90template <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 pattern
100template <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 randomly
109template <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 sequence
119template <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 support
140
141#endif // LIBCXX_TEST_BENCHMARKS_ALGORITHMS_SORTING_COMMON_H
142

source code of libcxx/test/benchmarks/algorithms/sorting/common.h