folly::compression::detail::UpperBitsReader< Encoder, Instructions, SizeType > Class Template Reference

#include <EliasFanoCoding.h>

Inheritance diagram for folly::compression::detail::UpperBitsReader< Encoder, Instructions, SizeType >:

Public Types
typedef Encoder::ValueType	ValueType

Public Member Functions
	UpperBitsReader (const typename Encoder::CompressedList &list)
void	reset ()
SizeType	position () const
ValueType	value () const
ValueType	previous ()
ValueType	next ()
ValueType	skip (SizeType n)
ValueType	skipToNext (ValueType v)
SizeType	prepareSkipTo (ValueType v) const
ValueType	jump (size_t n)
ValueType	jumpToNext (ValueType v)
ValueType	previousValue () const
void	setDone (SizeType endPos)

Private Types
typedef Encoder::SkipValueType	SkipValueType
using	block_t = uint64_t
using	OuterType = typename std::common_type< ValueType, SizeType >::type

Private Member Functions
ValueType	setValue (size_t inner)
void	reposition (SizeType dest)
void	getPreviousInfo (block_t &block, size_t &inner, OuterType &outer) const
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 unsigned char *const	start_
block_t	block_
SizeType	position_
OuterType	outer_
ValueType	value_
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_

Detailed Description

template<class Encoder, class Instructions, class SizeType>
class folly::compression::detail::UpperBitsReader< Encoder, Instructions, SizeType >

Definition at line 337 of file EliasFanoCoding.h.

Member Typedef Documentation

template<class Encoder, class Instructions, class SizeType>

using folly::compression::detail::UpperBitsReader< Encoder, Instructions, SizeType >::block_t = uint64_t

private

Definition at line 538 of file EliasFanoCoding.h.

template<class Encoder, class Instructions, class SizeType>

using folly::compression::detail::UpperBitsReader< Encoder, Instructions, SizeType >::OuterType = typename std::common_type<ValueType, SizeType>::type

private

Definition at line 541 of file EliasFanoCoding.h.

template<class Encoder, class Instructions, class SizeType>

typedef Encoder::SkipValueType folly::compression::detail::UpperBitsReader< Encoder, Instructions, SizeType >::SkipValueType

private

Definition at line 339 of file EliasFanoCoding.h.

template<class Encoder, class Instructions, class SizeType>

typedef Encoder::ValueType folly::compression::detail::UpperBitsReader< Encoder, Instructions, SizeType >::ValueType

Definition at line 342 of file EliasFanoCoding.h.

Constructor & Destructor Documentation

template<class Encoder, class Instructions, class SizeType>

folly::compression::detail::UpperBitsReader< Encoder, Instructions, SizeType >::UpperBitsReader ( const typename Encoder::CompressedList &  list )

inlineexplicit

Definition at line 344 of file EliasFanoCoding.h.

      : ForwardPointers<Encoder::forwardQuantum>(list.forwardPointers),
        SkipPointers<Encoder::skipQuantum>(list.skipPointers),
        start_(list.upper) {
    reset();
  }

Member Function Documentation

template<class Encoder, class Instructions, class SizeType>

void folly::compression::detail::UpperBitsReader< Encoder, Instructions, SizeType >::getPreviousInfo ( block_t &  block, size_t &  inner, OuterType &  outer  ) const

inlineprivate

Definition at line 543 of file EliasFanoCoding.h.

References max, start_, and UNLIKELY.

                                                                              {
    DCHECK_NE(position(), std::numeric_limits<SizeType>::max());
    DCHECK_GT(position(), 0);

    outer = outer_;
    block = folly::loadUnaligned<block_t>(start_ + outer);
    inner = size_t(value_) - 8 * outer_ + position_;
    block &= (block_t(1) << inner) - 1;
    while (UNLIKELY(block == 0)) {
      DCHECK_GT(outer, 0);
      outer -= std::min<OuterType>(sizeof(block_t), outer);
      block = folly::loadUnaligned<block_t>(start_ + outer);
    }
    inner = 8 * sizeof(block_t) - 1 - Instructions::clz(block);
  }

template<class Encoder, class Instructions, class SizeType>

ValueType folly::compression::detail::UpperBitsReader< Encoder, Instructions, SizeType >::jump ( size_t  n )

inline

Definition at line 495 of file EliasFanoCoding.h.

References max, and folly::gen::skip().

                           {
    if (Encoder::forwardQuantum == 0 || n <= Encoder::forwardQuantum) {
      reset();
    } else {
      // Avoid reading the head, skip() will reposition.
      position_ = std::numeric_limits<SizeType>::max();
    }
    return skip(n);
  }

