folly::compression::EliasFanoEncoderV2< Value, SkipValue, kSkipQuantum, kForwardQuantum >::Layout Struct Reference

#include <EliasFanoCoding.h>

Public Member Functions
size_t	bytes () const
template<class Range >
EliasFanoCompressedListBase< typename Range::iterator >	openList (Range &buf) const
MutableCompressedList	allocList () const

Static Public Member Functions
static Layout	fromUpperBoundAndSize (size_t upperBound, size_t size)
static Layout	fromInternalSizes (uint8_t numLowerBits, size_t upper, size_t size)

Public Attributes
size_t	size = 0
uint8_t	numLowerBits = 0
size_t	lower = 0
size_t	upper = 0
size_t	skipPointers = 0
size_t	forwardPointers = 0

Detailed Description

template<class Value, class SkipValue = size_t, size_t kSkipQuantum = 0, size_t kForwardQuantum = 0>
struct folly::compression::EliasFanoEncoderV2< Value, SkipValue, kSkipQuantum, kForwardQuantum >::Layout

Definition at line 228 of file EliasFanoCoding.h.

Member Function Documentation

template<class Value , class SkipValue = size_t, size_t kSkipQuantum = 0, size_t kForwardQuantum = 0>

MutableCompressedList folly::compression::EliasFanoEncoderV2< Value, SkipValue, kSkipQuantum, kForwardQuantum >::Layout::allocList ( ) const

inline

Definition at line 310 of file EliasFanoCoding.h.

References folly::compression::EliasFanoCompressedListBase< Pointer >::size, and uint8_t.

                                          {
    uint8_t* buf = nullptr;
    // WARNING: Current read/write logic assumes that the 7 bytes
    // following the last byte of lower and upper sequences are
    // readable (stored value doesn't matter and won't be changed), so
    // we allocate additional 7 bytes, but do not include them in size
    // of returned value.
    if (size > 0) {
      buf = static_cast<uint8_t*>(malloc(bytes() + 7));
    }
    folly::MutableByteRange bufRange(buf, bytes());
    return openList(bufRange);
  }

template<class Value , class SkipValue = size_t, size_t kSkipQuantum = 0, size_t kForwardQuantum = 0>

size_t folly::compression::EliasFanoEncoderV2< Value, SkipValue, kSkipQuantum, kForwardQuantum >::Layout::bytes ( ) const

inline

Definition at line 284 of file EliasFanoCoding.h.

References folly::compression::EliasFanoCompressedListBase< Pointer >::forwardPointers, folly::compression::EliasFanoCompressedListBase< Pointer >::lower, folly::compression::EliasFanoCompressedListBase< Pointer >::skipPointers, and folly::compression::EliasFanoCompressedListBase< Pointer >::upper.

                       {
    return lower + upper + skipPointers + forwardPointers;
  }

template<class Value , class SkipValue = size_t, size_t kSkipQuantum = 0, size_t kForwardQuantum = 0>

static Layout folly::compression::EliasFanoEncoderV2< Value, SkipValue, kSkipQuantum, kForwardQuantum >::Layout::fromInternalSizes ( uint8_t  numLowerBits, size_t  upper, size_t  size  )

inlinestatic

Definition at line 253 of file EliasFanoCoding.h.

