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

#include <EliasFanoCoding.h>

Classes
struct	Layout

Public Types
typedef EliasFanoCompressedList	CompressedList
typedef MutableEliasFanoCompressedList	MutableCompressedList
typedef Value	ValueType
typedef SkipValue	SkipValueType

Public Member Functions
	EliasFanoEncoderV2 (const MutableCompressedList &result)
	EliasFanoEncoderV2 (size_t size, ValueType upperBound)
void	add (ValueType value)
const MutableCompressedList &	finish () const

Static Public Member Functions
static uint8_t	defaultNumLowerBits (size_t upperBound, size_t size)
template<class RandomAccessIterator >
static MutableCompressedList	encode (RandomAccessIterator begin, RandomAccessIterator end)

Static Public Attributes
static constexpr size_t	skipQuantum = kSkipQuantum
static constexpr size_t	forwardQuantum = kForwardQuantum

Static Private Member Functions
static void	writeBits56 (unsigned char *data, size_t pos, uint8_t len, uint64_t value)

Private Attributes
unsigned char *	lower_ = nullptr
unsigned char *	upper_ = nullptr
SkipValueType *	skipPointers_ = nullptr
SkipValueType *	forwardPointers_ = nullptr
ValueType	lastValue_ = 0
size_t	size_ = 0
size_t	skipPointersSize_ = 0
MutableCompressedList	result_

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 >

Definition at line 97 of file EliasFanoCoding.h.

Member Typedef Documentation

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

typedef EliasFanoCompressedList folly::compression::EliasFanoEncoderV2< Value, SkipValue, kSkipQuantum, kForwardQuantum >::CompressedList

Definition at line 100 of file EliasFanoCoding.h.

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

typedef MutableEliasFanoCompressedList folly::compression::EliasFanoEncoderV2< Value, SkipValue, kSkipQuantum, kForwardQuantum >::MutableCompressedList

Definition at line 103 of file EliasFanoCoding.h.

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

typedef SkipValue folly::compression::EliasFanoEncoderV2< Value, SkipValue, kSkipQuantum, kForwardQuantum >::SkipValueType

Definition at line 106 of file EliasFanoCoding.h.

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

typedef Value folly::compression::EliasFanoEncoderV2< Value, SkipValue, kSkipQuantum, kForwardQuantum >::ValueType

Definition at line 105 of file EliasFanoCoding.h.

Constructor & Destructor Documentation

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

folly::compression::EliasFanoEncoderV2< Value, SkipValue, kSkipQuantum, kForwardQuantum >::EliasFanoEncoderV2 ( const MutableCompressedList &  result )

inlineexplicit

Definition at line 145 of file EliasFanoCoding.h.

References folly::Range< Iter >::begin(), folly::compression::EliasFanoCompressedListBase< Pointer >::data, and folly::Range< Iter >::end().

      : lower_(result.lower),
        upper_(result.upper),
        skipPointers_(reinterpret_cast<SkipValueType*>(result.skipPointers)),
        forwardPointers_(
            reinterpret_cast<SkipValueType*>(result.forwardPointers)),
        result_(result) {
    std::fill(result.data.begin(), result.data.end(), '\0');
  }

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

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

inline

Definition at line 155 of file EliasFanoCoding.h.

      : EliasFanoEncoderV2(
            Layout::fromUpperBoundAndSize(upperBound, size).allocList()) {}

Member Function Documentation

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

void folly::compression::EliasFanoEncoderV2< Value, SkipValue, kSkipQuantum, kForwardQuantum >::add ( ValueType  value )

inline

Definition at line 159 of file EliasFanoCoding.h.

References k, max, folly::compression::EliasFanoCompressedListBase< Pointer >::numLowerBits, and folly::value().

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

                            {
    CHECK_LT(value, std::numeric_limits<ValueType>::max());
    CHECK_GE(value, lastValue_);

    const auto numLowerBits = result_.numLowerBits;
    const ValueType upperBits = value >> numLowerBits;

    // Upper sequence consists of upperBits 0-bits and (size_ + 1) 1-bits.
    const size_t pos = upperBits + size_;
    upper_[pos / 8] |= 1U << (pos % 8);
    // Append numLowerBits bits to lower sequence.
    if (numLowerBits != 0) {
      const ValueType lowerBits = value & ((ValueType(1) << numLowerBits) - 1);
      writeBits56(lower_, size_ * numLowerBits, numLowerBits, lowerBits);
    }

    if /* constexpr */ (skipQuantum != 0) {
      while ((skipPointersSize_ + 1) * skipQuantum <= upperBits) {
        // Store the number of preceding 1-bits.
        skipPointers_[skipPointersSize_++] = SkipValue(size_);
      }
    }

    if /* constexpr */ (forwardQuantum != 0) {
      if ((size_ + 1) % forwardQuantum == 0) {
        const auto k = size_ / forwardQuantum;
        // Store the number of preceding 0-bits.
        forwardPointers_[k] = upperBits;
      }
    }

    lastValue_ = value;
    ++size_;
  }

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

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

