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
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
+++ /dev/null
-/*
- * 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 <cassert>
-#include <cinttypes>
-#include <cstdint>
-#include <cstring>
-#include <iterator>
-#include <limits>
-#include <type_traits>
-
-#include <boost/iterator/iterator_adaptor.hpp>
-
-#include <folly/Portability.h>
-#include <folly/detail/BitIteratorDetail.h>
-#include <folly/lang/Bits.h>
-
-namespace folly {
-
-/**
- * Fast bit iteration facility.
- */
-
-template <class BaseIter>
-class BitIterator;
-template <class BaseIter>
-BitIterator<BaseIter> findFirstSet(
- BitIterator<BaseIter>,
- BitIterator<BaseIter>);
-/**
- * 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 BaseIter>
-class BitIterator : public bititerator_detail::BitIteratorBase<BaseIter>::type {
- public:
- /**
- * Return the number of bits in an element of the underlying iterator.
- */
- static unsigned int bitsPerBlock() {
- return std::numeric_limits<typename std::make_unsigned<
- typename std::iterator_traits<BaseIter>::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<BaseIter>::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<BaseIter>::reference,
- typename std::iterator_traits<BaseIter>::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 <class BaseIter>
-BitIterator<BaseIter> makeBitIterator(const BaseIter& iter) {
- return BitIterator<BaseIter>(iter);
-}
-
-/**
- * Find first bit set in a range of bit iterators.
- * 4.5x faster than the obvious std::find(begin, end, true);
- */
-template <class BaseIter>
-BitIterator<BaseIter> findFirstSet(
- BitIterator<BaseIter> begin,
- BitIterator<BaseIter> 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
concurrency/UnboundedQueue.h \
container/Access.h \
container/Array.h \
+ container/detail/BitIteratorDetail.h \
container/Iterator.h \
container/Enumerate.h \
container/EvictingCacheMap.h \
detail/AtFork.h \
detail/AtomicHashUtils.h \
detail/AtomicUnorderedMapUtils.h \
- detail/BitIteratorDetail.h \
detail/DiscriminatedPtrDetail.h \
detail/FileUtilDetail.h \
detail/FingerprintPolynomial.h \
--- /dev/null
+/*
+ * 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 <cassert>
+#include <cinttypes>
+#include <cstdint>
+#include <cstring>
+#include <iterator>
+#include <limits>
+#include <type_traits>
+
+#include <boost/iterator/iterator_adaptor.hpp>
+
+#include <folly/Portability.h>
+#include <folly/container/detail/BitIteratorDetail.h>
+#include <folly/lang/Bits.h>
+
+namespace folly {
+
+/**
+ * Fast bit iteration facility.
+ */
+
+template <class BaseIter>
+class BitIterator;
+template <class BaseIter>
+BitIterator<BaseIter> findFirstSet(
+ BitIterator<BaseIter>,
+ BitIterator<BaseIter>);
+/**
+ * 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 BaseIter>
+class BitIterator : public bititerator_detail::BitIteratorBase<BaseIter>::type {
+ public:
+ /**
+ * Return the number of bits in an element of the underlying iterator.
+ */
+ static unsigned int bitsPerBlock() {
+ return std::numeric_limits<typename std::make_unsigned<
+ typename std::iterator_traits<BaseIter>::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<BaseIter>::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<BaseIter>::reference,
+ typename std::iterator_traits<BaseIter>::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 <class BaseIter>
+BitIterator<BaseIter> makeBitIterator(const BaseIter& iter) {
+ return BitIterator<BaseIter>(iter);
+}
+
+/**
+ * Find first bit set in a range of bit iterators.
+ * 4.5x faster than the obvious std::find(begin, end, true);
+ */
+template <class BaseIter>
+BitIterator<BaseIter> findFirstSet(
+ BitIterator<BaseIter> begin,
+ BitIterator<BaseIter> 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
--- /dev/null
+/*
+ * 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 <iterator>
+#include <type_traits>
+
+#include <boost/iterator/iterator_adaptor.hpp>
+
+namespace folly {
+
+template <class BaseIter> 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 Ref, class Value>
+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 <class BaseIter>
+struct BitIteratorBase {
+ static_assert(std::is_integral<typename BaseIter::value_type>::value,
+ "BitIterator may only be used with integral types");
+ typedef boost::iterator_adaptor<
+ BitIterator<BaseIter>, // Derived
+ BaseIter, // Base
+ bool, // Value
+ boost::use_default, // CategoryOrTraversal
+ bititerator_detail::BitReference<
+ typename std::iterator_traits<BaseIter>::reference,
+ typename std::iterator_traits<BaseIter>::value_type
+ >, // Reference
+ ssize_t> type;
+};
+
+} // namespace bititerator_detail
+} // namespace folly
--- /dev/null
+/*
+ * 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 <folly/container/BitIterator.h>
+
+#include <algorithm>
+#include <limits>
+#include <type_traits>
+#include <vector>
+
+#include <folly/Benchmark.h>
+#include <folly/portability/GFlags.h>
+#include <folly/portability/GTest.h>
+
+using namespace folly;
+using namespace folly::bititerator_detail;
+
+namespace {
+
+template <class INT, class IT>
+void checkIt(INT exp, IT& it) {
+ typedef typename std::make_unsigned<INT>::type utype;
+ size_t bits = std::numeric_limits<utype>::digits;
+ utype uexp = exp;
+ for (size_t i = 0; i < bits; ++i) {
+ bool e = uexp & 1;
+ EXPECT_EQ(e, *it++);
+ uexp >>= 1;
+ }
+}
+
+template <class INT, class IT>
+void checkRange(INT exp, IT begin, IT end) {
+ typedef typename std::make_unsigned<INT>::type utype;
+ utype uexp = exp;
+ size_t i = 0;
+ auto bitEnd = makeBitIterator(end);
+ for (BitIterator<IT> it = makeBitIterator(begin); it != bitEnd; ++it, ++i) {
+ bool e = uexp & 1;
+ EXPECT_EQ(e, *it);
+ uexp >>= 1;
+ }
+}
+
+} // namespace
+
+TEST(BitIterator, Simple) {
+ std::vector<int> 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<int> v;
+ v.push_back(0x10);
+ v.push_back(0x42);
+ auto bi(makeBitIterator(v.cbegin()));
+ checkIt(0x10, bi);
+ checkIt(0x42, bi);
+}
+
+namespace {
+
+template <class BaseIter>
+BitIterator<BaseIter> simpleFFS(BitIterator<BaseIter> begin,
+ BitIterator<BaseIter> end) {
+ return std::find(begin, end, true);
+}
+
+template <class FFS>
+void runFFSTest(FFS fn) {
+ static const size_t bpb = 8 * sizeof(uint64_t);
+ std::vector<uint64_t> 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<std::vector<uint64_t>::const_iterator>;
+ while (iters--) {
+ runFFSTest(fn);
+ }
+}
+
+void runRealFFSTest(int iters) {
+ auto fn = findFirstSet<std::vector<uint64_t>::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;
+}
+++ /dev/null
-/*
- * 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 <iterator>
-#include <type_traits>
-
-#include <boost/iterator/iterator_adaptor.hpp>
-
-namespace folly {
-
-template <class BaseIter> 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 Ref, class Value>
-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 <class BaseIter>
-struct BitIteratorBase {
- static_assert(std::is_integral<typename BaseIter::value_type>::value,
- "BitIterator may only be used with integral types");
- typedef boost::iterator_adaptor<
- BitIterator<BaseIter>, // Derived
- BaseIter, // Base
- bool, // Value
- boost::use_default, // CategoryOrTraversal
- bititerator_detail::BitReference<
- typename std::iterator_traits<BaseIter>::reference,
- typename std::iterator_traits<BaseIter>::value_type
- >, // Reference
- ssize_t> type;
-};
-
-} // namespace bititerator_detail
-} // namespace folly
#include <folly/io/async/HHWheelTimer.h>
#include <folly/io/async/Request.h>
-#include <folly/BitIterator.h>
#include <folly/Memory.h>
#include <folly/Optional.h>
#include <folly/ScopeGuard.h>
+#include <folly/container/BitIterator.h>
#include <folly/lang/Bits.h>
+++ /dev/null
-/*
- * 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 <folly/BitIterator.h>
-
-#include <algorithm>
-#include <limits>
-#include <type_traits>
-#include <vector>
-
-#include <folly/Benchmark.h>
-#include <folly/portability/GFlags.h>
-#include <folly/portability/GTest.h>
-
-using namespace folly;
-using namespace folly::bititerator_detail;
-
-namespace {
-
-template <class INT, class IT>
-void checkIt(INT exp, IT& it) {
- typedef typename std::make_unsigned<INT>::type utype;
- size_t bits = std::numeric_limits<utype>::digits;
- utype uexp = exp;
- for (size_t i = 0; i < bits; ++i) {
- bool e = uexp & 1;
- EXPECT_EQ(e, *it++);
- uexp >>= 1;
- }
-}
-
-template <class INT, class IT>
-void checkRange(INT exp, IT begin, IT end) {
- typedef typename std::make_unsigned<INT>::type utype;
- utype uexp = exp;
- size_t i = 0;
- auto bitEnd = makeBitIterator(end);
- for (BitIterator<IT> it = makeBitIterator(begin); it != bitEnd; ++it, ++i) {
- bool e = uexp & 1;
- EXPECT_EQ(e, *it);
- uexp >>= 1;
- }
-}
-
-} // namespace
-
-TEST(BitIterator, Simple) {
- std::vector<int> 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<int> v;
- v.push_back(0x10);
- v.push_back(0x42);
- auto bi(makeBitIterator(v.cbegin()));
- checkIt(0x10, bi);
- checkIt(0x42, bi);
-}
-
-namespace {
-
-template <class BaseIter>
-BitIterator<BaseIter> simpleFFS(BitIterator<BaseIter> begin,
- BitIterator<BaseIter> end) {
- return std::find(begin, end, true);
-}
-
-template <class FFS>
-void runFFSTest(FFS fn) {
- static const size_t bpb = 8 * sizeof(uint64_t);
- std::vector<uint64_t> 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<std::vector<uint64_t>::const_iterator>;
- while (iters--) {
- runFFSTest(fn);
- }
-}
-
-void runRealFFSTest(int iters) {
- auto fn = findFirstSet<std::vector<uint64_t>::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;
-}
#include <string>
-#include <folly/BitIterator.h>
#include <folly/Format.h>
#include <folly/IPAddress.h>
#include <folly/MacAddress.h>
#include <folly/String.h>
+#include <folly/container/BitIterator.h>
#include <folly/detail/IPAddressSource.h>
#include <folly/lang/Bits.h>
#include <folly/portability/GMock.h>
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
projects / folly.git / commitdiff