References folly::compression::EliasFanoEncoderV2< Value, SkipValue, kSkipQuantum, kForwardQuantum >::Layout::forwardPointers, folly::compression::EliasFanoEncoderV2< Value, SkipValue, kSkipQuantum, kForwardQuantum >::Layout::lower, folly::compression::EliasFanoCompressedListBase< Pointer >::numLowerBits, folly::compression::EliasFanoEncoderV2< Value, SkipValue, kSkipQuantum, kForwardQuantum >::Layout::numLowerBits, folly::compression::EliasFanoCompressedListBase< Pointer >::size, folly::compression::EliasFanoEncoderV2< Value, SkipValue, kSkipQuantum, kForwardQuantum >::Layout::size, folly::compression::EliasFanoEncoderV2< Value, SkipValue, kSkipQuantum, kForwardQuantum >::Layout::skipPointers, folly::compression::EliasFanoCompressedListBase< Pointer >::upper, and folly::compression::EliasFanoEncoderV2< Value, SkipValue, kSkipQuantum, kForwardQuantum >::Layout::upper.

                                                                     {
    Layout layout;
    layout.size = size;
    layout.numLowerBits = numLowerBits;

    layout.lower = (numLowerBits * size + 7) / 8;
    layout.upper = upper;

    // *** Skip pointers.
    // Store (1-indexed) position of every skipQuantum-th
    // 0-bit in upper bits sequence.
    if /* constexpr */ (skipQuantum != 0) {
      // 8 * upper is used here instead of upperSizeBits, as that is
      // more serialization-friendly way (upperSizeBits doesn't need
      // to be known by this function, unlike upper).

      size_t numSkipPointers = (8 * upper - size) / skipQuantum;
      layout.skipPointers = numSkipPointers * sizeof(SkipValueType);
    }

    // *** Forward pointers.
    // Store (1-indexed) position of every forwardQuantum-th
    // 1-bit in upper bits sequence.
    if /* constexpr */ (forwardQuantum != 0) {
      size_t numForwardPointers = size / forwardQuantum;
      layout.forwardPointers = numForwardPointers * sizeof(SkipValueType);
    }

    return layout;
  }

template<class Value , class SkipValue = size_t, size_t kSkipQuantum = 0, size_t kForwardQuantum = 0>

static Layout folly::compression::EliasFanoEncoderV2< Value, SkipValue, kSkipQuantum, kForwardQuantum >::Layout::fromUpperBoundAndSize ( size_t  upperBound, size_t  size  )

inlinestatic

Definition at line 230 of file EliasFanoCoding.h.

References max, min, folly::compression::EliasFanoCompressedListBase< Pointer >::numLowerBits, uint8_t, folly::compression::EliasFanoCompressedListBase< Pointer >::upper, and testing::Value().

                                                                      {
    // numLowerBits can be at most 56 because of detail::writeBits56.
    const uint8_t numLowerBits =
        std::min(defaultNumLowerBits(upperBound, size), uint8_t(56));
    // *** Upper bits.
    // Upper bits are stored using unary delta encoding.
    // For example, (3 5 5 9) will be encoded as 1000011001000_2.
    const size_t upperSizeBits =
        (upperBound >> numLowerBits) + // Number of 0-bits to be stored.
        size; // 1-bits.
    const size_t upper = (upperSizeBits + 7) / 8;

    // *** Validity checks.
    // Shift by numLowerBits must be valid.
    CHECK_LT(numLowerBits, 8 * sizeof(Value));
    CHECK_LT(size, std::numeric_limits<SkipValueType>::max());
    CHECK_LT(
        upperBound >> numLowerBits, std::numeric_limits<SkipValueType>::max());

    return fromInternalSizes(numLowerBits, upper, size);
  }

template<class Value , class SkipValue = size_t, size_t kSkipQuantum = 0, size_t kForwardQuantum = 0>

template<class Range >

EliasFanoCompressedListBase<typename Range::iterator> folly::compression::EliasFanoEncoderV2< Value, SkipValue, kSkipQuantum, kForwardQuantum >::Layout::openList ( Range &  buf ) const

inline

Definition at line 289 of file EliasFanoCoding.h.

