src/leveldb/db/version_set_test.cc

   1 // Copyright (c) 2011 The LevelDB Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file. See the AUTHORS file for names of contributors.
   4
   5 #include "db/version_set.h"
   6 #include "util/logging.h"
   7 #include "util/testharness.h"
   8 #include "util/testutil.h"
   9
  10 namespace leveldb {
  11
  12 class FindFileTest {
  13  public:
  14   std::vector<FileMetaData*> files_;
  15   bool disjoint_sorted_files_;
  16
  17   FindFileTest() : disjoint_sorted_files_(true) { }
  18
  19   ~FindFileTest() {
  20     for (int i = 0; i < files_.size(); i++) {
  21       delete files_[i];
  22     }
  23   }
  24
  25   void Add(const char* smallest, const char* largest,
  26            SequenceNumber smallest_seq = 100,
  27            SequenceNumber largest_seq = 100) {
  28     FileMetaData* f = new FileMetaData;
  29     f->number = files_.size() + 1;
  30     f->smallest = InternalKey(smallest, smallest_seq, kTypeValue);
  31     f->largest = InternalKey(largest, largest_seq, kTypeValue);
  32     files_.push_back(f);
  33   }
  34
  35   int Find(const char* key) {
  36     InternalKey target(key, 100, kTypeValue);
  37     InternalKeyComparator cmp(BytewiseComparator());
  38     return FindFile(cmp, files_, target.Encode());
  39   }
  40
  41   bool Overlaps(const char* smallest, const char* largest) {
  42     InternalKeyComparator cmp(BytewiseComparator());
  43     Slice s(smallest != NULL ? smallest : "");
  44     Slice l(largest != NULL ? largest : "");
  45     return SomeFileOverlapsRange(cmp, disjoint_sorted_files_, files_,
  46                                  (smallest != NULL ? &s : NULL),
  47                                  (largest != NULL ? &l : NULL));
  48   }
  49 };
  50
  51 TEST(FindFileTest, Empty) {
  52   ASSERT_EQ(0, Find("foo"));
  53   ASSERT_TRUE(! Overlaps("a", "z"));
  54   ASSERT_TRUE(! Overlaps(NULL, "z"));
  55   ASSERT_TRUE(! Overlaps("a", NULL));
  56   ASSERT_TRUE(! Overlaps(NULL, NULL));
  57 }
  58
  59 TEST(FindFileTest, Single) {
  60   Add("p", "q");
  61   ASSERT_EQ(0, Find("a"));
  62   ASSERT_EQ(0, Find("p"));
  63   ASSERT_EQ(0, Find("p1"));
  64   ASSERT_EQ(0, Find("q"));
  65   ASSERT_EQ(1, Find("q1"));
  66   ASSERT_EQ(1, Find("z"));
  67
  68   ASSERT_TRUE(! Overlaps("a", "b"));
  69   ASSERT_TRUE(! Overlaps("z1", "z2"));
  70   ASSERT_TRUE(Overlaps("a", "p"));
  71   ASSERT_TRUE(Overlaps("a", "q"));
  72   ASSERT_TRUE(Overlaps("a", "z"));
  73   ASSERT_TRUE(Overlaps("p", "p1"));
  74   ASSERT_TRUE(Overlaps("p", "q"));
  75   ASSERT_TRUE(Overlaps("p", "z"));
  76   ASSERT_TRUE(Overlaps("p1", "p2"));
  77   ASSERT_TRUE(Overlaps("p1", "z"));
  78   ASSERT_TRUE(Overlaps("q", "q"));
  79   ASSERT_TRUE(Overlaps("q", "q1"));
  80
  81   ASSERT_TRUE(! Overlaps(NULL, "j"));
  82   ASSERT_TRUE(! Overlaps("r", NULL));
  83   ASSERT_TRUE(Overlaps(NULL, "p"));
  84   ASSERT_TRUE(Overlaps(NULL, "p1"));
  85   ASSERT_TRUE(Overlaps("q", NULL));
  86   ASSERT_TRUE(Overlaps(NULL, NULL));
  87 }
  88
  89
  90 TEST(FindFileTest, Multiple) {
  91   Add("150", "200");
  92   Add("200", "250");
  93   Add("300", "350");
  94   Add("400", "450");
  95   ASSERT_EQ(0, Find("100"));
  96   ASSERT_EQ(0, Find("150"));
  97   ASSERT_EQ(0, Find("151"));
  98   ASSERT_EQ(0, Find("199"));
  99   ASSERT_EQ(0, Find("200"));
 100   ASSERT_EQ(1, Find("201"));
 101   ASSERT_EQ(1, Find("249"));
 102   ASSERT_EQ(1, Find("250"));
 103   ASSERT_EQ(2, Find("251"));
 104   ASSERT_EQ(2, Find("299"));
 105   ASSERT_EQ(2, Find("300"));
 106   ASSERT_EQ(2, Find("349"));
 107   ASSERT_EQ(2, Find("350"));
 108   ASSERT_EQ(3, Find("351"));
 109   ASSERT_EQ(3, Find("400"));
 110   ASSERT_EQ(3, Find("450"));
 111   ASSERT_EQ(4, Find("451"));
 112
 113   ASSERT_TRUE(! Overlaps("100", "149"));
 114   ASSERT_TRUE(! Overlaps("251", "299"));
 115   ASSERT_TRUE(! Overlaps("451", "500"));
 116   ASSERT_TRUE(! Overlaps("351", "399"));
 117
 118   ASSERT_TRUE(Overlaps("100", "150"));
 119   ASSERT_TRUE(Overlaps("100", "200"));
 120   ASSERT_TRUE(Overlaps("100", "300"));
 121   ASSERT_TRUE(Overlaps("100", "400"));
 122   ASSERT_TRUE(Overlaps("100", "500"));
 123   ASSERT_TRUE(Overlaps("375", "400"));
 124   ASSERT_TRUE(Overlaps("450", "450"));
 125   ASSERT_TRUE(Overlaps("450", "500"));
 126 }
 127
 128 TEST(FindFileTest, MultipleNullBoundaries) {
 129   Add("150", "200");
 130   Add("200", "250");
 131   Add("300", "350");
 132   Add("400", "450");
 133   ASSERT_TRUE(! Overlaps(NULL, "149"));
 134   ASSERT_TRUE(! Overlaps("451", NULL));
 135   ASSERT_TRUE(Overlaps(NULL, NULL));
 136   ASSERT_TRUE(Overlaps(NULL, "150"));
 137   ASSERT_TRUE(Overlaps(NULL, "199"));
 138   ASSERT_TRUE(Overlaps(NULL, "200"));
 139   ASSERT_TRUE(Overlaps(NULL, "201"));
 140   ASSERT_TRUE(Overlaps(NULL, "400"));
 141   ASSERT_TRUE(Overlaps(NULL, "800"));
 142   ASSERT_TRUE(Overlaps("100", NULL));
 143   ASSERT_TRUE(Overlaps("200", NULL));
 144   ASSERT_TRUE(Overlaps("449", NULL));
 145   ASSERT_TRUE(Overlaps("450", NULL));
 146 }
 147
 148 TEST(FindFileTest, OverlapSequenceChecks) {
 149   Add("200", "200", 5000, 3000);
 150   ASSERT_TRUE(! Overlaps("199", "199"));
 151   ASSERT_TRUE(! Overlaps("201", "300"));
 152   ASSERT_TRUE(Overlaps("200", "200"));
 153   ASSERT_TRUE(Overlaps("190", "200"));
 154   ASSERT_TRUE(Overlaps("200", "210"));
 155 }
 156
 157 TEST(FindFileTest, OverlappingFiles) {
 158   Add("150", "600");
 159   Add("400", "500");
 160   disjoint_sorted_files_ = false;
 161   ASSERT_TRUE(! Overlaps("100", "149"));
 162   ASSERT_TRUE(! Overlaps("601", "700"));
 163   ASSERT_TRUE(Overlaps("100", "150"));
 164   ASSERT_TRUE(Overlaps("100", "200"));
 165   ASSERT_TRUE(Overlaps("100", "300"));
 166   ASSERT_TRUE(Overlaps("100", "400"));
 167   ASSERT_TRUE(Overlaps("100", "500"));
 168   ASSERT_TRUE(Overlaps("375", "400"));
 169   ASSERT_TRUE(Overlaps("450", "450"));
 170   ASSERT_TRUE(Overlaps("450", "500"));
 171   ASSERT_TRUE(Overlaps("450", "700"));
 172   ASSERT_TRUE(Overlaps("600", "700"));
 173 }
 174
 175 }  // namespace leveldb
 176
 177 int main(int argc, char** argv) {
 178   return leveldb::test::RunAllTests();
 179 }