template<class Encoder, class Instructions, class SizeType>

ValueType folly::compression::detail::UpperBitsReader< Encoder, Instructions, SizeType >::jumpToNext ( ValueType  v )

inline

Definition at line 505 of file EliasFanoCoding.h.

                                    {
    if (Encoder::skipQuantum == 0 || v < Encoder::skipQuantum) {
      reset();
    } else {
      value_ = 0; // Avoid reading the head, skipToNext() will reposition.
    }
    return skipToNext(v);
  }

template<class Encoder, class Instructions, class SizeType>

ValueType folly::compression::detail::UpperBitsReader< Encoder, Instructions, SizeType >::next ( )

inline

Definition at line 375 of file EliasFanoCoding.h.

References start_.

                   {
    // Skip to the first non-zero block.
    while (block_ == 0) {
      outer_ += sizeof(block_t);
      block_ = folly::loadUnaligned<block_t>(start_ + outer_);
    }

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

    return setValue(inner);
  }

template<class Encoder, class Instructions, class SizeType>

SizeType folly::compression::detail::UpperBitsReader< Encoder, Instructions, SizeType >::position ( ) const

inline

Definition at line 358 of file EliasFanoCoding.h.

                            {
    return position_;
  }

template<class Encoder, class Instructions, class SizeType>

SizeType folly::compression::detail::UpperBitsReader< Encoder, Instructions, SizeType >::prepareSkipTo ( ValueType  v ) const

inline

Prepare to skip to value. This is a constant-time operation that will prefetch memory required for a skipTo(value) call.

Returns

position of reader

Definition at line 469 of file EliasFanoCoding.h.

References addr, upload::dest, start_, and shell_builder::steps.

                                            {
    auto position = position_;

    if (Encoder::skipQuantum > 0 && v >= value_ + Encoder::skipQuantum) {
      auto outer = outer_;
      const size_t steps = v / Encoder::skipQuantum;
      const size_t dest = folly::loadUnaligned<SkipValueType>(
          this->skipPointers_ + (steps - 1) * sizeof(SkipValueType));

      position = dest - 1;
      outer = (dest + Encoder::skipQuantum * steps) / 8;

      // Prefetch up to the beginning of where we linear search. After that,
      // hardware prefetching will outperform our own. In addition, this
      // simplifies calculating what to prefetch as we don't have to calculate
      // the entire destination address. Two cache lines are prefetched because
      // this results in fewer cycles used (based on practical results) than
      // one. However, three cache lines does not have any additional effect.
      const auto addr = start_ + outer;
      __builtin_prefetch(addr);
      __builtin_prefetch(addr + kCacheLineSize);
    }

    return position;
  }

template<class Encoder, class Instructions, class SizeType>

ValueType folly::compression::detail::UpperBitsReader< Encoder, Instructions, SizeType >::previous ( )

inline

Definition at line 365 of file EliasFanoCoding.h.

References start_.

                       {
    size_t inner;
    block_t block;
    getPreviousInfo(block, inner, outer_);
    block_ = folly::loadUnaligned<block_t>(start_ + outer_);
    block_ ^= block;
    --position_;
    return setValue(inner);
  }

template<class Encoder, class Instructions, class SizeType>

ValueType folly::compression::detail::UpperBitsReader< Encoder, Instructions, SizeType >::previousValue ( ) const

inline

Definition at line 514 of file EliasFanoCoding.h.

                                  {
    block_t block;
    size_t inner;
    OuterType outer;
    getPreviousInfo(block, inner, outer);
    return static_cast<ValueType>(8 * outer + inner - (position_ - 1));
  }

template<class Encoder, class Instructions, class SizeType>

void folly::compression::detail::UpperBitsReader< Encoder, Instructions, SizeType >::reposition ( SizeType  dest )

inlineprivate

Definition at line 532 of file EliasFanoCoding.h.

References start_.

                                 {
    outer_ = dest / 8;
    block_ = folly::loadUnaligned<block_t>(start_ + outer_);
    block_ &= ~((block_t(1) << (dest % 8)) - 1);
  }

template<class Encoder, class Instructions, class SizeType>

void folly::compression::detail::UpperBitsReader< Encoder, Instructions, SizeType >::reset ( )

inline

Definition at line 351 of file EliasFanoCoding.h.

References max, and start_.

               {
    block_ = start_ != nullptr ? folly::loadUnaligned<block_t>(start_) : 0;
    position_ = std::numeric_limits<SizeType>::max();
    outer_ = 0;
    value_ = 0;
  }

