Line data Source code
1 : // Copyright 2014 the V8 project authors. All rights reserved.
2 : // Use of this source code is governed by a BSD-style license that can be
3 : // found in the LICENSE file.
4 :
5 : #include <climits>
6 :
7 : #include "src/base/utils/random-number-generator.h"
8 : #include "testing/gtest/include/gtest/gtest.h"
9 :
10 : namespace v8 {
11 : namespace base {
12 :
13 486 : class RandomNumberGeneratorTest : public ::testing::TestWithParam<int> {};
14 :
15 : static const int kMaxRuns = 12345;
16 :
17 1444383 : static void CheckSample(std::vector<uint64_t> sample, uint64_t max,
18 : size_t size) {
19 2888766 : EXPECT_EQ(sample.size(), size);
20 :
21 : // Check if values are unique.
22 : std::sort(sample.begin(), sample.end());
23 4333149 : EXPECT_EQ(std::adjacent_find(sample.begin(), sample.end()), sample.end());
24 :
25 28331793 : for (uint64_t x : sample) {
26 26887410 : EXPECT_LT(x, max);
27 : }
28 1444383 : }
29 :
30 333315 : static void CheckSlowSample(const std::vector<uint64_t>& sample, uint64_t max,
31 : size_t size,
32 : const std::unordered_set<uint64_t>& excluded) {
33 666630 : CheckSample(sample, max, size);
34 :
35 1444365 : for (uint64_t i : sample) {
36 2222100 : EXPECT_FALSE(excluded.count(i));
37 : }
38 333315 : }
39 :
40 1111068 : static void TestNextSample(RandomNumberGenerator& rng, uint64_t max,
41 : size_t size, bool slow = false) {
42 : std::vector<uint64_t> sample =
43 2222136 : slow ? rng.NextSampleSlow(max, size) : rng.NextSample(max, size);
44 :
45 2222136 : CheckSample(sample, max, size);
46 1111068 : }
47 :
48 18480 : TEST_P(RandomNumberGeneratorTest, NextIntWithMaxValue) {
49 9 : RandomNumberGenerator rng(GetParam());
50 111114 : for (int max = 1; max <= kMaxRuns; ++max) {
51 111105 : int n = rng.NextInt(max);
52 111105 : EXPECT_LE(0, n);
53 111105 : EXPECT_LT(n, max);
54 : }
55 9 : }
56 :
57 :
58 18480 : TEST_P(RandomNumberGeneratorTest, NextBooleanReturnsFalseOrTrue) {
59 9 : RandomNumberGenerator rng(GetParam());
60 222219 : for (int k = 0; k < kMaxRuns; ++k) {
61 : bool b = rng.NextBool();
62 : EXPECT_TRUE(b == false || b == true);
63 : }
64 9 : }
65 :
66 :
67 18480 : TEST_P(RandomNumberGeneratorTest, NextDoubleReturnsValueBetween0And1) {
68 9 : RandomNumberGenerator rng(GetParam());
69 222219 : for (int k = 0; k < kMaxRuns; ++k) {
70 111105 : double d = rng.NextDouble();
71 111105 : EXPECT_LE(0.0, d);
72 111105 : EXPECT_LT(d, 1.0);
73 : }
74 9 : }
75 :
76 : #if GTEST_HAS_DEATH_TEST
77 15373 : TEST(RandomNumberGenerator, NextSampleInvalidParam) {
78 : RandomNumberGenerator rng(123);
79 : std::vector<uint64_t> sample;
80 2 : EXPECT_DEATH(sample = rng.NextSample(10, 11), ".*Check failed: n <= max.*");
81 1 : }
82 :
83 15373 : TEST(RandomNumberGenerator, NextSampleSlowInvalidParam1) {
84 : RandomNumberGenerator rng(123);
85 : std::vector<uint64_t> sample;
86 2 : EXPECT_DEATH(sample = rng.NextSampleSlow(10, 11),
87 0 : ".*Check failed: max - excluded.size*");
88 1 : }
89 :
90 15373 : TEST(RandomNumberGenerator, NextSampleSlowInvalidParam2) {
91 : RandomNumberGenerator rng(123);
92 : std::vector<uint64_t> sample;
93 2 : EXPECT_DEATH(sample = rng.NextSampleSlow(5, 3, {0, 2, 3}),
94 0 : ".*Check failed: max - excluded.size*");
95 1 : }
96 : #endif
97 :
98 18480 : TEST_P(RandomNumberGeneratorTest, NextSample0) {
99 : size_t m = 1;
100 9 : RandomNumberGenerator rng(GetParam());
101 :
102 9 : TestNextSample(rng, m, 0);
103 9 : }
104 :
105 18480 : TEST_P(RandomNumberGeneratorTest, NextSampleSlow0) {
106 : size_t m = 1;
107 9 : RandomNumberGenerator rng(GetParam());
108 :
109 9 : TestNextSample(rng, m, 0, true);
110 9 : }
111 :
112 18480 : TEST_P(RandomNumberGeneratorTest, NextSample1) {
113 : size_t m = 10;
114 9 : RandomNumberGenerator rng(GetParam());
115 :
116 222219 : for (int k = 0; k < kMaxRuns; ++k) {
117 111105 : TestNextSample(rng, m, 1);
118 : }
119 9 : }
120 :
121 18480 : TEST_P(RandomNumberGeneratorTest, NextSampleSlow1) {
122 : size_t m = 10;
123 9 : RandomNumberGenerator rng(GetParam());
124 :
125 222219 : for (int k = 0; k < kMaxRuns; ++k) {
126 111105 : TestNextSample(rng, m, 1, true);
127 : }
128 9 : }
129 :
130 18480 : TEST_P(RandomNumberGeneratorTest, NextSampleMax) {
131 : size_t m = 10;
132 9 : RandomNumberGenerator rng(GetParam());
133 :
134 222219 : for (int k = 0; k < kMaxRuns; ++k) {
135 111105 : TestNextSample(rng, m, m);
136 : }
137 9 : }
138 :
139 18480 : TEST_P(RandomNumberGeneratorTest, NextSampleSlowMax) {
140 : size_t m = 10;
141 9 : RandomNumberGenerator rng(GetParam());
142 :
143 222219 : for (int k = 0; k < kMaxRuns; ++k) {
144 111105 : TestNextSample(rng, m, m, true);
145 : }
146 9 : }
147 :
148 18480 : TEST_P(RandomNumberGeneratorTest, NextSampleHalf) {
149 : size_t n = 5;
150 : uint64_t m = 10;
151 9 : RandomNumberGenerator rng(GetParam());
152 :
153 222219 : for (int k = 0; k < kMaxRuns; ++k) {
154 111105 : TestNextSample(rng, m, n);
155 : }
156 9 : }
157 :
158 18480 : TEST_P(RandomNumberGeneratorTest, NextSampleSlowHalf) {
159 : size_t n = 5;
160 : uint64_t m = 10;
161 9 : RandomNumberGenerator rng(GetParam());
162 :
163 222219 : for (int k = 0; k < kMaxRuns; ++k) {
164 111105 : TestNextSample(rng, m, n, true);
165 : }
166 9 : }
167 :
168 18480 : TEST_P(RandomNumberGeneratorTest, NextSampleMoreThanHalf) {
169 : size_t n = 90;
170 : uint64_t m = 100;
171 9 : RandomNumberGenerator rng(GetParam());
172 :
173 222219 : for (int k = 0; k < kMaxRuns; ++k) {
174 111105 : TestNextSample(rng, m, n);
175 : }
176 9 : }
177 :
178 18480 : TEST_P(RandomNumberGeneratorTest, NextSampleSlowMoreThanHalf) {
179 : size_t n = 90;
180 : uint64_t m = 100;
181 9 : RandomNumberGenerator rng(GetParam());
182 :
183 222219 : for (int k = 0; k < kMaxRuns; ++k) {
184 111105 : TestNextSample(rng, m, n, true);
185 : }
186 9 : }
187 :
188 18480 : TEST_P(RandomNumberGeneratorTest, NextSampleLessThanHalf) {
189 : size_t n = 10;
190 : uint64_t m = 100;
191 9 : RandomNumberGenerator rng(GetParam());
192 :
193 222219 : for (int k = 0; k < kMaxRuns; ++k) {
194 111105 : TestNextSample(rng, m, n);
195 : }
196 9 : }
197 :
198 18480 : TEST_P(RandomNumberGeneratorTest, NextSampleSlowLessThanHalf) {
199 : size_t n = 10;
200 : uint64_t m = 100;
201 9 : RandomNumberGenerator rng(GetParam());
202 :
203 222219 : for (int k = 0; k < kMaxRuns; ++k) {
204 111105 : TestNextSample(rng, m, n, true);
205 : }
206 9 : }
207 :
208 18480 : TEST_P(RandomNumberGeneratorTest, NextSampleSlowExcluded) {
209 : size_t n = 2;
210 : uint64_t m = 10;
211 9 : std::unordered_set<uint64_t> excluded = {2, 4, 5, 9};
212 9 : RandomNumberGenerator rng(GetParam());
213 :
214 222219 : for (int k = 0; k < kMaxRuns; ++k) {
215 111105 : std::vector<uint64_t> sample = rng.NextSampleSlow(m, n, excluded);
216 :
217 111105 : CheckSlowSample(sample, m, n, excluded);
218 : }
219 9 : }
220 :
221 18480 : TEST_P(RandomNumberGeneratorTest, NextSampleSlowExcludedMax1) {
222 : size_t n = 1;
223 : uint64_t m = 5;
224 9 : std::unordered_set<uint64_t> excluded = {0, 2, 3, 4};
225 9 : RandomNumberGenerator rng(GetParam());
226 :
227 222219 : for (int k = 0; k < kMaxRuns; ++k) {
228 111105 : std::vector<uint64_t> sample = rng.NextSampleSlow(m, n, excluded);
229 :
230 111105 : CheckSlowSample(sample, m, n, excluded);
231 : }
232 9 : }
233 :
234 18480 : TEST_P(RandomNumberGeneratorTest, NextSampleSlowExcludedMax2) {
235 : size_t n = 7;
236 : uint64_t m = 10;
237 9 : std::unordered_set<uint64_t> excluded = {0, 4, 8};
238 9 : RandomNumberGenerator rng(GetParam());
239 :
240 222219 : for (int k = 0; k < kMaxRuns; ++k) {
241 111105 : std::vector<uint64_t> sample = rng.NextSampleSlow(m, n, excluded);
242 :
243 111105 : CheckSlowSample(sample, m, n, excluded);
244 : }
245 9 : }
246 :
247 1122010 : INSTANTIATE_TEST_SUITE_P(RandomSeeds, RandomNumberGeneratorTest,
248 : ::testing::Values(INT_MIN, -1, 0, 1, 42, 100,
249 : 1234567890, 987654321, INT_MAX));
250 :
251 : } // namespace base
252 9222 : } // namespace v8
|
