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: |
15 | FindFileTest() : disjoint_sorted_files_(true) {} |
16 | |
17 | ~FindFileTest() { |
18 | for (int i = 0; i < files_.size(); i++) { |
19 | delete files_[i]; |
20 | } |
21 | } |
22 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
188 | AddBoundaryInputsTest() : icmp_(BytewiseComparator()) {} |
189 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |