Line data Source code
1 : // Copyright (c) 2011 The LevelDB Authors. All rights reserved.
2 : // Use of this source code is governed by a BSD-style license that can be
3 : // found in the LICENSE file. See the AUTHORS file for names of contributors.
4 :
5 : #include "db/db_iter.h"
6 :
7 : #include "db/filename.h"
8 : #include "db/db_impl.h"
9 : #include "db/dbformat.h"
10 : #include "leveldb/env.h"
11 : #include "leveldb/iterator.h"
12 : #include "port/port.h"
13 : #include "util/logging.h"
14 : #include "util/mutexlock.h"
15 : #include "util/random.h"
16 :
17 : namespace leveldb {
18 :
19 : #if 0
20 : static void DumpInternalIter(Iterator* iter) {
21 : for (iter->SeekToFirst(); iter->Valid(); iter->Next()) {
22 : ParsedInternalKey k;
23 : if (!ParseInternalKey(iter->key(), &k)) {
24 : fprintf(stderr, "Corrupt '%s'\n", EscapeString(iter->key()).c_str());
25 : } else {
26 : fprintf(stderr, "@ '%s'\n", k.DebugString().c_str());
27 : }
28 : }
29 : }
30 : #endif
31 :
32 : namespace {
33 :
34 : // Memtables and sstables that make the DB representation contain
35 : // (userkey,seq,type) => uservalue entries. DBIter
36 : // combines multiple entries for the same userkey found in the DB
37 : // representation into a single entry while accounting for sequence
38 : // numbers, deletion markers, overwrites, etc.
39 : class DBIter: public Iterator {
40 : public:
41 : // Which direction is the iterator currently moving?
42 : // (1) When moving forward, the internal iterator is positioned at
43 : // the exact entry that yields this->key(), this->value()
44 : // (2) When moving backwards, the internal iterator is positioned
45 : // just before all entries whose user key == this->key().
46 : enum Direction {
47 : kForward,
48 : kReverse
49 : };
50 :
51 159 : DBIter(DBImpl* db, const Comparator* cmp, Iterator* iter, SequenceNumber s,
52 : uint32_t seed)
53 : : db_(db),
54 : user_comparator_(cmp),
55 : iter_(iter),
56 : sequence_(s),
57 : direction_(kForward),
58 : valid_(false),
59 : rnd_(seed),
60 795 : bytes_counter_(RandomPeriod()) {
61 159 : }
62 954 : virtual ~DBIter() {
63 159 : delete iter_;
64 318 : }
65 11298 : virtual bool Valid() const { return valid_; }
66 11196 : virtual Slice key() const {
67 11196 : assert(valid_);
68 22392 : return (direction_ == kForward) ? ExtractUserKey(iter_->key()) : saved_key_;
69 : }
70 11139 : virtual Slice value() const {
71 11139 : assert(valid_);
72 22278 : return (direction_ == kForward) ? iter_->value() : saved_value_;
73 : }
74 0 : virtual Status status() const {
75 0 : if (status_.ok()) {
76 0 : return iter_->status();
77 : } else {
78 0 : return status_;
79 : }
80 : }
81 :
82 : virtual void Next();
83 : virtual void Prev();
84 : virtual void Seek(const Slice& target);
85 : virtual void SeekToFirst();
86 : virtual void SeekToLast();
87 :
88 : private:
89 : void FindNextUserEntry(bool skipping, std::string* skip);
90 : void FindPrevUserEntry();
91 : bool ParseKey(ParsedInternalKey* key);
92 :
93 0 : inline void SaveKey(const Slice& k, std::string* dst) {
94 11139 : dst->assign(k.data(), k.size());
95 0 : }
96 :
97 159 : inline void ClearSavedValue() {
98 318 : if (saved_value_.capacity() > 1048576) {
99 : std::string empty;
100 0 : swap(empty, saved_value_);
101 : } else {
102 159 : saved_value_.clear();
103 : }
104 159 : }
105 :
106 : // Pick next gap with average value of config::kReadBytesPeriod.
107 : ssize_t RandomPeriod() {
108 432 : return rnd_.Uniform(2*config::kReadBytesPeriod);
109 : }
110 :
111 : DBImpl* db_;
112 : const Comparator* const user_comparator_;
113 : Iterator* const iter_;
114 : SequenceNumber const sequence_;
115 :
116 : Status status_;
117 : std::string saved_key_; // == current key when direction_==kReverse
118 : std::string saved_value_; // == current raw value when direction_==kReverse
119 : Direction direction_;
120 : bool valid_;
121 :
122 : Random rnd_;
123 : ssize_t bytes_counter_;
124 :
125 : // No copying allowed
126 : DBIter(const DBIter&);
127 : void operator=(const DBIter&);
128 : };
129 :
130 22337 : inline bool DBIter::ParseKey(ParsedInternalKey* ikey) {
131 22337 : Slice k = iter_->key();
132 22337 : ssize_t n = k.size() + iter_->value().size();
133 22337 : bytes_counter_ -= n;
134 44731 : while (bytes_counter_ < 0) {
135 57 : bytes_counter_ += RandomPeriod();
136 57 : db_->RecordReadSample(k);
137 : }
138 22337 : if (!ParseInternalKey(k, ikey)) {
139 0 : status_ = Status::Corruption("corrupted internal key in DBIter");
140 0 : return false;
141 : } else {
142 : return true;
143 : }
144 : }
145 :
146 11139 : void DBIter::Next() {
147 11139 : assert(valid_);
148 :
149 11139 : if (direction_ == kReverse) { // Switch directions?
150 0 : direction_ = kForward;
151 : // iter_ is pointing just before the entries for this->key(),
152 : // so advance into the range of entries for this->key() and then
153 : // use the normal skipping code below.
154 0 : if (!iter_->Valid()) {
155 0 : iter_->SeekToFirst();
156 : } else {
157 0 : iter_->Next();
158 : }
159 0 : if (!iter_->Valid()) {
160 0 : valid_ = false;
161 0 : saved_key_.clear();
162 11139 : return;
163 : }
164 : // saved_key_ already contains the key to skip past.
165 : } else {
166 : // Store in saved_key_ the current key so we skip it below.
167 22278 : SaveKey(ExtractUserKey(iter_->key()), &saved_key_);
168 : }
169 :
170 11139 : FindNextUserEntry(true, &saved_key_);
171 : }
172 :
173 11198 : void DBIter::FindNextUserEntry(bool skipping, std::string* skip) {
174 : // Loop until we hit an acceptable entry to yield
175 11198 : assert(iter_->Valid());
176 11198 : assert(direction_ == kForward);
177 11139 : do {
178 : ParsedInternalKey ikey;
179 22337 : if (ParseKey(&ikey) && ikey.sequence <= sequence_) {
180 22337 : switch (ikey.type) {
181 : case kTypeDeletion:
182 : // Arrange to skip all upcoming entries for this key since
183 : // they are hidden by this deletion.
184 0 : SaveKey(ikey.user_key, skip);
185 : skipping = true;
186 : break;
187 : case kTypeValue:
188 67011 : if (skipping &&
189 89171 : user_comparator_->Compare(ikey.user_key, *skip) <= 0) {
190 : // Entry hidden
191 : } else {
192 11198 : valid_ = true;
193 11198 : saved_key_.clear();
194 22396 : return;
195 : }
196 : break;
197 : }
198 : }
199 11139 : iter_->Next();
200 11139 : } while (iter_->Valid());
201 0 : saved_key_.clear();
202 0 : valid_ = false;
203 : }
204 :
205 0 : void DBIter::Prev() {
206 0 : assert(valid_);
207 :
208 0 : if (direction_ == kForward) { // Switch directions?
209 : // iter_ is pointing at the current entry. Scan backwards until
210 : // the key changes so we can use the normal reverse scanning code.
211 0 : assert(iter_->Valid()); // Otherwise valid_ would have been false
212 0 : SaveKey(ExtractUserKey(iter_->key()), &saved_key_);
213 : while (true) {
214 0 : iter_->Prev();
215 0 : if (!iter_->Valid()) {
216 0 : valid_ = false;
217 0 : saved_key_.clear();
218 0 : ClearSavedValue();
219 0 : return;
220 : }
221 0 : if (user_comparator_->Compare(ExtractUserKey(iter_->key()),
222 0 : saved_key_) < 0) {
223 : break;
224 : }
225 : }
226 0 : direction_ = kReverse;
227 : }
228 :
229 0 : FindPrevUserEntry();
230 : }
231 :
232 0 : void DBIter::FindPrevUserEntry() {
233 0 : assert(direction_ == kReverse);
234 :
235 0 : ValueType value_type = kTypeDeletion;
236 0 : if (iter_->Valid()) {
237 0 : do {
238 : ParsedInternalKey ikey;
239 0 : if (ParseKey(&ikey) && ikey.sequence <= sequence_) {
240 0 : if ((value_type != kTypeDeletion) &&
241 0 : user_comparator_->Compare(ikey.user_key, saved_key_) < 0) {
242 : // We encountered a non-deleted value in entries for previous keys,
243 : break;
244 : }
245 0 : value_type = ikey.type;
246 0 : if (value_type == kTypeDeletion) {
247 0 : saved_key_.clear();
248 0 : ClearSavedValue();
249 : } else {
250 0 : Slice raw_value = iter_->value();
251 0 : if (saved_value_.capacity() > raw_value.size() + 1048576) {
252 : std::string empty;
253 0 : swap(empty, saved_value_);
254 : }
255 0 : SaveKey(ExtractUserKey(iter_->key()), &saved_key_);
256 0 : saved_value_.assign(raw_value.data(), raw_value.size());
257 : }
258 : }
259 0 : iter_->Prev();
260 0 : } while (iter_->Valid());
261 : }
262 :
263 0 : if (value_type == kTypeDeletion) {
264 : // End
265 0 : valid_ = false;
266 0 : saved_key_.clear();
267 0 : ClearSavedValue();
268 0 : direction_ = kForward;
269 : } else {
270 0 : valid_ = true;
271 : }
272 0 : }
273 :
274 93 : void DBIter::Seek(const Slice& target) {
275 93 : direction_ = kForward;
276 93 : ClearSavedValue();
277 93 : saved_key_.clear();
278 : AppendInternalKey(
279 186 : &saved_key_, ParsedInternalKey(target, sequence_, kValueTypeForSeek));
280 186 : iter_->Seek(saved_key_);
281 93 : if (iter_->Valid()) {
282 57 : FindNextUserEntry(false, &saved_key_ /* temporary storage */);
283 : } else {
284 36 : valid_ = false;
285 : }
286 93 : }
287 :
288 66 : void DBIter::SeekToFirst() {
289 66 : direction_ = kForward;
290 66 : ClearSavedValue();
291 66 : iter_->SeekToFirst();
292 66 : if (iter_->Valid()) {
293 2 : FindNextUserEntry(false, &saved_key_ /* temporary storage */);
294 : } else {
295 64 : valid_ = false;
296 : }
297 66 : }
298 :
299 0 : void DBIter::SeekToLast() {
300 0 : direction_ = kReverse;
301 0 : ClearSavedValue();
302 0 : iter_->SeekToLast();
303 0 : FindPrevUserEntry();
304 0 : }
305 :
306 : } // anonymous namespace
307 :
308 159 : Iterator* NewDBIterator(
309 : DBImpl* db,
310 : const Comparator* user_key_comparator,
311 : Iterator* internal_iter,
312 : SequenceNumber sequence,
313 : uint32_t seed) {
314 159 : return new DBIter(db, user_key_comparator, internal_iter, sequence, seed);
315 : }
316 :
317 : } // namespace leveldb
|
