ceph/src/rocksdb/table/merger_test.cc

   1 //  Copyright (c) 2011-present, Facebook, Inc.  All rights reserved.
   2 //  This source code is licensed under both the GPLv2 (found in the
   3 //  COPYING file in the root directory) and Apache 2.0 License
   4 //  (found in the LICENSE.Apache file in the root directory).
   5
   6 #include <vector>
   7 #include <string>
   8
   9 #include "table/merging_iterator.h"
  10 #include "util/testharness.h"
  11 #include "util/testutil.h"
  12
  13 namespace rocksdb {
  14
  15 class MergerTest : public testing::Test {
  16  public:
  17   MergerTest()
  18       : icomp_(BytewiseComparator()),
  19         rnd_(3),
  20         merging_iterator_(nullptr),
  21         single_iterator_(nullptr) {}
  22   ~MergerTest() override = default;
  23   std::vector<std::string> GenerateStrings(size_t len, int string_len) {
  24     std::vector<std::string> ret;
  25
  26     for (size_t i = 0; i < len; ++i) {
  27       InternalKey ik(test::RandomHumanReadableString(&rnd_, string_len), 0,
  28                      ValueType::kTypeValue);
  29       ret.push_back(ik.Encode().ToString(false));
  30     }
  31     return ret;
  32   }
  33
  34   void AssertEquivalence() {
  35     auto a = merging_iterator_.get();
  36     auto b = single_iterator_.get();
  37     if (!a->Valid()) {
  38       ASSERT_TRUE(!b->Valid());
  39     } else {
  40       ASSERT_TRUE(b->Valid());
  41       ASSERT_EQ(b->key().ToString(), a->key().ToString());
  42       ASSERT_EQ(b->value().ToString(), a->value().ToString());
  43     }
  44   }
  45
  46   void SeekToRandom() {
  47     InternalKey ik(test::RandomHumanReadableString(&rnd_, 5), 0,
  48                    ValueType::kTypeValue);
  49     Seek(ik.Encode().ToString(false));
  50   }
  51
  52   void Seek(std::string target) {
  53     merging_iterator_->Seek(target);
  54     single_iterator_->Seek(target);
  55   }
  56
  57   void SeekToFirst() {
  58     merging_iterator_->SeekToFirst();
  59     single_iterator_->SeekToFirst();
  60   }
  61
  62   void SeekToLast() {
  63     merging_iterator_->SeekToLast();
  64     single_iterator_->SeekToLast();
  65   }
  66
  67   void Next(int times) {
  68     for (int i = 0; i < times && merging_iterator_->Valid(); ++i) {
  69       AssertEquivalence();
  70       merging_iterator_->Next();
  71       single_iterator_->Next();
  72     }
  73     AssertEquivalence();
  74   }
  75
  76   void Prev(int times) {
  77     for (int i = 0; i < times && merging_iterator_->Valid(); ++i) {
  78       AssertEquivalence();
  79       merging_iterator_->Prev();
  80       single_iterator_->Prev();
  81     }
  82     AssertEquivalence();
  83   }
  84
  85   void NextAndPrev(int times) {
  86     for (int i = 0; i < times && merging_iterator_->Valid(); ++i) {
  87       AssertEquivalence();
  88       if (rnd_.OneIn(2)) {
  89         merging_iterator_->Prev();
  90         single_iterator_->Prev();
  91       } else {
  92         merging_iterator_->Next();
  93         single_iterator_->Next();
  94       }
  95     }
  96     AssertEquivalence();
  97   }
  98
  99   void Generate(size_t num_iterators, size_t strings_per_iterator,
 100                 int letters_per_string) {
 101     std::vector<InternalIterator*> small_iterators;
 102     for (size_t i = 0; i < num_iterators; ++i) {
 103       auto strings = GenerateStrings(strings_per_iterator, letters_per_string);
 104       small_iterators.push_back(new test::VectorIterator(strings));
 105       all_keys_.insert(all_keys_.end(), strings.begin(), strings.end());
 106     }
 107
 108     merging_iterator_.reset(
 109         NewMergingIterator(&icomp_, &small_iterators[0],
 110                            static_cast<int>(small_iterators.size())));
 111     single_iterator_.reset(new test::VectorIterator(all_keys_));
 112   }
 113
 114   InternalKeyComparator icomp_;
 115   Random rnd_;
 116   std::unique_ptr<InternalIterator> merging_iterator_;
 117   std::unique_ptr<InternalIterator> single_iterator_;
 118   std::vector<std::string> all_keys_;
 119 };
 120
 121 TEST_F(MergerTest, SeekToRandomNextTest) {
 122   Generate(1000, 50, 50);
 123   for (int i = 0; i < 10; ++i) {
 124     SeekToRandom();
 125     AssertEquivalence();
 126     Next(50000);
 127   }
 128 }
 129
 130 TEST_F(MergerTest, SeekToRandomNextSmallStringsTest) {
 131   Generate(1000, 50, 2);
 132   for (int i = 0; i < 10; ++i) {
 133     SeekToRandom();
 134     AssertEquivalence();
 135     Next(50000);
 136   }
 137 }
 138
 139 TEST_F(MergerTest, SeekToRandomPrevTest) {
 140   Generate(1000, 50, 50);
 141   for (int i = 0; i < 10; ++i) {
 142     SeekToRandom();
 143     AssertEquivalence();
 144     Prev(50000);
 145   }
 146 }
 147
 148 TEST_F(MergerTest, SeekToRandomRandomTest) {
 149   Generate(200, 50, 50);
 150   for (int i = 0; i < 3; ++i) {
 151     SeekToRandom();
 152     AssertEquivalence();
 153     NextAndPrev(5000);
 154   }
 155 }
 156
 157 TEST_F(MergerTest, SeekToFirstTest) {
 158   Generate(1000, 50, 50);
 159   for (int i = 0; i < 10; ++i) {
 160     SeekToFirst();
 161     AssertEquivalence();
 162     Next(50000);
 163   }
 164 }
 165
 166 TEST_F(MergerTest, SeekToLastTest) {
 167   Generate(1000, 50, 50);
 168   for (int i = 0; i < 10; ++i) {
 169     SeekToLast();
 170     AssertEquivalence();
 171     Prev(50000);
 172   }
 173 }
 174
 175 }  // namespace rocksdb
 176
 177 int main(int argc, char** argv) {
 178   ::testing::InitGoogleTest(&argc, argv);
 179   return RUN_ALL_TESTS();
 180 }