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:
FindFileTest()14   FindFileTest() : disjoint_sorted_files_(true) {}
15 
~FindFileTest()16   ~FindFileTest() {
17     for (int i = 0; i < files_.size(); i++) {
18       delete files_[i];
19     }
20   }
21 
Add(const char * smallest,const char * largest,SequenceNumber smallest_seq=100,SequenceNumber largest_seq=100)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 
Find(const char * key)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 
Overlaps(const char * smallest,const char * largest)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 
TEST(FindFileTest,Empty)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 
TEST(FindFileTest,Single)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 
TEST(FindFileTest,Multiple)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 
TEST(FindFileTest,MultipleNullBoundaries)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 
TEST(FindFileTest,OverlapSequenceChecks)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 
TEST(FindFileTest,OverlappingFiles)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 
AddBoundaryInputsTest()187   AddBoundaryInputsTest() : icmp_(BytewiseComparator()) {}
188 
~AddBoundaryInputsTest()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 
CreateFileMetaData(uint64_t number,InternalKey smallest,InternalKey largest)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 
TEST(AddBoundaryInputsTest,TestEmptyFileSets)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 
TEST(AddBoundaryInputsTest,TestEmptyLevelFiles)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 
TEST(AddBoundaryInputsTest,TestEmptyCompactionFiles)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 
TEST(AddBoundaryInputsTest,TestNoBoundaryFiles)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 
TEST(AddBoundaryInputsTest,TestOneBoundaryFiles)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 
TEST(AddBoundaryInputsTest,TestTwoBoundaryFiles)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 
TEST(AddBoundaryInputsTest,TestDisjoinFilePointers)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 
main(int argc,char ** argv)332 int main(int argc, char** argv) { return leveldb::test::RunAllTests(); }
333