]>
git.proxmox.com Git - ceph.git/blob - ceph/src/rocksdb/db/file_indexer.cc
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).
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.
10 #include "db/file_indexer.h"
13 #include "db/version_edit.h"
14 #include "rocksdb/comparator.h"
18 FileIndexer::FileIndexer(const Comparator
* ucmp
)
19 : num_levels_(0), ucmp_(ucmp
), level_rb_(nullptr) {}
21 size_t FileIndexer::NumLevelIndex() const { return next_level_index_
.size(); }
23 size_t FileIndexer::LevelIndexSize(size_t level
) const {
24 if (level
>= next_level_index_
.size()) {
27 return next_level_index_
[level
].num_index
;
30 void FileIndexer::GetNextLevelIndex(const size_t level
, const size_t file_index
,
31 const int cmp_smallest
,
32 const int cmp_largest
, int32_t* left_bound
,
33 int32_t* right_bound
) const {
36 // Last level, no hint
37 if (level
== num_levels_
- 1) {
43 assert(level
< num_levels_
- 1);
44 assert(static_cast<int32_t>(file_index
) <= level_rb_
[level
]);
46 const IndexUnit
* index_units
= next_level_index_
[level
].index_units
;
47 const auto& index
= index_units
[file_index
];
49 if (cmp_smallest
< 0) {
50 *left_bound
= (level
> 0 && file_index
> 0)
51 ? index_units
[file_index
- 1].largest_lb
53 *right_bound
= index
.smallest_rb
;
54 } else if (cmp_smallest
== 0) {
55 *left_bound
= index
.smallest_lb
;
56 *right_bound
= index
.smallest_rb
;
57 } else if (cmp_smallest
> 0 && cmp_largest
< 0) {
58 *left_bound
= index
.smallest_lb
;
59 *right_bound
= index
.largest_rb
;
60 } else if (cmp_largest
== 0) {
61 *left_bound
= index
.largest_lb
;
62 *right_bound
= index
.largest_rb
;
63 } else if (cmp_largest
> 0) {
64 *left_bound
= index
.largest_lb
;
65 *right_bound
= level_rb_
[level
+ 1];
70 assert(*left_bound
>= 0);
71 assert(*left_bound
<= *right_bound
+ 1);
72 assert(*right_bound
<= level_rb_
[level
+ 1]);
75 void FileIndexer::UpdateIndex(Arena
* arena
, const size_t num_levels
,
76 std::vector
<FileMetaData
*>* const files
) {
77 if (files
== nullptr) {
80 if (num_levels
== 0) { // uint_32 0-1 would cause bad behavior
81 num_levels_
= num_levels
;
84 assert(level_rb_
== nullptr); // level_rb_ should be init here
86 num_levels_
= num_levels
;
87 next_level_index_
.resize(num_levels
);
89 char* mem
= arena
->AllocateAligned(num_levels_
* sizeof(int32_t));
90 level_rb_
= new (mem
) int32_t[num_levels_
];
91 for (size_t i
= 0; i
< num_levels_
; i
++) {
96 for (size_t level
= 1; level
< num_levels_
- 1; ++level
) {
97 const auto& upper_files
= files
[level
];
98 const int32_t upper_size
= static_cast<int32_t>(upper_files
.size());
99 const auto& lower_files
= files
[level
+ 1];
100 level_rb_
[level
] = static_cast<int32_t>(upper_files
.size()) - 1;
101 if (upper_size
== 0) {
104 IndexLevel
& index_level
= next_level_index_
[level
];
105 index_level
.num_index
= upper_size
;
106 mem
= arena
->AllocateAligned(upper_size
* sizeof(IndexUnit
));
107 index_level
.index_units
= new (mem
) IndexUnit
[upper_size
];
110 upper_files
, lower_files
, &index_level
,
111 [this](const FileMetaData
* a
, const FileMetaData
* b
)->int {
112 return ucmp_
->Compare(a
->smallest
.user_key(), b
->largest
.user_key());
114 [](IndexUnit
* index
, int32_t f_idx
) { index
->smallest_lb
= f_idx
; });
116 upper_files
, lower_files
, &index_level
,
117 [this](const FileMetaData
* a
, const FileMetaData
* b
)->int {
118 return ucmp_
->Compare(a
->largest
.user_key(), b
->largest
.user_key());
120 [](IndexUnit
* index
, int32_t f_idx
) { index
->largest_lb
= f_idx
; });
122 upper_files
, lower_files
, &index_level
,
123 [this](const FileMetaData
* a
, const FileMetaData
* b
)->int {
124 return ucmp_
->Compare(a
->smallest
.user_key(), b
->smallest
.user_key());
126 [](IndexUnit
* index
, int32_t f_idx
) { index
->smallest_rb
= f_idx
; });
128 upper_files
, lower_files
, &index_level
,
129 [this](const FileMetaData
* a
, const FileMetaData
* b
)->int {
130 return ucmp_
->Compare(a
->largest
.user_key(), b
->smallest
.user_key());
132 [](IndexUnit
* index
, int32_t f_idx
) { index
->largest_rb
= f_idx
; });
135 level_rb_
[num_levels_
- 1] =
136 static_cast<int32_t>(files
[num_levels_
- 1].size()) - 1;
139 void FileIndexer::CalculateLB(
140 const std::vector
<FileMetaData
*>& upper_files
,
141 const std::vector
<FileMetaData
*>& lower_files
, IndexLevel
* index_level
,
142 std::function
<int(const FileMetaData
*, const FileMetaData
*)> cmp_op
,
143 std::function
<void(IndexUnit
*, int32_t)> set_index
) {
144 const int32_t upper_size
= static_cast<int32_t>(upper_files
.size());
145 const int32_t lower_size
= static_cast<int32_t>(lower_files
.size());
146 int32_t upper_idx
= 0;
147 int32_t lower_idx
= 0;
149 IndexUnit
* index
= index_level
->index_units
;
150 while (upper_idx
< upper_size
&& lower_idx
< lower_size
) {
151 int cmp
= cmp_op(upper_files
[upper_idx
], lower_files
[lower_idx
]);
154 set_index(&index
[upper_idx
], lower_idx
);
157 } else if (cmp
> 0) {
158 // Lower level's file (largest) is smaller, a key won't hit in that
159 // file. Move to next lower file
162 // Lower level's file becomes larger, update the index, and
163 // move to the next upper file
164 set_index(&index
[upper_idx
], lower_idx
);
169 while (upper_idx
< upper_size
) {
170 // Lower files are exhausted, that means the remaining upper files are
171 // greater than any lower files. Set the index to be the lower level size.
172 set_index(&index
[upper_idx
], lower_size
);
177 void FileIndexer::CalculateRB(
178 const std::vector
<FileMetaData
*>& upper_files
,
179 const std::vector
<FileMetaData
*>& lower_files
, IndexLevel
* index_level
,
180 std::function
<int(const FileMetaData
*, const FileMetaData
*)> cmp_op
,
181 std::function
<void(IndexUnit
*, int32_t)> set_index
) {
182 const int32_t upper_size
= static_cast<int32_t>(upper_files
.size());
183 const int32_t lower_size
= static_cast<int32_t>(lower_files
.size());
184 int32_t upper_idx
= upper_size
- 1;
185 int32_t lower_idx
= lower_size
- 1;
187 IndexUnit
* index
= index_level
->index_units
;
188 while (upper_idx
>= 0 && lower_idx
>= 0) {
189 int cmp
= cmp_op(upper_files
[upper_idx
], lower_files
[lower_idx
]);
192 set_index(&index
[upper_idx
], lower_idx
);
195 } else if (cmp
< 0) {
196 // Lower level's file (smallest) is larger, a key won't hit in that
197 // file. Move to next lower file.
200 // Lower level's file becomes smaller, update the index, and move to
201 // the next the upper file
202 set_index(&index
[upper_idx
], lower_idx
);
206 while (upper_idx
>= 0) {
207 // Lower files are exhausted, that means the remaining upper files are
208 // smaller than any lower files. Set it to -1.
209 set_index(&index
[upper_idx
], -1);
214 } // namespace rocksdb