1 // Copyright (c) 2011-present, Facebook, Inc. All rights reserved. 2 // This source code is licensed under both the GPLv2 (found in the 3 // COPYING file in the root directory) and Apache 2.0 License 4 // (found in the LICENSE.Apache file in the root directory). 5 #pragma once 6 7 #ifndef ROCKSDB_LITE 8 9 #include <string> 10 #include <vector> 11 #include <queue> 12 13 #include "db/dbformat.h" 14 #include "memory/arena.h" 15 #include "rocksdb/db.h" 16 #include "rocksdb/iterator.h" 17 #include "rocksdb/options.h" 18 #include "table/internal_iterator.h" 19 20 namespace ROCKSDB_NAMESPACE { 21 22 class DBImpl; 23 class Env; 24 struct SuperVersion; 25 class ColumnFamilyData; 26 class ForwardLevelIterator; 27 class VersionStorageInfo; 28 struct FileMetaData; 29 30 class MinIterComparator { 31 public: MinIterComparator(const Comparator * comparator)32 explicit MinIterComparator(const Comparator* comparator) : 33 comparator_(comparator) {} 34 operator()35 bool operator()(InternalIterator* a, InternalIterator* b) { 36 return comparator_->Compare(a->key(), b->key()) > 0; 37 } 38 private: 39 const Comparator* comparator_; 40 }; 41 42 typedef std::priority_queue<InternalIterator*, std::vector<InternalIterator*>, 43 MinIterComparator> MinIterHeap; 44 45 /** 46 * ForwardIterator is a special type of iterator that only supports Seek() 47 * and Next(). It is expected to perform better than TailingIterator by 48 * removing the encapsulation and making all information accessible within 49 * the iterator. At the current implementation, snapshot is taken at the 50 * time Seek() is called. The Next() followed do not see new values after. 51 */ 52 class ForwardIterator : public InternalIterator { 53 public: 54 ForwardIterator(DBImpl* db, const ReadOptions& read_options, 55 ColumnFamilyData* cfd, SuperVersion* current_sv = nullptr); 56 virtual ~ForwardIterator(); 57 SeekForPrev(const Slice &)58 void SeekForPrev(const Slice& /*target*/) override { 59 status_ = Status::NotSupported("ForwardIterator::SeekForPrev()"); 60 valid_ = false; 61 } SeekToLast()62 void SeekToLast() override { 63 status_ = Status::NotSupported("ForwardIterator::SeekToLast()"); 64 valid_ = false; 65 } Prev()66 void Prev() override { 67 status_ = Status::NotSupported("ForwardIterator::Prev"); 68 valid_ = false; 69 } 70 71 virtual bool Valid() const override; 72 void SeekToFirst() override; 73 virtual void Seek(const Slice& target) override; 74 virtual void Next() override; 75 virtual Slice key() const override; 76 virtual Slice value() const override; 77 virtual Status status() const override; 78 virtual Status GetProperty(std::string prop_name, std::string* prop) override; 79 virtual void SetPinnedItersMgr( 80 PinnedIteratorsManager* pinned_iters_mgr) override; 81 virtual bool IsKeyPinned() const override; 82 virtual bool IsValuePinned() const override; 83 84 bool TEST_CheckDeletedIters(int* deleted_iters, int* num_iters); 85 86 private: 87 void Cleanup(bool release_sv); 88 // Unreference and, if needed, clean up the current SuperVersion. This is 89 // either done immediately or deferred until this iterator is unpinned by 90 // PinnedIteratorsManager. 91 void SVCleanup(); 92 static void SVCleanup( 93 DBImpl* db, SuperVersion* sv, bool background_purge_on_iterator_cleanup); 94 static void DeferredSVCleanup(void* arg); 95 96 void RebuildIterators(bool refresh_sv); 97 void RenewIterators(); 98 void BuildLevelIterators(const VersionStorageInfo* vstorage); 99 void ResetIncompleteIterators(); 100 void SeekInternal(const Slice& internal_key, bool seek_to_first); 101 void UpdateCurrent(); 102 bool NeedToSeekImmutable(const Slice& internal_key); 103 void DeleteCurrentIter(); 104 uint32_t FindFileInRange( 105 const std::vector<FileMetaData*>& files, const Slice& internal_key, 106 uint32_t left, uint32_t right); 107 108 bool IsOverUpperBound(const Slice& internal_key) const; 109 110 // Set PinnedIteratorsManager for all children Iterators, this function should 111 // be called whenever we update children Iterators or pinned_iters_mgr_. 112 void UpdateChildrenPinnedItersMgr(); 113 114 // A helper function that will release iter in the proper manner, or pass it 115 // to pinned_iters_mgr_ to release it later if pinning is enabled. 116 void DeleteIterator(InternalIterator* iter, bool is_arena = false); 117 118 DBImpl* const db_; 119 const ReadOptions read_options_; 120 ColumnFamilyData* const cfd_; 121 const SliceTransform* const prefix_extractor_; 122 const Comparator* user_comparator_; 123 MinIterHeap immutable_min_heap_; 124 125 SuperVersion* sv_; 126 InternalIterator* mutable_iter_; 127 std::vector<InternalIterator*> imm_iters_; 128 std::vector<InternalIterator*> l0_iters_; 129 std::vector<ForwardLevelIterator*> level_iters_; 130 InternalIterator* current_; 131 bool valid_; 132 133 // Internal iterator status; set only by one of the unsupported methods. 134 Status status_; 135 // Status of immutable iterators, maintained here to avoid iterating over 136 // all of them in status(). 137 Status immutable_status_; 138 // Indicates that at least one of the immutable iterators pointed to a key 139 // larger than iterate_upper_bound and was therefore destroyed. Seek() may 140 // need to rebuild such iterators. 141 bool has_iter_trimmed_for_upper_bound_; 142 // Is current key larger than iterate_upper_bound? If so, makes Valid() 143 // return false. 144 bool current_over_upper_bound_; 145 146 // Left endpoint of the range of keys that immutable iterators currently 147 // cover. When Seek() is called with a key that's within that range, immutable 148 // iterators don't need to be moved; see NeedToSeekImmutable(). This key is 149 // included in the range after a Seek(), but excluded when advancing the 150 // iterator using Next(). 151 IterKey prev_key_; 152 bool is_prev_set_; 153 bool is_prev_inclusive_; 154 155 PinnedIteratorsManager* pinned_iters_mgr_; 156 Arena arena_; 157 }; 158 159 } // namespace ROCKSDB_NAMESPACE 160 #endif // ROCKSDB_LITE 161