2 * Copyright 2014 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 template <class Reader, class List>
77 void testNext(const std::vector<uint32_t>& data, const List& list) {
79 EXPECT_EQ(reader.value(), 0);
80 for (size_t i = 0; i < data.size(); ++i) {
81 EXPECT_TRUE(reader.next());
82 EXPECT_EQ(reader.value(), data[i]);
83 EXPECT_EQ(reader.position(), i);
85 EXPECT_FALSE(reader.next());
86 EXPECT_EQ(reader.value(), std::numeric_limits<uint32_t>::max());
87 EXPECT_EQ(reader.position(), reader.size());
90 template <class Reader, class List>
91 void testSkip(const std::vector<uint32_t>& data, const List& list,
93 CHECK_GT(skipStep, 0);
95 EXPECT_EQ(reader.value(), 0);
96 for (size_t i = skipStep - 1; i < data.size(); i += skipStep) {
97 EXPECT_TRUE(reader.skip(skipStep));
98 EXPECT_EQ(reader.value(), data[i]);
99 EXPECT_EQ(reader.position(), i);
101 EXPECT_FALSE(reader.skip(skipStep));
102 EXPECT_EQ(reader.value(), std::numeric_limits<uint32_t>::max());
103 EXPECT_EQ(reader.position(), reader.size());
104 EXPECT_FALSE(reader.next());
107 template <class Reader, class List>
108 void testSkip(const std::vector<uint32_t>& data, const List& list) {
109 for (size_t skipStep = 1; skipStep < 25; ++skipStep) {
110 testSkip<Reader, List>(data, list, skipStep);
112 for (size_t skipStep = 25; skipStep <= 500; skipStep += 25) {
113 testSkip<Reader, List>(data, list, skipStep);
117 template <class Reader, class List>
118 void testSkipTo(const std::vector<uint32_t>& data, const List& list,
120 CHECK_GT(skipToStep, 0);
123 EXPECT_EQ(reader.value(), 0);
125 const uint32_t delta = std::max<uint32_t>(1, data.back() / skipToStep);
126 uint32_t value = delta;
127 auto it = data.begin();
129 it = std::lower_bound(it, data.end(), value);
130 if (it == data.end()) {
131 EXPECT_FALSE(reader.skipTo(value));
134 EXPECT_TRUE(reader.skipTo(value));
135 EXPECT_EQ(reader.value(), *it);
136 value = reader.value() + delta;
138 EXPECT_EQ(reader.value(), std::numeric_limits<uint32_t>::max());
139 EXPECT_EQ(reader.position(), reader.size());
140 EXPECT_FALSE(reader.next());
143 template <class Reader, class List>
144 void testSkipTo(const std::vector<uint32_t>& data, const List& list) {
145 for (size_t steps = 10; steps < 100; steps += 10) {
146 testSkipTo<Reader, List>(data, list, steps);
148 for (size_t steps = 100; steps <= 1000; steps += 100) {
149 testSkipTo<Reader, List>(data, list, steps);
151 testSkipTo<Reader, List>(data, list, std::numeric_limits<size_t>::max());
154 EXPECT_FALSE(reader.skipTo(data.back() + 1));
155 EXPECT_EQ(reader.value(), std::numeric_limits<uint32_t>::max());
156 EXPECT_EQ(reader.position(), reader.size());
157 EXPECT_FALSE(reader.next());
161 template <class Reader, class List>
162 void testJump(const std::vector<uint32_t>& data, const List& list) {
164 std::vector<size_t> is(data.size());
165 for (size_t i = 0; i < data.size(); ++i) {
168 std::shuffle(is.begin(), is.end(), gen);
169 if (Reader::EncoderType::forwardQuantum == 0) {
170 is.resize(std::min<size_t>(is.size(), 100));
174 EXPECT_TRUE(reader.jump(0));
175 EXPECT_EQ(reader.value(), 0);
177 EXPECT_TRUE(reader.jump(i + 1));
178 EXPECT_EQ(reader.value(), data[i]);
179 EXPECT_EQ(reader.position(), i);
181 EXPECT_FALSE(reader.jump(data.size() + 1));
182 EXPECT_EQ(reader.value(), std::numeric_limits<uint32_t>::max());
183 EXPECT_EQ(reader.position(), reader.size());
186 template <class Reader, class List>
187 void testJumpTo(const std::vector<uint32_t>& data, const List& list) {
188 CHECK(!data.empty());
193 std::uniform_int_distribution<> values(0, data.back());
194 const size_t iters = Reader::EncoderType::skipQuantum == 0 ? 100 : 10000;
195 for (size_t i = 0; i < iters; ++i) {
196 const uint32_t value = values(gen);
197 auto it = std::lower_bound(data.begin(), data.end(), value);
198 CHECK(it != data.end());
199 EXPECT_TRUE(reader.jumpTo(value));
200 EXPECT_EQ(reader.value(), *it);
201 EXPECT_EQ(reader.position(), std::distance(data.begin(), it));
204 EXPECT_TRUE(reader.jumpTo(0));
205 EXPECT_EQ(reader.value(), 0);
206 EXPECT_EQ(reader.position(), -1);
208 if (data.front() > 0) {
209 EXPECT_TRUE(reader.jumpTo(1));
210 EXPECT_EQ(reader.value(), data.front());
211 EXPECT_EQ(reader.position(), 0);
214 EXPECT_TRUE(reader.jumpTo(data.back()));
215 EXPECT_EQ(reader.value(), data.back());
216 EXPECT_EQ(reader.position(), reader.size() - 1);
218 EXPECT_FALSE(reader.jumpTo(data.back() + 1));
219 EXPECT_EQ(reader.value(), std::numeric_limits<uint32_t>::max());
220 EXPECT_EQ(reader.position(), reader.size());
223 template <class Reader, class Encoder>
225 const typename Encoder::ValueType* const data = nullptr;
226 auto list = Encoder::encode(data, data);
229 EXPECT_FALSE(reader.next());
230 EXPECT_EQ(reader.size(), 0);
234 EXPECT_FALSE(reader.skip(1));
235 EXPECT_FALSE(reader.skip(10));
236 EXPECT_FALSE(reader.jump(1));
237 EXPECT_FALSE(reader.jump(10));
241 EXPECT_FALSE(reader.skipTo(1));
242 EXPECT_FALSE(reader.jumpTo(1));
246 template <class Reader, class Encoder>
247 void testAll(const std::vector<uint32_t>& data) {
248 auto list = Encoder::encode(data.begin(), data.end());
249 testNext<Reader>(data, list);
250 testSkip<Reader>(data, list);
251 testSkipTo<Reader>(data, list);
252 testJump<Reader>(data, list);
253 testJumpTo<Reader>(data, list);
257 template <class Reader, class List>
258 void bmNext(const List& list, const std::vector<uint32_t>& data, size_t iters) {
264 for (size_t i = 0; i < iters; ++i) {
265 if (LIKELY(reader.next())) {
266 folly::doNotOptimizeAway(reader.value());
273 template <class Reader, class List>
274 void bmSkip(const List& list, const std::vector<uint32_t>& data,
275 size_t logAvgSkip, size_t iters) {
276 size_t avg = (size_t(1) << logAvgSkip);
277 size_t base = avg - (avg >> 2);
278 size_t mask = (avg > 1) ? (avg >> 1) - 1 : 0;
281 for (size_t i = 0; i < iters; ++i) {
282 size_t skip = base + (i & mask);
283 if (LIKELY(reader.skip(skip))) {
284 folly::doNotOptimizeAway(reader.value());
291 template <class Reader, class List>
292 void bmSkipTo(const List& list, const std::vector<uint32_t>& data,
293 size_t logAvgSkip, size_t iters) {
294 size_t avg = (size_t(1) << logAvgSkip);
295 size_t base = avg - (avg >> 2);
296 size_t mask = (avg > 1) ? (avg >> 1) - 1 : 0;
299 for (size_t i = 0, j = -1; i < iters; ++i) {
300 size_t skip = base + (i & mask);
302 if (j >= data.size()) {
307 reader.skipTo(data[j]);
308 folly::doNotOptimizeAway(reader.value());
312 template <class Reader, class List>
313 void bmJump(const List& list, const std::vector<uint32_t>& data,
314 const std::vector<size_t>& order, size_t iters) {
315 CHECK(!data.empty());
316 CHECK_EQ(data.size(), order.size());
319 for (size_t i = 0, j = 0; i < iters; ++i, ++j) {
320 if (j == order.size()) j = 0;
321 reader.jump(order[j]);
322 folly::doNotOptimizeAway(reader.value());
326 template <class Reader, class List>
327 void bmJumpTo(const List& list, const std::vector<uint32_t>& data,
328 const std::vector<size_t>& order, size_t iters) {
329 CHECK(!data.empty());
330 CHECK_EQ(data.size(), order.size());
333 for (size_t i = 0, j = 0; i < iters; ++i, ++j) {
334 if (j == order.size()) j = 0;
335 reader.jumpTo(data[order[j]]);
336 folly::doNotOptimizeAway(reader.value());
342 #endif // FOLLY_EXPERIMENTAL_CODING_TEST_UTILS_H