/bitcoin/src/leveldb/db/db_iter.cc

Source
// Copyright (c) 2011 The LevelDB Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file. See the AUTHORS file for names of contributors.

#include "db/db_iter.h"

#include "db/db_impl.h"
#include "db/dbformat.h"
#include "db/filename.h"
#include "leveldb/env.h"
#include "leveldb/iterator.h"
#include "port/port.h"
#include "util/logging.h"
#include "util/mutexlock.h"
#include "util/random.h"

namespace leveldb {

#if 0
static void DumpInternalIter(Iterator* iter) {
  for (iter->SeekToFirst(); iter->Valid(); iter->Next()) {
    ParsedInternalKey k;
    if (!ParseInternalKey(iter->key(), &k)) {
      fprintf(stderr, "Corrupt '%s'\n", EscapeString(iter->key()).c_str());
    } else {
      fprintf(stderr, "@ '%s'\n", k.DebugString().c_str());
    }
  }
}
#endif

namespace {

// Memtables and sstables that make the DB representation contain
// (userkey,seq,type) => uservalue entries.  DBIter
// combines multiple entries for the same userkey found in the DB
// representation into a single entry while accounting for sequence
// numbers, deletion markers, overwrites, etc.
class DBIter : public Iterator {
 public:
  // Which direction is the iterator currently moving?
  // (1) When moving forward, the internal iterator is positioned at
  //     the exact entry that yields this->key(), this->value()
  // (2) When moving backwards, the internal iterator is positioned
  //     just before all entries whose user key == this->key().
  enum Direction { kForward, kReverse };

  DBIter(DBImpl* db, const Comparator* cmp, Iterator* iter, SequenceNumber s,
         uint32_t seed)
      : db_(db),
        user_comparator_(cmp),
        iter_(iter),
        sequence_(s),
        direction_(kForward),
        valid_(false),
        rnd_(seed),
        bytes_until_read_sampling_(RandomCompactionPeriod()) {}

  DBIter(const DBIter&) = delete;
  DBIter& operator=(const DBIter&) = delete;

  ~DBIter() override { delete iter_; }
  bool Valid() const override { return valid_; }
  Slice key() const override {
    assert(valid_);
    return (direction_ == kForward) ? ExtractUserKey(iter_->key()) : saved_key_;
  }
  Slice value() const override {
    assert(valid_);
    return (direction_ == kForward) ? iter_->value() : saved_value_;
  }
  Status status() const override {
    if (status_.ok()) {
      return iter_->status();
    } else {
      return status_;
    }
  }

  void Next() override;
  void Prev() override;
  void Seek(const Slice& target) override;
  void SeekToFirst() override;
  void SeekToLast() override;

 private:
  void FindNextUserEntry(bool skipping, std::string* skip);
  void FindPrevUserEntry();
  bool ParseKey(ParsedInternalKey* key);

  inline void SaveKey(const Slice& k, std::string* dst) {
    dst->assign(k.data(), k.size());
  }

  inline void ClearSavedValue() {
    if (saved_value_.capacity() > 1048576) {
      std::string empty;
      swap(empty, saved_value_);
    } else {
      saved_value_.clear();
    }
  }

  // Picks the number of bytes that can be read until a compaction is scheduled.
  size_t RandomCompactionPeriod() {
    return rnd_.Uniform(2 * config::kReadBytesPeriod);
  }

