2 * Copyright 2016 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 #include <folly/Bits.h>
20 #include <type_traits>
24 #include <gtest/gtest.h>
26 #include <folly/Benchmark.h>
27 #include <folly/portability/GFlags.h>
29 using namespace folly;
30 using namespace folly::bititerator_detail;
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;
39 for (size_t i = 0; i < bits; ++i) {
46 template <class INT, class IT>
47 void checkRange(INT exp, IT begin, IT end) {
48 typedef typename std::make_unsigned<INT>::type utype;
51 auto bitEnd = makeBitIterator(end);
52 for (BitIterator<IT> it = makeBitIterator(begin); it != bitEnd; ++it, ++i) {
61 TEST(BitIterator, Simple) {
65 auto bi(makeBitIterator(v.begin()));
68 checkRange(0x0000004200000010ULL, v.begin(), v.end());
78 *++bi = true; // 128 (note pre-increment)
83 TEST(BitIterator, Const) {
87 auto bi(makeBitIterator(v.cbegin()));
94 template <class BaseIter>
95 BitIterator<BaseIter> simpleFFS(BitIterator<BaseIter> begin,
96 BitIterator<BaseIter> end) {
97 return std::find(begin, end, true);
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);
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);
117 size_t b = firstSet - 1;
118 data[b / bpb] |= (1ULL << (b % bpb));
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;
125 if (firstSet < startBit + 1 || firstSet >= endBit + 1) {
126 EXPECT_EQ(endBit, p - begin)
127 << " firstSet=" << firstSet << " startBit=" << startBit
128 << " endBit=" << endBit << " nblocks=" << nblocks;
130 EXPECT_EQ(firstSet - 1, p - begin)
131 << " firstSet=" << firstSet << " startBit=" << startBit
132 << " endBit=" << endBit << " nblocks=" << nblocks;
140 void runSimpleFFSTest(int iters) {
141 auto fn = simpleFFS<std::vector<uint64_t>::const_iterator>;
147 void runRealFFSTest(int iters) {
148 auto fn = findFirstSet<std::vector<uint64_t>::const_iterator>;
156 TEST(BitIterator, SimpleFindFirstSet) {
160 TEST(BitIterator, FindFirstSet) {
164 BENCHMARK(SimpleFFSTest, iters) {
165 runSimpleFFSTest(iters);
167 BENCHMARK(RealFFSTest, iters) {
168 runRealFFSTest(iters);
171 /* --bm_min_iters=10 --bm_max_iters=100
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
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();