folly/container/test/BitIteratorTest.cpp

   1 /*
   2  * Copyright 2011-present 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 #include <folly/container/BitIterator.h>
  18
  19 #include <algorithm>
  20 #include <limits>
  21 #include <type_traits>
  22 #include <vector>
  23
  24 #include <folly/Benchmark.h>
  25 #include <folly/portability/GFlags.h>
  26 #include <folly/portability/GTest.h>
  27
  28 using namespace folly;
  29 using namespace folly::bititerator_detail;
  30
  31 namespace {
  32
  33 template <class INT, class IT>
  34 void checkIt(INT exp, IT& it) {
  35   typedef typename std::make_unsigned<INT>::type utype;
  36   size_t bits = std::numeric_limits<utype>::digits;
  37   utype uexp = exp;
  38   for (size_t i = 0; i < bits; ++i) {
  39     bool e = uexp & 1;
  40     EXPECT_EQ(e, *it++);
  41     uexp >>= 1;
  42   }
  43 }
  44
  45 template <class INT, class IT>
  46 void checkRange(INT exp, IT begin, IT end) {
  47   typedef typename std::make_unsigned<INT>::type utype;
  48   utype uexp = exp;
  49   size_t i = 0;
  50   auto bitEnd = makeBitIterator(end);
  51   for (BitIterator<IT> it = makeBitIterator(begin); it != bitEnd; ++it, ++i) {
  52     bool e = uexp & 1;
  53     EXPECT_EQ(e, *it);
  54     uexp >>= 1;
  55   }
  56 }
  57
  58 } // namespace
  59
  60 TEST(BitIterator, Simple) {
  61   std::vector<int> v;
  62   v.push_back(0x10);
  63   v.push_back(0x42);
  64   auto bi(makeBitIterator(v.begin()));
  65   checkIt(0x10, bi);
  66   checkIt(0x42, bi);
  67   checkRange(0x0000004200000010ULL, v.begin(), v.end());
  68
  69   v[0] = 0;
  70   bi = v.begin();
  71   *bi++ = true;     // 1
  72   *bi++ = false;
  73   *bi++ = true;     // 4
  74   *bi++ = false;
  75   *bi++ = false;
  76   *bi++ = true;     // 32
  77   *++bi = true;     // 128 (note pre-increment)
  78
  79   EXPECT_EQ(165, v[0]);
  80 }
  81
  82 TEST(BitIterator, Const) {
  83   std::vector<int> v;
  84   v.push_back(0x10);
  85   v.push_back(0x42);
  86   auto bi(makeBitIterator(v.cbegin()));
  87   checkIt(0x10, bi);
  88   checkIt(0x42, bi);
  89 }
  90
  91 namespace {
  92
  93 template <class BaseIter>
  94 BitIterator<BaseIter> simpleFFS(BitIterator<BaseIter> begin,
  95                                 BitIterator<BaseIter> end) {
  96   return std::find(begin, end, true);
  97 }
  98
  99 template <class FFS>
 100 void runFFSTest(FFS fn) {
 101   static const size_t bpb = 8 * sizeof(uint64_t);
 102   std::vector<uint64_t> data;
 103   for (size_t nblocks = 1; nblocks <= 3; ++nblocks) {
 104     size_t nbits = nblocks * bpb;
 105     data.resize(nblocks);
 106     auto begin = makeBitIterator(data.cbegin());
 107     auto end = makeBitIterator(data.cend());
 108     EXPECT_EQ(nbits, end - begin);
 109     EXPECT_FALSE(begin == end);
 110
 111     // Try every possible combination of first bit set (including none),
 112     // start bit, end bit
 113     for (size_t firstSet = 0; firstSet <= nbits; ++firstSet) {
 114       data.assign(nblocks, 0);
 115       if (firstSet) {
 116         size_t b = firstSet - 1;
 117         data[b / bpb] |= (1ULL << (b % bpb));
 118       }
 119       for (size_t startBit = 0; startBit <= nbits; ++startBit) {
 120         for (size_t endBit = startBit; endBit <= nbits; ++endBit) {
 121           auto p = begin + startBit;
 122           auto q = begin + endBit;
 123           p = fn(p, q);
 124           if (firstSet < startBit + 1 || firstSet >= endBit + 1) {
 125             EXPECT_EQ(endBit, p - begin)
 126               << "  firstSet=" << firstSet << " startBit=" << startBit
 127               << " endBit=" << endBit << " nblocks=" << nblocks;
 128           } else {
 129             EXPECT_EQ(firstSet - 1, p - begin)
 130               << "  firstSet=" << firstSet << " startBit=" << startBit
 131               << " endBit=" << endBit << " nblocks=" << nblocks;
 132           }
 133         }
 134       }
 135     }
 136   }
 137 }
 138
 139 void runSimpleFFSTest(int iters) {
 140   auto fn = simpleFFS<std::vector<uint64_t>::const_iterator>;
 141   while (iters--) {
 142     runFFSTest(fn);
 143   }
 144 }
 145
 146 void runRealFFSTest(int iters) {
 147   auto fn = findFirstSet<std::vector<uint64_t>::const_iterator>;
 148   while (iters--) {
 149     runFFSTest(fn);
 150   }
 151 }
 152
 153 } // namespace
 154
 155 TEST(BitIterator, SimpleFindFirstSet) {
 156   runSimpleFFSTest(1);
 157 }
 158
 159 TEST(BitIterator, FindFirstSet) {
 160   runRealFFSTest(1);
 161 }
 162
 163 BENCHMARK(SimpleFFSTest, iters) {
 164   runSimpleFFSTest(iters);
 165 }
 166 BENCHMARK(RealFFSTest, iters) {
 167   runRealFFSTest(iters);
 168 }
 169
 170 /* --bm_min_iters=10 --bm_max_iters=100
 171
 172 Benchmark                               Iters   Total t    t/iter iter/sec
 173 ------------------------------------------------------------------------------
 174 runSimpleFFSTest                           10   4.82 s     482 ms  2.075
 175 runRealFFSTest                             19  2.011 s   105.9 ms  9.447
 176
 177 */
 178
 179 int main(int argc, char** argv) {
 180   testing::InitGoogleTest(&argc, argv);
 181   gflags::ParseCommandLineFlags(&argc, &argv, true);
 182   auto ret = RUN_ALL_TESTS();
 183   if (!ret && FLAGS_benchmark) {
 184     folly::runBenchmarks();
 185   }
 186   return ret;
 187 }