References folly::detail::advance, folly::Range< Iter >::advance(), folly::test::begin(), folly::compression::EliasFanoCompressedListBase< Pointer >::data, folly::Range< Iter >::data(), folly::compression::EliasFanoCompressedListBase< Pointer >::forwardPointers, folly::compression::EliasFanoCompressedListBase< Pointer >::lower, folly::compression::EliasFanoCompressedListBase< Pointer >::numLowerBits, folly::compression::EliasFanoCompressedListBase< Pointer >::size, folly::compression::EliasFanoCompressedListBase< Pointer >::skipPointers, folly::Range< Iter >::subpiece(), and folly::compression::EliasFanoCompressedListBase< Pointer >::upper.

                        {
    EliasFanoCompressedListBase<typename Range::iterator> result;
    result.size = size;
    result.numLowerBits = numLowerBits;
    result.data = buf.subpiece(0, bytes());

    auto advance = [&](size_t n) {
      auto begin = buf.data();
      buf.advance(n);
      return begin;
    };

    result.skipPointers = advance(skipPointers);
    result.forwardPointers = advance(forwardPointers);
    result.lower = advance(lower);
    result.upper = advance(upper);

    return result;
  }

Member Data Documentation

template<class Value , class SkipValue = size_t, size_t kSkipQuantum = 0, size_t kForwardQuantum = 0>

size_t folly::compression::EliasFanoEncoderV2< Value, SkipValue, kSkipQuantum, kForwardQuantum >::Layout::forwardPointers = 0

Definition at line 331 of file EliasFanoCoding.h.

Referenced by folly::compression::EliasFanoEncoderV2< Value, SkipValue, kSkipQuantum, kForwardQuantum >::Layout::fromInternalSizes().

template<class Value , class SkipValue = size_t, size_t kSkipQuantum = 0, size_t kForwardQuantum = 0>

size_t folly::compression::EliasFanoEncoderV2< Value, SkipValue, kSkipQuantum, kForwardQuantum >::Layout::lower = 0

Definition at line 328 of file EliasFanoCoding.h.

Referenced by folly::compression::EliasFanoEncoderV2< Value, SkipValue, kSkipQuantum, kForwardQuantum >::Layout::fromInternalSizes().

template<class Value , class SkipValue = size_t, size_t kSkipQuantum = 0, size_t kForwardQuantum = 0>

uint8_t folly::compression::EliasFanoEncoderV2< Value, SkipValue, kSkipQuantum, kForwardQuantum >::Layout::numLowerBits = 0

Definition at line 325 of file EliasFanoCoding.h.

Referenced by folly::compression::EliasFanoEncoderV2< Value, SkipValue, kSkipQuantum, kForwardQuantum >::Layout::fromInternalSizes().

template<class Value , class SkipValue = size_t, size_t kSkipQuantum = 0, size_t kForwardQuantum = 0>

size_t folly::compression::EliasFanoEncoderV2< Value, SkipValue, kSkipQuantum, kForwardQuantum >::Layout::size = 0

Definition at line 324 of file EliasFanoCoding.h.

Referenced by folly::compression::EliasFanoEncoderV2< Value, SkipValue, kSkipQuantum, kForwardQuantum >::Layout::fromInternalSizes().

template<class Value , class SkipValue = size_t, size_t kSkipQuantum = 0, size_t kForwardQuantum = 0>

size_t folly::compression::EliasFanoEncoderV2< Value, SkipValue, kSkipQuantum, kForwardQuantum >::Layout::skipPointers = 0

Definition at line 330 of file EliasFanoCoding.h.

Referenced by folly::compression::EliasFanoEncoderV2< Value, SkipValue, kSkipQuantum, kForwardQuantum >::Layout::fromInternalSizes().

template<class Value , class SkipValue = size_t, size_t kSkipQuantum = 0, size_t kForwardQuantum = 0>

size_t folly::compression::EliasFanoEncoderV2< Value, SkipValue, kSkipQuantum, kForwardQuantum >::Layout::upper = 0

Definition at line 329 of file EliasFanoCoding.h.

Referenced by folly::compression::EliasFanoEncoderV2< Value, SkipValue, kSkipQuantum, kForwardQuantum >::Layout::fromInternalSizes().

---

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

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