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