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 FindFileTest() : disjoint_sorted_files_(true) {} 15 16 ~FindFileTest() { 17 for (int i = 0; i < files_.size(); i++) { 18 delete files_[i]; 19 } 20 } 21 22 void Add(const char* smallest, const char* largest, 23 SequenceNumber smallest_seq = 100, 24 SequenceNumber largest_seq = 100) { 25 FileMetaData* f = new FileMetaData; 26 f->number = files_.size() + 1; 27 f->smallest = InternalKey(smallest, smallest_seq, kTypeValue); 28 f->largest = InternalKey(largest, largest_seq, kTypeValue); 29 files_.push_back(f); 30 } 31 32 int Find(const char* key) { 33 InternalKey target(key, 100, kTypeValue); 34 InternalKeyComparator cmp(BytewiseComparator()); 35 return FindFile(cmp, files_, target.Encode()); 36 } 37 38 bool Overlaps(const char* smallest, const char* largest) { 39 InternalKeyComparator cmp(BytewiseComparator()); 40 Slice s(smallest != nullptr ? smallest : ""); 41 Slice l(largest != nullptr ? largest : ""); 42 return SomeFileOverlapsRange(cmp, disjoint_sorted_files_, files_, 43 (smallest != nullptr ? &s : nullptr), 44 (largest != nullptr ? &l : nullptr)); 45 } 46 47 bool disjoint_sorted_files_; 48 49 private: 50 std::vector<FileMetaData*> files_; 51 }; 52 53 TEST(FindFileTest, Empty) { 54 ASSERT_EQ(0, Find("foo")); 55 ASSERT_TRUE(!Overlaps("a", "z")); 56 ASSERT_TRUE(!Overlaps(nullptr, "z")); 57 ASSERT_TRUE(!Overlaps("a", nullptr)); 58 ASSERT_TRUE(!Overlaps(nullptr, nullptr)); 59 } 60 61 TEST(FindFileTest, Single) { 62 Add("p", "q"); 63 ASSERT_EQ(0, Find("a")); 64 ASSERT_EQ(0, Find("p")); 65 ASSERT_EQ(0, Find("p1")); 66 ASSERT_EQ(0, Find("q")); 67 ASSERT_EQ(1, Find("q1")); 68 ASSERT_EQ(1, Find("z")); 69 70 ASSERT_TRUE(!Overlaps("a", "b")); 71 ASSERT_TRUE(!Overlaps("z1", "z2")); 72 ASSERT_TRUE(Overlaps("a", "p")); 73 ASSERT_TRUE(Overlaps("a", "q")); 74 ASSERT_TRUE(Overlaps("a", "z")); 75 ASSERT_TRUE(Overlaps("p", "p1")); 76 ASSERT_TRUE(Overlaps("p", "q")); 77 ASSERT_TRUE(Overlaps("p", "z")); 78 ASSERT_TRUE(Overlaps("p1", "p2")); 79 ASSERT_TRUE(Overlaps("p1", "z")); 80 ASSERT_TRUE(Overlaps("q", "q")); 81 ASSERT_TRUE(Overlaps("q", "q1")); 82 83 ASSERT_TRUE(!Overlaps(nullptr, "j")); 84 ASSERT_TRUE(!Overlaps("r", nullptr)); 85 ASSERT_TRUE(Overlaps(nullptr, "p")); 86 ASSERT_TRUE(Overlaps(nullptr, "p1")); 87 ASSERT_TRUE(Overlaps("q", nullptr)); 88 ASSERT_TRUE(Overlaps(nullptr, nullptr)); 89 } 90 91 TEST(FindFileTest, Multiple) { 92 Add("150", "200"); 93 Add("200", "250"); 94 Add("300", "350"); 95 Add("400", "450"); 96 ASSERT_EQ(0, Find("100")); 97 ASSERT_EQ(0, Find("150")); 98 ASSERT_EQ(0, Find("151")); 99 ASSERT_EQ(0, Find("199")); 100 ASSERT_EQ(0, Find("200")); 101 ASSERT_EQ(1, Find("201")); 102 ASSERT_EQ(1, Find("249")); 103 ASSERT_EQ(1, Find("250")); 104 ASSERT_EQ(2, Find("251")); 105 ASSERT_EQ(2, Find("299")); 106 ASSERT_EQ(2, Find("300")); 107 ASSERT_EQ(2, Find("349")); 108 ASSERT_EQ(2, Find("350")); 109 ASSERT_EQ(3, Find("351")); 110 ASSERT_EQ(3, Find("400")); 111 ASSERT_EQ(3, Find("450")); 112 ASSERT_EQ(4, Find("451")); 113 114 ASSERT_TRUE(!Overlaps("100", "149")); 115 ASSERT_TRUE(!Overlaps("251", "299")); 116 ASSERT_TRUE(!Overlaps("451", "500")); 117 ASSERT_TRUE(!Overlaps("351", "399")); 118 119 ASSERT_TRUE(Overlaps("100", "150")); 120 ASSERT_TRUE(Overlaps("100", "200")); 121 ASSERT_TRUE(Overlaps("100", "300")); 122 ASSERT_TRUE(Overlaps("100", "400")); 123 ASSERT_TRUE(Overlaps("100", "500")); 124 ASSERT_TRUE(Overlaps("375", "400")); 125 ASSERT_TRUE(Overlaps("450", "450")); 126 ASSERT_TRUE(Overlaps("450", "500")); 127 } 128 129 TEST(FindFileTest, MultipleNullBoundaries) { 130 Add("150", "200"); 131 Add("200", "250"); 132 Add("300", "350"); 133 Add("400", "450"); 134 ASSERT_TRUE(!Overlaps(nullptr, "149")); 135 ASSERT_TRUE(!Overlaps("451", nullptr)); 136 ASSERT_TRUE(Overlaps(nullptr, nullptr)); 137 ASSERT_TRUE(Overlaps(nullptr, "150")); 138 ASSERT_TRUE(Overlaps(nullptr, "199")); 139 ASSERT_TRUE(Overlaps(nullptr, "200")); 140 ASSERT_TRUE(Overlaps(nullptr, "201")); 141 ASSERT_TRUE(Overlaps(nullptr, "400")); 142 ASSERT_TRUE(Overlaps(nullptr, "800")); 143 ASSERT_TRUE(Overlaps("100", nullptr)); 144 ASSERT_TRUE(Overlaps("200", nullptr)); 145 ASSERT_TRUE(Overlaps("449", nullptr)); 146 ASSERT_TRUE(Overlaps("450", nullptr)); 147 } 148 149 TEST(FindFileTest, OverlapSequenceChecks) { 150 Add("200", "200", 5000, 3000); 151 ASSERT_TRUE(!Overlaps("199", "199")); 152 ASSERT_TRUE(!Overlaps("201", "300")); 153 ASSERT_TRUE(Overlaps("200", "200")); 154 ASSERT_TRUE(Overlaps("190", "200")); 155 ASSERT_TRUE(Overlaps("200", "210")); 156 } 157 158 TEST(FindFileTest, OverlappingFiles) { 159 Add("150", "600"); 160 Add("400", "500"); 161 disjoint_sorted_files_ = false; 162 ASSERT_TRUE(!Overlaps("100", "149")); 163 ASSERT_TRUE(!Overlaps("601", "700")); 164 ASSERT_TRUE(Overlaps("100", "150")); 165 ASSERT_TRUE(Overlaps("100", "200")); 166 ASSERT_TRUE(Overlaps("100", "300")); 167 ASSERT_TRUE(Overlaps("100", "400")); 168 ASSERT_TRUE(Overlaps("100", "500")); 169 ASSERT_TRUE(Overlaps("375", "400")); 170 ASSERT_TRUE(Overlaps("450", "450")); 171 ASSERT_TRUE(Overlaps("450", "500")); 172 ASSERT_TRUE(Overlaps("450", "700")); 173 ASSERT_TRUE(Overlaps("600", "700")); 174 } 175 176 void AddBoundaryInputs(const InternalKeyComparator& icmp, 177 const std::vector<FileMetaData*>& level_files, 178 std::vector<FileMetaData*>* compaction_files); 179 180 class AddBoundaryInputsTest { 181 public: 182 std::vector<FileMetaData*> level_files_; 183 std::vector<FileMetaData*> compaction_files_; 184 std::vector<FileMetaData*> all_files_; 185 InternalKeyComparator icmp_; 186 187 AddBoundaryInputsTest() : icmp_(BytewiseComparator()) {} 188 189 ~AddBoundaryInputsTest() { 190 for (size_t i = 0; i < all_files_.size(); ++i) { 191 delete all_files_[i]; 192 } 193 all_files_.clear(); 194 } 195 196 FileMetaData* CreateFileMetaData(uint64_t number, InternalKey smallest, 197 InternalKey largest) { 198 FileMetaData* f = new FileMetaData(); 199 f->number = number; 200 f->smallest = smallest; 201 f->largest = largest; 202 all_files_.push_back(f); 203 return f; 204 } 205 }; 206 207 TEST(AddBoundaryInputsTest, TestEmptyFileSets) { 208 AddBoundaryInputs(icmp_, level_files_, &compaction_files_); 209 ASSERT_TRUE(compaction_files_.empty()); 210 ASSERT_TRUE(level_files_.empty()); 211 } 212 213 TEST(AddBoundaryInputsTest, TestEmptyLevelFiles) { 214 FileMetaData* f1 = 215 CreateFileMetaData(1, InternalKey("100", 2, kTypeValue), 216 InternalKey(InternalKey("100", 1, kTypeValue))); 217 compaction_files_.push_back(f1); 218 219 AddBoundaryInputs(icmp_, level_files_, &compaction_files_); 220 ASSERT_EQ(1, compaction_files_.size()); 221 ASSERT_EQ(f1, compaction_files_[0]); 222 ASSERT_TRUE(level_files_.empty()); 223 } 224 225 TEST(AddBoundaryInputsTest, TestEmptyCompactionFiles) { 226 FileMetaData* f1 = 227 CreateFileMetaData(1, InternalKey("100", 2, kTypeValue), 228 InternalKey(InternalKey("100", 1, kTypeValue))); 229 level_files_.push_back(f1); 230 231 AddBoundaryInputs(icmp_, level_files_, &compaction_files_); 232 ASSERT_TRUE(compaction_files_.empty()); 233 ASSERT_EQ(1, level_files_.size()); 234 ASSERT_EQ(f1, level_files_[0]); 235 } 236 237 TEST(AddBoundaryInputsTest, TestNoBoundaryFiles) { 238 FileMetaData* f1 = 239 CreateFileMetaData(1, InternalKey("100", 2, kTypeValue), 240 InternalKey(InternalKey("100", 1, kTypeValue))); 241 FileMetaData* f2 = 242 CreateFileMetaData(1, InternalKey("200", 2, kTypeValue), 243 InternalKey(InternalKey("200", 1, kTypeValue))); 244 FileMetaData* f3 = 245 CreateFileMetaData(1, InternalKey("300", 2, kTypeValue), 246 InternalKey(InternalKey("300", 1, kTypeValue))); 247 248 level_files_.push_back(f3); 249 level_files_.push_back(f2); 250 level_files_.push_back(f1); 251 compaction_files_.push_back(f2); 252 compaction_files_.push_back(f3); 253 254 AddBoundaryInputs(icmp_, level_files_, &compaction_files_); 255 ASSERT_EQ(2, compaction_files_.size()); 256 } 257 258 TEST(AddBoundaryInputsTest, TestOneBoundaryFiles) { 259 FileMetaData* f1 = 260 CreateFileMetaData(1, InternalKey("100", 3, kTypeValue), 261 InternalKey(InternalKey("100", 2, kTypeValue))); 262 FileMetaData* f2 = 263 CreateFileMetaData(1, InternalKey("100", 1, kTypeValue), 264 InternalKey(InternalKey("200", 3, kTypeValue))); 265 FileMetaData* f3 = 266 CreateFileMetaData(1, InternalKey("300", 2, kTypeValue), 267 InternalKey(InternalKey("300", 1, kTypeValue))); 268 269 level_files_.push_back(f3); 270 level_files_.push_back(f2); 271 level_files_.push_back(f1); 272 compaction_files_.push_back(f1); 273 274 AddBoundaryInputs(icmp_, level_files_, &compaction_files_); 275 ASSERT_EQ(2, compaction_files_.size()); 276 ASSERT_EQ(f1, compaction_files_[0]); 277 ASSERT_EQ(f2, compaction_files_[1]); 278 } 279 280 TEST(AddBoundaryInputsTest, TestTwoBoundaryFiles) { 281 FileMetaData* f1 = 282 CreateFileMetaData(1, InternalKey("100", 6, kTypeValue), 283 InternalKey(InternalKey("100", 5, kTypeValue))); 284 FileMetaData* f2 = 285 CreateFileMetaData(1, InternalKey("100", 2, kTypeValue), 286 InternalKey(InternalKey("300", 1, kTypeValue))); 287 FileMetaData* f3 = 288 CreateFileMetaData(1, InternalKey("100", 4, kTypeValue), 289 InternalKey(InternalKey("100", 3, kTypeValue))); 290 291 level_files_.push_back(f2); 292 level_files_.push_back(f3); 293 level_files_.push_back(f1); 294 compaction_files_.push_back(f1); 295 296 AddBoundaryInputs(icmp_, level_files_, &compaction_files_); 297 ASSERT_EQ(3, compaction_files_.size()); 298 ASSERT_EQ(f1, compaction_files_[0]); 299 ASSERT_EQ(f3, compaction_files_[1]); 300 ASSERT_EQ(f2, compaction_files_[2]); 301 } 302 303 TEST(AddBoundaryInputsTest, TestDisjoinFilePointers) { 304 FileMetaData* f1 = 305 CreateFileMetaData(1, InternalKey("100", 6, kTypeValue), 306 InternalKey(InternalKey("100", 5, kTypeValue))); 307 FileMetaData* f2 = 308 CreateFileMetaData(1, InternalKey("100", 6, kTypeValue), 309 InternalKey(InternalKey("100", 5, kTypeValue))); 310 FileMetaData* f3 = 311 CreateFileMetaData(1, InternalKey("100", 2, kTypeValue), 312 InternalKey(InternalKey("300", 1, kTypeValue))); 313 FileMetaData* f4 = 314 CreateFileMetaData(1, InternalKey("100", 4, kTypeValue), 315 InternalKey(InternalKey("100", 3, kTypeValue))); 316 317 level_files_.push_back(f2); 318 level_files_.push_back(f3); 319 level_files_.push_back(f4); 320 321 compaction_files_.push_back(f1); 322 323 AddBoundaryInputs(icmp_, level_files_, &compaction_files_); 324 ASSERT_EQ(3, compaction_files_.size()); 325 ASSERT_EQ(f1, compaction_files_[0]); 326 ASSERT_EQ(f4, compaction_files_[1]); 327 ASSERT_EQ(f3, compaction_files_[2]); 328 } 329 330 } // namespace leveldb 331 332 int main(int argc, char** argv) { return leveldb::test::RunAllTests(); }