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 300
