A core-cached shared_ptr

[folly.git] / folly / experimental / test / EliasFanoCodingTest.cpp

diff --git a/folly/experimental/test/EliasFanoCodingTest.cpp b/folly/experimental/test/EliasFanoCodingTest.cpp
index 63652300680916857781d19630a3d3808a1a1c8d..55af37d84d189cace91cbd8d0fe8b020eff99739 100644 (file)
--- a/folly/experimental/test/EliasFanoCodingTest.cpp
+++ b/folly/experimental/test/EliasFanoCodingTest.cpp
@@ -46,7 +46,7 @@ uint8_t slowDefaultNumLowerBits(size_t upperBound, size_t size) {
 TEST(EliasFanoCoding, defaultNumLowerBits) {
   // Verify that slowDefaultNumLowerBits and optimized
   // Encoder::defaultNumLowerBits agree.
-  constexpr size_t kNumIterations = 2500;
+  static constexpr size_t kNumIterations = 2500;
   auto compare = [](size_t upperBound, size_t size) {
     using Encoder = EliasFanoEncoderV2<size_t>;
     EXPECT_EQ(int(slowDefaultNumLowerBits(upperBound, size)),
@@ -94,11 +94,12 @@ class EliasFanoCodingTest : public ::testing::Test {
     testEmpty<Reader, Encoder>();
   }
 
-  template <size_t kSkipQuantum, size_t kForwardQuantum>
+  template <size_t kSkipQuantum, size_t kForwardQuantum, class SizeType>
   void doTestAll() {
     typedef EliasFanoEncoderV2<
       uint32_t, uint32_t, kSkipQuantum, kForwardQuantum> Encoder;
-    typedef EliasFanoReader<Encoder, instructions::EF_TEST_ARCH> Reader;
+    using Reader =
+        EliasFanoReader<Encoder, instructions::EF_TEST_ARCH, false, SizeType>;
     testAll<Reader, Encoder>({0});
     testAll<Reader, Encoder>(generateRandomList(100 * 1000, 10 * 1000 * 1000));
     testAll<Reader, Encoder>(generateSeqList(1, 100000, 100));
@@ -110,19 +111,23 @@ TEST_F(EliasFanoCodingTest, Empty) {
 }
 
 TEST_F(EliasFanoCodingTest, Simple) {
-  doTestAll<0, 0>();
+  doTestAll<0, 0, uint32_t>();
+  doTestAll<0, 0, size_t>();
 }
 
 TEST_F(EliasFanoCodingTest, SkipPointers) {
-  doTestAll<128, 0>();
+  doTestAll<128, 0, uint32_t>();
+  doTestAll<128, 0, size_t>();
 }
 
 TEST_F(EliasFanoCodingTest, ForwardPointers) {
-  doTestAll<0, 128>();
+  doTestAll<0, 128, uint32_t>();
+  doTestAll<0, 128, size_t>();
 }
 
 TEST_F(EliasFanoCodingTest, SkipForwardPointers) {
-  doTestAll<128, 128>();
+  doTestAll<128, 128, uint32_t>();
+  doTestAll<128, 128, size_t>();
 }
 
 TEST_F(EliasFanoCodingTest, Select64) {
@@ -138,6 +143,30 @@ TEST_F(EliasFanoCodingTest, Select64) {
   }
 }
 
+TEST_F(EliasFanoCodingTest, BugLargeGapInUpperBits) { // t16274876
+  typedef EliasFanoEncoderV2<uint32_t, uint32_t, 2, 2> Encoder;
+  typedef EliasFanoReader<Encoder, instructions::EF_TEST_ARCH> Reader;
+  constexpr uint32_t kLargeValue = 127;
+
+  // Build a list where the upper bits have a large gap after the
+  // first element, so that we need to reposition in the upper bits
+  // using skips to position the iterator on the second element.
+  std::vector<uint32_t> data = {0, kLargeValue};
+  for (uint32_t i = 0; i < kLargeValue; ++i) {
+    data.push_back(data.back() + 1);
+  }
+  auto list = Encoder::encode(data.begin(), data.end());
+
+  {
+    Reader reader(list);
+    ASSERT_TRUE(reader.skipTo(kLargeValue - 1));
+    ASSERT_EQ(kLargeValue, reader.value());
+    ASSERT_EQ(0, reader.previousValue());
+  }
+
+  list.free();
+}
+
 namespace bm {
 
 typedef EliasFanoEncoderV2<uint32_t, uint32_t, 128, 128> Encoder;