folly::compression::BitVectorReader< Encoder, Instructions, kUnchecked > Class Template Reference

#include <BitVectorCoding.h>

Inheritance diagram for folly::compression::BitVectorReader< Encoder, Instructions, kUnchecked >:

Public Types
typedef Encoder	EncoderType
typedef Encoder::ValueType	ValueType
typedef Encoder::ValueType	SizeType
typedef Encoder::SkipValueType	SkipValueType

Public Member Functions
	BitVectorReader (const typename Encoder::CompressedList &list)
void	reset ()
bool	next ()
bool	skip (SizeType n)
bool	skipTo (ValueType v)
SizeType	size () const
bool	valid () const
SizeType	position () const
ValueType	value () const
bool	jump (SizeType n)
bool	jumpTo (ValueType v)
bool	setDone ()

Private Member Functions
bool	setValue (size_t inner)
void	reposition (size_t dest)
Private Member Functions inherited from folly::compression::detail::ForwardPointers< Encoder::forwardQuantum >
	ForwardPointers (const unsigned char *ptr)
Private Member Functions inherited from folly::compression::detail::SkipPointers< Encoder::skipQuantum >
	SkipPointers (const unsigned char *ptr)

Private Attributes
const uint8_t *const	bits_
uint64_t	block_
SizeType	outer_
SizeType	position_
ValueType	value_
const SizeType	size_
const ValueType	upperBound_
Private Attributes inherited from folly::compression::detail::ForwardPointers< Encoder::forwardQuantum >
const unsigned char *const	forwardPointers_
Private Attributes inherited from folly::compression::detail::SkipPointers< Encoder::skipQuantum >
const unsigned char *const	skipPointers_

Static Private Attributes
static constexpr ValueType	kInvalidValue
static constexpr size_t	kLinearScanThreshold = 4

Detailed Description

template<class Encoder, class Instructions = instructions::Default, bool kUnchecked = false>
class folly::compression::BitVectorReader< Encoder, Instructions, kUnchecked >

Definition at line 247 of file BitVectorCoding.h.

Member Typedef Documentation

template<class Encoder , class Instructions = instructions::Default, bool kUnchecked = false>

typedef Encoder folly::compression::BitVectorReader< Encoder, Instructions, kUnchecked >::EncoderType

Definition at line 250 of file BitVectorCoding.h.

template<class Encoder , class Instructions = instructions::Default, bool kUnchecked = false>

typedef Encoder::ValueType folly::compression::BitVectorReader< Encoder, Instructions, kUnchecked >::SizeType

Definition at line 253 of file BitVectorCoding.h.

template<class Encoder , class Instructions = instructions::Default, bool kUnchecked = false>

typedef Encoder::SkipValueType folly::compression::BitVectorReader< Encoder, Instructions, kUnchecked >::SkipValueType

Definition at line 254 of file BitVectorCoding.h.

template<class Encoder , class Instructions = instructions::Default, bool kUnchecked = false>

typedef Encoder::ValueType folly::compression::BitVectorReader< Encoder, Instructions, kUnchecked >::ValueType

Definition at line 251 of file BitVectorCoding.h.

Constructor & Destructor Documentation

template<class Encoder , class Instructions = instructions::Default, bool kUnchecked = false>

folly::compression::BitVectorReader< Encoder, Instructions, kUnchecked >::BitVectorReader ( const typename Encoder::CompressedList &  list )

inlineexplicit

Definition at line 256 of file BitVectorCoding.h.

      : detail::ForwardPointers<Encoder::forwardQuantum>(list.forwardPointers),
        detail::SkipPointers<Encoder::skipQuantum>(list.skipPointers),
        bits_(list.bits),
        size_(list.size),
        upperBound_(
            (kUnchecked || UNLIKELY(list.size == 0)) ? 0 : list.upperBound) {
    reset();
  }

Member Function Documentation

template<class Encoder , class Instructions = instructions::Default, bool kUnchecked = false>

bool folly::compression::BitVectorReader< Encoder, Instructions, kUnchecked >::jump ( SizeType  n )

inline

Definition at line 404 of file BitVectorCoding.h.

References folly::gen::skip().

                        {
    reset();
    return skip(n + 1);
  }

template<class Encoder , class Instructions = instructions::Default, bool kUnchecked = false>

bool folly::compression::BitVectorReader< Encoder, Instructions, kUnchecked >::jumpTo ( ValueType  v )

inline

Definition at line 409 of file BitVectorCoding.h.

                           {
    reset();
    return skipTo(v);
  }

template<class Encoder , class Instructions = instructions::Default, bool kUnchecked = false>

bool folly::compression::BitVectorReader< Encoder, Instructions, kUnchecked >::next ( )

inline

Definition at line 273 of file BitVectorCoding.h.

