proxygen
Classes | Public Types | Public Member Functions | Static Public Member Functions | Static Public Attributes | Private Attributes | List of all members
folly::compression::BitVectorEncoder< Value, SkipValue, kSkipQuantum, kForwardQuantum > Struct Template Reference

#include <BitVectorCoding.h>

Classes

struct  Layout
 

Public Types

typedef BitVectorCompressedList CompressedList
 
typedef MutableBitVectorCompressedList MutableCompressedList
 
typedef Value ValueType
 
typedef SkipValue SkipValueType
 

Public Member Functions

 BitVectorEncoder (const MutableCompressedList &result)
 
 BitVectorEncoder (size_t size, ValueType upperBound)
 
void add (ValueType value)
 
const MutableCompressedList & finish () const
 

Static Public Member Functions

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
 

Private Attributes

uint8_t *const bits_ = nullptr
 
uint8_t *const skipPointers_ = nullptr
 
uint8_t *const forwardPointers_ = nullptr
 
ValueType lastValue_ = -1
 
size_t size_ = 0
 
size_t skipPointersSize_ = 0
 
MutableCompressedList result_
 

Detailed Description

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

Definition at line 79 of file BitVectorCoding.h.

Member Typedef Documentation

template<class Value , class SkipValue , size_t kSkipQuantum = 0, size_t kForwardQuantum = 0>
typedef BitVectorCompressedList folly::compression::BitVectorEncoder< Value, SkipValue, kSkipQuantum, kForwardQuantum >::CompressedList

Definition at line 82 of file BitVectorCoding.h.

template<class Value , class SkipValue , size_t kSkipQuantum = 0, size_t kForwardQuantum = 0>
typedef MutableBitVectorCompressedList folly::compression::BitVectorEncoder< Value, SkipValue, kSkipQuantum, kForwardQuantum >::MutableCompressedList

Definition at line 85 of file BitVectorCoding.h.

template<class Value , class SkipValue , size_t kSkipQuantum = 0, size_t kForwardQuantum = 0>
typedef SkipValue folly::compression::BitVectorEncoder< Value, SkipValue, kSkipQuantum, kForwardQuantum >::SkipValueType

Definition at line 88 of file BitVectorCoding.h.

template<class Value , class SkipValue , size_t kSkipQuantum = 0, size_t kForwardQuantum = 0>
typedef Value folly::compression::BitVectorEncoder< Value, SkipValue, kSkipQuantum, kForwardQuantum >::ValueType

Definition at line 87 of file BitVectorCoding.h.

Constructor & Destructor Documentation

template<class Value , class SkipValue , size_t kSkipQuantum = 0, size_t kForwardQuantum = 0>
folly::compression::BitVectorEncoder< Value, SkipValue, kSkipQuantum, kForwardQuantum >::BitVectorEncoder ( const MutableCompressedList &  result)
inlineexplicit

Definition at line 108 of file BitVectorCoding.h.

References folly::compression::BitVectorCompressedListBase< Pointer >::data, folly::Range< Iter >::data(), and folly::Range< Iter >::size().

109  : bits_(result.bits),
110  skipPointers_(result.skipPointers),
111  forwardPointers_(result.forwardPointers),
112  result_(result) {
113  memset(result.data.data(), 0, result.data.size());
114  }
template<class Value , class SkipValue , size_t kSkipQuantum = 0, size_t kForwardQuantum = 0>
folly::compression::BitVectorEncoder< Value, SkipValue, kSkipQuantum, kForwardQuantum >::BitVectorEncoder ( size_t  size,
ValueType  upperBound 
)
inline

Definition at line 116 of file BitVectorCoding.h.

117  : BitVectorEncoder(
118  Layout::fromUpperBoundAndSize(upperBound, size).allocList()) {}
folly::compression::BitVectorEncoder::BitVectorEncoder
BitVectorEncoder(const MutableCompressedList &result)
Definition: BitVectorCoding.h:108
folly::size
constexpr auto size(C const &c) -> decltype(c.size())
Definition: Access.h:45
folly::compression::BitVectorEncoder::Layout::fromUpperBoundAndSize
static Layout fromUpperBoundAndSize(size_t upperBound, size_t size)
Definition: BitVectorCoding.h:178

Member Function Documentation

template<class Value , class SkipValue , size_t kSkipQuantum = 0, size_t kForwardQuantum = 0>
void folly::compression::BitVectorEncoder< Value, SkipValue, kSkipQuantum, kForwardQuantum >::add ( ValueType  value)
inline

Definition at line 120 of file BitVectorCoding.h.

References max, cpp.gmock_class::set, uint64_t, and folly::value().

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

