Branch data 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/db_impl.h"
# 8 : : #include "db/dbformat.h"
# 9 : : #include "db/filename.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 { kForward, kReverse };
# 47 : :
# 48 : : DBIter(DBImpl* db, const Comparator* cmp, Iterator* iter, SequenceNumber s,
# 49 : : uint32_t seed)
# 50 : : : db_(db),
# 51 : : user_comparator_(cmp),
# 52 : : iter_(iter),
# 53 : : sequence_(s),
# 54 : : direction_(kForward),
# 55 : : valid_(false),
# 56 : : rnd_(seed),
# 57 : 3379 : bytes_until_read_sampling_(RandomCompactionPeriod()) {}
# 58 : :
# 59 : : DBIter(const DBIter&) = delete;
# 60 : : DBIter& operator=(const DBIter&) = delete;
# 61 : :
# 62 : 3379 : ~DBIter() override { delete iter_; }
# 63 : 102224 : bool Valid() const override { return valid_; }
# 64 : 98813 : Slice key() const override {
# 65 : 98813 : assert(valid_);
# 66 [ + - ]: 98813 : return (direction_ == kForward) ? ExtractUserKey(iter_->key()) : saved_key_;
# 67 : 98813 : }
# 68 : 97919 : Slice value() const override {
# 69 : 97919 : assert(valid_);
# 70 [ + - ]: 97919 : return (direction_ == kForward) ? iter_->value() : saved_value_;
# 71 : 97919 : }
# 72 : 0 : Status status() const override {
# 73 [ # # ]: 0 : if (status_.ok()) {
# 74 : 0 : return iter_->status();
# 75 : 0 : } else {
# 76 : 0 : return status_;
# 77 : 0 : }
# 78 : 0 : }
# 79 : :
# 80 : : void Next() override;
# 81 : : void Prev() override;
# 82 : : void Seek(const Slice& target) override;
# 83 : : void SeekToFirst() override;
# 84 : : void SeekToLast() override;
# 85 : :
# 86 : : private:
# 87 : : void FindNextUserEntry(bool skipping, std::string* skip);
# 88 : : void FindPrevUserEntry();
# 89 : : bool ParseKey(ParsedInternalKey* key);
# 90 : :
# 91 : 100541 : inline void SaveKey(const Slice& k, std::string* dst) {
# 92 : 100541 : dst->assign(k.data(), k.size());
# 93 : 100541 : }
# 94 : :
# 95 : 3383 : inline void ClearSavedValue() {
# 96 [ - + ]: 3383 : if (saved_value_.capacity() > 1048576) {
# 97 : 0 : std::string empty;
# 98 : 0 : swap(empty, saved_value_);
# 99 : 3383 : } else {
# 100 : 3383 : saved_value_.clear();
# 101 : 3383 : }
# 102 : 3383 : }
# 103 : :
# 104 : : // Picks the number of bytes that can be read until a compaction is scheduled.
# 105 : 3712 : size_t RandomCompactionPeriod() {
# 106 : 3712 : return rnd_.Uniform(2 * config::kReadBytesPeriod);
# 107 : 3712 : }
# 108 : :
# 109 : : DBImpl* db_;
# 110 : : const Comparator* const user_comparator_;
# 111 : : Iterator* const iter_;
# 112 : : SequenceNumber const sequence_;
# 113 : : Status status_;
# 114 : : std::string saved_key_; // == current key when direction_==kReverse
# 115 : : std::string saved_value_; // == current raw value when direction_==kReverse
# 116 : : Direction direction_;
# 117 : : bool valid_;
# 118 : : Random rnd_;
# 119 : : size_t bytes_until_read_sampling_;
# 120 : : };
# 121 : :
# 122 : 107750 : inline bool DBIter::ParseKey(ParsedInternalKey* ikey) {
# 123 : 107750 : Slice k = iter_->key();
# 124 : :
# 125 : 107750 : size_t bytes_read = k.size() + iter_->value().size();
# 126 [ + + ]: 108083 : while (bytes_until_read_sampling_ < bytes_read) {
# 127 : 333 : bytes_until_read_sampling_ += RandomCompactionPeriod();
# 128 : 333 : db_->RecordReadSample(k);
# 129 : 333 : }
# 130 : 107750 : assert(bytes_until_read_sampling_ >= bytes_read);
# 131 : 0 : bytes_until_read_sampling_ -= bytes_read;
# 132 : :
# 133 [ - + ]: 107750 : if (!ParseInternalKey(k, ikey)) {
# 134 : 0 : status_ = Status::Corruption("corrupted internal key in DBIter");
# 135 : 0 : return false;
# 136 : 107750 : } else {
# 137 : 107750 : return true;
# 138 : 107750 : }
# 139 : 107750 : }
# 140 : :
# 141 : 97919 : void DBIter::Next() {
# 142 : 97919 : assert(valid_);
# 143 : :
# 144 [ - + ]: 97919 : if (direction_ == kReverse) { // Switch directions?
# 145 : 0 : direction_ = kForward;
# 146 : : // iter_ is pointing just before the entries for this->key(),
# 147 : : // so advance into the range of entries for this->key() and then
# 148 : : // use the normal skipping code below.
# 149 [ # # ]: 0 : if (!iter_->Valid()) {
# 150 : 0 : iter_->SeekToFirst();
# 151 : 0 : } else {
# 152 : 0 : iter_->Next();
# 153 : 0 : }
# 154 [ # # ]: 0 : if (!iter_->Valid()) {
# 155 : 0 : valid_ = false;
# 156 : 0 : saved_key_.clear();
# 157 : 0 : return;
# 158 : 0 : }
# 159 : : // saved_key_ already contains the key to skip past.
# 160 : 97919 : } else {
# 161 : : // Store in saved_key_ the current key so we skip it below.
# 162 : 97919 : SaveKey(ExtractUserKey(iter_->key()), &saved_key_);
# 163 : :
# 164 : : // iter_ is pointing to current key. We can now safely move to the next to
# 165 : : // avoid checking current key.
# 166 : 97919 : iter_->Next();
# 167 [ + + ]: 97919 : if (!iter_->Valid()) {
# 168 : 33 : valid_ = false;
# 169 : 33 : saved_key_.clear();
# 170 : 33 : return;
# 171 : 33 : }
# 172 : 97919 : }
# 173 : :
# 174 : 97886 : FindNextUserEntry(true, &saved_key_);
# 175 : 97886 : }
# 176 : :
# 177 : 98979 : void DBIter::FindNextUserEntry(bool skipping, std::string* skip) {
# 178 : : // Loop until we hit an acceptable entry to yield
# 179 : 98979 : assert(iter_->Valid());
# 180 : 0 : assert(direction_ == kForward);
# 181 : 107750 : do {
# 182 : 107750 : ParsedInternalKey ikey;
# 183 [ + - ][ + + ]: 107750 : if (ParseKey(&ikey) && ikey.sequence <= sequence_) {
# 184 [ - + ]: 107366 : switch (ikey.type) {
# 185 [ + + ]: 2622 : case kTypeDeletion:
# 186 : : // Arrange to skip all upcoming entries for this key since
# 187 : : // they are hidden by this deletion.
# 188 : 2622 : SaveKey(ikey.user_key, skip);
# 189 : 2622 : skipping = true;
# 190 : 2622 : break;
# 191 [ + + ]: 104744 : case kTypeValue:
# 192 [ + + ][ + + ]: 104744 : if (skipping &&
# 193 [ + + ]: 104744 : user_comparator_->Compare(ikey.user_key, *skip) <= 0) {
# 194 : : // Entry hidden
# 195 : 98885 : } else {
# 196 : 98885 : valid_ = true;
# 197 : 98885 : saved_key_.clear();
# 198 : 98885 : return;
# 199 : 98885 : }
# 200 : 5859 : break;
# 201 : 107366 : }
# 202 : 107366 : }
# 203 : 8865 : iter_->Next();
# 204 [ + + ]: 8865 : } while (iter_->Valid());
# 205 : 94 : saved_key_.clear();
# 206 : 94 : valid_ = false;
# 207 : 94 : }
# 208 : :
# 209 : 0 : void DBIter::Prev() {
# 210 : 0 : assert(valid_);
# 211 : :
# 212 [ # # ]: 0 : if (direction_ == kForward) { // Switch directions?
# 213 : : // iter_ is pointing at the current entry. Scan backwards until
# 214 : : // the key changes so we can use the normal reverse scanning code.
# 215 : 0 : assert(iter_->Valid()); // Otherwise valid_ would have been false
# 216 : 0 : SaveKey(ExtractUserKey(iter_->key()), &saved_key_);
# 217 : 0 : while (true) {
# 218 : 0 : iter_->Prev();
# 219 [ # # ]: 0 : if (!iter_->Valid()) {
# 220 : 0 : valid_ = false;
# 221 : 0 : saved_key_.clear();
# 222 : 0 : ClearSavedValue();
# 223 : 0 : return;
# 224 : 0 : }
# 225 [ # # ]: 0 : if (user_comparator_->Compare(ExtractUserKey(iter_->key()), saved_key_) <
# 226 : 0 : 0) {
# 227 : 0 : break;
# 228 : 0 : }
# 229 : 0 : }
# 230 : 0 : direction_ = kReverse;
# 231 : 0 : }
# 232 : :
# 233 : 0 : FindPrevUserEntry();
# 234 : 0 : }
# 235 : :
# 236 : 0 : void DBIter::FindPrevUserEntry() {
# 237 : 0 : assert(direction_ == kReverse);
# 238 : :
# 239 : 0 : ValueType value_type = kTypeDeletion;
# 240 [ # # ]: 0 : if (iter_->Valid()) {
# 241 : 0 : do {
# 242 : 0 : ParsedInternalKey ikey;
# 243 [ # # ][ # # ]: 0 : if (ParseKey(&ikey) && ikey.sequence <= sequence_) {
# 244 [ # # ][ # # ]: 0 : if ((value_type != kTypeDeletion) &&
# 245 [ # # ]: 0 : user_comparator_->Compare(ikey.user_key, saved_key_) < 0) {
# 246 : : // We encountered a non-deleted value in entries for previous keys,
# 247 : 0 : break;
# 248 : 0 : }
# 249 : 0 : value_type = ikey.type;
# 250 [ # # ]: 0 : if (value_type == kTypeDeletion) {
# 251 : 0 : saved_key_.clear();
# 252 : 0 : ClearSavedValue();
# 253 : 0 : } else {
# 254 : 0 : Slice raw_value = iter_->value();
# 255 [ # # ]: 0 : if (saved_value_.capacity() > raw_value.size() + 1048576) {
# 256 : 0 : std::string empty;
# 257 : 0 : swap(empty, saved_value_);
# 258 : 0 : }
# 259 : 0 : SaveKey(ExtractUserKey(iter_->key()), &saved_key_);
# 260 : 0 : saved_value_.assign(raw_value.data(), raw_value.size());
# 261 : 0 : }
# 262 : 0 : }
# 263 : 0 : iter_->Prev();
# 264 [ # # ]: 0 : } while (iter_->Valid());
# 265 : 0 : }
# 266 : :
# 267 [ # # ]: 0 : if (value_type == kTypeDeletion) {
# 268 : : // End
# 269 : 0 : valid_ = false;
# 270 : 0 : saved_key_.clear();
# 271 : 0 : ClearSavedValue();
# 272 : 0 : direction_ = kForward;
# 273 : 0 : } else {
# 274 : 0 : valid_ = true;
# 275 : 0 : }
# 276 : 0 : }
# 277 : :
# 278 : 2884 : void DBIter::Seek(const Slice& target) {
# 279 : 2884 : direction_ = kForward;
# 280 : 2884 : ClearSavedValue();
# 281 : 2884 : saved_key_.clear();
# 282 : 2884 : AppendInternalKey(&saved_key_,
# 283 : 2884 : ParsedInternalKey(target, sequence_, kValueTypeForSeek));
# 284 : 2884 : iter_->Seek(saved_key_);
# 285 [ + + ]: 2884 : if (iter_->Valid()) {
# 286 : 1089 : FindNextUserEntry(false, &saved_key_ /* temporary storage */);
# 287 : 1795 : } else {
# 288 : 1795 : valid_ = false;
# 289 : 1795 : }
# 290 : 2884 : }
# 291 : :
# 292 : 499 : void DBIter::SeekToFirst() {
# 293 : 499 : direction_ = kForward;
# 294 : 499 : ClearSavedValue();
# 295 : 499 : iter_->SeekToFirst();
# 296 [ + + ]: 499 : if (iter_->Valid()) {
# 297 : 4 : FindNextUserEntry(false, &saved_key_ /* temporary storage */);
# 298 : 495 : } else {
# 299 : 495 : valid_ = false;
# 300 : 495 : }
# 301 : 499 : }
# 302 : :
# 303 : 0 : void DBIter::SeekToLast() {
# 304 : 0 : direction_ = kReverse;
# 305 : 0 : ClearSavedValue();
# 306 : 0 : iter_->SeekToLast();
# 307 : 0 : FindPrevUserEntry();
# 308 : 0 : }
# 309 : :
# 310 : : } // anonymous namespace
# 311 : :
# 312 : : Iterator* NewDBIterator(DBImpl* db, const Comparator* user_key_comparator,
# 313 : : Iterator* internal_iter, SequenceNumber sequence,
# 314 : 3379 : uint32_t seed) {
# 315 : 3379 : return new DBIter(db, user_key_comparator, internal_iter, sequence, seed);
# 316 : 3379 : }
# 317 : :
# 318 : : } // namespace leveldb
|
