]>
Commit | Line | Data |
---|---|---|
7c673cae | 1 | // Copyright (c) 2011-present, Facebook, Inc. All rights reserved. |
11fdf7f2 TL |
2 | // This source code is licensed under both the GPLv2 (found in the |
3 | // COPYING file in the root directory) and Apache 2.0 License | |
4 | // (found in the LICENSE.Apache file in the root directory). | |
7c673cae FG |
5 | // |
6 | // Copyright (c) 2011 The LevelDB Authors. All rights reserved. | |
7 | // Use of this source code is governed by a BSD-style license that can be | |
8 | // found in the LICENSE file. See the AUTHORS file for names of contributors. | |
9 | ||
7c673cae | 10 | #include "db/file_indexer.h" |
1e59de90 | 11 | |
f67539c2 | 12 | #include <string> |
1e59de90 | 13 | |
7c673cae FG |
14 | #include "db/dbformat.h" |
15 | #include "db/version_edit.h" | |
16 | #include "port/stack_trace.h" | |
17 | #include "rocksdb/comparator.h" | |
f67539c2 TL |
18 | #include "test_util/testharness.h" |
19 | #include "test_util/testutil.h" | |
7c673cae | 20 | |
f67539c2 | 21 | namespace ROCKSDB_NAMESPACE { |
7c673cae FG |
22 | |
23 | class IntComparator : public Comparator { | |
24 | public: | |
25 | int Compare(const Slice& a, const Slice& b) const override { | |
26 | assert(a.size() == 8); | |
27 | assert(b.size() == 8); | |
28 | int64_t diff = *reinterpret_cast<const int64_t*>(a.data()) - | |
29 | *reinterpret_cast<const int64_t*>(b.data()); | |
30 | if (diff < 0) { | |
31 | return -1; | |
32 | } else if (diff == 0) { | |
33 | return 0; | |
34 | } else { | |
35 | return 1; | |
36 | } | |
37 | } | |
38 | ||
39 | const char* Name() const override { return "IntComparator"; } | |
40 | ||
11fdf7f2 TL |
41 | void FindShortestSeparator(std::string* /*start*/, |
42 | const Slice& /*limit*/) const override {} | |
7c673cae | 43 | |
11fdf7f2 | 44 | void FindShortSuccessor(std::string* /*key*/) const override {} |
7c673cae FG |
45 | }; |
46 | ||
47 | class FileIndexerTest : public testing::Test { | |
48 | public: | |
49 | FileIndexerTest() | |
50 | : kNumLevels(4), files(new std::vector<FileMetaData*>[kNumLevels]) {} | |
51 | ||
494da23a | 52 | ~FileIndexerTest() override { |
7c673cae FG |
53 | ClearFiles(); |
54 | delete[] files; | |
55 | } | |
56 | ||
57 | void AddFile(int level, int64_t smallest, int64_t largest) { | |
58 | auto* f = new FileMetaData(); | |
59 | f->smallest = IntKey(smallest); | |
60 | f->largest = IntKey(largest); | |
61 | files[level].push_back(f); | |
62 | } | |
63 | ||
64 | InternalKey IntKey(int64_t v) { | |
65 | return InternalKey(Slice(reinterpret_cast<char*>(&v), 8), 0, kTypeValue); | |
66 | } | |
67 | ||
68 | void ClearFiles() { | |
69 | for (uint32_t i = 0; i < kNumLevels; ++i) { | |
70 | for (auto* f : files[i]) { | |
71 | delete f; | |
72 | } | |
73 | files[i].clear(); | |
74 | } | |
75 | } | |
76 | ||
77 | void GetNextLevelIndex(const uint32_t level, const uint32_t file_index, | |
1e59de90 TL |
78 | const int cmp_smallest, const int cmp_largest, |
79 | int32_t* left_index, int32_t* right_index) { | |
7c673cae FG |
80 | *left_index = 100; |
81 | *right_index = 100; | |
82 | indexer->GetNextLevelIndex(level, file_index, cmp_smallest, cmp_largest, | |
83 | left_index, right_index); | |
84 | } | |
85 | ||
86 | int32_t left = 100; | |
87 | int32_t right = 100; | |
88 | const uint32_t kNumLevels; | |
89 | IntComparator ucmp; | |
90 | FileIndexer* indexer; | |
91 | ||
92 | std::vector<FileMetaData*>* files; | |
93 | }; | |
94 | ||
95 | // Case 0: Empty | |
96 | TEST_F(FileIndexerTest, Empty) { | |
97 | Arena arena; | |
98 | indexer = new FileIndexer(&ucmp); | |
99 | indexer->UpdateIndex(&arena, 0, files); | |
100 | delete indexer; | |
101 | } | |
102 | ||
103 | // Case 1: no overlap, files are on the left of next level files | |
104 | TEST_F(FileIndexerTest, no_overlap_left) { | |
105 | Arena arena; | |
106 | indexer = new FileIndexer(&ucmp); | |
107 | // level 1 | |
108 | AddFile(1, 100, 200); | |
109 | AddFile(1, 300, 400); | |
110 | AddFile(1, 500, 600); | |
111 | // level 2 | |
112 | AddFile(2, 1500, 1600); | |
113 | AddFile(2, 1601, 1699); | |
114 | AddFile(2, 1700, 1800); | |
115 | // level 3 | |
116 | AddFile(3, 2500, 2600); | |
117 | AddFile(3, 2601, 2699); | |
118 | AddFile(3, 2700, 2800); | |
119 | indexer->UpdateIndex(&arena, kNumLevels, files); | |
120 | for (uint32_t level = 1; level < 3; ++level) { | |
121 | for (uint32_t f = 0; f < 3; ++f) { | |
122 | GetNextLevelIndex(level, f, -1, -1, &left, &right); | |
123 | ASSERT_EQ(0, left); | |
124 | ASSERT_EQ(-1, right); | |
125 | GetNextLevelIndex(level, f, 0, -1, &left, &right); | |
126 | ASSERT_EQ(0, left); | |
127 | ASSERT_EQ(-1, right); | |
128 | GetNextLevelIndex(level, f, 1, -1, &left, &right); | |
129 | ASSERT_EQ(0, left); | |
130 | ASSERT_EQ(-1, right); | |
131 | GetNextLevelIndex(level, f, 1, 0, &left, &right); | |
132 | ASSERT_EQ(0, left); | |
133 | ASSERT_EQ(-1, right); | |
134 | GetNextLevelIndex(level, f, 1, 1, &left, &right); | |
135 | ASSERT_EQ(0, left); | |
136 | ASSERT_EQ(2, right); | |
137 | } | |
138 | } | |
139 | delete indexer; | |
140 | ClearFiles(); | |
141 | } | |
142 | ||
143 | // Case 2: no overlap, files are on the right of next level files | |
144 | TEST_F(FileIndexerTest, no_overlap_right) { | |
145 | Arena arena; | |
146 | indexer = new FileIndexer(&ucmp); | |
147 | // level 1 | |
148 | AddFile(1, 2100, 2200); | |
149 | AddFile(1, 2300, 2400); | |
150 | AddFile(1, 2500, 2600); | |
151 | // level 2 | |
152 | AddFile(2, 1500, 1600); | |
153 | AddFile(2, 1501, 1699); | |
154 | AddFile(2, 1700, 1800); | |
155 | // level 3 | |
156 | AddFile(3, 500, 600); | |
157 | AddFile(3, 501, 699); | |
158 | AddFile(3, 700, 800); | |
159 | indexer->UpdateIndex(&arena, kNumLevels, files); | |
160 | for (uint32_t level = 1; level < 3; ++level) { | |
161 | for (uint32_t f = 0; f < 3; ++f) { | |
162 | GetNextLevelIndex(level, f, -1, -1, &left, &right); | |
163 | ASSERT_EQ(f == 0 ? 0 : 3, left); | |
164 | ASSERT_EQ(2, right); | |
165 | GetNextLevelIndex(level, f, 0, -1, &left, &right); | |
166 | ASSERT_EQ(3, left); | |
167 | ASSERT_EQ(2, right); | |
168 | GetNextLevelIndex(level, f, 1, -1, &left, &right); | |
169 | ASSERT_EQ(3, left); | |
170 | ASSERT_EQ(2, right); | |
171 | GetNextLevelIndex(level, f, 1, -1, &left, &right); | |
172 | ASSERT_EQ(3, left); | |
173 | ASSERT_EQ(2, right); | |
174 | GetNextLevelIndex(level, f, 1, 0, &left, &right); | |
175 | ASSERT_EQ(3, left); | |
176 | ASSERT_EQ(2, right); | |
177 | GetNextLevelIndex(level, f, 1, 1, &left, &right); | |
178 | ASSERT_EQ(3, left); | |
179 | ASSERT_EQ(2, right); | |
180 | } | |
181 | } | |
182 | delete indexer; | |
183 | } | |
184 | ||
185 | // Case 3: empty L2 | |
186 | TEST_F(FileIndexerTest, empty_L2) { | |
187 | Arena arena; | |
188 | indexer = new FileIndexer(&ucmp); | |
189 | for (uint32_t i = 1; i < kNumLevels; ++i) { | |
190 | ASSERT_EQ(0U, indexer->LevelIndexSize(i)); | |
191 | } | |
192 | // level 1 | |
193 | AddFile(1, 2100, 2200); | |
194 | AddFile(1, 2300, 2400); | |
195 | AddFile(1, 2500, 2600); | |
196 | // level 3 | |
197 | AddFile(3, 500, 600); | |
198 | AddFile(3, 501, 699); | |
199 | AddFile(3, 700, 800); | |
200 | indexer->UpdateIndex(&arena, kNumLevels, files); | |
201 | for (uint32_t f = 0; f < 3; ++f) { | |
202 | GetNextLevelIndex(1, f, -1, -1, &left, &right); | |
203 | ASSERT_EQ(0, left); | |
204 | ASSERT_EQ(-1, right); | |
205 | GetNextLevelIndex(1, f, 0, -1, &left, &right); | |
206 | ASSERT_EQ(0, left); | |
207 | ASSERT_EQ(-1, right); | |
208 | GetNextLevelIndex(1, f, 1, -1, &left, &right); | |
209 | ASSERT_EQ(0, left); | |
210 | ASSERT_EQ(-1, right); | |
211 | GetNextLevelIndex(1, f, 1, -1, &left, &right); | |
212 | ASSERT_EQ(0, left); | |
213 | ASSERT_EQ(-1, right); | |
214 | GetNextLevelIndex(1, f, 1, 0, &left, &right); | |
215 | ASSERT_EQ(0, left); | |
216 | ASSERT_EQ(-1, right); | |
217 | GetNextLevelIndex(1, f, 1, 1, &left, &right); | |
218 | ASSERT_EQ(0, left); | |
219 | ASSERT_EQ(-1, right); | |
220 | } | |
221 | delete indexer; | |
222 | ClearFiles(); | |
223 | } | |
224 | ||
225 | // Case 4: mixed | |
226 | TEST_F(FileIndexerTest, mixed) { | |
227 | Arena arena; | |
228 | indexer = new FileIndexer(&ucmp); | |
229 | // level 1 | |
230 | AddFile(1, 100, 200); | |
231 | AddFile(1, 250, 400); | |
232 | AddFile(1, 450, 500); | |
233 | // level 2 | |
234 | AddFile(2, 100, 150); // 0 | |
235 | AddFile(2, 200, 250); // 1 | |
236 | AddFile(2, 251, 300); // 2 | |
237 | AddFile(2, 301, 350); // 3 | |
238 | AddFile(2, 500, 600); // 4 | |
239 | // level 3 | |
240 | AddFile(3, 0, 50); | |
241 | AddFile(3, 100, 200); | |
242 | AddFile(3, 201, 250); | |
243 | indexer->UpdateIndex(&arena, kNumLevels, files); | |
244 | // level 1, 0 | |
245 | GetNextLevelIndex(1, 0, -1, -1, &left, &right); | |
246 | ASSERT_EQ(0, left); | |
247 | ASSERT_EQ(0, right); | |
248 | GetNextLevelIndex(1, 0, 0, -1, &left, &right); | |
249 | ASSERT_EQ(0, left); | |
250 | ASSERT_EQ(0, right); | |
251 | GetNextLevelIndex(1, 0, 1, -1, &left, &right); | |
252 | ASSERT_EQ(0, left); | |
253 | ASSERT_EQ(1, right); | |
254 | GetNextLevelIndex(1, 0, 1, 0, &left, &right); | |
255 | ASSERT_EQ(1, left); | |
256 | ASSERT_EQ(1, right); | |
257 | GetNextLevelIndex(1, 0, 1, 1, &left, &right); | |
258 | ASSERT_EQ(1, left); | |
259 | ASSERT_EQ(4, right); | |
260 | // level 1, 1 | |
261 | GetNextLevelIndex(1, 1, -1, -1, &left, &right); | |
262 | ASSERT_EQ(1, left); | |
263 | ASSERT_EQ(1, right); | |
264 | GetNextLevelIndex(1, 1, 0, -1, &left, &right); | |
265 | ASSERT_EQ(1, left); | |
266 | ASSERT_EQ(1, right); | |
267 | GetNextLevelIndex(1, 1, 1, -1, &left, &right); | |
268 | ASSERT_EQ(1, left); | |
269 | ASSERT_EQ(3, right); | |
270 | GetNextLevelIndex(1, 1, 1, 0, &left, &right); | |
271 | ASSERT_EQ(4, left); | |
272 | ASSERT_EQ(3, right); | |
273 | GetNextLevelIndex(1, 1, 1, 1, &left, &right); | |
274 | ASSERT_EQ(4, left); | |
275 | ASSERT_EQ(4, right); | |
276 | // level 1, 2 | |
277 | GetNextLevelIndex(1, 2, -1, -1, &left, &right); | |
278 | ASSERT_EQ(4, left); | |
279 | ASSERT_EQ(3, right); | |
280 | GetNextLevelIndex(1, 2, 0, -1, &left, &right); | |
281 | ASSERT_EQ(4, left); | |
282 | ASSERT_EQ(3, right); | |
283 | GetNextLevelIndex(1, 2, 1, -1, &left, &right); | |
284 | ASSERT_EQ(4, left); | |
285 | ASSERT_EQ(4, right); | |
286 | GetNextLevelIndex(1, 2, 1, 0, &left, &right); | |
287 | ASSERT_EQ(4, left); | |
288 | ASSERT_EQ(4, right); | |
289 | GetNextLevelIndex(1, 2, 1, 1, &left, &right); | |
290 | ASSERT_EQ(4, left); | |
291 | ASSERT_EQ(4, right); | |
292 | // level 2, 0 | |
293 | GetNextLevelIndex(2, 0, -1, -1, &left, &right); | |
294 | ASSERT_EQ(0, left); | |
295 | ASSERT_EQ(1, right); | |
296 | GetNextLevelIndex(2, 0, 0, -1, &left, &right); | |
297 | ASSERT_EQ(1, left); | |
298 | ASSERT_EQ(1, right); | |
299 | GetNextLevelIndex(2, 0, 1, -1, &left, &right); | |
300 | ASSERT_EQ(1, left); | |
301 | ASSERT_EQ(1, right); | |
302 | GetNextLevelIndex(2, 0, 1, 0, &left, &right); | |
303 | ASSERT_EQ(1, left); | |
304 | ASSERT_EQ(1, right); | |
305 | GetNextLevelIndex(2, 0, 1, 1, &left, &right); | |
306 | ASSERT_EQ(1, left); | |
307 | ASSERT_EQ(2, right); | |
308 | // level 2, 1 | |
309 | GetNextLevelIndex(2, 1, -1, -1, &left, &right); | |
310 | ASSERT_EQ(1, left); | |
311 | ASSERT_EQ(1, right); | |
312 | GetNextLevelIndex(2, 1, 0, -1, &left, &right); | |
313 | ASSERT_EQ(1, left); | |
314 | ASSERT_EQ(1, right); | |
315 | GetNextLevelIndex(2, 1, 1, -1, &left, &right); | |
316 | ASSERT_EQ(1, left); | |
317 | ASSERT_EQ(2, right); | |
318 | GetNextLevelIndex(2, 1, 1, 0, &left, &right); | |
319 | ASSERT_EQ(2, left); | |
320 | ASSERT_EQ(2, right); | |
321 | GetNextLevelIndex(2, 1, 1, 1, &left, &right); | |
322 | ASSERT_EQ(2, left); | |
323 | ASSERT_EQ(2, right); | |
324 | // level 2, [2 - 4], no overlap | |
325 | for (uint32_t f = 2; f <= 4; ++f) { | |
326 | GetNextLevelIndex(2, f, -1, -1, &left, &right); | |
327 | ASSERT_EQ(f == 2 ? 2 : 3, left); | |
328 | ASSERT_EQ(2, right); | |
329 | GetNextLevelIndex(2, f, 0, -1, &left, &right); | |
330 | ASSERT_EQ(3, left); | |
331 | ASSERT_EQ(2, right); | |
332 | GetNextLevelIndex(2, f, 1, -1, &left, &right); | |
333 | ASSERT_EQ(3, left); | |
334 | ASSERT_EQ(2, right); | |
335 | GetNextLevelIndex(2, f, 1, 0, &left, &right); | |
336 | ASSERT_EQ(3, left); | |
337 | ASSERT_EQ(2, right); | |
338 | GetNextLevelIndex(2, f, 1, 1, &left, &right); | |
339 | ASSERT_EQ(3, left); | |
340 | ASSERT_EQ(2, right); | |
341 | } | |
342 | delete indexer; | |
343 | ClearFiles(); | |
344 | } | |
345 | ||
f67539c2 | 346 | } // namespace ROCKSDB_NAMESPACE |
7c673cae FG |
347 | |
348 | int main(int argc, char** argv) { | |
f67539c2 | 349 | ROCKSDB_NAMESPACE::port::InstallStackTraceHandler(); |
7c673cae FG |
350 | ::testing::InitGoogleTest(&argc, argv); |
351 | return RUN_ALL_TESTS(); | |
352 | } |