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]);
84 EXPECT_FALSE(reader.next());
85 EXPECT_EQ(reader.value(), std::numeric_limits<uint32_t>::max());
88 template <class Reader, class List>
89 void testSkip(const std::vector<uint32_t>& data, const List& list,
91 CHECK_GT(skipStep, 0);
93 EXPECT_EQ(reader.value(), 0);
94 for (size_t i = skipStep - 1; i < data.size(); i += skipStep) {
95 EXPECT_TRUE(reader.skip(skipStep));
96 EXPECT_EQ(reader.value(), data[i]);
98 EXPECT_FALSE(reader.skip(skipStep));
99 EXPECT_EQ(reader.value(), std::numeric_limits<uint32_t>::max());
100 EXPECT_FALSE(reader.next());
103 template <class Reader, class List>
104 void testSkip(const std::vector<uint32_t>& data, const List& list) {
105 for (size_t skipStep = 1; skipStep < 25; ++skipStep) {
106 testSkip<Reader, List>(data, list, skipStep);
108 for (size_t skipStep = 25; skipStep <= 500; skipStep += 25) {
109 testSkip<Reader, List>(data, list, skipStep);
113 template <class Reader, class List>
114 void testSkipTo(const std::vector<uint32_t>& data, const List& list,
116 CHECK_GT(skipToStep, 0);
119 EXPECT_EQ(reader.value(), 0);
121 const uint32_t delta = std::max<uint32_t>(1, data.back() / skipToStep);
122 uint32_t value = delta;
123 auto it = data.begin();
125 it = std::lower_bound(it, data.end(), value);
126 if (it == data.end()) {
127 EXPECT_FALSE(reader.skipTo(value));
130 EXPECT_TRUE(reader.skipTo(value));
131 EXPECT_EQ(reader.value(), *it);
132 value = reader.value() + delta;
134 EXPECT_EQ(reader.value(), std::numeric_limits<uint32_t>::max());
135 EXPECT_FALSE(reader.next());
138 template <class Reader, class List>
139 void testSkipTo(const std::vector<uint32_t>& data, const List& list) {
140 for (size_t steps = 10; steps < 100; steps += 10) {
141 testSkipTo<Reader, List>(data, list, steps);
143 for (size_t steps = 100; steps <= 1000; steps += 100) {
144 testSkipTo<Reader, List>(data, list, steps);
146 testSkipTo<Reader, List>(data, list, std::numeric_limits<size_t>::max());
149 EXPECT_FALSE(reader.skipTo(data.back() + 1));
150 EXPECT_EQ(reader.value(), std::numeric_limits<uint32_t>::max());
151 EXPECT_FALSE(reader.next());
155 template <class Reader, class List>
156 void testJump(const std::vector<uint32_t>& data, const List& list) {
158 std::vector<size_t> is(data.size());
159 for (size_t i = 0; i < data.size(); ++i) {
162 std::shuffle(is.begin(), is.end(), gen);
163 if (Reader::EncoderType::forwardQuantum == 0) {
164 is.resize(std::min<size_t>(is.size(), 100));
168 EXPECT_TRUE(reader.jump(0));
169 EXPECT_EQ(reader.value(), 0);
171 EXPECT_TRUE(reader.jump(i + 1));
172 EXPECT_EQ(reader.value(), data[i]);
174 EXPECT_FALSE(reader.jump(data.size() + 1));
175 EXPECT_EQ(reader.value(), std::numeric_limits<uint32_t>::max());
178 template <class Reader, class List>
179 void testJumpTo(const std::vector<uint32_t>& data, const List& list) {
180 CHECK(!data.empty());
185 std::uniform_int_distribution<> values(0, data.back());
186 const size_t iters = Reader::EncoderType::skipQuantum == 0 ? 100 : 10000;
187 for (size_t i = 0; i < iters; ++i) {
188 const uint32_t value = values(gen);
189 auto it = std::lower_bound(data.begin(), data.end(), value);
190 CHECK(it != data.end());
191 EXPECT_TRUE(reader.jumpTo(value));
192 EXPECT_EQ(reader.value(), *it);
195 EXPECT_TRUE(reader.jumpTo(0));
196 EXPECT_EQ(reader.value(), 0);
198 if (data.front() > 0) {
199 EXPECT_TRUE(reader.jumpTo(1));
200 EXPECT_EQ(reader.value(), data.front());
203 EXPECT_TRUE(reader.jumpTo(data.back()));
204 EXPECT_EQ(reader.value(), data.back());
206 EXPECT_FALSE(reader.jumpTo(data.back() + 1));
207 EXPECT_EQ(reader.value(), std::numeric_limits<uint32_t>::max());
210 template <class Reader, class Encoder>
212 const typename Encoder::ValueType* const data = nullptr;
213 auto list = Encoder::encode(data, data);
216 EXPECT_FALSE(reader.next());
217 EXPECT_EQ(reader.size(), 0);
221 EXPECT_FALSE(reader.skip(1));
222 EXPECT_FALSE(reader.skip(10));
223 EXPECT_FALSE(reader.jump(1));
224 EXPECT_FALSE(reader.jump(10));
228 EXPECT_FALSE(reader.skipTo(1));
229 EXPECT_FALSE(reader.jumpTo(1));
233 template <class Reader, class Encoder>
234 void testAll(const std::vector<uint32_t>& data) {
235 auto list = Encoder::encode(data.begin(), data.end());
236 testNext<Reader>(data, list);
237 testSkip<Reader>(data, list);
238 testSkipTo<Reader>(data, list);
239 testJump<Reader>(data, list);
240 testJumpTo<Reader>(data, list);
244 template <class Reader, class List>
245 void bmNext(const List& list, const std::vector<uint32_t>& data,
250 for (size_t i = 0, j; i < iters; ) {
252 for (j = 0; reader.next(); ++j, ++i) {
253 CHECK_EQ(reader.value(), data[j]) << j;
258 template <class Reader, class List>
259 void bmSkip(const List& list, const std::vector<uint32_t>& data,
260 size_t skip, size_t iters) {
261 if (skip >= data.size()) {
264 for (size_t i = 0, j; i < iters; ) {
266 for (j = skip - 1; j < data.size(); j += skip, ++i) {
268 CHECK_EQ(reader.value(), data[j]);
273 template <class Reader, class List>
274 void bmSkipTo(const List& list, const std::vector<uint32_t>& data,
275 size_t skip, size_t iters) {
276 if (skip >= data.size()) {
279 for (size_t i = 0, j; i < iters; ) {
281 for (j = 0; j < data.size(); j += skip, ++i) {
282 reader.skipTo(data[j]);
283 CHECK_EQ(reader.value(), data[j]);
288 template <class Reader, class List>
289 void bmJump(const List& list, const std::vector<uint32_t>& data,
290 const std::vector<size_t>& order, size_t iters) {
291 CHECK(!data.empty());
292 CHECK_EQ(data.size(), order.size());
295 for (size_t i = 0; i < iters; ) {
296 for (size_t j : order) {
298 CHECK_EQ(reader.value(), data[j]);
304 template <class Reader, class List>
305 void bmJumpTo(const List& list, const std::vector<uint32_t>& data,
306 const std::vector<size_t>& order, size_t iters) {
307 CHECK(!data.empty());
308 CHECK_EQ(data.size(), order.size());
311 for (size_t i = 0; i < iters; ) {
312 for (size_t j : order) {
313 reader.jumpTo(data[j]);
314 CHECK_EQ(reader.value(), data[j]);
322 #endif // FOLLY_EXPERIMENTAL_CODING_TEST_UTILS_H