inlinestatic

Definition at line 112 of file EliasFanoCoding.h.

References folly::findLastSet(), and UNLIKELY.

                                                                     {
    if (UNLIKELY(size == 0 || upperBound < size)) {
      return 0;
    }
    // Result that should be returned is "floor(log(upperBound / size))".
    // In order to avoid expensive division, we rely on
    // "floor(a) - floor(b) - 1 <= floor(a - b) <= floor(a) - floor(b)".
    // Assuming "candidate = floor(log(upperBound)) - floor(log(upperBound))",
    // then result is either "candidate - 1" or "candidate".
    auto candidate = folly::findLastSet(upperBound) - folly::findLastSet(size);
    // NOTE: As size != 0, "candidate" is always < 64.
    return (size > (upperBound >> candidate)) ? candidate - 1 : candidate;
  }

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

template<class RandomAccessIterator >

static MutableCompressedList folly::compression::EliasFanoEncoderV2< Value, SkipValue, kSkipQuantum, kForwardQuantum >::encode ( RandomAccessIterator  begin, RandomAccessIterator  end  )

inlinestatic

Definition at line 132 of file EliasFanoCoding.h.

References folly::compression::EliasFanoEncoderV2< Value, SkipValue, kSkipQuantum, kForwardQuantum >::add(), folly::test::begin(), folly::test::end(), and folly::compression::EliasFanoEncoderV2< Value, SkipValue, kSkipQuantum, kForwardQuantum >::finish().

                                {
    if (begin == end) {
      return MutableCompressedList();
    }
    EliasFanoEncoderV2 encoder(size_t(end - begin), *(end - 1));
    for (; begin != end; ++begin) {
      encoder.add(*begin);
    }
    return encoder.finish();
  }

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

const MutableCompressedList& folly::compression::EliasFanoEncoderV2< Value, SkipValue, kSkipQuantum, kForwardQuantum >::finish ( ) const

inline

Definition at line 194 of file EliasFanoCoding.h.

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

                                              {
    CHECK_EQ(size_, result_.size);
    return result_;
  }

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

static void folly::compression::EliasFanoEncoderV2< Value, SkipValue, kSkipQuantum, kForwardQuantum >::writeBits56 ( unsigned char *  data, size_t  pos, uint8_t  len, uint64_t  value  )

inlinestaticprivate

Definition at line 202 of file EliasFanoCoding.h.

References ptr, uint32_t, and uint64_t.

                                                                            {
    DCHECK_LE(uint32_t(len), 56);
    DCHECK_EQ(0, value & ~((uint64_t(1) << len) - 1));
    unsigned char* const ptr = data + (pos / 8);
    uint64_t ptrv = folly::loadUnaligned<uint64_t>(ptr);
    ptrv |= value << (pos % 8);
    folly::storeUnaligned<uint64_t>(ptr, ptrv);
  }

Member Data Documentation

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

SkipValueType* folly::compression::EliasFanoEncoderV2< Value, SkipValue, kSkipQuantum, kForwardQuantum >::forwardPointers_ = nullptr

private

Definition at line 214 of file EliasFanoCoding.h.

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

constexpr size_t folly::compression::EliasFanoEncoderV2< Value, SkipValue, kSkipQuantum, kForwardQuantum >::forwardQuantum = kForwardQuantum

static

Definition at line 110 of file EliasFanoCoding.h.

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

ValueType folly::compression::EliasFanoEncoderV2< Value, SkipValue, kSkipQuantum, kForwardQuantum >::lastValue_ = 0

private

Definition at line 216 of file EliasFanoCoding.h.

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

unsigned char* folly::compression::EliasFanoEncoderV2< Value, SkipValue, kSkipQuantum, kForwardQuantum >::lower_ = nullptr

private

Definition at line 211 of file EliasFanoCoding.h.

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

MutableCompressedList folly::compression::EliasFanoEncoderV2< Value, SkipValue, kSkipQuantum, kForwardQuantum >::result_

private

Definition at line 220 of file EliasFanoCoding.h.

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

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

private

Definition at line 217 of file EliasFanoCoding.h.

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

SkipValueType* folly::compression::EliasFanoEncoderV2< Value, SkipValue, kSkipQuantum, kForwardQuantum >::skipPointers_ = nullptr

private

Definition at line 213 of file EliasFanoCoding.h.

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

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

private

Definition at line 218 of file EliasFanoCoding.h.

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

constexpr size_t folly::compression::EliasFanoEncoderV2< Value, SkipValue, kSkipQuantum, kForwardQuantum >::skipQuantum = kSkipQuantum

static

Definition at line 109 of file EliasFanoCoding.h.

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

unsigned char* folly::compression::EliasFanoEncoderV2< Value, SkipValue, kSkipQuantum, kForwardQuantum >::upper_ = nullptr

private

Definition at line 212 of file EliasFanoCoding.h.

---

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

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