]>
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"
15 #include "db/version_edit.h"
16 #include "rocksdb/comparator.h"
18 namespace ROCKSDB_NAMESPACE
{
20 FileIndexer::FileIndexer(const Comparator
* ucmp
)
21 : num_levels_(0), ucmp_(ucmp
), level_rb_(nullptr) {}
23 size_t FileIndexer::NumLevelIndex() const { return next_level_index_
.size(); }
25 size_t FileIndexer::LevelIndexSize(size_t level
) const {
26 if (level
>= next_level_index_
.size()) {
29 return next_level_index_
[level
].num_index
;
32 void FileIndexer::GetNextLevelIndex(const size_t level
, const size_t file_index
,
33 const int cmp_smallest
,
34 const int cmp_largest
, int32_t* left_bound
,
35 int32_t* right_bound
) const {
38 // Last level, no hint
39 if (level
== num_levels_
- 1) {
45 assert(level
< num_levels_
- 1);
46 assert(static_cast<int32_t>(file_index
) <= level_rb_
[level
]);
48 const IndexUnit
* index_units
= next_level_index_
[level
].index_units
;
49 const auto& index
= index_units
[file_index
];
51 if (cmp_smallest
< 0) {
52 *left_bound
= (level
> 0 && file_index
> 0)
53 ? index_units
[file_index
- 1].largest_lb
55 *right_bound
= index
.smallest_rb
;
56 } else if (cmp_smallest
== 0) {
57 *left_bound
= index
.smallest_lb
;
58 *right_bound
= index
.smallest_rb
;
59 } else if (cmp_smallest
> 0 && cmp_largest
< 0) {
60 *left_bound
= index
.smallest_lb
;
61 *right_bound
= index
.largest_rb
;
62 } else if (cmp_largest
== 0) {
63 *left_bound
= index
.largest_lb
;
64 *right_bound
= index
.largest_rb
;
65 } else if (cmp_largest
> 0) {
66 *left_bound
= index
.largest_lb
;
67 *right_bound
= level_rb_
[level
+ 1];
72 assert(*left_bound
>= 0);
73 assert(*left_bound
<= *right_bound
+ 1);
74 assert(*right_bound
<= level_rb_
[level
+ 1]);
77 void FileIndexer::UpdateIndex(Arena
* arena
, const size_t num_levels
,
78 std::vector
<FileMetaData
*>* const files
) {
79 if (files
== nullptr) {
82 if (num_levels
== 0) { // uint_32 0-1 would cause bad behavior
83 num_levels_
= num_levels
;
86 assert(level_rb_
== nullptr); // level_rb_ should be init here
88 num_levels_
= num_levels
;
89 next_level_index_
.resize(num_levels
);
91 char* mem
= arena
->AllocateAligned(num_levels_
* sizeof(int32_t));
92 level_rb_
= new (mem
) int32_t[num_levels_
];
93 for (size_t i
= 0; i
< num_levels_
; i
++) {
98 for (size_t level
= 1; level
< num_levels_
- 1; ++level
) {
99 const auto& upper_files
= files
[level
];
100 const int32_t upper_size
= static_cast<int32_t>(upper_files
.size());
101 const auto& lower_files
= files
[level
+ 1];
102 level_rb_
[level
] = static_cast<int32_t>(upper_files
.size()) - 1;
103 if (upper_size
== 0) {
106 IndexLevel
& index_level
= next_level_index_
[level
];
107 index_level
.num_index
= upper_size
;
108 mem
= arena
->AllocateAligned(upper_size
* sizeof(IndexUnit
));
109 index_level
.index_units
= new (mem
) IndexUnit
[upper_size
];
112 upper_files
, lower_files
, &index_level
,
113 [this](const FileMetaData
* a
, const FileMetaData
* b
) -> int {
114 return ucmp_
->CompareWithoutTimestamp(a
->smallest
.user_key(),
115 b
->largest
.user_key());
117 [](IndexUnit
* index
, int32_t f_idx
) { index
->smallest_lb
= f_idx
; });
119 upper_files
, lower_files
, &index_level
,
120 [this](const FileMetaData
* a
, const FileMetaData
* b
) -> int {
121 return ucmp_
->CompareWithoutTimestamp(a
->largest
.user_key(),
122 b
->largest
.user_key());
124 [](IndexUnit
* index
, int32_t f_idx
) { index
->largest_lb
= f_idx
; });
126 upper_files
, lower_files
, &index_level
,
127 [this](const FileMetaData
* a
, const FileMetaData
* b
) -> int {
128 return ucmp_
->CompareWithoutTimestamp(a
->smallest
.user_key(),
129 b
->smallest
.user_key());
131 [](IndexUnit
* index
, int32_t f_idx
) { index
->smallest_rb
= f_idx
; });
133 upper_files
, lower_files
, &index_level
,
134 [this](const FileMetaData
* a
, const FileMetaData
* b
) -> int {
135 return ucmp_
->CompareWithoutTimestamp(a
->largest
.user_key(),
136 b
->smallest
.user_key());
138 [](IndexUnit
* index
, int32_t f_idx
) { index
->largest_rb
= f_idx
; });
141 level_rb_
[num_levels_
- 1] =
142 static_cast<int32_t>(files
[num_levels_
- 1].size()) - 1;
145 void FileIndexer::CalculateLB(
146 const std::vector
<FileMetaData
*>& upper_files
,
147 const std::vector
<FileMetaData
*>& lower_files
, IndexLevel
* index_level
,
148 std::function
<int(const FileMetaData
*, const FileMetaData
*)> cmp_op
,
149 std::function
<void(IndexUnit
*, int32_t)> set_index
) {
150 const int32_t upper_size
= static_cast<int32_t>(upper_files
.size());
151 const int32_t lower_size
= static_cast<int32_t>(lower_files
.size());
152 int32_t upper_idx
= 0;
153 int32_t lower_idx
= 0;
155 IndexUnit
* index
= index_level
->index_units
;
156 while (upper_idx
< upper_size
&& lower_idx
< lower_size
) {
157 int cmp
= cmp_op(upper_files
[upper_idx
], lower_files
[lower_idx
]);
160 set_index(&index
[upper_idx
], lower_idx
);
162 } else if (cmp
> 0) {
163 // Lower level's file (largest) is smaller, a key won't hit in that
164 // file. Move to next lower file
167 // Lower level's file becomes larger, update the index, and
168 // move to the next upper file
169 set_index(&index
[upper_idx
], lower_idx
);
174 while (upper_idx
< upper_size
) {
175 // Lower files are exhausted, that means the remaining upper files are
176 // greater than any lower files. Set the index to be the lower level size.
177 set_index(&index
[upper_idx
], lower_size
);
182 void FileIndexer::CalculateRB(
183 const std::vector
<FileMetaData
*>& upper_files
,
184 const std::vector
<FileMetaData
*>& lower_files
, IndexLevel
* index_level
,
185 std::function
<int(const FileMetaData
*, const FileMetaData
*)> cmp_op
,
186 std::function
<void(IndexUnit
*, int32_t)> set_index
) {
187 const int32_t upper_size
= static_cast<int32_t>(upper_files
.size());
188 const int32_t lower_size
= static_cast<int32_t>(lower_files
.size());
189 int32_t upper_idx
= upper_size
- 1;
190 int32_t lower_idx
= lower_size
- 1;
192 IndexUnit
* index
= index_level
->index_units
;
193 while (upper_idx
>= 0 && lower_idx
>= 0) {
194 int cmp
= cmp_op(upper_files
[upper_idx
], lower_files
[lower_idx
]);
197 set_index(&index
[upper_idx
], lower_idx
);
199 } else if (cmp
< 0) {
200 // Lower level's file (smallest) is larger, a key won't hit in that
201 // file. Move to next lower file.
204 // Lower level's file becomes smaller, update the index, and move to
205 // the next the upper file
206 set_index(&index
[upper_idx
], lower_idx
);
210 while (upper_idx
>= 0) {
211 // Lower files are exhausted, that means the remaining upper files are
212 // smaller than any lower files. Set it to -1.
213 set_index(&index
[upper_idx
], -1);
218 } // namespace ROCKSDB_NAMESPACE