References uint64_t, and UNLIKELY.

              {
    if (!kUnchecked && UNLIKELY(position() + 1 >= size_)) {
      return setDone();
    }

    while (block_ == 0) {
      outer_ += sizeof(uint64_t);
      block_ = folly::loadUnaligned<uint64_t>(bits_ + outer_);
    }

    ++position_;
    auto inner = Instructions::ctz(block_);
    block_ = Instructions::blsr(block_);

    return setValue(inner);
  }

template<class Encoder , class Instructions = instructions::Default, bool kUnchecked = false>

SizeType folly::compression::BitVectorReader< Encoder, Instructions, kUnchecked >::position ( ) const

inline

Definition at line 396 of file BitVectorCoding.h.

                            {
    return position_;
  }

template<class Encoder , class Instructions = instructions::Default, bool kUnchecked = false>

void folly::compression::BitVectorReader< Encoder, Instructions, kUnchecked >::reposition ( size_t  dest )

inlineprivate

Definition at line 430 of file BitVectorCoding.h.

References uint64_t.

                               {
    outer_ = dest / 64 * 8;
    // We maintain the invariant that outer_ is divisible by 8.
    block_ = folly::loadUnaligned<uint64_t>(bits_ + outer_);
    block_ &= ~((uint64_t(1) << (dest % 64)) - 1);
  }

template<class Encoder , class Instructions = instructions::Default, bool kUnchecked = false>

void folly::compression::BitVectorReader< Encoder, Instructions, kUnchecked >::reset ( )

inline

Definition at line 266 of file BitVectorCoding.h.

               {
    block_ = (bits_ != nullptr) ? folly::loadUnaligned<uint64_t>(bits_) : 0;
    outer_ = 0;
    position_ = -1;
    value_ = kInvalidValue;
  }

template<class Encoder , class Instructions = instructions::Default, bool kUnchecked = false>

bool folly::compression::BitVectorReader< Encoder, Instructions, kUnchecked >::setDone ( )

inline

Definition at line 414 of file BitVectorCoding.h.

                 {
    value_ = kInvalidValue;
    position_ = size_;
    return false;
  }

template<class Encoder , class Instructions = instructions::Default, bool kUnchecked = false>

bool folly::compression::BitVectorReader< Encoder, Instructions, kUnchecked >::setValue ( size_t  inner )

inlineprivate

Definition at line 425 of file BitVectorCoding.h.

                              {
    value_ = static_cast<ValueType>(8 * outer_ + inner);
    return true;
  }

template<class Encoder , class Instructions = instructions::Default, bool kUnchecked = false>

SizeType folly::compression::BitVectorReader< Encoder, Instructions, kUnchecked >::size ( ) const

inline

Definition at line 388 of file BitVectorCoding.h.

                        {
    return size_;
  }

template<class Encoder , class Instructions = instructions::Default, bool kUnchecked = false>

bool folly::compression::BitVectorReader< Encoder, Instructions, kUnchecked >::skip ( SizeType  n )

inline

Definition at line 290 of file BitVectorCoding.h.

References upload::dest, i, LIKELY, cpp.ast::next(), folly::popcount(), shell_builder::steps, and uint64_t.

                        {
    CHECK_GT(n, 0);

    if (!kUnchecked && position() + n >= size_) {
      return setDone();
    }
    // Small skip optimization.
    if (LIKELY(n < kLinearScanThreshold)) {
      for (size_t i = 0; i < n; ++i) {
        next();
      }
      return true;
    }

    position_ += n;

    // Use forward pointer.
    if (Encoder::forwardQuantum > 0 && n > Encoder::forwardQuantum) {
      const size_t steps = position_ / Encoder::forwardQuantum;
      const size_t dest = folly::loadUnaligned<SkipValueType>(
          this->forwardPointers_ + (steps - 1) * sizeof(SkipValueType));

      reposition(dest);
      n = position_ + 1 - steps * Encoder::forwardQuantum;
    }

    size_t cnt;
    // Find necessary block.
    while ((cnt = Instructions::popcount(block_)) < n) {
      n -= cnt;
      outer_ += sizeof(uint64_t);
      block_ = folly::loadUnaligned<uint64_t>(bits_ + outer_);
    }

    // Skip to the n-th one in the block.
    DCHECK_GT(n, 0);
    auto inner = select64<Instructions>(block_, n - 1);
    block_ &= (uint64_t(-1) << inner) << 1;

    return setValue(inner);
  }

template<class Encoder , class Instructions = instructions::Default, bool kUnchecked = false>

bool folly::compression::BitVectorReader< Encoder, Instructions, kUnchecked >::skipTo ( ValueType  v )

inline

Definition at line 332 of file BitVectorCoding.h.

