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 std::vector<uint32_t> generateRandomList(size_t n, uint32_t maxId) {
  33   CHECK_LT(n, 2 * maxId);
  34   std::mt19937 gen;
  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(gen);
  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 std::vector<uint32_t> generateSeqList(uint32_t minId, uint32_t maxId,
  50                                       uint32_t step = 1) {
  51   CHECK_LE(minId, maxId);
  52   CHECK_GT(step, 0);
  53   std::vector<uint32_t> ids;
  54   ids.reserve((maxId - minId) / step + 1);
  55   for (uint32_t i = minId; i <= maxId; i += step) {
  56     ids.push_back(i);
  57   }
  58   return ids;
  59 }
  60
  61 std::vector<uint32_t> loadList(const std::string& filename) {
  62   std::ifstream fin(filename);
  63   std::vector<uint32_t> result;
  64   uint32_t id;
  65   while (fin >> id) {
  66     result.push_back(id);
  67   }
  68   return result;
  69 }
  70
  71 template <class Reader, class List>
  72 void testNext(const std::vector<uint32_t>& data, const List& list) {
  73   Reader reader(list);
  74   EXPECT_EQ(reader.value(), 0);
  75   for (size_t i = 0; i < data.size(); ++i) {
  76     EXPECT_TRUE(reader.next());
  77     EXPECT_EQ(reader.value(), data[i]);
  78   }
  79   EXPECT_FALSE(reader.next());
  80   EXPECT_EQ(reader.value(), std::numeric_limits<uint32_t>::max());
  81 }
  82
  83 template <class Reader, class List>
  84 void testSkip(const std::vector<uint32_t>& data, const List& list,
  85               size_t skipStep) {
  86   CHECK_GT(skipStep, 0);
  87   Reader reader(list);
  88   EXPECT_EQ(reader.value(), 0);
  89   for (size_t i = skipStep - 1; i < data.size(); i += skipStep) {
  90     EXPECT_TRUE(reader.skip(skipStep));
  91     EXPECT_EQ(reader.value(), data[i]);
  92   }
  93   EXPECT_FALSE(reader.skip(skipStep));
  94   EXPECT_EQ(reader.value(), std::numeric_limits<uint32_t>::max());
  95   EXPECT_FALSE(reader.next());
  96 }
  97
  98 template <class Reader, class List>
  99 void testSkip(const std::vector<uint32_t>& data, const List& list) {
 100   for (size_t skipStep = 1; skipStep < 25; ++skipStep) {
 101     testSkip<Reader, List>(data, list, skipStep);
 102   }
 103   for (size_t skipStep = 25; skipStep <= 500; skipStep += 25) {
 104     testSkip<Reader, List>(data, list, skipStep);
 105   }
 106 }
 107
 108 template <class Reader, class List>
 109 void testSkipTo(const std::vector<uint32_t>& data, const List& list,
 110                 size_t skipToStep) {
 111   CHECK_GT(skipToStep, 0);
 112
 113   Reader reader(list);
 114   EXPECT_EQ(reader.value(), 0);
 115
 116   const uint32_t delta = std::max<uint32_t>(1, data.back() / skipToStep);
 117   uint32_t value = delta;
 118   auto it = data.begin();
 119   while (true) {
 120     it = std::lower_bound(it, data.end(), value);
 121     if (it == data.end()) {
 122       EXPECT_FALSE(reader.skipTo(value));
 123       break;
 124     }
 125     EXPECT_TRUE(reader.skipTo(value));
 126     EXPECT_EQ(reader.value(), *it);
 127     value = reader.value() + delta;
 128   }
 129
 130   EXPECT_EQ(reader.value(), std::numeric_limits<uint32_t>::max());
 131   EXPECT_FALSE(reader.next());
 132 }
 133
 134 template <class Reader, class List>
 135 void testSkipTo(const std::vector<uint32_t>& data, const List& list) {
 136   for (size_t steps = 10; steps < 100; steps += 10) {
 137     testSkipTo<Reader, List>(data, list, steps);
 138   }
 139   for (size_t steps = 100; steps <= 1000; steps += 100) {
 140     testSkipTo<Reader, List>(data, list, steps);
 141   }
 142   testSkipTo<Reader, List>(data, list, std::numeric_limits<size_t>::max());
 143   {
 144     Reader reader(list);
 145     EXPECT_FALSE(reader.skipTo(data.back() + 1));
 146     EXPECT_EQ(reader.value(), std::numeric_limits<uint32_t>::max());
 147     EXPECT_FALSE(reader.next());
 148   }
 149 }
 150
 151 template <class Reader, class Encoder>
 152 void testEmpty() {
 153   typename Encoder::CompressedList list;
 154   const typename Encoder::ValueType* const data = nullptr;
 155   Encoder::encode(data, 0, list);
 156   {
 157     Reader reader(list);
 158     EXPECT_FALSE(reader.next());
 159     EXPECT_EQ(reader.size(), 0);
 160   }
 161   {
 162     Reader reader(list);
 163     EXPECT_FALSE(reader.skip(1));
 164     EXPECT_FALSE(reader.skip(10));
 165   }
 166   {
 167     Reader reader(list);
 168     EXPECT_FALSE(reader.skipTo(1));
 169   }
 170 }
 171
 172 template <class Reader, class Encoder>
 173 void testAll(const std::vector<uint32_t>& data) {
 174   typename Encoder::CompressedList list;
 175   Encoder::encode(data.begin(), data.end(), list);
 176   testNext<Reader>(data, list);
 177   testSkip<Reader>(data, list);
 178   testSkipTo<Reader>(data, list);
 179   list.free();
 180 }
 181
 182 template <class Reader, class List>
 183 void bmNext(const List& list, const std::vector<uint32_t>& data,
 184             size_t iters) {
 185   if (data.empty()) {
 186     return;
 187   }
 188   for (size_t i = 0, j; i < iters; ) {
 189     Reader reader(list);
 190     for (j = 0; reader.next(); ++j, ++i) {
 191       const uint32_t value = reader.value();
 192       CHECK_EQ(value, data[j]) << j;
 193     }
 194   }
 195 }
 196
 197 template <class Reader, class List>
 198 void bmSkip(const List& list, const std::vector<uint32_t>& data,
 199             size_t skip, size_t iters) {
 200   if (skip >= data.size()) {
 201     return;
 202   }
 203   for (size_t i = 0, j; i < iters; ) {
 204     Reader reader(list);
 205     for (j = skip - 1; j < data.size(); j += skip, ++i) {
 206       reader.skip(skip);
 207       const uint32_t value = reader.value();
 208       CHECK_EQ(value, data[j]);
 209     }
 210   }
 211 }
 212
 213 template <class Reader, class List>
 214 void bmSkipTo(const List& list, const std::vector<uint32_t>& data,
 215               size_t skip, size_t iters) {
 216   if (skip >= data.size()) {
 217     return;
 218   }
 219   for (size_t i = 0, j; i < iters; ) {
 220     Reader reader(list);
 221     for (j = 0; j < data.size(); j += skip, ++i) {
 222       reader.skipTo(data[j]);
 223       const uint32_t value = reader.value();
 224       CHECK_EQ(value, data[j]);
 225     }
 226   }
 227 }
 228
 229 }}  // namespaces
 230
 231 #endif  // FOLLY_EXPERIMENTAL_CODING_TEST_UTILS_H