folly::BitIterator< BaseIter > Class Template Reference

#include <BitIterator.h>

Inheritance diagram for folly::BitIterator< BaseIter >:

Public Member Functions
	BitIterator (const BaseIter &iter, size_t bitOff=0)
size_t	bitOffset () const
void	advanceToNextBlock ()
BitIterator &	operator= (const BaseIter &other)

Static Public Member Functions
static unsigned int	bitsPerBlock ()

Private Types
typedef bititerator_detail::BitReference< typename std::iterator_traits< BaseIter >::reference, typename std::iterator_traits< BaseIter >::value_type >	BitRef

Private Member Functions
void	advanceInBlock (size_t n)
BitRef	dereference () const
void	advance (ssize_t n)
void	increment ()
void	decrement ()
bool	equal (const BitIterator &other) const
ssize_t	distance_to (const BitIterator &other) const

Private Attributes
size_t	bitOffset_

Friends
class	boost::iterator_core_access
BitIterator	findFirstSet (BitIterator, BitIterator)

Detailed Description

template<class BaseIter>
class folly::BitIterator< BaseIter >

Fast bit iteration facility.

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.

Definition at line 52 of file BitIterator.h.

Member Typedef Documentation

template<class BaseIter>

typedef bititerator_detail::BitReference< typename std::iterator_traits<BaseIter>::reference, typename std::iterator_traits<BaseIter>::value_type> folly::BitIterator< BaseIter >::BitRef

private

Definition at line 106 of file BitIterator.h.

Constructor & Destructor Documentation

template<class BaseIter>

folly::BitIterator< BaseIter >::BitIterator ( const BaseIter &  iter, size_t  bitOff = 0  )

inlineexplicit

Construct a BitIterator that points at a given bit offset (default 0) in iter.

Definition at line 78 of file BitIterator.h.

References folly::BitIterator< BaseIter >::bitOffset_, and folly::BitIterator< BaseIter >::bitsPerBlock().

Referenced by folly::BitIterator< BaseIter >::operator=().

      : bititerator_detail::BitIteratorBase<BaseIter>::type(iter),
        bitOffset_(bitOff) {
    assert(bitOffset_ < bitsPerBlock());
  }

Member Function Documentation

template<class BaseIter>

void folly::BitIterator< BaseIter >::advance ( ssize_t  n )

inlineprivate

Definition at line 117 of file BitIterator.h.

References folly::BitIterator< BaseIter >::bitOffset_, and folly::BitIterator< BaseIter >::bitsPerBlock().

                          {
    size_t bpb = bitsPerBlock();
    ssize_t blocks = n / ssize_t(bpb);
    bitOffset_ += n % bpb;
    if (bitOffset_ >= bpb) {
      bitOffset_ -= bpb;
      ++blocks;
    }
    this->base_reference() += blocks;
  }

template<class BaseIter>

void folly::BitIterator< BaseIter >::advanceInBlock ( size_t  n )

inlineprivate

Definition at line 108 of file BitIterator.h.

References folly::BitIterator< BaseIter >::bitOffset_, and folly::BitIterator< BaseIter >::bitsPerBlock().

Referenced by folly::findFirstSet().

                                {
    bitOffset_ += n;
    assert(bitOffset_ < bitsPerBlock());
  }

template<class BaseIter>

void folly::BitIterator< BaseIter >::advanceToNextBlock ( )

inline

Definition at line 88 of file BitIterator.h.

References folly::BitIterator< BaseIter >::bitOffset_.

Referenced by folly::findFirstSet(), and folly::BitIterator< BaseIter >::increment().

                            {
    bitOffset_ = 0;
    ++this->base_reference();
  }

template<class BaseIter>

size_t folly::BitIterator< BaseIter >::bitOffset ( ) const

inline

Definition at line 84 of file BitIterator.h.

References folly::BitIterator< BaseIter >::bitOffset_.

Referenced by folly::findFirstSet().

                           {
    return bitOffset_;
  }

template<class BaseIter>

static unsigned int folly::BitIterator< BaseIter >::bitsPerBlock ( )

inlinestatic

Return the number of bits in an element of the underlying iterator.

Definition at line 69 of file BitIterator.h.

References type.