References cpp.ast::next(), folly::popcount(), uint64_t, and folly::value().

                           {
    // Also works when value_ == kInvalidValue.
    if (v != kInvalidValue) {
      DCHECK_GE(v + 1, value_ + 1);
    }

    if (!kUnchecked && v > upperBound_) {
      return setDone();
    } else if (v == value_) {
      return true;
    }

    // Small skip optimization.
    if (v - value_ < kLinearScanThreshold) {
      do {
        next();
      } while (value() < v);

      return true;
    }

    if (Encoder::skipQuantum > 0 && v - value_ > Encoder::skipQuantum) {
      size_t q = v / Encoder::skipQuantum;
      auto skipPointer = folly::loadUnaligned<SkipValueType>(
          this->skipPointers_ + (q - 1) * sizeof(SkipValueType));
      position_ = static_cast<SizeType>(skipPointer) - 1;

      reposition(q * Encoder::skipQuantum);
    }

    // Find the value.
    size_t outer = v / 64 * 8;

    while (outer_ < outer) {
      position_ += Instructions::popcount(block_);
      outer_ += sizeof(uint64_t);
      block_ = folly::loadUnaligned<uint64_t>(bits_ + outer_);
    }

    DCHECK_EQ(outer_, outer);
    uint64_t mask = ~((uint64_t(1) << (v % 64)) - 1);
    position_ += Instructions::popcount(block_ & ~mask) + 1;
    block_ &= mask;

    while (block_ == 0) {
      outer_ += sizeof(uint64_t);
      block_ = folly::loadUnaligned<uint64_t>(bits_ + outer_);
    }

    auto inner = Instructions::ctz(block_);
    block_ = Instructions::blsr(block_);

    setValue(inner);
    return true;
  }

template<class Encoder , class Instructions = instructions::Default, bool kUnchecked = false>

bool folly::compression::BitVectorReader< Encoder, Instructions, kUnchecked >::valid ( ) const

inline

Definition at line 392 of file BitVectorCoding.h.

References folly::compression::BitVectorCompressedListBase< Pointer >::size.

                     {
    return position() < size(); // Also checks that position() != -1.
  }

template<class Encoder , class Instructions = instructions::Default, bool kUnchecked = false>

ValueType folly::compression::BitVectorReader< Encoder, Instructions, kUnchecked >::value ( ) const

inline

Definition at line 399 of file BitVectorCoding.h.

                          {
    DCHECK(valid());
    return value_;
  }

Member Data Documentation

template<class Encoder , class Instructions = instructions::Default, bool kUnchecked = false>

const uint8_t* const folly::compression::BitVectorReader< Encoder, Instructions, kUnchecked >::bits_

private

Definition at line 439 of file BitVectorCoding.h.

template<class Encoder , class Instructions = instructions::Default, bool kUnchecked = false>

uint64_t folly::compression::BitVectorReader< Encoder, Instructions, kUnchecked >::block_

private

Definition at line 440 of file BitVectorCoding.h.

template<class Encoder , class Instructions = instructions::Default, bool kUnchecked = false>

constexpr ValueType folly::compression::BitVectorReader< Encoder, Instructions, kUnchecked >::kInvalidValue

staticprivate

Initial value:

=
      std::numeric_limits<ValueType>::max()

Definition at line 421 of file BitVectorCoding.h.

template<class Encoder , class Instructions = instructions::Default, bool kUnchecked = false>

constexpr size_t folly::compression::BitVectorReader< Encoder, Instructions, kUnchecked >::kLinearScanThreshold = 4

staticprivate

Definition at line 437 of file BitVectorCoding.h.

template<class Encoder , class Instructions = instructions::Default, bool kUnchecked = false>

SizeType folly::compression::BitVectorReader< Encoder, Instructions, kUnchecked >::outer_

private

Definition at line 441 of file BitVectorCoding.h.

template<class Encoder , class Instructions = instructions::Default, bool kUnchecked = false>

SizeType folly::compression::BitVectorReader< Encoder, Instructions, kUnchecked >::position_

private

Definition at line 442 of file BitVectorCoding.h.

template<class Encoder , class Instructions = instructions::Default, bool kUnchecked = false>

const SizeType folly::compression::BitVectorReader< Encoder, Instructions, kUnchecked >::size_

private

Definition at line 445 of file BitVectorCoding.h.

template<class Encoder , class Instructions = instructions::Default, bool kUnchecked = false>

const ValueType folly::compression::BitVectorReader< Encoder, Instructions, kUnchecked >::upperBound_

private

Definition at line 446 of file BitVectorCoding.h.

template<class Encoder , class Instructions = instructions::Default, bool kUnchecked = false>

ValueType folly::compression::BitVectorReader< Encoder, Instructions, kUnchecked >::value_

private

Definition at line 443 of file BitVectorCoding.h.

---

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

• proxygen/folly/folly/experimental/BitVectorCoding.h