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