template<class Encoder, class Instructions, class SizeType>

void folly::compression::detail::UpperBitsReader< Encoder, Instructions, SizeType >::setDone ( SizeType  endPos )

inline

Definition at line 522 of file EliasFanoCoding.h.

                                {
    position_ = endPos;
  }

template<class Encoder, class Instructions, class SizeType>

ValueType folly::compression::detail::UpperBitsReader< Encoder, Instructions, SizeType >::setValue ( size_t  inner )

inlineprivate

Definition at line 527 of file EliasFanoCoding.h.

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

template<class Encoder, class Instructions, class SizeType>

ValueType folly::compression::detail::UpperBitsReader< Encoder, Instructions, SizeType >::skip ( SizeType  n )

inline

Definition at line 389 of file EliasFanoCoding.h.

References upload::dest, folly::popcount(), start_, and shell_builder::steps.

                             {
    DCHECK_GT(n, 0);

    position_ += n; // n 1-bits will be read.

    // 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 + steps * Encoder::forwardQuantum);
      n = position_ + 1 - steps * Encoder::forwardQuantum; // n is > 0.
    }

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

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

    return setValue(inner);
  }

template<class Encoder, class Instructions, class SizeType>

ValueType folly::compression::detail::UpperBitsReader< Encoder, Instructions, SizeType >::skipToNext ( ValueType  v )

inline

Definition at line 422 of file EliasFanoCoding.h.

References upload::dest, LIKELY, cpp.ast::next(), folly::popcount(), folly::gen::skip(), start_, and shell_builder::steps.

                                    {
    DCHECK_GE(v, value_);

    // Use skip pointer.
    if (Encoder::skipQuantum > 0 && v >= value_ + Encoder::skipQuantum) {
      const size_t steps = v / Encoder::skipQuantum;
      const size_t dest = folly::loadUnaligned<SkipValueType>(
          this->skipPointers_ + (steps - 1) * sizeof(SkipValueType));

      reposition(dest + Encoder::skipQuantum * steps);
      position_ = dest - 1;

      // Correct value_ will be set during the next() call at the end.

      // NOTE: Corresponding block of lower bits sequence may be
      // prefetched here (via __builtin_prefetch), but experiments
      // didn't show any significant improvements.
    }

    // Skip by blocks.
    size_t cnt;
    size_t skip = v - (8 * outer_ - position_ - 1);

    constexpr size_t kBitsPerBlock = 8 * sizeof(block_t);
    while ((cnt = Instructions::popcount(~block_)) < skip) {
      skip -= cnt;
      position_ += kBitsPerBlock - cnt;
      outer_ += sizeof(block_t);
      block_ = folly::loadUnaligned<block_t>(start_ + outer_);
    }

    if (LIKELY(skip)) {
      auto inner = select64<Instructions>(~block_, skip - 1);
      position_ += inner - skip + 1;
      block_ &= block_t(-1) << inner;
    }

    next();
    return value_;
  }

template<class Encoder, class Instructions, class SizeType>

ValueType folly::compression::detail::UpperBitsReader< Encoder, Instructions, SizeType >::value ( ) const

inline

Definition at line 361 of file EliasFanoCoding.h.

                          {
    return value_;
  }

Member Data Documentation

template<class Encoder, class Instructions, class SizeType>

block_t folly::compression::detail::UpperBitsReader< Encoder, Instructions, SizeType >::block_

private

Definition at line 560 of file EliasFanoCoding.h.

template<class Encoder, class Instructions, class SizeType>

OuterType folly::compression::detail::UpperBitsReader< Encoder, Instructions, SizeType >::outer_

private

Definition at line 562 of file EliasFanoCoding.h.

template<class Encoder, class Instructions, class SizeType>

SizeType folly::compression::detail::UpperBitsReader< Encoder, Instructions, SizeType >::position_

private

Definition at line 561 of file EliasFanoCoding.h.

template<class Encoder, class Instructions, class SizeType>

const unsigned char* const folly::compression::detail::UpperBitsReader< Encoder, Instructions, SizeType >::start_

private

Definition at line 559 of file EliasFanoCoding.h.

template<class Encoder, class Instructions, class SizeType>

ValueType folly::compression::detail::UpperBitsReader< Encoder, Instructions, SizeType >::value_

private

Definition at line 563 of file EliasFanoCoding.h.

---

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

• proxygen/folly/folly/experimental/EliasFanoCoding.h