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 BENCHMARK_GENERATE_INPUT_H
10#define BENCHMARK_GENERATE_INPUT_H
11
12#include <algorithm>
13#include <climits>
14#include <concepts>
15#include <cstddef>
16#include <initializer_list>
17#include <random>
18#include <string>
19#include <vector>
20
21static const char Letters[] = {
22 '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K',
23 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z', 'a', 'b', 'c', 'd', 'e', 'f',
24 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};
25static const std::size_t LettersSize = sizeof(Letters);
26
27inline std::default_random_engine& getRandomEngine() {
28 static std::default_random_engine RandEngine(std::random_device{}());
29 return RandEngine;
30}
31
32inline char getRandomChar() {
33 std::uniform_int_distribution<> LettersDist(0, LettersSize - 1);
34 return Letters[LettersDist(getRandomEngine())];
35}
36
37template <class IntT>
38inline IntT getRandomInteger(IntT Min, IntT Max) {
39 std::uniform_int_distribution<unsigned long long> dist(Min, Max);
40 return static_cast<IntT>(dist(getRandomEngine()));
41}
42
43inline std::string getRandomString(std::size_t Len) {
44 std::string str(Len, 0);
45 std::generate_n(first: str.begin(), n: Len, gen: &getRandomChar);
46 return str;
47}
48
49template <class IntT>
50inline std::vector<IntT> getDuplicateIntegerInputs(std::size_t N) {
51 std::vector<IntT> inputs(N, static_cast<IntT>(-1));
52 return inputs;
53}
54
55template <class IntT>
56inline std::vector<IntT> getSortedIntegerInputs(std::size_t N) {
57 std::vector<IntT> inputs;
58 inputs.reserve(N);
59 for (std::size_t i = 0; i < N; i += 1)
60 inputs.push_back(i);
61 return inputs;
62}
63
64template <class IntT>
65std::vector<IntT> getSortedLargeIntegerInputs(std::size_t N) {
66 std::vector<IntT> inputs;
67 inputs.reserve(N);
68 for (std::size_t i = 0; i < N; ++i)
69 inputs.push_back(i + N);
70 return inputs;
71}
72
73template <class IntT>
74std::vector<IntT> getSortedTopBitsIntegerInputs(std::size_t N) {
75 std::vector<IntT> inputs = getSortedIntegerInputs<IntT>(N);
76 for (auto& E : inputs)
77 E <<= ((sizeof(IntT) / 2) * CHAR_BIT);
78 return inputs;
79}
80
81template <class IntT>
82inline std::vector<IntT> getReverseSortedIntegerInputs(std::size_t N) {
83 std::vector<IntT> inputs;
84 inputs.reserve(N);
85 std::size_t i = N;
86 while (i > 0) {
87 --i;
88 inputs.push_back(i);
89 }
90 return inputs;
91}
92
93template <class IntT>
94std::vector<IntT> getPipeOrganIntegerInputs(std::size_t N) {
95 std::vector<IntT> v;
96 v.reserve(N);
97 for (std::size_t i = 0; i < N / 2; ++i)
98 v.push_back(i);
99 for (std::size_t i = N / 2; i < N; ++i)
100 v.push_back(N - i);
101 return v;
102}
103
104template <class IntT>
105std::vector<IntT> getRandomIntegerInputs(std::size_t N) {
106 std::vector<IntT> inputs;
107 inputs.reserve(N);
108 for (std::size_t i = 0; i < N; ++i)
109 inputs.push_back(getRandomInteger<IntT>(0, std::numeric_limits<IntT>::max()));
110 return inputs;
111}
112
113inline std::vector<std::string> getRandomStringInputsWithLength(std::size_t N, std::size_t len) { // N-by-len
114 std::vector<std::string> inputs;
115 inputs.reserve(n: N);
116 for (std::size_t i = 0; i < N; ++i)
117 inputs.push_back(x: getRandomString(Len: len));
118 return inputs;
119}
120
121inline std::vector<std::string> getDuplicateStringInputs(std::size_t N) {
122 std::vector<std::string> inputs(N, getRandomString(Len: 1024));
123 return inputs;
124}
125
126inline std::vector<std::string> getRandomStringInputs(std::size_t N) {
127 return getRandomStringInputsWithLength(N, len: 1024);
128}
129
130template <class IntT>
131std::vector<std::vector<IntT>> getRandomIntegerInputsWithLength(std::size_t N, std::size_t len) { // N-by-len
132 std::vector<std::vector<IntT>> inputs;
133 inputs.reserve(N);
134 for (std::size_t i = 0; i < N; ++i)
135 inputs.push_back(getRandomIntegerInputs<IntT>(len));
136 return inputs;
137}
138
139inline std::vector<std::string> getSSORandomStringInputs(size_t N) {
140 std::vector<std::string> inputs;
141 for (size_t i = 0; i < N; ++i)
142 inputs.push_back(x: getRandomString(Len: 10)); // SSO
143 return inputs;
144}
145
146inline std::vector<std::string> getPrefixedRandomStringInputs(size_t N) {
147 std::vector<std::string> inputs;
148 inputs.reserve(n: N);
149 constexpr int kSuffixLength = 32;
150 const std::string prefix = getRandomString(Len: 1024 - kSuffixLength);
151 for (std::size_t i = 0; i < N; ++i)
152 inputs.push_back(x: prefix + getRandomString(Len: kSuffixLength));
153 return inputs;
154}
155
156inline std::vector<std::string> getSortedStringInputs(std::size_t N) {
157 std::vector<std::string> inputs = getRandomStringInputs(N);
158 std::sort(first: inputs.begin(), last: inputs.end());
159 return inputs;
160}
161
162inline std::vector<std::string> getReverseSortedStringInputs(std::size_t N) {
163 std::vector<std::string> inputs = getSortedStringInputs(N);
164 std::reverse(first: inputs.begin(), last: inputs.end());
165 return inputs;
166}
167
168inline std::vector<const char*> getRandomCStringInputs(std::size_t N) {
169 static std::vector<std::string> inputs = getRandomStringInputs(N);
170 std::vector<const char*> cinputs;
171 for (auto const& str : inputs)
172 cinputs.push_back(x: str.c_str());
173 return cinputs;
174}
175
176template <class T>
177struct Generate {
178 // When the contents don't matter
179 static T arbitrary();
180
181 // Prefer a cheap-to-construct element if possible
182 static T cheap();
183
184 // Prefer an expensive-to-construct element if possible
185 static T expensive();
186};
187
188template <class T>
189 requires std::integral<T>
190struct Generate<T> {
191 static T arbitrary() { return 42; }
192 static T cheap() { return 42; }
193 static T expensive() { return 42; }
194 static T random() { return getRandomInteger<T>(std::numeric_limits<T>::min(), std::numeric_limits<T>::max()); }
195};
196
197template <>
198struct Generate<std::string> {
199 static std::string arbitrary() { return "hello world"; }
200 static std::string cheap() { return "small"; }
201 static std::string expensive() { return std::string(256, 'x'); }
202 static std::string random() {
203 auto length = getRandomInteger<std::size_t>(Min: 1, Max: 1024);
204 return getRandomString(Len: length);
205 }
206};
207
208template <class T>
209T random_different_from(std::initializer_list<T> others) {
210 T value;
211 do {
212 value = Generate<T>::random();
213 } while (std::find(others.begin(), others.end(), value) != others.end());
214 return value;
215}
216
217#endif // BENCHMARK_GENERATE_INPUT_H
218

source code of libcxx/test/benchmarks/GenerateInput.h