  DBImpl* db_;
  const Comparator* const user_comparator_;
  Iterator* const iter_;
  SequenceNumber const sequence_;
  Status status_;
  std::string saved_key_;    // == current key when direction_==kReverse
  std::string saved_value_;  // == current raw value when direction_==kReverse
  Direction direction_;
  bool valid_;
  Random rnd_;
  size_t bytes_until_read_sampling_;
};

inline bool DBIter::ParseKey(ParsedInternalKey* ikey) {
  Slice k = iter_->key();

  size_t bytes_read = k.size() + iter_->value().size();
  while (bytes_until_read_sampling_ < bytes_read) {
    bytes_until_read_sampling_ += RandomCompactionPeriod();
    db_->RecordReadSample(k);
  }
  assert(bytes_until_read_sampling_ >= bytes_read);
  bytes_until_read_sampling_ -= bytes_read;

  if (!ParseInternalKey(k, ikey)) {
    status_ = Status::Corruption("corrupted internal key in DBIter");
    return false;
  } else {
    return true;
  }
}

void DBIter::Next() {
  assert(valid_);

  if (direction_ == kReverse) {  // Switch directions?
    direction_ = kForward;
    // iter_ is pointing just before the entries for this->key(),
    // so advance into the range of entries for this->key() and then
    // use the normal skipping code below.
    if (!iter_->Valid()) {
      iter_->SeekToFirst();
    } else {
      iter_->Next();
    }
    if (!iter_->Valid()) {
      valid_ = false;
      saved_key_.clear();
      return;
    }
    // saved_key_ already contains the key to skip past.
  } else {
    // Store in saved_key_ the current key so we skip it below.
    SaveKey(ExtractUserKey(iter_->key()), &saved_key_);

    // iter_ is pointing to current key. We can now safely move to the next to
    // avoid checking current key.
    iter_->Next();
    if (!iter_->Valid()) {
      valid_ = false;
      saved_key_.clear();
      return;
    }
  }

  FindNextUserEntry(true, &saved_key_);
}

void DBIter::FindNextUserEntry(bool skipping, std::string* skip) {
  // Loop until we hit an acceptable entry to yield
  assert(iter_->Valid());
  assert(direction_ == kForward);
  do {
    ParsedInternalKey ikey;
    if (ParseKey(&ikey) && ikey.sequence <= sequence_) {
      switch (ikey.type) {
        case kTypeDeletion:
          // Arrange to skip all upcoming entries for this key since
          // they are hidden by this deletion.
          SaveKey(ikey.user_key, skip);
          skipping = true;
          break;
        case kTypeValue:
          if (skipping &&
              user_comparator_->Compare(ikey.user_key, *skip) <= 0) {
            // Entry hidden
          } else {
            valid_ = true;
            saved_key_.clear();
            return;
          }
          break;
      }
    }
    iter_->Next();
  } while (iter_->Valid());
  saved_key_.clear();
  valid_ = false;
}

void DBIter::Prev() {
  assert(valid_);

  if (direction_ == kForward) {  // Switch directions?
    // iter_ is pointing at the current entry.  Scan backwards until
    // the key changes so we can use the normal reverse scanning code.
    assert(iter_->Valid());  // Otherwise valid_ would have been false
    SaveKey(ExtractUserKey(iter_->key()), &saved_key_);
    while (true) {
      iter_->Prev();
      if (!iter_->Valid()) {
        valid_ = false;
        saved_key_.clear();
        ClearSavedValue();
        return;
      }
      if (user_comparator_->Compare(ExtractUserKey(iter_->key()), saved_key_) <
          0) {
        break;
      }
    }
    direction_ = kReverse;
  }

  FindPrevUserEntry();
}

void DBIter::FindPrevUserEntry() {
  assert(direction_ == kReverse);

  ValueType value_type = kTypeDeletion;
  if (iter_->Valid()) {
    do {
      ParsedInternalKey ikey;
      if (ParseKey(&ikey) && ikey.sequence <= sequence_) {
        if ((value_type != kTypeDeletion) &&
            user_comparator_->Compare(ikey.user_key, saved_key_) < 0) {
          // We encountered a non-deleted value in entries for previous keys,
          break;
        }
        value_type = ikey.type;
        if (value_type == kTypeDeletion) {
          saved_key_.clear();
          ClearSavedValue();
        } else {
          Slice raw_value = iter_->value();
          if (saved_value_.capacity() > raw_value.size() + 1048576) {
            std::string empty;
            swap(empty, saved_value_);
          }
          SaveKey(ExtractUserKey(iter_->key()), &saved_key_);
          saved_value_.assign(raw_value.data(), raw_value.size());
        }
      }
      iter_->Prev();
    } while (iter_->Valid());
  }

  if (value_type == kTypeDeletion) {
    // End
    valid_ = false;
    saved_key_.clear();
    ClearSavedValue();
    direction_ = kForward;
  } else {
    valid_ = true;
  }
}

void DBIter::Seek(const Slice& target) {
  direction_ = kForward;
  ClearSavedValue();
  saved_key_.clear();
  AppendInternalKey(&saved_key_,
                    ParsedInternalKey(target, sequence_, kValueTypeForSeek));
  iter_->Seek(saved_key_);
  if (iter_->Valid()) {
    FindNextUserEntry(false, &saved_key_ /* temporary storage */);
  } else {
    valid_ = false;
  }
}

void DBIter::SeekToFirst() {
  direction_ = kForward;
  ClearSavedValue();
  iter_->SeekToFirst();
  if (iter_->Valid()) {
    FindNextUserEntry(false, &saved_key_ /* temporary storage */);
  } else {
    valid_ = false;
  }
}

void DBIter::SeekToLast() {
  direction_ = kReverse;
  ClearSavedValue();
  iter_->SeekToLast();
  FindPrevUserEntry();
}

}  // anonymous namespace

Iterator* NewDBIterator(DBImpl* db, const Comparator* user_key_comparator,
                        Iterator* internal_iter, SequenceNumber sequence,
                        uint32_t seed) {
  return new DBIter(db, user_key_comparator, internal_iter, sequence, seed);
}

}  // namespace leveldb

