1 //  Copyright (c) 2011-present, Facebook, Inc.  All rights reserved.
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).
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 "db/file_indexer.h"
11 #include <string>
12 #include "db/dbformat.h"
13 #include "db/version_edit.h"
14 #include "port/stack_trace.h"
15 #include "rocksdb/comparator.h"
16 #include "test_util/testharness.h"
17 #include "test_util/testutil.h"
18 
19 namespace ROCKSDB_NAMESPACE {
20 
21 class IntComparator : public Comparator {
22  public:
Compare(const Slice & a,const Slice & b) const23   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 
Name() const37   const char* Name() const override { return "IntComparator"; }
38 
FindShortestSeparator(std::string *,const Slice &) const39   void FindShortestSeparator(std::string* /*start*/,
40                              const Slice& /*limit*/) const override {}
41 
FindShortSuccessor(std::string *) const42   void FindShortSuccessor(std::string* /*key*/) const override {}
43 };
44 
45 class FileIndexerTest : public testing::Test {
46  public:
FileIndexerTest()47   FileIndexerTest()
48       : kNumLevels(4), files(new std::vector<FileMetaData*>[kNumLevels]) {}
49 
~FileIndexerTest()50   ~FileIndexerTest() override {
51     ClearFiles();
52     delete[] files;
53   }
54 
AddFile(int level,int64_t smallest,int64_t largest)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 
IntKey(int64_t v)62   InternalKey IntKey(int64_t v) {
63     return InternalKey(Slice(reinterpret_cast<char*>(&v), 8), 0, kTypeValue);
64   }
65 
ClearFiles()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 
GetNextLevelIndex(const uint32_t level,const uint32_t file_index,const int cmp_smallest,const int cmp_largest,int32_t * left_index,int32_t * right_index)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
TEST_F(FileIndexerTest,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
TEST_F(FileIndexerTest,no_overlap_left)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
TEST_F(FileIndexerTest,no_overlap_right)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
TEST_F(FileIndexerTest,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
TEST_F(FileIndexerTest,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_NAMESPACE
345 
main(int argc,char ** argv)346 int main(int argc, char** argv) {
347   ROCKSDB_NAMESPACE::port::InstallStackTraceHandler();
348   ::testing::InitGoogleTest(&argc, argv);
349   return RUN_ALL_TESTS();
350 }
351