Referenced by folly::BitIterator< BaseIter >::advance(), folly::BitIterator< BaseIter >::advanceInBlock(), folly::BitIterator< BaseIter >::BitIterator(), folly::BitIterator< BaseIter >::decrement(), folly::BitIterator< BaseIter >::distance_to(), and folly::BitIterator< BaseIter >::increment().

                                     {
    return std::numeric_limits<typename std::make_unsigned<
        typename std::iterator_traits<BaseIter>::value_type>::type>::digits;
  }

template<class BaseIter>

void folly::BitIterator< BaseIter >::decrement ( )

inlineprivate

Definition at line 134 of file BitIterator.h.

References folly::BitIterator< BaseIter >::bitOffset_, and folly::BitIterator< BaseIter >::bitsPerBlock().

                   {
    if (bitOffset_-- == 0) {
      bitOffset_ = bitsPerBlock() - 1;
      --this->base_reference();
    }
  }

template<class BaseIter>

BitRef folly::BitIterator< BaseIter >::dereference ( ) const

inlineprivate

Definition at line 113 of file BitIterator.h.

References folly::BitIterator< BaseIter >::bitOffset_.

                             {
    return BitRef(*this->base_reference(), bitOffset_);
  }

template<class BaseIter>

ssize_t folly::BitIterator< BaseIter >::distance_to ( const BitIterator< BaseIter > &  other ) const

inlineprivate

Definition at line 147 of file BitIterator.h.

References folly::BitIterator< BaseIter >::bitOffset_, and folly::BitIterator< BaseIter >::bitsPerBlock().

                                                      {
    return ssize_t(
        (other.base_reference() - this->base_reference()) * bitsPerBlock() +
        other.bitOffset_ - bitOffset_);
  }

template<class BaseIter>

bool folly::BitIterator< BaseIter >::equal ( const BitIterator< BaseIter > &  other ) const

inlineprivate

Definition at line 141 of file BitIterator.h.

References folly::BitIterator< BaseIter >::bitOffset_.

                                             {
    return (
        bitOffset_ == other.bitOffset_ &&
        this->base_reference() == other.base_reference());
  }

template<class BaseIter>

void folly::BitIterator< BaseIter >::increment ( )

inlineprivate

Definition at line 128 of file BitIterator.h.

References folly::BitIterator< BaseIter >::advanceToNextBlock(), folly::BitIterator< BaseIter >::bitOffset_, and folly::BitIterator< BaseIter >::bitsPerBlock().

                   {
    if (++bitOffset_ == bitsPerBlock()) {
      advanceToNextBlock();
    }
  }

template<class BaseIter>

BitIterator& folly::BitIterator< BaseIter >::operator= ( const BaseIter &  other )

inline

Definition at line 93 of file BitIterator.h.

References folly::BitIterator< BaseIter >::BitIterator().

                                                {
    this->~BitIterator();
    new (this) BitIterator(other);
    return *this;
  }

Friends And Related Function Documentation

template<class BaseIter>

friend class boost::iterator_core_access

friend

Definition at line 100 of file BitIterator.h.

template<class BaseIter>

BitIterator findFirstSet ( BitIterator< BaseIter >  begin, BitIterator< BaseIter >  end  )

friend

Find first bit set in a range of bit iterators. 4.5x faster than the obvious std::find(begin, end, true);

Definition at line 170 of file BitIterator.h.

Referenced by folly::findFirstSet().

                               {
  // shortcut to avoid ugly static_cast<>
  static const typename std::iterator_traits<BaseIter>::value_type one = 1;

  while (begin.base() != end.base()) {
    typename std::iterator_traits<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 std::iterator_traits<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;
}

Member Data Documentation

template<class BaseIter>

size_t folly::BitIterator< BaseIter >::bitOffset_

private

Definition at line 153 of file BitIterator.h.

Referenced by folly::BitIterator< BaseIter >::advance(), folly::BitIterator< BaseIter >::advanceInBlock(), folly::BitIterator< BaseIter >::advanceToNextBlock(), folly::BitIterator< BaseIter >::BitIterator(), folly::BitIterator< BaseIter >::bitOffset(), folly::BitIterator< BaseIter >::decrement(), folly::BitIterator< BaseIter >::dereference(), folly::BitIterator< BaseIter >::distance_to(), folly::BitIterator< BaseIter >::equal(), and folly::BitIterator< BaseIter >::increment().

---

The documentation for this class was generated from the following file:

• proxygen/folly/folly/container/BitIterator.h