version_set_test.cc raw
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(); }
333