From: Yedidya Feldblum Date: Fri, 5 Jan 2018 03:44:07 +0000 (-0800) Subject: Move folly/BitIterator.h to folly/container/ X-Git-Tag: v2018.01.08.00~11 X-Git-Url: http://plrg.eecs.uci.edu/git/?p=folly.git;a=commitdiff_plain;h=f6ed4a26c0f3e6ba12788206e54add9db18e4dd6 Move folly/BitIterator.h to folly/container/ Summary: [Folly] Move `folly/BitIterator.h` to `folly/container/`. Reviewed By: djwatson Differential Revision: D6648357 fbshipit-source-id: 5617e3210f58435fcbf3ef07fa745da47dbce475 --- diff --git a/CMakeLists.txt b/CMakeLists.txt index dd5dff53..df597cfc 100755 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -337,6 +337,7 @@ if (BUILD_TESTS) DIRECTORY container/test/ TEST access_test SOURCES AccessTest.cpp TEST array_test SOURCES ArrayTest.cpp + TEST bit_iterator_test SOURCES BitIteratorTest.cpp TEST enumerate_test SOURCES EnumerateTest.cpp TEST evicting_cache_map_test SOURCES EvictingCacheMapTest.cpp TEST foreach_test SOURCES ForeachTest.cpp @@ -563,7 +564,6 @@ if (BUILD_TESTS) TEST atomic_linked_list_test SOURCES AtomicLinkedListTest.cpp TEST atomic_struct_test SOURCES AtomicStructTest.cpp TEST atomic_unordered_map_test SOURCES AtomicUnorderedMapTest.cpp - TEST bit_iterator_test SOURCES BitIteratorTest.cpp TEST cacheline_padded_test SOURCES CachelinePaddedTest.cpp TEST clock_gettime_wrappers_test SOURCES ClockGettimeWrappersTest.cpp TEST concurrent_skip_list_test SOURCES ConcurrentSkipListTest.cpp diff --git a/folly/BitIterator.h b/folly/BitIterator.h deleted file mode 100644 index 0446bd13..00000000 --- a/folly/BitIterator.h +++ /dev/null @@ -1,209 +0,0 @@ -/* - * Copyright 2017 Facebook, Inc. - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -/** - * BitIterator - * Wrapper around an iterator over an integral type that iterates - * over its underlying bits in MSb to LSb order - * - * findFirstSet(BitIterator begin, BitIterator end) - * return a BitIterator pointing to the first 1 bit in [begin, end), or - * end if all bits in [begin, end) are 0 - * - * @author Tudor Bosman (tudorb@fb.com) - */ - -#pragma once - -#include -#include -#include -#include -#include -#include -#include - -#include - -#include -#include -#include - -namespace folly { - -/** - * Fast bit iteration facility. - */ - -template -class BitIterator; -template -BitIterator findFirstSet( - BitIterator, - BitIterator); -/** - * Wrapper around an iterator over an integer type that iterates - * over its underlying bits in LSb to MSb order. - * - * BitIterator models the same iterator concepts as the base iterator. - */ -template -class BitIterator : public bititerator_detail::BitIteratorBase::type { - public: - /** - * Return the number of bits in an element of the underlying iterator. - */ - static unsigned int bitsPerBlock() { - return std::numeric_limits::value_type>::type>::digits; - } - - /** - * Construct a BitIterator that points at a given bit offset (default 0) - * in iter. - */ - explicit BitIterator(const BaseIter& iter, size_t bitOff = 0) - : bititerator_detail::BitIteratorBase::type(iter), - bitOffset_(bitOff) { - assert(bitOffset_ < bitsPerBlock()); - } - - size_t bitOffset() const { - return bitOffset_; - } - - void advanceToNextBlock() { - bitOffset_ = 0; - ++this->base_reference(); - } - - BitIterator& operator=(const BaseIter& other) { - this->~BitIterator(); - new (this) BitIterator(other); - return *this; - } - - private: - friend class boost::iterator_core_access; - friend BitIterator findFirstSet<>(BitIterator, BitIterator); - - typedef bititerator_detail::BitReference< - typename std::iterator_traits::reference, - typename std::iterator_traits::value_type> - BitRef; - - void advanceInBlock(size_t n) { - bitOffset_ += n; - assert(bitOffset_ < bitsPerBlock()); - } - - BitRef dereference() const { - return BitRef(*this->base_reference(), bitOffset_); - } - - void advance(ssize_t n) { - size_t bpb = bitsPerBlock(); - ssize_t blocks = n / ssize_t(bpb); - bitOffset_ += n % bpb; - if (bitOffset_ >= bpb) { - bitOffset_ -= bpb; - ++blocks; - } - this->base_reference() += blocks; - } - - void increment() { - if (++bitOffset_ == bitsPerBlock()) { - advanceToNextBlock(); - } - } - - void decrement() { - if (bitOffset_-- == 0) { - bitOffset_ = bitsPerBlock() - 1; - --this->base_reference(); - } - } - - bool equal(const BitIterator& other) const { - return ( - bitOffset_ == other.bitOffset_ && - this->base_reference() == other.base_reference()); - } - - ssize_t distance_to(const BitIterator& other) const { - return ssize_t( - (other.base_reference() - this->base_reference()) * bitsPerBlock() + - other.bitOffset_ - bitOffset_); - } - - size_t bitOffset_; -}; - -/** - * Helper function, so you can write - * auto bi = makeBitIterator(container.begin()); - */ -template -BitIterator makeBitIterator(const BaseIter& iter) { - return BitIterator(iter); -} - -/** - * Find first bit set in a range of bit iterators. - * 4.5x faster than the obvious std::find(begin, end, true); - */ -template -BitIterator findFirstSet( - BitIterator begin, - BitIterator end) { - // shortcut to avoid ugly static_cast<> - static const typename BaseIter::value_type one = 1; - - while (begin.base() != end.base()) { - typename BaseIter::value_type v = *begin.base(); - // mask out the bits that don't matter (< begin.bitOffset) - v &= ~((one << begin.bitOffset()) - 1); - size_t firstSet = findFirstSet(v); - if (firstSet) { - --firstSet; // now it's 0-based - assert(firstSet >= begin.bitOffset()); - begin.advanceInBlock(firstSet - begin.bitOffset()); - return begin; - } - begin.advanceToNextBlock(); - } - - // now begin points to the same block as end - if (end.bitOffset() != 0) { // assume end is dereferenceable - typename BaseIter::value_type v = *begin.base(); - // mask out the bits that don't matter (< begin.bitOffset) - v &= ~((one << begin.bitOffset()) - 1); - // mask out the bits that don't matter (>= end.bitOffset) - v &= (one << end.bitOffset()) - 1; - size_t firstSet = findFirstSet(v); - if (firstSet) { - --firstSet; // now it's 0-based - assert(firstSet >= begin.bitOffset()); - begin.advanceInBlock(firstSet - begin.bitOffset()); - return begin; - } - } - - return end; -} - -} // namespace folly diff --git a/folly/Makefile.am b/folly/Makefile.am index c5b9d9ca..8144f806 100644 --- a/folly/Makefile.am +++ b/folly/Makefile.am @@ -57,6 +57,7 @@ nobase_follyinclude_HEADERS = \ concurrency/UnboundedQueue.h \ container/Access.h \ container/Array.h \ + container/detail/BitIteratorDetail.h \ container/Iterator.h \ container/Enumerate.h \ container/EvictingCacheMap.h \ @@ -67,7 +68,6 @@ nobase_follyinclude_HEADERS = \ detail/AtFork.h \ detail/AtomicHashUtils.h \ detail/AtomicUnorderedMapUtils.h \ - detail/BitIteratorDetail.h \ detail/DiscriminatedPtrDetail.h \ detail/FileUtilDetail.h \ detail/FingerprintPolynomial.h \ diff --git a/folly/container/BitIterator.h b/folly/container/BitIterator.h new file mode 100644 index 00000000..c071e89f --- /dev/null +++ b/folly/container/BitIterator.h @@ -0,0 +1,209 @@ +/* + * Copyright 2011-present Facebook, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +/** + * BitIterator + * Wrapper around an iterator over an integral type that iterates + * over its underlying bits in MSb to LSb order + * + * findFirstSet(BitIterator begin, BitIterator end) + * return a BitIterator pointing to the first 1 bit in [begin, end), or + * end if all bits in [begin, end) are 0 + * + * @author Tudor Bosman (tudorb@fb.com) + */ + +#pragma once + +#include +#include +#include +#include +#include +#include +#include + +#include + +#include +#include +#include + +namespace folly { + +/** + * Fast bit iteration facility. + */ + +template +class BitIterator; +template +BitIterator findFirstSet( + BitIterator, + BitIterator); +/** + * Wrapper around an iterator over an integer type that iterates + * over its underlying bits in LSb to MSb order. + * + * BitIterator models the same iterator concepts as the base iterator. + */ +template +class BitIterator : public bititerator_detail::BitIteratorBase::type { + public: + /** + * Return the number of bits in an element of the underlying iterator. + */ + static unsigned int bitsPerBlock() { + return std::numeric_limits::value_type>::type>::digits; + } + + /** + * Construct a BitIterator that points at a given bit offset (default 0) + * in iter. + */ + explicit BitIterator(const BaseIter& iter, size_t bitOff = 0) + : bititerator_detail::BitIteratorBase::type(iter), + bitOffset_(bitOff) { + assert(bitOffset_ < bitsPerBlock()); + } + + size_t bitOffset() const { + return bitOffset_; + } + + void advanceToNextBlock() { + bitOffset_ = 0; + ++this->base_reference(); + } + + BitIterator& operator=(const BaseIter& other) { + this->~BitIterator(); + new (this) BitIterator(other); + return *this; + } + + private: + friend class boost::iterator_core_access; + friend BitIterator findFirstSet<>(BitIterator, BitIterator); + + typedef bititerator_detail::BitReference< + typename std::iterator_traits::reference, + typename std::iterator_traits::value_type> + BitRef; + + void advanceInBlock(size_t n) { + bitOffset_ += n; + assert(bitOffset_ < bitsPerBlock()); + } + + BitRef dereference() const { + return BitRef(*this->base_reference(), bitOffset_); + } + + void advance(ssize_t n) { + size_t bpb = bitsPerBlock(); + ssize_t blocks = n / ssize_t(bpb); + bitOffset_ += n % bpb; + if (bitOffset_ >= bpb) { + bitOffset_ -= bpb; + ++blocks; + } + this->base_reference() += blocks; + } + + void increment() { + if (++bitOffset_ == bitsPerBlock()) { + advanceToNextBlock(); + } + } + + void decrement() { + if (bitOffset_-- == 0) { + bitOffset_ = bitsPerBlock() - 1; + --this->base_reference(); + } + } + + bool equal(const BitIterator& other) const { + return ( + bitOffset_ == other.bitOffset_ && + this->base_reference() == other.base_reference()); + } + + ssize_t distance_to(const BitIterator& other) const { + return ssize_t( + (other.base_reference() - this->base_reference()) * bitsPerBlock() + + other.bitOffset_ - bitOffset_); + } + + size_t bitOffset_; +}; + +/** + * Helper function, so you can write + * auto bi = makeBitIterator(container.begin()); + */ +template +BitIterator makeBitIterator(const BaseIter& iter) { + return BitIterator(iter); +} + +/** + * Find first bit set in a range of bit iterators. + * 4.5x faster than the obvious std::find(begin, end, true); + */ +template +BitIterator findFirstSet( + BitIterator begin, + BitIterator end) { + // shortcut to avoid ugly static_cast<> + static const typename BaseIter::value_type one = 1; + + while (begin.base() != end.base()) { + typename BaseIter::value_type v = *begin.base(); + // mask out the bits that don't matter (< begin.bitOffset) + v &= ~((one << begin.bitOffset()) - 1); + size_t firstSet = findFirstSet(v); + if (firstSet) { + --firstSet; // now it's 0-based + assert(firstSet >= begin.bitOffset()); + begin.advanceInBlock(firstSet - begin.bitOffset()); + return begin; + } + begin.advanceToNextBlock(); + } + + // now begin points to the same block as end + if (end.bitOffset() != 0) { // assume end is dereferenceable + typename BaseIter::value_type v = *begin.base(); + // mask out the bits that don't matter (< begin.bitOffset) + v &= ~((one << begin.bitOffset()) - 1); + // mask out the bits that don't matter (>= end.bitOffset) + v &= (one << end.bitOffset()) - 1; + size_t firstSet = findFirstSet(v); + if (firstSet) { + --firstSet; // now it's 0-based + assert(firstSet >= begin.bitOffset()); + begin.advanceInBlock(firstSet - begin.bitOffset()); + return begin; + } + } + + return end; +} + +} // namespace folly diff --git a/folly/container/detail/BitIteratorDetail.h b/folly/container/detail/BitIteratorDetail.h new file mode 100644 index 00000000..be9883b9 --- /dev/null +++ b/folly/container/detail/BitIteratorDetail.h @@ -0,0 +1,89 @@ +/* + * Copyright 2011-present Facebook, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#pragma once + +#include +#include + +#include + +namespace folly { + +template class BitIterator; + +namespace bititerator_detail { + +// Reference to a bit. +// Templatize on both parent reference and value types to capture +// const-ness correctly and to work with the case where Ref is a +// reference-like type (not T&), just like our BitReference here. +template +class BitReference { + public: + BitReference(Ref r, size_t bit) : ref_(r), bit_(bit) { } + + /* implicit */ operator bool() const { + return ref_ & (one_ << bit_); + } + + BitReference& operator=(bool b) { + if (b) { + set(); + } else { + clear(); + } + return *this; + } + + void set() { + ref_ |= (one_ << bit_); + } + + void clear() { + ref_ &= ~(one_ << bit_); + } + + void flip() { + ref_ ^= (one_ << bit_); + } + + private: + // shortcut to avoid writing static_cast everywhere + const static Value one_ = 1; + + Ref ref_; + size_t bit_; +}; + +template +struct BitIteratorBase { + static_assert(std::is_integral::value, + "BitIterator may only be used with integral types"); + typedef boost::iterator_adaptor< + BitIterator, // Derived + BaseIter, // Base + bool, // Value + boost::use_default, // CategoryOrTraversal + bititerator_detail::BitReference< + typename std::iterator_traits::reference, + typename std::iterator_traits::value_type + >, // Reference + ssize_t> type; +}; + +} // namespace bititerator_detail +} // namespace folly diff --git a/folly/container/test/BitIteratorTest.cpp b/folly/container/test/BitIteratorTest.cpp new file mode 100644 index 00000000..e452ad87 --- /dev/null +++ b/folly/container/test/BitIteratorTest.cpp @@ -0,0 +1,187 @@ +/* + * Copyright 2011-present Facebook, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include + +#include +#include +#include +#include + +#include +#include +#include + +using namespace folly; +using namespace folly::bititerator_detail; + +namespace { + +template +void checkIt(INT exp, IT& it) { + typedef typename std::make_unsigned::type utype; + size_t bits = std::numeric_limits::digits; + utype uexp = exp; + for (size_t i = 0; i < bits; ++i) { + bool e = uexp & 1; + EXPECT_EQ(e, *it++); + uexp >>= 1; + } +} + +template +void checkRange(INT exp, IT begin, IT end) { + typedef typename std::make_unsigned::type utype; + utype uexp = exp; + size_t i = 0; + auto bitEnd = makeBitIterator(end); + for (BitIterator it = makeBitIterator(begin); it != bitEnd; ++it, ++i) { + bool e = uexp & 1; + EXPECT_EQ(e, *it); + uexp >>= 1; + } +} + +} // namespace + +TEST(BitIterator, Simple) { + std::vector v; + v.push_back(0x10); + v.push_back(0x42); + auto bi(makeBitIterator(v.begin())); + checkIt(0x10, bi); + checkIt(0x42, bi); + checkRange(0x0000004200000010ULL, v.begin(), v.end()); + + v[0] = 0; + bi = v.begin(); + *bi++ = true; // 1 + *bi++ = false; + *bi++ = true; // 4 + *bi++ = false; + *bi++ = false; + *bi++ = true; // 32 + *++bi = true; // 128 (note pre-increment) + + EXPECT_EQ(165, v[0]); +} + +TEST(BitIterator, Const) { + std::vector v; + v.push_back(0x10); + v.push_back(0x42); + auto bi(makeBitIterator(v.cbegin())); + checkIt(0x10, bi); + checkIt(0x42, bi); +} + +namespace { + +template +BitIterator simpleFFS(BitIterator begin, + BitIterator end) { + return std::find(begin, end, true); +} + +template +void runFFSTest(FFS fn) { + static const size_t bpb = 8 * sizeof(uint64_t); + std::vector data; + for (size_t nblocks = 1; nblocks <= 3; ++nblocks) { + size_t nbits = nblocks * bpb; + data.resize(nblocks); + auto begin = makeBitIterator(data.cbegin()); + auto end = makeBitIterator(data.cend()); + EXPECT_EQ(nbits, end - begin); + EXPECT_FALSE(begin == end); + + // Try every possible combination of first bit set (including none), + // start bit, end bit + for (size_t firstSet = 0; firstSet <= nbits; ++firstSet) { + data.assign(nblocks, 0); + if (firstSet) { + size_t b = firstSet - 1; + data[b / bpb] |= (1ULL << (b % bpb)); + } + for (size_t startBit = 0; startBit <= nbits; ++startBit) { + for (size_t endBit = startBit; endBit <= nbits; ++endBit) { + auto p = begin + startBit; + auto q = begin + endBit; + p = fn(p, q); + if (firstSet < startBit + 1 || firstSet >= endBit + 1) { + EXPECT_EQ(endBit, p - begin) + << " firstSet=" << firstSet << " startBit=" << startBit + << " endBit=" << endBit << " nblocks=" << nblocks; + } else { + EXPECT_EQ(firstSet - 1, p - begin) + << " firstSet=" << firstSet << " startBit=" << startBit + << " endBit=" << endBit << " nblocks=" << nblocks; + } + } + } + } + } +} + +void runSimpleFFSTest(int iters) { + auto fn = simpleFFS::const_iterator>; + while (iters--) { + runFFSTest(fn); + } +} + +void runRealFFSTest(int iters) { + auto fn = findFirstSet::const_iterator>; + while (iters--) { + runFFSTest(fn); + } +} + +} // namespace + +TEST(BitIterator, SimpleFindFirstSet) { + runSimpleFFSTest(1); +} + +TEST(BitIterator, FindFirstSet) { + runRealFFSTest(1); +} + +BENCHMARK(SimpleFFSTest, iters) { + runSimpleFFSTest(iters); +} +BENCHMARK(RealFFSTest, iters) { + runRealFFSTest(iters); +} + +/* --bm_min_iters=10 --bm_max_iters=100 + +Benchmark Iters Total t t/iter iter/sec +------------------------------------------------------------------------------ +runSimpleFFSTest 10 4.82 s 482 ms 2.075 +runRealFFSTest 19 2.011 s 105.9 ms 9.447 + +*/ + +int main(int argc, char** argv) { + testing::InitGoogleTest(&argc, argv); + gflags::ParseCommandLineFlags(&argc, &argv, true); + auto ret = RUN_ALL_TESTS(); + if (!ret && FLAGS_benchmark) { + folly::runBenchmarks(); + } + return ret; +} diff --git a/folly/detail/BitIteratorDetail.h b/folly/detail/BitIteratorDetail.h deleted file mode 100644 index 7f4f57e3..00000000 --- a/folly/detail/BitIteratorDetail.h +++ /dev/null @@ -1,89 +0,0 @@ -/* - * Copyright 2017 Facebook, Inc. - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#pragma once - -#include -#include - -#include - -namespace folly { - -template class BitIterator; - -namespace bititerator_detail { - -// Reference to a bit. -// Templatize on both parent reference and value types to capture -// const-ness correctly and to work with the case where Ref is a -// reference-like type (not T&), just like our BitReference here. -template -class BitReference { - public: - BitReference(Ref r, size_t bit) : ref_(r), bit_(bit) { } - - /* implicit */ operator bool() const { - return ref_ & (one_ << bit_); - } - - BitReference& operator=(bool b) { - if (b) { - set(); - } else { - clear(); - } - return *this; - } - - void set() { - ref_ |= (one_ << bit_); - } - - void clear() { - ref_ &= ~(one_ << bit_); - } - - void flip() { - ref_ ^= (one_ << bit_); - } - - private: - // shortcut to avoid writing static_cast everywhere - const static Value one_ = 1; - - Ref ref_; - size_t bit_; -}; - -template -struct BitIteratorBase { - static_assert(std::is_integral::value, - "BitIterator may only be used with integral types"); - typedef boost::iterator_adaptor< - BitIterator, // Derived - BaseIter, // Base - bool, // Value - boost::use_default, // CategoryOrTraversal - bititerator_detail::BitReference< - typename std::iterator_traits::reference, - typename std::iterator_traits::value_type - >, // Reference - ssize_t> type; -}; - -} // namespace bititerator_detail -} // namespace folly diff --git a/folly/io/async/HHWheelTimer.cpp b/folly/io/async/HHWheelTimer.cpp index dd7301f5..2e22a6d2 100644 --- a/folly/io/async/HHWheelTimer.cpp +++ b/folly/io/async/HHWheelTimer.cpp @@ -17,10 +17,10 @@ #include #include -#include #include #include #include +#include #include diff --git a/folly/test/BitIteratorTest.cpp b/folly/test/BitIteratorTest.cpp deleted file mode 100644 index 0fd13a2c..00000000 --- a/folly/test/BitIteratorTest.cpp +++ /dev/null @@ -1,187 +0,0 @@ -/* - * Copyright 2017 Facebook, Inc. - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#include - -#include -#include -#include -#include - -#include -#include -#include - -using namespace folly; -using namespace folly::bititerator_detail; - -namespace { - -template -void checkIt(INT exp, IT& it) { - typedef typename std::make_unsigned::type utype; - size_t bits = std::numeric_limits::digits; - utype uexp = exp; - for (size_t i = 0; i < bits; ++i) { - bool e = uexp & 1; - EXPECT_EQ(e, *it++); - uexp >>= 1; - } -} - -template -void checkRange(INT exp, IT begin, IT end) { - typedef typename std::make_unsigned::type utype; - utype uexp = exp; - size_t i = 0; - auto bitEnd = makeBitIterator(end); - for (BitIterator it = makeBitIterator(begin); it != bitEnd; ++it, ++i) { - bool e = uexp & 1; - EXPECT_EQ(e, *it); - uexp >>= 1; - } -} - -} // namespace - -TEST(BitIterator, Simple) { - std::vector v; - v.push_back(0x10); - v.push_back(0x42); - auto bi(makeBitIterator(v.begin())); - checkIt(0x10, bi); - checkIt(0x42, bi); - checkRange(0x0000004200000010ULL, v.begin(), v.end()); - - v[0] = 0; - bi = v.begin(); - *bi++ = true; // 1 - *bi++ = false; - *bi++ = true; // 4 - *bi++ = false; - *bi++ = false; - *bi++ = true; // 32 - *++bi = true; // 128 (note pre-increment) - - EXPECT_EQ(165, v[0]); -} - -TEST(BitIterator, Const) { - std::vector v; - v.push_back(0x10); - v.push_back(0x42); - auto bi(makeBitIterator(v.cbegin())); - checkIt(0x10, bi); - checkIt(0x42, bi); -} - -namespace { - -template -BitIterator simpleFFS(BitIterator begin, - BitIterator end) { - return std::find(begin, end, true); -} - -template -void runFFSTest(FFS fn) { - static const size_t bpb = 8 * sizeof(uint64_t); - std::vector data; - for (size_t nblocks = 1; nblocks <= 3; ++nblocks) { - size_t nbits = nblocks * bpb; - data.resize(nblocks); - auto begin = makeBitIterator(data.cbegin()); - auto end = makeBitIterator(data.cend()); - EXPECT_EQ(nbits, end - begin); - EXPECT_FALSE(begin == end); - - // Try every possible combination of first bit set (including none), - // start bit, end bit - for (size_t firstSet = 0; firstSet <= nbits; ++firstSet) { - data.assign(nblocks, 0); - if (firstSet) { - size_t b = firstSet - 1; - data[b / bpb] |= (1ULL << (b % bpb)); - } - for (size_t startBit = 0; startBit <= nbits; ++startBit) { - for (size_t endBit = startBit; endBit <= nbits; ++endBit) { - auto p = begin + startBit; - auto q = begin + endBit; - p = fn(p, q); - if (firstSet < startBit + 1 || firstSet >= endBit + 1) { - EXPECT_EQ(endBit, p - begin) - << " firstSet=" << firstSet << " startBit=" << startBit - << " endBit=" << endBit << " nblocks=" << nblocks; - } else { - EXPECT_EQ(firstSet - 1, p - begin) - << " firstSet=" << firstSet << " startBit=" << startBit - << " endBit=" << endBit << " nblocks=" << nblocks; - } - } - } - } - } -} - -void runSimpleFFSTest(int iters) { - auto fn = simpleFFS::const_iterator>; - while (iters--) { - runFFSTest(fn); - } -} - -void runRealFFSTest(int iters) { - auto fn = findFirstSet::const_iterator>; - while (iters--) { - runFFSTest(fn); - } -} - -} // namespace - -TEST(BitIterator, SimpleFindFirstSet) { - runSimpleFFSTest(1); -} - -TEST(BitIterator, FindFirstSet) { - runRealFFSTest(1); -} - -BENCHMARK(SimpleFFSTest, iters) { - runSimpleFFSTest(iters); -} -BENCHMARK(RealFFSTest, iters) { - runRealFFSTest(iters); -} - -/* --bm_min_iters=10 --bm_max_iters=100 - -Benchmark Iters Total t t/iter iter/sec ------------------------------------------------------------------------------- -runSimpleFFSTest 10 4.82 s 482 ms 2.075 -runRealFFSTest 19 2.011 s 105.9 ms 9.447 - -*/ - -int main(int argc, char** argv) { - testing::InitGoogleTest(&argc, argv); - gflags::ParseCommandLineFlags(&argc, &argv, true); - auto ret = RUN_ALL_TESTS(); - if (!ret && FLAGS_benchmark) { - folly::runBenchmarks(); - } - return ret; -} diff --git a/folly/test/IPAddressTest.cpp b/folly/test/IPAddressTest.cpp index 23ab3c01..c42ec180 100644 --- a/folly/test/IPAddressTest.cpp +++ b/folly/test/IPAddressTest.cpp @@ -18,11 +18,11 @@ #include -#include #include #include #include #include +#include #include #include #include diff --git a/folly/test/Makefile.am b/folly/test/Makefile.am index 32055e92..41cfcb4f 100644 --- a/folly/test/Makefile.am +++ b/folly/test/Makefile.am @@ -170,7 +170,7 @@ bits_test_SOURCES = ../lang/test/BitsTest.cpp bits_test_LDADD = libfollytestmain.la $(top_builddir)/libfollybenchmark.la TESTS += bits_test -bit_iterator_test_SOURCES = BitIteratorTest.cpp +bit_iterator_test_SOURCES = ../container/test/BitIteratorTest.cpp bit_iterator_test_LDADD = libfollytestmain.la $(top_builddir)/libfollybenchmark.la TESTS += bit_iterator_test