folly/experimental/test/CodingTestUtils.h

   1 /*
   2  * Copyright 2014 Facebook, Inc.
   3  *
   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
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  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.
  15  */
  16
  17 #ifndef FOLLY_EXPERIMENTAL_CODING_TEST_UTILS_H
  18 #define FOLLY_EXPERIMENTAL_CODING_TEST_UTILS_H
  19
  20 #include <algorithm>
  21 #include <fstream>
  22 #include <limits>
  23 #include <random>
  24 #include <string>
  25 #include <vector>
  26 #include <unordered_set>
  27 #include <glog/logging.h>
  28 #include <gtest/gtest.h>
  29
  30 namespace folly { namespace compression {
  31
  32 template <class URNG>
  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);
  41     }
  42   }
  43
  44   std::vector<uint32_t> ids(dataset.begin(), dataset.end());
  45   std::sort(ids.begin(), ids.end());
  46   return ids;
  47 }
  48
  49 inline std::vector<uint32_t> generateRandomList(size_t n, uint32_t maxId) {
  50   std::mt19937 gen;
  51   return generateRandomList(n, maxId, gen);
  52 }
  53
  54 inline std::vector<uint32_t> generateSeqList(uint32_t minId, uint32_t maxId,
  55                                              uint32_t step = 1) {
  56   CHECK_LE(minId, maxId);
  57   CHECK_GT(step, 0);
  58   std::vector<uint32_t> ids;
  59   ids.reserve((maxId - minId) / step + 1);
  60   for (uint32_t i = minId; i <= maxId; i += step) {
  61     ids.push_back(i);
  62   }
  63   return ids;
  64 }
  65
  66 inline std::vector<uint32_t> loadList(const std::string& filename) {
  67   std::ifstream fin(filename);
  68   std::vector<uint32_t> result;
  69   uint32_t id;
  70   while (fin >> id) {
  71     result.push_back(id);
  72   }
  73   return result;
  74 }
  75
  76 template <class Reader, class List>
  77 void testNext(const std::vector<uint32_t>& data, const List& list) {
  78   Reader reader(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   }
  84   EXPECT_FALSE(reader.next());
  85   EXPECT_EQ(reader.value(), std::numeric_limits<uint32_t>::max());
  86 }
  87
  88 template <class Reader, class List>
  89 void testSkip(const std::vector<uint32_t>& data, const List& list,
  90               size_t skipStep) {
  91   CHECK_GT(skipStep, 0);
  92   Reader reader(list);
  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]);
  97   }
  98   EXPECT_FALSE(reader.skip(skipStep));
  99   EXPECT_EQ(reader.value(), std::numeric_limits<uint32_t>::max());
 100   EXPECT_FALSE(reader.next());
 101 }
 102
 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);
 107   }
 108   for (size_t skipStep = 25; skipStep <= 500; skipStep += 25) {
 109     testSkip<Reader, List>(data, list, skipStep);
 110   }
 111 }
 112
 113 template <class Reader, class List>
 114 void testSkipTo(const std::vector<uint32_t>& data, const List& list,
 115                 size_t skipToStep) {
 116   CHECK_GT(skipToStep, 0);
 117
 118   Reader reader(list);
 119   EXPECT_EQ(reader.value(), 0);
 120
 121   const uint32_t delta = std::max<uint32_t>(1, data.back() / skipToStep);
 122   uint32_t value = delta;
 123   auto it = data.begin();
 124   while (true) {
 125     it = std::lower_bound(it, data.end(), value);
 126     if (it == data.end()) {
 127       EXPECT_FALSE(reader.skipTo(value));
 128       break;
 129     }
 130     EXPECT_TRUE(reader.skipTo(value));
 131     EXPECT_EQ(reader.value(), *it);
 132     value = reader.value() + delta;
 133   }
 134   EXPECT_EQ(reader.value(), std::numeric_limits<uint32_t>::max());
 135   EXPECT_FALSE(reader.next());
 136 }
 137
 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);
 142   }
 143   for (size_t steps = 100; steps <= 1000; steps += 100) {
 144     testSkipTo<Reader, List>(data, list, steps);
 145   }
 146   testSkipTo<Reader, List>(data, list, std::numeric_limits<size_t>::max());
 147   {
 148     Reader reader(list);
 149     EXPECT_FALSE(reader.skipTo(data.back() + 1));
 150     EXPECT_EQ(reader.value(), std::numeric_limits<uint32_t>::max());
 151     EXPECT_FALSE(reader.next());
 152   }
 153 }
 154
 155 template <class Reader, class List>
 156 void testJump(const std::vector<uint32_t>& data, const List& list) {
 157   std::mt19937 gen;
 158   std::vector<size_t> is(data.size());
 159   for (size_t i = 0; i < data.size(); ++i) {
 160     is[i] = i;
 161   }
 162   std::shuffle(is.begin(), is.end(), gen);
 163   if (Reader::EncoderType::forwardQuantum == 0) {
 164     is.resize(std::min<size_t>(is.size(), 100));
 165   }
 166
 167   Reader reader(list);
 168   EXPECT_TRUE(reader.jump(0));
 169   EXPECT_EQ(reader.value(), 0);
 170   for (auto i : is) {
 171     EXPECT_TRUE(reader.jump(i + 1));
 172     EXPECT_EQ(reader.value(), data[i]);
 173   }
 174   EXPECT_FALSE(reader.jump(data.size() + 1));
 175   EXPECT_EQ(reader.value(), std::numeric_limits<uint32_t>::max());
 176 }
 177
 178 template <class Reader, class List>
 179 void testJumpTo(const std::vector<uint32_t>& data, const List& list) {
 180   CHECK(!data.empty());
 181
 182   Reader reader(list);
 183
 184   std::mt19937 gen;
 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);
 193   }
 194
 195   EXPECT_TRUE(reader.jumpTo(0));
 196   EXPECT_EQ(reader.value(), 0);
 197
 198   if (data.front() > 0) {
 199     EXPECT_TRUE(reader.jumpTo(1));
 200     EXPECT_EQ(reader.value(), data.front());
 201   }
 202
 203   EXPECT_TRUE(reader.jumpTo(data.back()));
 204   EXPECT_EQ(reader.value(), data.back());
 205
 206   EXPECT_FALSE(reader.jumpTo(data.back() + 1));
 207   EXPECT_EQ(reader.value(), std::numeric_limits<uint32_t>::max());
 208 }
 209
 210 template <class Reader, class Encoder>
 211 void testEmpty() {
 212   const typename Encoder::ValueType* const data = nullptr;
 213   auto list = Encoder::encode(data, data);
 214   {
 215     Reader reader(list);
 216     EXPECT_FALSE(reader.next());
 217     EXPECT_EQ(reader.size(), 0);
 218   }
 219   {
 220     Reader reader(list);
 221     EXPECT_FALSE(reader.skip(1));
 222     EXPECT_FALSE(reader.skip(10));
 223     EXPECT_FALSE(reader.jump(1));
 224     EXPECT_FALSE(reader.jump(10));
 225   }
 226   {
 227     Reader reader(list);
 228     EXPECT_FALSE(reader.skipTo(1));
 229     EXPECT_FALSE(reader.jumpTo(1));
 230   }
 231 }
 232
 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);
 241   list.free();
 242 }
 243
 244 template <class Reader, class List>
 245 void bmNext(const List& list, const std::vector<uint32_t>& data,
 246             size_t iters) {
 247   if (data.empty()) {
 248     return;
 249   }
 250   for (size_t i = 0, j; i < iters; ) {
 251     Reader reader(list);
 252     for (j = 0; reader.next(); ++j, ++i) {
 253       CHECK_EQ(reader.value(), data[j]) << j;
 254     }
 255   }
 256 }
 257
 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()) {
 262     return;
 263   }
 264   for (size_t i = 0, j; i < iters; ) {
 265     Reader reader(list);
 266     for (j = skip - 1; j < data.size(); j += skip, ++i) {
 267       reader.skip(skip);
 268       CHECK_EQ(reader.value(), data[j]);
 269     }
 270   }
 271 }
 272
 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()) {
 277     return;
 278   }
 279   for (size_t i = 0, j; i < iters; ) {
 280     Reader reader(list);
 281     for (j = 0; j < data.size(); j += skip, ++i) {
 282       reader.skipTo(data[j]);
 283       CHECK_EQ(reader.value(), data[j]);
 284     }
 285   }
 286 }
 287
 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());
 293
 294   Reader reader(list);
 295   for (size_t i = 0; i < iters; ) {
 296     for (size_t j : order) {
 297       reader.jump(j + 1);
 298       CHECK_EQ(reader.value(), data[j]);
 299       ++i;
 300     }
 301   }
 302 }
 303
 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());
 309
 310   Reader reader(list);
 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]);
 315       ++i;
 316     }
 317   }
 318 }
 319
 320 }}  // namespaces
 321
 322 #endif  // FOLLY_EXPERIMENTAL_CODING_TEST_UTILS_H