Coverage Report

Created: 2025-06-10 13:21

Line	Count	Source
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	35.8k	: db_(db),
51	35.8k	user_comparator_(cmp),
52	35.8k	iter_(iter),
53	35.8k	sequence_(s),
54	35.8k	direction_(kForward),
55	35.8k	valid_(false),
56	35.8k	rnd_(seed),
57	35.8k	bytes_until_read_sampling_(RandomCompactionPeriod()) {}
58
59		DBIter(const DBIter&) = delete;
60		DBIter& operator=(const DBIter&) = delete;
61
62	35.8k	~DBIter() override { delete iter_; }
63	33.2k	bool Valid() const override { return valid_; }
64	6.51k	Slice key() const override {
65	6.51k	assert(valid_); Branch (65:5): [True: 6.51k, False: 0]
66	6.51k	return (direction_ == kForward) ? ExtractUserKey(iter_->key()) : saved_key_; Branch (66:12): [True: 6.51k, False: 0]
67	6.51k	}
68	6.51k	Slice value() const override {
69	6.51k	assert(valid_); Branch (69:5): [True: 6.51k, False: 0]
70	6.51k	return (direction_ == kForward) ? iter_->value() : saved_value_; Branch (70:12): [True: 6.51k, False: 0]
71	6.51k	}
72	0	Status status() const override {
73	0	if (status_.ok()) { Branch (73:9): [True: 0, False: 0]
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	6.51k	inline void SaveKey(const Slice& k, std::string* dst) {
92	6.51k	dst->assign(k.data(), k.size());
93	6.51k	}
94
95	35.8k	inline void ClearSavedValue() {
96	35.8k	if (saved_value_.capacity() > 1048576) { Branch (96:9): [True: 0, False: 35.8k]
97	0	std::string empty;
98	0	swap(empty, saved_value_);
99	35.8k	} else {
100	35.8k	saved_value_.clear();
101	35.8k	}
102	35.8k	}
103
104		// Picks the number of bytes that can be read until a compaction is scheduled.
105	35.8k	size_t RandomCompactionPeriod() {
106	35.8k	return rnd_.Uniform(2 * config::kReadBytesPeriod);
107	35.8k	}
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	9.30k	inline bool DBIter::ParseKey(ParsedInternalKey* ikey) {
123	9.30k	Slice k = iter_->key();
124
125	9.30k	size_t bytes_read = k.size() + iter_->value().size();
126	9.30k	while (bytes_until_read_sampling_ < bytes_read) { Branch (126:10): [True: 0, False: 9.30k]
127	0	bytes_until_read_sampling_ += RandomCompactionPeriod();
128	0	db_->RecordReadSample(k);
129	0	}
130	9.30k	assert(bytes_until_read_sampling_ >= bytes_read); Branch (130:3): [True: 9.30k, False: 0]
131	9.30k	bytes_until_read_sampling_ -= bytes_read;
132
133	9.30k	if (!ParseInternalKey(k, ikey)) { Branch (133:7): [True: 0, False: 9.30k]
134	0	status_ = Status::Corruption("corrupted internal key in DBIter");
135	0	return false;
136	9.30k	} else {
137	9.30k	return true;
138	9.30k	}
139	9.30k	}
140
141	6.51k	void DBIter::Next() {
142	6.51k	assert(valid_); Branch (142:3): [True: 6.51k, False: 0]
143
144	6.51k	if (direction_ == kReverse) { // Switch directions? Branch (144:7): [True: 0, False: 6.51k]
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()) { Branch (149:9): [True: 0, False: 0]
150	0	iter_->SeekToFirst();
151	0	} else {
152	0	iter_->Next();
153	0	}
154	0	if (!iter_->Valid()) { Branch (154:9): [True: 0, False: 0]
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	6.51k	} else {
161		// Store in saved_key_ the current key so we skip it below.
162	6.51k	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	6.51k	iter_->Next();
167	6.51k	if (!iter_->Valid()) { Branch (167:9): [True: 1.72k, False: 4.79k]
168	1.72k	valid_ = false;
169	1.72k	saved_key_.clear();
170	1.72k	return;
171	1.72k	}
172	6.51k	}
173
174	4.79k	FindNextUserEntry(true, &saved_key_);
175	4.79k	}
176
177	7.41k	void DBIter::FindNextUserEntry(bool skipping, std::string* skip) {
178		// Loop until we hit an acceptable entry to yield
179	7.41k	assert(iter_->Valid()); Branch (179:3): [True: 7.41k, False: 0]
180	7.41k	assert(direction_ == kForward); Branch (180:3): [True: 7.41k, False: 0]
181	9.30k	do {
182	9.30k	ParsedInternalKey ikey;
183	9.30k	if (ParseKey(&ikey) && ikey.sequence <= sequence_) { Branch (183:9): [True: 9.30k, False: 0] Branch (183:28): [True: 9.30k, False: 0]
184	9.30k	switch (ikey.type) { Branch (184:15): [True: 0, False: 9.30k]
185	0	case kTypeDeletion: Branch (185:9): [True: 0, False: 9.30k]
186		// Arrange to skip all upcoming entries for this key since
187		// they are hidden by this deletion.
188	0	SaveKey(ikey.user_key, skip);
189	0	skipping = true;
190	0	break;
191	9.30k	case kTypeValue: Branch (191:9): [True: 9.30k, False: 0]
192	9.30k	if (skipping && Branch (192:15): [True: 6.68k, False: 2.62k] Branch (192:15): [True: 2.71k, False: 6.58k]
193	9.30k	user_comparator_->Compare(ikey.user_key, *skip) <= 0) { Branch (193:15): [True: 2.71k, False: 3.96k]
194		// Entry hidden
195	6.58k	} else {
196	6.58k	valid_ = true;
197	6.58k	saved_key_.clear();
198	6.58k	return;
199	6.58k	}
200	2.71k	break;
201	9.30k	}
202	9.30k	}
203	2.71k	iter_->Next();
204	2.71k	} while (iter_->Valid()); Branch (204:12): [True: 1.88k, False: 828]
205	828	saved_key_.clear();
206	828	valid_ = false;
207	828	}
208
209	0	void DBIter::Prev() {
210	0	assert(valid_); Branch (210:3): [True: 0, False: 0]
211
212	0	if (direction_ == kForward) { // Switch directions? Branch (212:7): [True: 0, False: 0]
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 Branch (215:5): [True: 0, False: 0]
216	0	SaveKey(ExtractUserKey(iter_->key()), &saved_key_);
217	0	while (true) { Branch (217:12): [Folded - Ignored]
218	0	iter_->Prev();
219	0	if (!iter_->Valid()) { Branch (219:11): [True: 0, False: 0]
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_) < Branch (225:11): [True: 0, False: 0]
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); Branch (237:3): [True: 0, False: 0]
238
239	0	ValueType value_type = kTypeDeletion;
240	0	if (iter_->Valid()) { Branch (240:7): [True: 0, False: 0]
241	0	do {
242	0	ParsedInternalKey ikey;
243	0	if (ParseKey(&ikey) && ikey.sequence <= sequence_) { Branch (243:11): [True: 0, False: 0] Branch (243:30): [True: 0, False: 0]
244	0	if ((value_type != kTypeDeletion) && Branch (244:13): [True: 0, False: 0] Branch (244:13): [True: 0, False: 0]
245	0	user_comparator_->Compare(ikey.user_key, saved_key_) < 0) { Branch (245:13): [True: 0, False: 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) { Branch (250:13): [True: 0, False: 0]
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) { Branch (255:15): [True: 0, False: 0]
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()); Branch (264:14): [True: 0, False: 0]
265	0	}
266
267	0	if (value_type == kTypeDeletion) { Branch (267:7): [True: 0, False: 0]
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	24.8k	void DBIter::Seek(const Slice& target) {
279	24.8k	direction_ = kForward;
280	24.8k	ClearSavedValue();
281	24.8k	saved_key_.clear();
282	24.8k	AppendInternalKey(&saved_key_,
283	24.8k	ParsedInternalKey(target, sequence_, kValueTypeForSeek));
284	24.8k	iter_->Seek(saved_key_);
285	24.8k	if (iter_->Valid()) { Branch (285:7): [True: 2.62k, False: 22.1k]
286	2.62k	FindNextUserEntry(false, &saved_key_ /* temporary storage */);
287	22.1k	} else {
288	22.1k	valid_ = false;
289	22.1k	}
290	24.8k	}
291
292	11.0k	void DBIter::SeekToFirst() {
293	11.0k	direction_ = kForward;
294	11.0k	ClearSavedValue();
295	11.0k	iter_->SeekToFirst();
296	11.0k	if (iter_->Valid()) { Branch (296:7): [True: 0, False: 11.0k]
297	0	FindNextUserEntry(false, &saved_key_ /* temporary storage */);
298	11.0k	} else {
299	11.0k	valid_ = false;
300	11.0k	}
301	11.0k	}
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	35.8k	uint32_t seed) {
315	35.8k	return new DBIter(db, user_key_comparator, internal_iter, sequence, seed);
316	35.8k	}
317
318		} // namespace leveldb