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.
5
#include "db/db_iter.h"
7
#include "db/filename.h"
8
#include "db/dbformat.h"
9
#include "leveldb/env.h"
10
#include "leveldb/iterator.h"
11
#include "port/port.h"
12
#include "util/logging.h"
13
#include "util/mutexlock.h"
18
static void DumpInternalIter(Iterator* iter) {
19
for (iter->SeekToFirst(); iter->Valid(); iter->Next()) {
21
if (!ParseInternalKey(iter->key(), &k)) {
22
fprintf(stderr, "Corrupt '%s'\n", EscapeString(iter->key()).c_str());
24
fprintf(stderr, "@ '%s'\n", k.DebugString().c_str());
32
// Memtables and sstables that make the DB representation contain
33
// (userkey,seq,type) => uservalue entries. DBIter
34
// combines multiple entries for the same userkey found in the DB
35
// representation into a single entry while accounting for sequence
36
// numbers, deletion markers, overwrites, etc.
37
class DBIter: public Iterator {
39
// Which direction is the iterator currently moving?
40
// (1) When moving forward, the internal iterator is positioned at
41
// the exact entry that yields this->key(), this->value()
42
// (2) When moving backwards, the internal iterator is positioned
43
// just before all entries whose user key == this->key().
49
DBIter(const std::string* dbname, Env* env,
50
const Comparator* cmp, Iterator* iter, SequenceNumber s)
53
user_comparator_(cmp),
62
virtual bool Valid() const { return valid_; }
63
virtual Slice key() const {
65
return (direction_ == kForward) ? ExtractUserKey(iter_->key()) : saved_key_;
67
virtual Slice value() const {
69
return (direction_ == kForward) ? iter_->value() : saved_value_;
71
virtual Status status() const {
73
return iter_->status();
81
virtual void Seek(const Slice& target);
82
virtual void SeekToFirst();
83
virtual void SeekToLast();
86
void FindNextUserEntry(bool skipping, std::string* skip);
87
void FindPrevUserEntry();
88
bool ParseKey(ParsedInternalKey* key);
90
inline void SaveKey(const Slice& k, std::string* dst) {
91
dst->assign(k.data(), k.size());
94
inline void ClearSavedValue() {
95
if (saved_value_.capacity() > 1048576) {
97
swap(empty, saved_value_);
103
const std::string* const dbname_;
105
const Comparator* const user_comparator_;
106
Iterator* const iter_;
107
SequenceNumber const sequence_;
110
std::string saved_key_; // == current key when direction_==kReverse
111
std::string saved_value_; // == current raw value when direction_==kReverse
112
Direction direction_;
115
// No copying allowed
116
DBIter(const DBIter&);
117
void operator=(const DBIter&);
120
inline bool DBIter::ParseKey(ParsedInternalKey* ikey) {
121
if (!ParseInternalKey(iter_->key(), ikey)) {
122
status_ = Status::Corruption("corrupted internal key in DBIter");
129
void DBIter::Next() {
132
if (direction_ == kReverse) { // Switch directions?
133
direction_ = kForward;
134
// iter_ is pointing just before the entries for this->key(),
135
// so advance into the range of entries for this->key() and then
136
// use the normal skipping code below.
137
if (!iter_->Valid()) {
138
iter_->SeekToFirst();
142
if (!iter_->Valid()) {
149
// Temporarily use saved_key_ as storage for key to skip.
150
std::string* skip = &saved_key_;
151
SaveKey(ExtractUserKey(iter_->key()), skip);
152
FindNextUserEntry(true, skip);
155
void DBIter::FindNextUserEntry(bool skipping, std::string* skip) {
156
// Loop until we hit an acceptable entry to yield
157
assert(iter_->Valid());
158
assert(direction_ == kForward);
160
ParsedInternalKey ikey;
161
if (ParseKey(&ikey) && ikey.sequence <= sequence_) {
164
// Arrange to skip all upcoming entries for this key since
165
// they are hidden by this deletion.
166
SaveKey(ikey.user_key, skip);
171
user_comparator_->Compare(ikey.user_key, *skip) <= 0) {
182
} while (iter_->Valid());
187
void DBIter::Prev() {
190
if (direction_ == kForward) { // Switch directions?
191
// iter_ is pointing at the current entry. Scan backwards until
192
// the key changes so we can use the normal reverse scanning code.
193
assert(iter_->Valid()); // Otherwise valid_ would have been false
194
SaveKey(ExtractUserKey(iter_->key()), &saved_key_);
197
if (!iter_->Valid()) {
203
if (user_comparator_->Compare(ExtractUserKey(iter_->key()),
208
direction_ = kReverse;
214
void DBIter::FindPrevUserEntry() {
215
assert(direction_ == kReverse);
217
ValueType value_type = kTypeDeletion;
218
if (iter_->Valid()) {
220
ParsedInternalKey ikey;
221
if (ParseKey(&ikey) && ikey.sequence <= sequence_) {
222
if ((value_type != kTypeDeletion) &&
223
user_comparator_->Compare(ikey.user_key, saved_key_) < 0) {
224
// We encountered a non-deleted value in entries for previous keys,
227
value_type = ikey.type;
228
if (value_type == kTypeDeletion) {
232
Slice raw_value = iter_->value();
233
if (saved_value_.capacity() > raw_value.size() + 1048576) {
235
swap(empty, saved_value_);
237
SaveKey(ExtractUserKey(iter_->key()), &saved_key_);
238
saved_value_.assign(raw_value.data(), raw_value.size());
242
} while (iter_->Valid());
245
if (value_type == kTypeDeletion) {
250
direction_ = kForward;
256
void DBIter::Seek(const Slice& target) {
257
direction_ = kForward;
261
&saved_key_, ParsedInternalKey(target, sequence_, kValueTypeForSeek));
262
iter_->Seek(saved_key_);
263
if (iter_->Valid()) {
264
FindNextUserEntry(false, &saved_key_ /* temporary storage */);
270
void DBIter::SeekToFirst() {
271
direction_ = kForward;
273
iter_->SeekToFirst();
274
if (iter_->Valid()) {
275
FindNextUserEntry(false, &saved_key_ /* temporary storage */);
281
void DBIter::SeekToLast() {
282
direction_ = kReverse;
288
} // anonymous namespace
290
Iterator* NewDBIterator(
291
const std::string* dbname,
293
const Comparator* user_key_comparator,
294
Iterator* internal_iter,
295
const SequenceNumber& sequence) {
296
return new DBIter(dbname, env, user_key_comparator, internal_iter, sequence);
299
} // namespace leveldb
added
removed
src/leveldb/db/db_iter.cc
