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