]>
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 "db/file_indexer.h" | |
11 | #include <algorithm> | |
12 | #include <functional> | |
13 | #include "db/version_edit.h" | |
14 | #include "rocksdb/comparator.h" | |
15 | ||
f67539c2 | 16 | namespace ROCKSDB_NAMESPACE { |
7c673cae FG |
17 | |
18 | FileIndexer::FileIndexer(const Comparator* ucmp) | |
19 | : num_levels_(0), ucmp_(ucmp), level_rb_(nullptr) {} | |
20 | ||
21 | size_t FileIndexer::NumLevelIndex() const { return next_level_index_.size(); } | |
22 | ||
23 | size_t FileIndexer::LevelIndexSize(size_t level) const { | |
24 | if (level >= next_level_index_.size()) { | |
25 | return 0; | |
26 | } | |
27 | return next_level_index_[level].num_index; | |
28 | } | |
29 | ||
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 { | |
34 | assert(level > 0); | |
35 | ||
36 | // Last level, no hint | |
37 | if (level == num_levels_ - 1) { | |
38 | *left_bound = 0; | |
39 | *right_bound = -1; | |
40 | return; | |
41 | } | |
42 | ||
43 | assert(level < num_levels_ - 1); | |
44 | assert(static_cast<int32_t>(file_index) <= level_rb_[level]); | |
45 | ||
46 | const IndexUnit* index_units = next_level_index_[level].index_units; | |
47 | const auto& index = index_units[file_index]; | |
48 | ||
49 | if (cmp_smallest < 0) { | |
50 | *left_bound = (level > 0 && file_index > 0) | |
51 | ? index_units[file_index - 1].largest_lb | |
52 | : 0; | |
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]; | |
66 | } else { | |
67 | assert(false); | |
68 | } | |
69 | ||
70 | assert(*left_bound >= 0); | |
71 | assert(*left_bound <= *right_bound + 1); | |
72 | assert(*right_bound <= level_rb_[level + 1]); | |
73 | } | |
74 | ||
75 | void FileIndexer::UpdateIndex(Arena* arena, const size_t num_levels, | |
76 | std::vector<FileMetaData*>* const files) { | |
77 | if (files == nullptr) { | |
78 | return; | |
79 | } | |
80 | if (num_levels == 0) { // uint_32 0-1 would cause bad behavior | |
81 | num_levels_ = num_levels; | |
82 | return; | |
83 | } | |
84 | assert(level_rb_ == nullptr); // level_rb_ should be init here | |
85 | ||
86 | num_levels_ = num_levels; | |
87 | next_level_index_.resize(num_levels); | |
88 | ||
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++) { | |
92 | level_rb_[i] = -1; | |
93 | } | |
94 | ||
95 | // L1 - Ln-1 | |
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) { | |
102 | continue; | |
103 | } | |
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]; | |
108 | ||
109 | CalculateLB( | |
110 | upper_files, lower_files, &index_level, | |
f67539c2 TL |
111 | [this](const FileMetaData* a, const FileMetaData* b) -> int { |
112 | return ucmp_->CompareWithoutTimestamp(a->smallest.user_key(), | |
113 | b->largest.user_key()); | |
7c673cae FG |
114 | }, |
115 | [](IndexUnit* index, int32_t f_idx) { index->smallest_lb = f_idx; }); | |
116 | CalculateLB( | |
117 | upper_files, lower_files, &index_level, | |
f67539c2 TL |
118 | [this](const FileMetaData* a, const FileMetaData* b) -> int { |
119 | return ucmp_->CompareWithoutTimestamp(a->largest.user_key(), | |
120 | b->largest.user_key()); | |
7c673cae FG |
121 | }, |
122 | [](IndexUnit* index, int32_t f_idx) { index->largest_lb = f_idx; }); | |
123 | CalculateRB( | |
124 | upper_files, lower_files, &index_level, | |
f67539c2 TL |
125 | [this](const FileMetaData* a, const FileMetaData* b) -> int { |
126 | return ucmp_->CompareWithoutTimestamp(a->smallest.user_key(), | |
127 | b->smallest.user_key()); | |
7c673cae FG |
128 | }, |
129 | [](IndexUnit* index, int32_t f_idx) { index->smallest_rb = f_idx; }); | |
130 | CalculateRB( | |
131 | upper_files, lower_files, &index_level, | |
f67539c2 TL |
132 | [this](const FileMetaData* a, const FileMetaData* b) -> int { |
133 | return ucmp_->CompareWithoutTimestamp(a->largest.user_key(), | |
134 | b->smallest.user_key()); | |
7c673cae FG |
135 | }, |
136 | [](IndexUnit* index, int32_t f_idx) { index->largest_rb = f_idx; }); | |
137 | } | |
138 | ||
139 | level_rb_[num_levels_ - 1] = | |
140 | static_cast<int32_t>(files[num_levels_ - 1].size()) - 1; | |
141 | } | |
142 | ||
143 | void FileIndexer::CalculateLB( | |
144 | const std::vector<FileMetaData*>& upper_files, | |
145 | const std::vector<FileMetaData*>& lower_files, IndexLevel* index_level, | |
146 | std::function<int(const FileMetaData*, const FileMetaData*)> cmp_op, | |
147 | std::function<void(IndexUnit*, int32_t)> set_index) { | |
148 | const int32_t upper_size = static_cast<int32_t>(upper_files.size()); | |
149 | const int32_t lower_size = static_cast<int32_t>(lower_files.size()); | |
150 | int32_t upper_idx = 0; | |
151 | int32_t lower_idx = 0; | |
152 | ||
153 | IndexUnit* index = index_level->index_units; | |
154 | while (upper_idx < upper_size && lower_idx < lower_size) { | |
155 | int cmp = cmp_op(upper_files[upper_idx], lower_files[lower_idx]); | |
156 | ||
157 | if (cmp == 0) { | |
158 | set_index(&index[upper_idx], lower_idx); | |
159 | ++upper_idx; | |
7c673cae FG |
160 | } else if (cmp > 0) { |
161 | // Lower level's file (largest) is smaller, a key won't hit in that | |
162 | // file. Move to next lower file | |
163 | ++lower_idx; | |
164 | } else { | |
165 | // Lower level's file becomes larger, update the index, and | |
166 | // move to the next upper file | |
167 | set_index(&index[upper_idx], lower_idx); | |
168 | ++upper_idx; | |
169 | } | |
170 | } | |
171 | ||
172 | while (upper_idx < upper_size) { | |
173 | // Lower files are exhausted, that means the remaining upper files are | |
174 | // greater than any lower files. Set the index to be the lower level size. | |
175 | set_index(&index[upper_idx], lower_size); | |
176 | ++upper_idx; | |
177 | } | |
178 | } | |
179 | ||
180 | void FileIndexer::CalculateRB( | |
181 | const std::vector<FileMetaData*>& upper_files, | |
182 | const std::vector<FileMetaData*>& lower_files, IndexLevel* index_level, | |
183 | std::function<int(const FileMetaData*, const FileMetaData*)> cmp_op, | |
184 | std::function<void(IndexUnit*, int32_t)> set_index) { | |
185 | const int32_t upper_size = static_cast<int32_t>(upper_files.size()); | |
186 | const int32_t lower_size = static_cast<int32_t>(lower_files.size()); | |
187 | int32_t upper_idx = upper_size - 1; | |
188 | int32_t lower_idx = lower_size - 1; | |
189 | ||
190 | IndexUnit* index = index_level->index_units; | |
191 | while (upper_idx >= 0 && lower_idx >= 0) { | |
192 | int cmp = cmp_op(upper_files[upper_idx], lower_files[lower_idx]); | |
193 | ||
194 | if (cmp == 0) { | |
195 | set_index(&index[upper_idx], lower_idx); | |
196 | --upper_idx; | |
7c673cae FG |
197 | } else if (cmp < 0) { |
198 | // Lower level's file (smallest) is larger, a key won't hit in that | |
199 | // file. Move to next lower file. | |
200 | --lower_idx; | |
201 | } else { | |
202 | // Lower level's file becomes smaller, update the index, and move to | |
203 | // the next the upper file | |
204 | set_index(&index[upper_idx], lower_idx); | |
205 | --upper_idx; | |
206 | } | |
207 | } | |
208 | while (upper_idx >= 0) { | |
209 | // Lower files are exhausted, that means the remaining upper files are | |
210 | // smaller than any lower files. Set it to -1. | |
211 | set_index(&index[upper_idx], -1); | |
212 | --upper_idx; | |
213 | } | |
214 | } | |
215 | ||
f67539c2 | 216 | } // namespace ROCKSDB_NAMESPACE |