2 * Copyright 2016 Facebook, Inc.
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
17 #ifndef FOLLY_EXPERIMENTAL_CODING_TEST_UTILS_H
18 #define FOLLY_EXPERIMENTAL_CODING_TEST_UTILS_H
26 #include <unordered_set>
27 #include <glog/logging.h>
28 #include <gtest/gtest.h>
30 namespace folly { namespace compression {
33 std::vector<uint32_t> generateRandomList(size_t n, uint32_t maxId, URNG&& g) {
34 CHECK_LT(n, 2 * maxId);
35 std::uniform_int_distribution<> uid(1, maxId);
36 std::unordered_set<uint32_t> dataset;
37 while (dataset.size() < n) {
38 uint32_t value = uid(g);
39 if (dataset.count(value) == 0) {
40 dataset.insert(value);
44 std::vector<uint32_t> ids(dataset.begin(), dataset.end());
45 std::sort(ids.begin(), ids.end());
49 inline std::vector<uint32_t> generateRandomList(size_t n, uint32_t maxId) {
51 return generateRandomList(n, maxId, gen);
54 inline std::vector<uint32_t> generateSeqList(uint32_t minId, uint32_t maxId,
56 CHECK_LE(minId, maxId);
58 std::vector<uint32_t> ids;
59 ids.reserve((maxId - minId) / step + 1);
60 for (uint32_t i = minId; i <= maxId; i += step) {
66 inline std::vector<uint32_t> loadList(const std::string& filename) {
67 std::ifstream fin(filename);
68 std::vector<uint32_t> result;
76 // Test previousValue only if Reader has it.
77 template <class... Args>
78 void maybeTestPreviousValue(Args&&...) { }
80 // Make all the arguments template because if the types are not exact,
81 // the above overload will be picked (for example i could be size_t or
83 template <class Vector, class Reader, class Index>
84 auto maybeTestPreviousValue(const Vector& data, Reader& reader, Index i)
85 -> decltype(reader.previousValue(), void()) {
87 EXPECT_EQ(reader.previousValue(), data[i - 1]);
91 template <class Reader, class List>
92 void testNext(const std::vector<uint32_t>& data, const List& list) {
94 EXPECT_FALSE(reader.valid());
96 for (size_t i = 0; i < data.size(); ++i) {
97 EXPECT_TRUE(reader.next());
98 EXPECT_TRUE(reader.valid());
99 EXPECT_EQ(reader.value(), data[i]);
100 EXPECT_EQ(reader.position(), i);
101 maybeTestPreviousValue(data, reader, i);
103 EXPECT_FALSE(reader.next());
104 EXPECT_FALSE(reader.valid());
105 EXPECT_EQ(reader.position(), reader.size());
108 template <class Reader, class List>
109 void testSkip(const std::vector<uint32_t>& data, const List& list,
111 CHECK_GT(skipStep, 0);
114 for (size_t i = skipStep - 1; i < data.size(); i += skipStep) {
115 EXPECT_TRUE(reader.skip(skipStep));
116 EXPECT_TRUE(reader.valid());
117 EXPECT_EQ(reader.value(), data[i]);
118 EXPECT_EQ(reader.position(), i);
119 maybeTestPreviousValue(data, reader, i);
121 EXPECT_FALSE(reader.skip(skipStep));
122 EXPECT_FALSE(reader.valid());
123 EXPECT_EQ(reader.position(), reader.size());
124 EXPECT_FALSE(reader.next());
127 template <class Reader, class List>
128 void testSkip(const std::vector<uint32_t>& data, const List& list) {
129 for (size_t skipStep = 1; skipStep < 25; ++skipStep) {
130 testSkip<Reader, List>(data, list, skipStep);
132 for (size_t skipStep = 25; skipStep <= 500; skipStep += 25) {
133 testSkip<Reader, List>(data, list, skipStep);
137 template <class Reader, class List>
138 void testSkipTo(const std::vector<uint32_t>& data, const List& list,
140 CHECK_GT(skipToStep, 0);
143 const uint32_t delta = std::max<uint32_t>(1, data.back() / skipToStep);
144 uint32_t value = delta;
145 auto it = data.begin();
147 it = std::lower_bound(it, data.end(), value);
148 if (it == data.end()) {
149 EXPECT_FALSE(reader.skipTo(value));
152 EXPECT_TRUE(reader.skipTo(value));
153 EXPECT_TRUE(reader.valid());
154 EXPECT_EQ(reader.value(), *it);
155 EXPECT_EQ(reader.position(), std::distance(data.begin(), it));
156 value = reader.value() + delta;
157 maybeTestPreviousValue(data, reader, std::distance(data.begin(), it));
159 EXPECT_FALSE(reader.valid());
160 EXPECT_EQ(reader.position(), reader.size());
161 EXPECT_FALSE(reader.next());
164 template <class Reader, class List>
165 void testSkipTo(const std::vector<uint32_t>& data, const List& list) {
166 for (size_t steps = 10; steps < 100; steps += 10) {
167 testSkipTo<Reader, List>(data, list, steps);
169 for (size_t steps = 100; steps <= 1000; steps += 100) {
170 testSkipTo<Reader, List>(data, list, steps);
172 testSkipTo<Reader, List>(data, list, std::numeric_limits<size_t>::max());
174 // Skip to the first element.
176 EXPECT_TRUE(reader.skipTo(data[0]));
177 EXPECT_EQ(reader.value(), data[0]);
178 EXPECT_EQ(reader.position(), 0);
181 // Skip past the last element.
183 EXPECT_FALSE(reader.skipTo(data.back() + 1));
184 EXPECT_FALSE(reader.valid());
185 EXPECT_EQ(reader.position(), reader.size());
186 EXPECT_FALSE(reader.next());
189 // Skip to maximum integer.
191 using ValueType = typename Reader::ValueType;
192 EXPECT_FALSE(reader.skipTo(std::numeric_limits<ValueType>::max()));
193 EXPECT_FALSE(reader.valid());
194 EXPECT_EQ(reader.position(), reader.size());
195 EXPECT_FALSE(reader.next());
199 template <class Reader, class List>
200 void testJump(const std::vector<uint32_t>& data, const List& list) {
202 std::vector<size_t> is(data.size());
203 for (size_t i = 0; i < data.size(); ++i) {
206 std::shuffle(is.begin(), is.end(), gen);
207 if (Reader::EncoderType::forwardQuantum == 0) {
208 is.resize(std::min<size_t>(is.size(), 100));
213 EXPECT_TRUE(reader.jump(i));
214 EXPECT_EQ(reader.value(), data[i]);
215 EXPECT_EQ(reader.position(), i);
216 maybeTestPreviousValue(data, reader, i);
218 EXPECT_FALSE(reader.jump(data.size()));
219 EXPECT_FALSE(reader.valid());
220 EXPECT_EQ(reader.position(), reader.size());
223 template <class Reader, class List>
224 void testJumpTo(const std::vector<uint32_t>& data, const List& list) {
225 CHECK(!data.empty());
230 std::uniform_int_distribution<> values(0, data.back());
231 const size_t iters = Reader::EncoderType::skipQuantum == 0 ? 100 : 10000;
232 for (size_t i = 0; i < iters; ++i) {
233 const uint32_t value = values(gen);
234 auto it = std::lower_bound(data.begin(), data.end(), value);
235 CHECK(it != data.end());
236 EXPECT_TRUE(reader.jumpTo(value));
237 EXPECT_EQ(reader.value(), *it);
238 EXPECT_EQ(reader.position(), std::distance(data.begin(), it));
241 EXPECT_TRUE(reader.jumpTo(0));
242 EXPECT_EQ(reader.value(), data[0]);
243 EXPECT_EQ(reader.position(), 0);
245 EXPECT_TRUE(reader.jumpTo(data.back()));
246 EXPECT_EQ(reader.value(), data.back());
247 EXPECT_EQ(reader.position(), reader.size() - 1);
249 EXPECT_FALSE(reader.jumpTo(data.back() + 1));
250 EXPECT_FALSE(reader.valid());
251 EXPECT_EQ(reader.position(), reader.size());
254 template <class Reader, class Encoder>
256 const typename Encoder::ValueType* const data = nullptr;
257 auto list = Encoder::encode(data, data);
260 EXPECT_FALSE(reader.next());
261 EXPECT_EQ(reader.size(), 0);
265 EXPECT_FALSE(reader.skip(1));
266 EXPECT_FALSE(reader.skip(10));
267 EXPECT_FALSE(reader.jump(0));
268 EXPECT_FALSE(reader.jump(10));
272 EXPECT_FALSE(reader.skipTo(1));
273 EXPECT_FALSE(reader.jumpTo(1));
277 template <class Reader, class Encoder>
278 void testAll(const std::vector<uint32_t>& data) {
279 auto list = Encoder::encode(data.begin(), data.end());
280 testNext<Reader>(data, list);
281 testSkip<Reader>(data, list);
282 testSkipTo<Reader>(data, list);
283 testJump<Reader>(data, list);
284 testJumpTo<Reader>(data, list);
288 template <class Reader, class List>
289 void bmNext(const List& list, const std::vector<uint32_t>& data, size_t iters) {
295 for (size_t i = 0; i < iters; ++i) {
296 if (LIKELY(reader.next())) {
297 folly::doNotOptimizeAway(reader.value());
304 template <class Reader, class List>
305 void bmSkip(const List& list,
306 const std::vector<uint32_t>& /* data */,
309 size_t avg = (size_t(1) << logAvgSkip);
310 size_t base = avg - (avg >> 2);
311 size_t mask = (avg > 1) ? (avg >> 1) - 1 : 0;
314 for (size_t i = 0; i < iters; ++i) {
315 size_t skip = base + (i & mask);
316 if (LIKELY(reader.skip(skip))) {
317 folly::doNotOptimizeAway(reader.value());
324 template <class Reader, class List>
325 void bmSkipTo(const List& list, const std::vector<uint32_t>& data,
326 size_t logAvgSkip, size_t iters) {
327 size_t avg = (size_t(1) << logAvgSkip);
328 size_t base = avg - (avg >> 2);
329 size_t mask = (avg > 1) ? (avg >> 1) - 1 : 0;
332 for (size_t i = 0, j = -1; i < iters; ++i) {
333 size_t skip = base + (i & mask);
335 if (j >= data.size()) {
340 reader.skipTo(data[j]);
341 folly::doNotOptimizeAway(reader.value());
345 template <class Reader, class List>
346 void bmJump(const List& list, const std::vector<uint32_t>& data,
347 const std::vector<size_t>& order, size_t iters) {
348 CHECK(!data.empty());
349 CHECK_EQ(data.size(), order.size());
352 for (size_t i = 0, j = 0; i < iters; ++i, ++j) {
353 if (j == order.size()) j = 0;
354 reader.jump(order[j]);
355 folly::doNotOptimizeAway(reader.value());
359 template <class Reader, class List>
360 void bmJumpTo(const List& list, const std::vector<uint32_t>& data,
361 const std::vector<size_t>& order, size_t iters) {
362 CHECK(!data.empty());
363 CHECK_EQ(data.size(), order.size());
366 for (size_t i = 0, j = 0; i < iters; ++i, ++j) {
367 if (j == order.size()) j = 0;
368 reader.jumpTo(data[order[j]]);
369 folly::doNotOptimizeAway(reader.value());
375 #endif // FOLLY_EXPERIMENTAL_CODING_TEST_UTILS_H