X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=folly%2FBits.h;h=889b3a0b0c2d6852cef8a0c9c623b6806a123ee8;hb=171c36527455c2709be57f2ccc41218d45689411;hp=4b71c18963600ebdd74b4eadc076d98cbf5fbb96;hpb=42a989fad8c0f52d5afa482afc5b531ed34887d2;p=folly.git

diff --git a/folly/Bits.h b/folly/Bits.h
index 4b71c189..889b3a0b 100644
--- a/folly/Bits.h
+++ b/folly/Bits.h
@@ -41,14 +41,6 @@
  *    Endian::little(x)   little <-> native
  *    Endian::swap(x)     big <-> little
  *
- * 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)
  */
 
@@ -65,16 +57,11 @@
 #include <cinttypes>
 #include <cstdint>
 #include <cstring>
-#include <iterator>
 #include <limits>
 #include <type_traits>
 
-#include <boost/iterator/iterator_adaptor.hpp>
-
-#include <folly/Assume.h>
-#include <folly/Likely.h>
 #include <folly/Portability.h>
-#include <folly/detail/BitIteratorDetail.h>
+#include <folly/lang/Assume.h>
 #include <folly/portability/Builtins.h>
 
 namespace folly {
@@ -332,170 +319,6 @@ class Endian {
 #undef FB_GEN2
 #undef FB_GEN1
 
-/**
- * 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;
-}
-
 
 template <class T, class Enable=void> struct Unaligned;
 
@@ -549,4 +372,13 @@ inline void storeUnaligned(void* p, T value) {
   }
 }
 
+template <typename T>
+T bitReverse(T n) {
+  auto m = static_cast<typename std::make_unsigned<T>::type>(n);
+  m = ((m & 0xAAAAAAAAAAAAAAAA) >> 1) | ((m & 0x5555555555555555) << 1);
+  m = ((m & 0xCCCCCCCCCCCCCCCC) >> 2) | ((m & 0x3333333333333333) << 2);
+  m = ((m & 0xF0F0F0F0F0F0F0F0) >> 4) | ((m & 0x0F0F0F0F0F0F0F0F) << 4);
+  return static_cast<T>(Endian::swap(m));
+}
+
 } // namespace folly