folly/test/BitIteratorTest.cpp

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