120  {
121  CHECK_LT(value, std::numeric_limits<ValueType>::max());
122  // Also works when lastValue_ == -1.
123  CHECK_GT(value + 1, lastValue_ + 1)
124  << "BitVectorCoding only supports stricly monotone lists";
125 
126  auto block = bits_ + (value / 64) * sizeof(uint64_t);
127  size_t inner = value % 64;
128  folly::Bits<folly::Unaligned<uint64_t>>::set(
129  reinterpret_cast<folly::Unaligned<uint64_t>*>(block), inner);
130 
131  if (skipQuantum != 0) {
132  size_t nextSkipPointerSize = value / skipQuantum;
133  while (skipPointersSize_ < nextSkipPointerSize) {
134  auto pos = skipPointersSize_++;
135  folly::storeUnaligned<SkipValueType>(
136  skipPointers_ + pos * sizeof(SkipValueType), size_);
137  }
138  }
139 
140  if (forwardQuantum != 0) {
141  if (size_ != 0 && (size_ % forwardQuantum == 0)) {
142  const auto pos = size_ / forwardQuantum - 1;
143  folly::storeUnaligned<SkipValueType>(
144  forwardPointers_ + pos * sizeof(SkipValueType), value);
145  }
146  }
147 
148  lastValue_ = value;
149  ++size_;
150  }
folly::compression::BitVectorEncoder::skipQuantum
static constexpr size_t skipQuantum
Definition: BitVectorCoding.h:91
max
LogLevel max
Definition: LogLevel.cpp:31
folly::compression::BitVectorEncoder::forwardQuantum
static constexpr size_t forwardQuantum
Definition: BitVectorCoding.h:92
cpp.gmock_class.set
set
Definition: gmock_class.py:44
folly::value
uint64_t value(const typename LockFreeRingBuffer< T, Atom >::Cursor &rbcursor)
Definition: LockFreeRingBufferTest.cpp:96
template<class Value , class SkipValue , size_t kSkipQuantum = 0, size_t kForwardQuantum = 0>
template<class RandomAccessIterator >
static MutableCompressedList folly::compression::BitVectorEncoder< Value, SkipValue, kSkipQuantum, kForwardQuantum >::encode ( RandomAccessIterator  begin,
RandomAccessIterator  end 
)
inlinestatic

Definition at line 95 of file BitVectorCoding.h.

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

Referenced by BENCHMARK().

97  {
98  if (begin == end) {
99  return MutableCompressedList();
100  }
101  BitVectorEncoder encoder(size_t(end - begin), *(end - 1));
102  for (; begin != end; ++begin) {
103  encoder.add(*begin);
104  }
105  return encoder.finish();
106  }
folly::compression::BitVectorEncoder::MutableCompressedList
MutableBitVectorCompressedList MutableCompressedList
Definition: BitVectorCoding.h:85
folly::test::begin
auto begin(TestAdlIterable &instance)
Definition: ForeachTest.cpp:56
folly::compression::BitVectorEncoder::BitVectorEncoder
BitVectorEncoder(const MutableCompressedList &result)
Definition: BitVectorCoding.h:108
folly::test::end
auto end(TestAdlIterable &instance)
Definition: ForeachTest.cpp:62
template<class Value , class SkipValue , size_t kSkipQuantum = 0, size_t kForwardQuantum = 0>
const MutableCompressedList& folly::compression::BitVectorEncoder< Value, SkipValue, kSkipQuantum, kForwardQuantum >::finish ( ) const
inline

Definition at line 152 of file BitVectorCoding.h.

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

152  {
153  CHECK_EQ(size_, result_.size);
154  // TODO(ott): Relax this assumption.
155  CHECK_EQ(result_.upperBound, lastValue_);
156  return result_;
157  }

Member Data Documentation

template<class Value , class SkipValue , size_t kSkipQuantum = 0, size_t kForwardQuantum = 0>
uint8_t* const folly::compression::BitVectorEncoder< Value, SkipValue, kSkipQuantum, kForwardQuantum >::bits_ = nullptr
private

Definition at line 160 of file BitVectorCoding.h.

template<class Value , class SkipValue , size_t kSkipQuantum = 0, size_t kForwardQuantum = 0>
uint8_t* const folly::compression::BitVectorEncoder< Value, SkipValue, kSkipQuantum, kForwardQuantum >::forwardPointers_ = nullptr
private

Definition at line 162 of file BitVectorCoding.h.

template<class Value , class SkipValue , size_t kSkipQuantum = 0, size_t kForwardQuantum = 0>
constexpr size_t folly::compression::BitVectorEncoder< Value, SkipValue, kSkipQuantum, kForwardQuantum >::forwardQuantum = kForwardQuantum
static

Definition at line 92 of file BitVectorCoding.h.

template<class Value , class SkipValue , size_t kSkipQuantum = 0, size_t kForwardQuantum = 0>
ValueType folly::compression::BitVectorEncoder< Value, SkipValue, kSkipQuantum, kForwardQuantum >::lastValue_ = -1
private

Definition at line 164 of file BitVectorCoding.h.

template<class Value , class SkipValue , size_t kSkipQuantum = 0, size_t kForwardQuantum = 0>
MutableCompressedList folly::compression::BitVectorEncoder< Value, SkipValue, kSkipQuantum, kForwardQuantum >::result_
private

Definition at line 168 of file BitVectorCoding.h.

template<class Value , class SkipValue , size_t kSkipQuantum = 0, size_t kForwardQuantum = 0>
size_t folly::compression::BitVectorEncoder< Value, SkipValue, kSkipQuantum, kForwardQuantum >::size_ = 0
private

Definition at line 165 of file BitVectorCoding.h.

template<class Value , class SkipValue , size_t kSkipQuantum = 0, size_t kForwardQuantum = 0>
uint8_t* const folly::compression::BitVectorEncoder< Value, SkipValue, kSkipQuantum, kForwardQuantum >::skipPointers_ = nullptr
private

Definition at line 161 of file BitVectorCoding.h.

template<class Value , class SkipValue , size_t kSkipQuantum = 0, size_t kForwardQuantum = 0>
size_t folly::compression::BitVectorEncoder< Value, SkipValue, kSkipQuantum, kForwardQuantum >::skipPointersSize_ = 0
private

Definition at line 166 of file BitVectorCoding.h.

template<class Value , class SkipValue , size_t kSkipQuantum = 0, size_t kForwardQuantum = 0>
constexpr size_t folly::compression::BitVectorEncoder< Value, SkipValue, kSkipQuantum, kForwardQuantum >::skipQuantum = kSkipQuantum
static

Definition at line 91 of file BitVectorCoding.h.

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