folly/BitIterator.h

   1 /*
   2  * Copyright 2017 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 /**
  18  * BitIterator
  19  *    Wrapper around an iterator over an integral type that iterates
  20  *    over its underlying bits in MSb to LSb order
  21  *
  22  * findFirstSet(BitIterator begin, BitIterator end)
  23  *    return a BitIterator pointing to the first 1 bit in [begin, end), or
  24  *    end if all bits in [begin, end) are 0
  25  *
  26  * @author Tudor Bosman (tudorb@fb.com)
  27  */
  28
  29 #pragma once
  30
  31 #include <cassert>
  32 #include <cinttypes>
  33 #include <cstdint>
  34 #include <cstring>
  35 #include <iterator>
  36 #include <limits>
  37 #include <type_traits>
  38
  39 #include <boost/iterator/iterator_adaptor.hpp>
  40
  41 #include <folly/Bits.h>
  42 #include <folly/Portability.h>
  43 #include <folly/detail/BitIteratorDetail.h>
  44
  45 namespace folly {
  46
  47 /**
  48  * Fast bit iteration facility.
  49  */
  50
  51 template <class BaseIter>
  52 class BitIterator;
  53 template <class BaseIter>
  54 BitIterator<BaseIter> findFirstSet(
  55     BitIterator<BaseIter>,
  56     BitIterator<BaseIter>);
  57 /**
  58  * Wrapper around an iterator over an integer type that iterates
  59  * over its underlying bits in LSb to MSb order.
  60  *
  61  * BitIterator models the same iterator concepts as the base iterator.
  62  */
  63 template <class BaseIter>
  64 class BitIterator : public bititerator_detail::BitIteratorBase<BaseIter>::type {
  65  public:
  66   /**
  67    * Return the number of bits in an element of the underlying iterator.
  68    */
  69   static unsigned int bitsPerBlock() {
  70     return std::numeric_limits<typename std::make_unsigned<
  71         typename std::iterator_traits<BaseIter>::value_type>::type>::digits;
  72   }
  73
  74   /**
  75    * Construct a BitIterator that points at a given bit offset (default 0)
  76    * in iter.
  77    */
  78   explicit BitIterator(const BaseIter& iter, size_t bitOff = 0)
  79       : bititerator_detail::BitIteratorBase<BaseIter>::type(iter),
  80         bitOffset_(bitOff) {
  81     assert(bitOffset_ < bitsPerBlock());
  82   }
  83
  84   size_t bitOffset() const {
  85     return bitOffset_;
  86   }
  87
  88   void advanceToNextBlock() {
  89     bitOffset_ = 0;
  90     ++this->base_reference();
  91   }
  92
  93   BitIterator& operator=(const BaseIter& other) {
  94     this->~BitIterator();
  95     new (this) BitIterator(other);
  96     return *this;
  97   }
  98
  99  private:
 100   friend class boost::iterator_core_access;
 101   friend BitIterator findFirstSet<>(BitIterator, BitIterator);
 102
 103   typedef bititerator_detail::BitReference<
 104       typename std::iterator_traits<BaseIter>::reference,
 105       typename std::iterator_traits<BaseIter>::value_type>
 106       BitRef;
 107
 108   void advanceInBlock(size_t n) {
 109     bitOffset_ += n;
 110     assert(bitOffset_ < bitsPerBlock());
 111   }
 112
 113   BitRef dereference() const {
 114     return BitRef(*this->base_reference(), bitOffset_);
 115   }
 116
 117   void advance(ssize_t n) {
 118     size_t bpb = bitsPerBlock();
 119     ssize_t blocks = n / ssize_t(bpb);
 120     bitOffset_ += n % bpb;
 121     if (bitOffset_ >= bpb) {
 122       bitOffset_ -= bpb;
 123       ++blocks;
 124     }
 125     this->base_reference() += blocks;
 126   }
 127
 128   void increment() {
 129     if (++bitOffset_ == bitsPerBlock()) {
 130       advanceToNextBlock();
 131     }
 132   }
 133
 134   void decrement() {
 135     if (bitOffset_-- == 0) {
 136       bitOffset_ = bitsPerBlock() - 1;
 137       --this->base_reference();
 138     }
 139   }
 140
 141   bool equal(const BitIterator& other) const {
 142     return (
 143         bitOffset_ == other.bitOffset_ &&
 144         this->base_reference() == other.base_reference());
 145   }
 146
 147   ssize_t distance_to(const BitIterator& other) const {
 148     return ssize_t(
 149         (other.base_reference() - this->base_reference()) * bitsPerBlock() +
 150         other.bitOffset_ - bitOffset_);
 151   }
 152
 153   size_t bitOffset_;
 154 };
 155
 156 /**
 157  * Helper function, so you can write
 158  * auto bi = makeBitIterator(container.begin());
 159  */
 160 template <class BaseIter>
 161 BitIterator<BaseIter> makeBitIterator(const BaseIter& iter) {
 162   return BitIterator<BaseIter>(iter);
 163 }
 164
 165 /**
 166  * Find first bit set in a range of bit iterators.
 167  * 4.5x faster than the obvious std::find(begin, end, true);
 168  */
 169 template <class BaseIter>
 170 BitIterator<BaseIter> findFirstSet(
 171     BitIterator<BaseIter> begin,
 172     BitIterator<BaseIter> end) {
 173   // shortcut to avoid ugly static_cast<>
 174   static const typename BaseIter::value_type one = 1;
 175
 176   while (begin.base() != end.base()) {
 177     typename BaseIter::value_type v = *begin.base();
 178     // mask out the bits that don't matter (< begin.bitOffset)
 179     v &= ~((one << begin.bitOffset()) - 1);
 180     size_t firstSet = findFirstSet(v);
 181     if (firstSet) {
 182       --firstSet; // now it's 0-based
 183       assert(firstSet >= begin.bitOffset());
 184       begin.advanceInBlock(firstSet - begin.bitOffset());
 185       return begin;
 186     }
 187     begin.advanceToNextBlock();
 188   }
 189
 190   // now begin points to the same block as end
 191   if (end.bitOffset() != 0) { // assume end is dereferenceable
 192     typename BaseIter::value_type v = *begin.base();
 193     // mask out the bits that don't matter (< begin.bitOffset)
 194     v &= ~((one << begin.bitOffset()) - 1);
 195     // mask out the bits that don't matter (>= end.bitOffset)
 196     v &= (one << end.bitOffset()) - 1;
 197     size_t firstSet = findFirstSet(v);
 198     if (firstSet) {
 199       --firstSet; // now it's 0-based
 200       assert(firstSet >= begin.bitOffset());
 201       begin.advanceInBlock(firstSet - begin.bitOffset());
 202       return begin;
 203     }
 204   }
 205
 206   return end;
 207 }
 208
 209 } // namespace folly