allow command to accept "--" separator

[folly.git] / folly / experimental / BitVectorCoding.h

diff --git a/folly/experimental/BitVectorCoding.h b/folly/experimental/BitVectorCoding.h
index e2290fcd3d8f35dd25f79c998c09018c87febc4c..68c20598b6272fd9fa6ea074a8f1d963ffb0dd83 100644 (file)
--- a/folly/experimental/BitVectorCoding.h
+++ b/folly/experimental/BitVectorCoding.h
@@ -1,5 +1,5 @@
 /*
- * Copyright 2017 Facebook, Inc.
+ * Copyright 2015-present Facebook, Inc.
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
@@ -20,13 +20,14 @@
 #include <limits>
 #include <type_traits>
 
-#include <folly/Bits.h>
 #include <folly/Likely.h>
 #include <folly/Portability.h>
 #include <folly/Range.h>
 #include <folly/experimental/Bits.h>
+#include <folly/experimental/CodingDetail.h>
 #include <folly/experimental/Instructions.h>
 #include <folly/experimental/Select64.h>
+#include <folly/lang/Bits.h>
 #include <glog/logging.h>
 
 #if !FOLLY_X64
@@ -69,10 +70,11 @@ struct BitVectorCompressedListBase {
 typedef BitVectorCompressedListBase<const uint8_t*> BitVectorCompressedList;
 typedef BitVectorCompressedListBase<uint8_t*> MutableBitVectorCompressedList;
 
-template <class Value,
-          class SkipValue,
-          size_t kSkipQuantum = 0,
-          size_t kForwardQuantum = 0>
+template <
+    class Value,
+    class SkipValue,
+    size_t kSkipQuantum = 0,
+    size_t kForwardQuantum = 0>
 struct BitVectorEncoder {
   static_assert(std::is_integral<Value>::value &&
                     std::is_unsigned<Value>::value,
@@ -164,10 +166,11 @@ struct BitVectorEncoder {
   MutableCompressedList result_;
 };
 
-template <class Value,
-          class SkipValue,
-          size_t kSkipQuantum,
-          size_t kForwardQuantum>
+template <
+    class Value,
+    class SkipValue,
+    size_t kSkipQuantum,
+    size_t kForwardQuantum>
 struct BitVectorEncoder<Value, SkipValue, kSkipQuantum, kForwardQuantum>::
     Layout {
   static Layout fromUpperBoundAndSize(size_t upperBound, size_t size) {
@@ -233,20 +236,24 @@ struct BitVectorEncoder<Value, SkipValue, kSkipQuantum, kForwardQuantum>::
   size_t forwardPointers = 0;
 };
 
-template <class Encoder,
-          class Instructions = instructions::Default,
-          bool kUnchecked = false>
-class BitVectorReader {
+template <
+    class Encoder,
+    class Instructions = instructions::Default,
+    bool kUnchecked = false>
+class BitVectorReader : detail::ForwardPointers<Encoder::forwardQuantum>,
+                        detail::SkipPointers<Encoder::skipQuantum> {
  public:
   typedef Encoder EncoderType;
   typedef typename Encoder::ValueType ValueType;
+  // A bitvector can only be as large as its largest value.
+  typedef typename Encoder::ValueType SizeType;
   typedef typename Encoder::SkipValueType SkipValueType;
 
   explicit BitVectorReader(const typename Encoder::CompressedList& list)
-      : size_(list.size),
+      : detail::ForwardPointers<Encoder::forwardQuantum>(list.forwardPointers),
+        detail::SkipPointers<Encoder::skipQuantum>(list.skipPointers),
         bits_(list.bits),
-        skipPointers_(list.skipPointers),
-        forwardPointers_(list.forwardPointers) {
+        size_(list.size) {
     reset();
 
     if (kUnchecked || UNLIKELY(list.size == 0)) {
@@ -260,7 +267,6 @@ class BitVectorReader {
   void reset() {
     block_ = (bits_ != nullptr) ? folly::loadUnaligned<uint64_t>(bits_) : 0;
     outer_ = 0;
-    inner_ = -1;
     position_ = -1;
     value_ = kInvalidValue;
   }
@@ -276,13 +282,13 @@ class BitVectorReader {
     }
 
     ++position_;
-    inner_ = Instructions::ctz(block_);
+    auto inner = Instructions::ctz(block_);
     block_ = Instructions::blsr(block_);
 
-    return setValue();
+    return setValue(inner);
   }
 
-  bool skip(size_t n) {
+  bool skip(SizeType n) {
     CHECK_GT(n, 0);
 
     if (!kUnchecked && position() + n >= size_) {
@@ -302,11 +308,10 @@ class BitVectorReader {
     if (Encoder::forwardQuantum > 0 && n > Encoder::forwardQuantum) {
       const size_t steps = position_ / Encoder::forwardQuantum;
       const size_t dest = folly::loadUnaligned<SkipValueType>(
-          forwardPointers_ + (steps - 1) * sizeof(SkipValueType));
+          this->forwardPointers_ + (steps - 1) * sizeof(SkipValueType));
 
       reposition(dest);
       n = position_ + 1 - steps * Encoder::forwardQuantum;
-      // Correct inner_ will be set at the end.
     }
 
     size_t cnt;
@@ -319,10 +324,10 @@ class BitVectorReader {
 
     // Skip to the n-th one in the block.
     DCHECK_GT(n, 0);
-    inner_ = select64<Instructions>(block_, n - 1);
-    block_ &= (uint64_t(-1) << inner_) << 1;
+    auto inner = select64<Instructions>(block_, n - 1);
+    block_ &= (uint64_t(-1) << inner) << 1;
 
-    return setValue();
+    return setValue(inner);
   }
 
   bool skipTo(ValueType v) {
@@ -346,8 +351,9 @@ class BitVectorReader {
 
     if (Encoder::skipQuantum > 0 && v - value_ > Encoder::skipQuantum) {
       size_t q = v / Encoder::skipQuantum;
-      position_ = size_t(folly::loadUnaligned<SkipValueType>(
-                      skipPointers_ + (q - 1) * sizeof(SkipValueType))) - 1;
+      auto skipPointer = folly::loadUnaligned<SkipValueType>(
+          this->skipPointers_ + (q - 1) * sizeof(SkipValueType));
+      position_ = static_cast<SizeType>(skipPointer) - 1;
 
       reposition(q * Encoder::skipQuantum);
     }
@@ -371,26 +377,30 @@ class BitVectorReader {
       block_ = folly::loadUnaligned<uint64_t>(bits_ + outer_);
     }
 
-    inner_ = Instructions::ctz(block_);
+    auto inner = Instructions::ctz(block_);
     block_ = Instructions::blsr(block_);
 
-    setValue();
+    setValue(inner);
     return true;
   }
 
-  size_t size() const { return size_; }
+  SizeType size() const {
+    return size_;
+  }
 
   bool valid() const {
     return position() < size(); // Also checks that position() != -1.
   }
 
-  size_t position() const { return position_; }
+  SizeType position() const {
+    return position_;
+  }
   ValueType value() const {
     DCHECK(valid());
     return value_;
   }
 
-  bool jump(size_t n) {
+  bool jump(SizeType n) {
     reset();
     return skip(n + 1);
   }
@@ -410,8 +420,8 @@ class BitVectorReader {
   constexpr static ValueType kInvalidValue =
     std::numeric_limits<ValueType>::max();  // Must hold kInvalidValue + 1 == 0.
 
-  bool setValue() {
-    value_ = static_cast<ValueType>(8 * outer_ + inner_);
+  bool setValue(size_t inner) {
+    value_ = static_cast<ValueType>(8 * outer_ + inner);
     return true;
   }
 
@@ -424,17 +434,15 @@ class BitVectorReader {
 
   constexpr static size_t kLinearScanThreshold = 4;
 
-  size_t outer_;
-  size_t inner_;
-  size_t position_;
+  const uint8_t* const bits_;
   uint64_t block_;
+  SizeType outer_;
+  SizeType position_;
   ValueType value_;
 
-  size_t size_;
+  SizeType size_;
   ValueType upperBound_;
-  const uint8_t* const bits_;
-  const uint8_t* const skipPointers_;
-  const uint8_t* const forwardPointers_;
 };
 
-}}  // namespaces
+} // namespace compression
+} // namespace folly