src/leveldb/db/db_iter.cc

   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/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"
  14
  15 namespace leveldb {
  16
  17 #if 0
  18 static void DumpInternalIter(Iterator* iter) {
  19   for (iter->SeekToFirst(); iter->Valid(); iter->Next()) {
  20     ParsedInternalKey k;
  21     if (!ParseInternalKey(iter->key(), &k)) {
  22       fprintf(stderr, "Corrupt '%s'\n", EscapeString(iter->key()).c_str());
  23     } else {
  24       fprintf(stderr, "@ '%s'\n", k.DebugString().c_str());
  25     }
  26   }
  27 }
  28 #endif
  29
  30 namespace {
  31
  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 {
  38  public:
  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().
  44   enum Direction {
  45     kForward,
  46     kReverse
  47   };
  48
  49   DBIter(const std::string* dbname, Env* env,
  50          const Comparator* cmp, Iterator* iter, SequenceNumber s)
  51       : dbname_(dbname),
  52         env_(env),
  53         user_comparator_(cmp),
  54         iter_(iter),
  55         sequence_(s),
  56         direction_(kForward),
  57         valid_(false) {
  58   }
  59   virtual ~DBIter() {
  60     delete iter_;
  61   }
  62   virtual bool Valid() const { return valid_; }
  63   virtual Slice key() const {
  64     assert(valid_);
  65     return (direction_ == kForward) ? ExtractUserKey(iter_->key()) : saved_key_;
  66   }
  67   virtual Slice value() const {
  68     assert(valid_);
  69     return (direction_ == kForward) ? iter_->value() : saved_value_;
  70   }
  71   virtual Status status() const {
  72     if (status_.ok()) {
  73       return iter_->status();
  74     } else {
  75       return status_;
  76     }
  77   }
  78
  79   virtual void Next();
  80   virtual void Prev();
  81   virtual void Seek(const Slice& target);
  82   virtual void SeekToFirst();
  83   virtual void SeekToLast();
  84
  85  private:
  86   void FindNextUserEntry(bool skipping, std::string* skip);
  87   void FindPrevUserEntry();
  88   bool ParseKey(ParsedInternalKey* key);
  89
  90   inline void SaveKey(const Slice& k, std::string* dst) {
  91     dst->assign(k.data(), k.size());
  92   }
  93
  94   inline void ClearSavedValue() {
  95     if (saved_value_.capacity() > 1048576) {
  96       std::string empty;
  97       swap(empty, saved_value_);
  98     } else {
  99       saved_value_.clear();
 100     }
 101   }
 102
 103   const std::string* const dbname_;
 104   Env* const env_;
 105   const Comparator* const user_comparator_;
 106   Iterator* const iter_;
 107   SequenceNumber const sequence_;
 108
 109   Status status_;
 110   std::string saved_key_;     // == current key when direction_==kReverse
 111   std::string saved_value_;   // == current raw value when direction_==kReverse
 112   Direction direction_;
 113   bool valid_;
 114
 115   // No copying allowed
 116   DBIter(const DBIter&);
 117   void operator=(const DBIter&);
 118 };
 119
 120 inline bool DBIter::ParseKey(ParsedInternalKey* ikey) {
 121   if (!ParseInternalKey(iter_->key(), ikey)) {
 122     status_ = Status::Corruption("corrupted internal key in DBIter");
 123     return false;
 124   } else {
 125     return true;
 126   }
 127 }
 128
 129 void DBIter::Next() {
 130   assert(valid_);
 131
 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();
 139     } else {
 140       iter_->Next();
 141     }
 142     if (!iter_->Valid()) {
 143       valid_ = false;
 144       saved_key_.clear();
 145       return;
 146     }
 147   }
 148
 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);
 153 }
 154
 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);
 159   do {
 160     ParsedInternalKey ikey;
 161     if (ParseKey(&ikey) && ikey.sequence <= sequence_) {
 162       switch (ikey.type) {
 163         case kTypeDeletion:
 164           // Arrange to skip all upcoming entries for this key since
 165           // they are hidden by this deletion.
 166           SaveKey(ikey.user_key, skip);
 167           skipping = true;
 168           break;
 169         case kTypeValue:
 170           if (skipping &&
 171               user_comparator_->Compare(ikey.user_key, *skip) <= 0) {
 172             // Entry hidden
 173           } else {
 174             valid_ = true;
 175             saved_key_.clear();
 176             return;
 177           }
 178           break;
 179       }
 180     }
 181     iter_->Next();
 182   } while (iter_->Valid());
 183   saved_key_.clear();
 184   valid_ = false;
 185 }
 186
 187 void DBIter::Prev() {
 188   assert(valid_);
 189
 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_);
 195     while (true) {
 196       iter_->Prev();
 197       if (!iter_->Valid()) {
 198         valid_ = false;
 199         saved_key_.clear();
 200         ClearSavedValue();
 201         return;
 202       }
 203       if (user_comparator_->Compare(ExtractUserKey(iter_->key()),
 204                                     saved_key_) < 0) {
 205         break;
 206       }
 207     }
 208     direction_ = kReverse;
 209   }
 210
 211   FindPrevUserEntry();
 212 }
 213
 214 void DBIter::FindPrevUserEntry() {
 215   assert(direction_ == kReverse);
 216
 217   ValueType value_type = kTypeDeletion;
 218   if (iter_->Valid()) {
 219     do {
 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,
 225           break;
 226         }
 227         value_type = ikey.type;
 228         if (value_type == kTypeDeletion) {
 229           saved_key_.clear();
 230           ClearSavedValue();
 231         } else {
 232           Slice raw_value = iter_->value();
 233           if (saved_value_.capacity() > raw_value.size() + 1048576) {
 234             std::string empty;
 235             swap(empty, saved_value_);
 236           }
 237           SaveKey(ExtractUserKey(iter_->key()), &saved_key_);
 238           saved_value_.assign(raw_value.data(), raw_value.size());
 239         }
 240       }
 241       iter_->Prev();
 242     } while (iter_->Valid());
 243   }
 244
 245   if (value_type == kTypeDeletion) {
 246     // End
 247     valid_ = false;
 248     saved_key_.clear();
 249     ClearSavedValue();
 250     direction_ = kForward;
 251   } else {
 252     valid_ = true;
 253   }
 254 }
 255
 256 void DBIter::Seek(const Slice& target) {
 257   direction_ = kForward;
 258   ClearSavedValue();
 259   saved_key_.clear();
 260   AppendInternalKey(
 261       &saved_key_, ParsedInternalKey(target, sequence_, kValueTypeForSeek));
 262   iter_->Seek(saved_key_);
 263   if (iter_->Valid()) {
 264     FindNextUserEntry(false, &saved_key_ /* temporary storage */);
 265   } else {
 266     valid_ = false;
 267   }
 268 }
 269
 270 void DBIter::SeekToFirst() {
 271   direction_ = kForward;
 272   ClearSavedValue();
 273   iter_->SeekToFirst();
 274   if (iter_->Valid()) {
 275     FindNextUserEntry(false, &saved_key_ /* temporary storage */);
 276   } else {
 277     valid_ = false;
 278   }
 279 }
 280
 281 void DBIter::SeekToLast() {
 282   direction_ = kReverse;
 283   ClearSavedValue();
 284   iter_->SeekToLast();
 285   FindPrevUserEntry();
 286 }
 287
 288 }  // anonymous namespace
 289
 290 Iterator* NewDBIterator(
 291     const std::string* dbname,
 292     Env* env,
 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);
 297 }
 298
 299 }  // namespace leveldb